MSC megapack. by Hidden

MSC megapack by Hidden

Számítógép hálózatok .................................................................................................................................... 2 1. Hálózatok, protokollarchitektúrák, ISO OSI és TCP/IP modellek, hálózati példák ........................................ 2 2. Adatkapcsolati réteg tervezési szempontjai ................................................................................................. 4 3. MAC alapok, Ethernet ...................................................................................................................................5 4. Hálózati alapelvek ......................................................................................................................................... 7 5. Routing ..........................................................................................................................................................8 6. Hálózatok összekapcsolása ........................................................................................................................... 9 7. IP.................................................................................................................................................................... 9 8. Szállítási protokollok, UDP, TCP .................................................................................................................. 12 9. Alkalmazások, DNS, E-mail, WWW .............................................................................................................13 Operációs rendszerek................................................................................................................................... 14 1. Bevezetés ....................................................................................................................................................14 2. Folyamatok..................................................................................................................................................17 3. Tárkezelés.................................................................................................................................................... 22 4. Védelem és biztonság .................................................................................................................................29 Algoritmuselmélet ....................................................................................................................................... 32 1. Keresések/Rendezések ...............................................................................................................................32 2. ..................................................................................................... 34 3. Gráfalgoritmusok és elemzésük.................................................................................................................. 37 4. Bonyolultságelmélet ...................................................................................................................................43 5. Általános algoritmustervezési módszerek ..................................................................................................44 6. ...................................................................................................................44 Szoftveres ismeretek.................................................................................................................................... 46 1. Eseményvezértelt programozás alapjai ...................................................................................................... 60 2. Tervezési minták .........................................................................................................................................60 3. Webes alkalmazások fejlesztése ................................................................................................................. 63

Számítógép hálózatok 1. Hálózatok, protokollarchitektúrák, ISO OSI és TCP/IP modellek, hálózati példák Könyv: 1.2, 1.3, 1.4 36-98.o Jegyzet: bevezetes.pdf, prot_arch.pdf

Hálózatok x x x x x x

WAN – wide area network – o !" MAN – metropolitan area network – városi hálózat o eredetileg: egy tipikus USA-beli metropolitan area, de nem feltétlenül város, néhány tíz km LAN – local area network – helyi v. lokális hálózat o tipikusan vállalaton, intézményen belüli hálózat HAN vagy PAN – home/personal area network – otthoni hálózat/személyi hálózat o otthoni, kis irodai hálózat (SOHO – small office/home office), esetleg többszintes épület, ~100 m-es kiterjedés WLAN – wireless lan – vezeték nélküli hálózat BAN – body area network o az emberi testen kiépített hálózat

Példák Arpanet Internet Geant H-Bone PlanetLab

Protokollhierarchia Annak érdekében, hogy csökkentsék a hálózatok bonyolultságát, a legtöbb hálózatot rétegekbe (layers) vagy szintekbe (levels) # $ #

%&" !" ' # & !" ' ! %

réteg s * " ! '

elrejtse. Az egymással szomszédos rétegek között interfész (interface) található. Az interfész azt definiálja, hogy az & '' * '' # Ahhoz ! %&"& " ! !

%

' # % + ;-edik réteg entitása a szolgálatelérési ponton keresztül átad egy interfész adategységet (Interface Data Unit, IDU) az n-edik réteg entitásának. <=>

információból és egy áll. Az SDU olyan információ, ami a !" '' ! ? + ;- ! # %&"

alacsonyabb réteg munkáját segíti (például megadja az SDU-' ' ;

része. Az SDU továbbítása érdekében az n-edik réteg entitása az SDU-t több részre darabolhatja szét, és fejrésszel ellátva egyenként elküldheti az egyes darabokat. Az így kialakított adategységeket protokoll adategységeknek (Protocol Data Units, PDU) nevezzük. A rétegek és protokollok halmazát hálózati architektúrának (network architec- ture) nevezzük. Az architektúra &%&" %&" !! ! '

réteghez meg tudja írni a programot, illetve meg tudja építeni a hardvert úgy, hogy az helyesen alkalmazza a % rotokollt. Oldal: 2 / 67

Ha egy adott rendszerben minden réteg egyetlen protokollal rendelkezik, akkor a rendszer protokolljainak összességét protokollkészletnek (protocol stack) nevezzük. ' ' entitásoknak (entities) vagy funkcionális elemeknek nevezzük. Egy entitás lehet szoftver-entitás (mint például egy folyamat), vagy hardver-entitás (mint például egy intelligens B/K chip). Az azonos ré- ' ' & (peer entities) nevezzük. Az n-edik réteg entitásai az (n + 1)-edik réteg számára nyújtanak szolgálatokat. Ebben az esetben az n-edik réteget szolgáltatónak (service provider), míg az (n + 1)-edik réteget szolgálatfelhasználónak (service user) nevezzük. Az n-edik réteg a saját szolgálataihoz az (n - 1)-edik réteg szolgálatait veszi igénybe. A nyújtott ' ' !J * & " &"#

A szolgálatokat a szolgálatelérési pontokon (Service Access Points, SAP) ke- resztül lehet igénybe venni.

ISO/OSI (International Organization for Standization, Open System Interconnection)

! "# x alkalmazási x megjelenítési x viszony Hálózatfüggetlen funkciókat alkalmaznak, alkalmazásorientált feladatiak vannak. Alsó rétegek: x szállítási x hálózati x adatkapcsolati x fizikai Q" % %&"

tartalmaznak. Borítékolás: Minden réteg Fej és opcionális Farok részt rak az Adat köré.

Alkalmazási réteg: Felhasználói programokkal és alkalmazásokkal kommunikáció (socket absztrakció) Megjelenítési réteg: %&" (pl. titkosítás) Viszony réteg: Megbízható, hibamentes (és gazdaságos) összeköttetés létrehozása a végpontok között. Szinkronizáció a közös % '# Szállítási réteg: Hibamentes összeköttetés létrehozása, a csomagsorrend helyreállítása. Általános (globális) címrendszer lokálisra konvertálása. Forgalomirányítás, útvonalkeresés. Hálózati réteg: Hálózati eszközök közötti kapcs ! % & ' %&" # X

az alhálózaton belül, forgalomirányítás, csomagjavítás. Adatkapcsolati réteg: Oldal: 3 / 67

Y # Q' ! esetleg javítása. Alhálózati címek kezelése. Fizikai réteg: Bitek, bitcsoportok továbbítása a fizikai csatornán. Egyéb jelzések a küldése a csatornára, ill. fogadása onnan.

TCP/IP

2. Adatkapcsolati réteg tervezési szempontjai Könyv: 3.1 szakasz Jegyzet: forg_szab.pdf Három szolgáltatás: x Nyugtázatlan összeköttetés nélküli szolgálat !' % ! & " !' # [ !

jóm ahol egyedül a sebesség számít (pl telefon) x Nyugtázott összeköttetés nélküli szolgálat n ! !' # $' ! & ? ; ! # x Nyugtázott összeköttetés alapú szolgálat nyugta is van, összeköttetés is van, így garantálni lehet, hogy minden csomag megérkezik, jól érkezik meg és a csomagok elküldés sorrendjében érkeznek meg Fázisai: 1. összeköttetés felépítése 2. adatátvitel, általában sorszámozott csomagokkal, a végén pufferürítés, változók törlése 3. összeköttetés bontása Keretezés: x \ J ' ! ! ' & x \ ' úrással x \ '' * x Bitkeverés Hibajavítás: x visszirányú hibajavítás más néven automatikus ismétléskérés x !' – hibajavító kódolás Bithibák felfedése és javítása: x redundáns információ hozzáadása (Error Control Coding – ECC) o blokk-kódolás o konvolúciós kódolás x Paritáskód, Hosszparitás, Tömbparitás, Hamming-kódok, CRC, Reed-Solomon kód,Viterbi-dekódolás Csomagvesztés során csomagismétlési stratégiák x megállás és várakozás (stop-and-wait) x visszalépés n-nel (go-back-n) x szelektív csomagismétlés (selective retransmission) Forgalomszabályozás (flow control): $" ! ! % '

hálózatban rendelkezésre álló kiszolgálási sebességhez Torlódásvezérlés (congestion control): Azok a módszerek, amelyekkel linkek, csomópontok i *! Oldal: 4 / 67

A torlódásvezérlést értelmezhetjük általánosabban is: " ! " A forgalomszabályozás fajtái - $% &# x Nyílthurkú (vezérlés) A kommunik&" %! " !" % A hálózat dönt az új összeköttetés elfogadásáról admission control, beengedés-szabályozás Forgalomleírók (traffic descriptors) követelményei x „Megjelenítési képesség” (representativity): képesek legyenek a forgalmat hosszútávon megjeleníteni -] % %

fenntartása x ! ?%';J !" & " % ^% ` x $ ! ? ';J Az út " ! x Használhatóság (usability): A felhasználó képes legyen megmondani, a hálózat képes legyen mérlegelni. x Zárthurkú (szabályozás) x !J & % % ! *% ?'; Típusai:

+ stop-and-wait + dinamikus ablak

3. MAC alapok, Ethernet Könyv: 4.2,4.3 szakasz Jegyzet: multiple_access.pdf, LAN1.pdf A többszörös hozzáférés fajtái: x \ ! % 'J x Vezérelt: engedély szerint x Szabad: igény szerint x A vezérlés módja: x J { &! !

% x Y J % !

% x A kiszolgálás kötöttsége: x Rugalmas: igény szerinti x Merev: „ami jár az jár” ' **ös hozzáférési módszerek x Lekérdezés (polling): & ! x Probing („próba-szerencse”): %! " '' & '' x Foglalás (reservation): a vezérl & ! # J - „versenyben” - Egyedi „csatornákon” ' *** +0" x Lekérdezés: explicit kérdés nélkül Oldal: 5 / 67

x x x x x

Probing: explicit kérdés nélkül Vezérjel (token) átadás: jogosultság átadása egymás között } (CS):

& % Foglalt „hang”: segítség a csatorna foglaltságának észlelésében Szabad hozzáférés (Aloha): minél kevesebb szervezés – van sima, réselt aloha (azonos hosszú csomagok – !; !%" !

? ! ! ;

Ethernet Jelölésrendszer x ABC (pl.: 10Base5) x A: adatsebesség (1 = 1 Mbit/s, 10=10 Mbit/s) x B rész: - Base = alapsávi(baseband) átvitel - Broad = szélessávú (broadban) átvitel x C rész: - Átviteli közeg T = twisted pair FX/LX/SX = fibre optics CX = shielded balanced copper T2 = 2 pair twisted pair T4 = 4 pair twisted pair - Szegmenshossz: 2 = 185 m 5 = 500 m x Tipikus kábelezések - 10Base5 – vastag kábeles, egy kábel nincs kör, mindenki direktben csatlakozik - 10Base2 – vékony kábeles (ua. csak nem „egyenes a kábel” - koax) - 10BaseT,10BaseF – hubos megoldás

MAC (Medium Access Control)

5 7# 10101010… SFD – keret kezdete (1 byte) Célcím (6 byte), pl. 00:DA:07:9B:43:1B Forráscím (6 byte) Típus/hossz (2 byte)J ! Adat: min. 46 byte, max. 1500 byte CRC -

*(4 byte)

890 ;”: az ütközések biztos érzékeléséhez T=C/(2*L) J ^ ` C: jelterjedési sebesség Oldal: 6 / 67

L: szegmens (busz) hossza

CSMA/CD Carrier Sense Multiple Access with Collision Detection (CSMA/CD) x % & ^ ` ?& ; x Ha nem érzékel adást, elkezdi küldeni a keretet x Q '' ''! ? &" - collision detection) x } ?; ?^'&%%` ; *'" A CSMA/CD-hoz szükséges, hogy x ?& – CS) x adás alatt érzékeljük, hogy más is ad (collision detection - CD) IEEE 802.3z Gigabit Ethernet x Megnyújtott keretformátum - $ ! ?Y Y=; '' x Frame bursting Az állomás (rövid) csomagok sorozatát küldheti el ! '

anélkül, hogy elengedné a csatornát („jumbo” keret)

4. Hálózati alapelvek Könyv: 5.1 szakasz Jegyzet: kapcsolas.pdf Összeköttetés-alapú hálózat: a kommunikál" & " ?-to-end connection) létesítenek, rendszerint külön protokoll alkalmazásával Összeköttetésmentes hálózat: " & " étrehozása nélkül történik Kapcsolóelemek megvalósítási módjai: tér- - -tér- ""

"# ' & * ' kimeneti blokkolás (output blocking): két bemenet ugyanazt a kimenetet akarja használni, ilyenkor az egyik kimenet blokkolt lesz Üzenetkapcsolás & {& " & # A két vég-csomópont közötti összeköttetés létrehozható két szomszédos csomópont közötti összeköttetések sorozataként is. Az egész üzenet egy egységként utazik. Megvalósításához: x az üzenetben címrész x a csomópontokban átmeneti tároló v. puffer tár kell Csomagkapcsolás & " '' csomagokra tördeli A csomag tartalmazza: x & " "{& x a címzett csomópont azonosítóját/címét x a csomag helyét az üzenetben & ' ! -> helyre kell állítani a sorrendet hálózatok csomóponti eszközei: x kapcsoló (switch): olyan csomópont, amely a csomagokat ugyanazon helyi hálózat más csomópontjaihoz továbbítja x útválasztó (router): ha két vagy több hálózat között továbbítja a csomagokat Csomagkapcsolás megvalósítható: Oldal: 7 / 67

x összeköttetésmentes hálózatokban, ez a datagram kapcsolás x összeköttetés alapú hálózatokban, ez a virtuális áramkörkapcsolás Datagram kapcsolás x Minden csomag önálló egységet képvisel x Minden csomag tartalmazza a rendeltetési hely teljes címét x A két végpont közötti csomópontok megvizsgálják a csomag fejrészét és kiválasztják az útvonal kapcsolatot (port), ahová a csomagot továbbítják. x ' ""

+ 0 venni: - & ! '' * helyére - hol található szabad csomópont, amely képes a csomag fogadására x A port leképezés (port mapping) célja: a csomag fejrészében található címhez gyorsan megtalálni a '' & Alapja az útvonalválasztó táblázat: x a cél-cím (destination address, DA) x a kimeneti kapcsolat (output port) x ! " ^ ` * Virtuális áramkörkapcsolás } & & & " között egy, a hálózat csomópontjai közötti ' " *l létesül. Csomópontokban VCI azonosító. A virtuális áramkörkapcsolásnál is megtalálható: x kapcsolat felépítés x adatátvitel x kapcsolat lebontás

5. Routing Könyv: 5.2 szakasz Jegyzet: routing.pdf Útvonaltábla: célpont- !

kitöltés: manuális – automatikus (centralizált vagy elosztott) Routing megoldások 1. Centralizált –szétosztott 2. %" % – forgalomfüggetlen 3. Egyutas – Többutas 4. Lépésenkénti – Forrás általi Elosztott routing – minden csomópont maga alakítja ki a tábláját x Távolság-vektor (distance-vector): Bellman-Ford algoritmus - A csomópontok elmondják a hálózatról alkotott elképzeléseiket a szomszédjaiknak. - Listát közölnek egymással: csomópont azonosító – távolság + melyik csomóponton keresztül (javítás) x Összeköttetés állapot (link-state): Dijkstra algoritmus - A csomópontok elmondják mindenkinek a szomszédjaikról nyert tapasztalataikat. - ! # (elárasztás) +sorszámozás és öregítés + hitelesítés Hierarchikus routing szükséges a gyors számítás miatt Autonóm rendszerek (AS) – routing domain x olyan egység, amelyen belül egységes routing policy érvényesül x egyetlen hálózat, vagy hálózatok csoportja x közös hálózatadminisztrátor kezeli x egyetlen szervezeti egység megbízásából Oldal: 8 / 67

x egész csoportra csak egy bejegyzés van más routing táblákba -] Multicast routing módszerek x ! - Elárasztás + lemondás (flood-and-prune) Legrövidebb útvonalfa alkalmazása Csoportlemondás Forráslemondás x Ritka elhelyezkedés - Explicit csatlakozás - Gerinc alapú fa alkalmazása (Core Based Tree) x Elhelyezkedés független -

6. Hálózatok összekapcsolása Könyv: 5.4 szakasz Jegyzet:LAN_2.pdf -

-OSI- rétegben helyezzük el ezt a funkciót: 1-es rétegben 2-es réteget ismert – bridge/switch (híd v. kapcsoló) 3-as réteget ismeri, a 2-est újrafenerálja router több réteget újragenerál gateway Bridge-ek és switch-ek - ! ' ? ! ; - Kapcsoló transzparens, plug-and-play, self-learning Hidak/kapcsolók: x % % Virtuális LANok

7. IP Könyv: 5.5 szakasz Jegyzet: IP_1.pdf, IP_2.pdf, IP_3.pdf Az IP feladata x Adattovábbítás a hálózat végpontjai között x \ % %&" - Címzés (addressing) és forgalomirányítás (routing) - Tördelés/fragmentálás (fragmentation) '>?%

0 x Csomagkapcsolt x Összeköttetés-mentes (connectionless) x „Best effort” – nincs garancia - A csomagokra igaz: Elveszhetnek Duplikálódhatnak Sorrendjük megváltozhat Meghibásodhatnak (nincs hibaészlelés és -javítás) x Egyéb NEM nyújtott szolgáltatások: - Torlódáskezelés - Ütemezés - Titkosítás és hitelesítés IP cím x 32 bites egyedi azonosító Oldal: 9 / 67

x x

x x x

x

Cím = hálózatazonosító + Egyedi azonosító Címosztályok - A – !" ' ? 'J ; - B – !" ' ? 'J ; - C – !" ' ? 'J ; - D – multicast 224.0.0.0 – 239.255.255.255 - E – fenntartott 240.0.0.0 – 255.255.255.255 HostID – csupa 0 = hálózat cím, csupa 1 = broadcast cím 127.0.0.0 – 127.255.255.255 loopbavck cím, helyi gépet azonosítja Privát IP tartományok (csak LAN-on érvényes) - 10.0.0.0 – 10.255.255.255 (A) - 127.16.0.0 – 172.31.255.255 (B) - 192.168.0.0 – 192.168.255.255 (C) Alhálózati maszk, jelzi a hostid hosszát -> gazdaságos

IPv4 Fejléc

x x x

x x x

x x x x x

VER (Version): ertéke: 4 vagy 6 (IPv4 / IPv6) IHL (Internet Header Length): a fejléc mérete DWORD-ökben, értéke: 5..(2-1) = 5 .. 15, tehát a fejléc mérete 20..60 byte ToS (Type of Service): QoS osztályok, paraméterek jelzésére. A legtöbb router nem támogatja. Leggyakoribb felhasználás: - DSCP (Differentiated Services Code Point) - ECN (Explicit Congestion Notification) Total Length: a teljes IP-csomag mérete byte-okban, értéke: 576..65535, (576: 20 fejléc + 512 adat + 44 IP-opciók és alsóbb rétegek fejlécei. Ekkora csomagot tördeletlenül kell továbbítani.) Identification: az IP-töredékek azonosítója Flags (3 bit): - 0: reserved, set to 0 - 1: DF (Dont Fragment), 1: ha tördelni kellene, el kell dobni - 2: MF (More Fragment), 1: nem az utolsó töredék, 0: utolsó töredék vagy tördeletlen Fragment Offset (13 bit) : & ' &" '-os egységekben TTL (Time To Live): csomag élettartama, eredetileg másodpercben, gyakorlatban hop-számban mérve (0-nál eldobjuk) Protocol: a payload-' & " Header Checksum: a fejléc minden WORD- ? & ;# &

'' * #

Source / Destination Address (2 x 32 bit): Oldal: 10 / 67

x x

a feladó és a címzett IP-címe IP Options: ritkán használt, opcionális, ezzel lehet pl. a csomag útját kijelölni Padding: ! < [ -t 4 byte többszörösére

IP routing „Hot potato” –elv x minél gyorsabban x & épést kell ismerni Routing tábla: x !" &{!" {%&{ & ""{ & " <-je x legnagyobb hálózatazonosító egyezés felé kell küldeni x de van default route is. ARP – Address Resolution Protocol : RARP – Reverse ARP x iP <-> Mac egyeztetés x remélem nem kell a PDU-ja Útvonal választó protokollok x Interior Gateway Protocols (IGPs) x Exterior Gateway Protocols (EGPs) IP jelzés- és menedzsmentüzenetei x ICMP: Internet Control Message Protocol x IGMP: Internet Group Management Protocol

IPv6 Címek x 128 bit x 8x16 bitben szokták ábrázolni x A v !!" ?; x 16 bites nullákat tartalmazó részek kihagyhatók, ha egymás után vannak, max egy ilyen blokk hagyható el x IPV4 -> ::x.x.x.x vagy ::FFFF:10.0.0.1 x unicast/multicast/anycast IPv6 PDU

x x x x

Version: =6 Traffic Class: forgalmi osztály (más néven: Priority) – ! ' < "

Flow Label: folyamazonosító címke & "

%

QoS-t és igazságos adatsebesség- ! é - Virtuális összeköttetések biztosítása adatfolyamok számára - Egy forrás-célállomás pár esetén több adatfolyam is lehet

Oldal: 11 / 67

- Skálázhatósági probléma a folyam-alapú eljárásoknál x Payload Length: adathossz - Nem tartalmazza fejrészt - Max. 64 KB-os csomag (de van jumbogram opció) x Hop Limit – ugrásszám-korlát, ugyanaz, mint IPv4-nél a TTL x Y J ' ' &

x QJ %&# ! J

- ' => ! " < %& & !

- < %&

IPv6 Header Extensions x Hop-by-hop Options Header x Routing Header x Fregmentation Header x Destination Options Header x Authentication Header x Encapsulation Security Payload Header

8. Szállítási protokollok, UDP, TCP Könyv: 6.4,6.5 szakasz Jegyzet: TCP.pdf A szállítási réteg: x Logikai kapcsolatok a végpontok alkalmazásai között x A szállítási protokollok a végpontokban futnak, a csomópontokban nem x Az alkalmazások adategységeit betördeljük a szállítási protokoll adategységeibe A szállítási réteg: alkalmazások közötti logikai kapcsolatok A hálózati réteg: végpontok közötti logikai kapcsolatok Szállítási protokollok: UDP és TCP x UDP: User Datagram Protocol x TCP: Transmission Control Protocol x Közös képességek - Portok kezelése - Multiplexelési képesség - Különbségek - Az UDP kapcsolatmentes transzport-szolgáltatást nyújt - A TCP kapcsolatalapú

UDP

Source port: opcionális (nem használt: 0) Hossz: oktettben, min: 8 Checksum: opc (nem használt: 0) Megj.: az IP-csoma & % >= &!& & &

TCP Célja: megbízható adatszállítás az IP nem megbízható datagrammjaival @

0# x } &" Oldal: 12 / 67

x Stream-típusú szolgáltatás: bit- (egyéb-) streamek sorrendhelyes átvitele x Strukturálatlan stream: delimiter-mentes streamek átvitele x %% J -'

x Duplex kapcsolatok x } %&" J '& " ? ' %" -be ágyazva) Megvalósítás: x Pozitív nyugtázással – nem lenne hatékony x Y * "' ? ' & ;

- Ez a TCP-ben oktett-

- Hatékony - Egyben forgalomszabályzási módszer is

Seq. number: az adat helye a byte-stream-ben Ack. number: a legközelebb várt byte sorszáma Code bits: a szegmens tartalma Window: %%

Checksum: mint az UDP-nél Urgent pointer: out-of-band adatok küldésére

9. Alkalmazások, DNS, E-mail, WWW Könyv: 7.1-7.3 szakasz Jegyzet: alkalmazasok.pdf …

Oldal: 13 / 67

Operációs rendszerek 1. Bevezetés Könyv: 17-57.oldal operációs rendszer (operating system): Réteg, amely a felhasználó és a hardver között helyezkedik el, olyan környezetet teremtve, !

az alkalmazó számára a számítógép kényelmes és hatékony használatát. x & ! ' ' %! " !

végre tudja hajtani saját programját. x Másodlagos célja a számítógép hardverének minél hatékonyabb használata, a programfejlesztés '' " # Virtuális gép koncepció: Az operációs rendszer egy olyan réteget képez a hardver fölött, amely elrejti annak körülményességét és bonyolu " a számítógép hardver szolgáltatásait. Így a felhasználó egy sokkal '' virtuális gépet (virtual machine, extended machine) lát. Történelmi áttekintés x &"

- Elektroncsövek, megbízhatatlan - A programokat dugaszolós kapcsolótáblán rögzítették - % ! - ! '% #

x Második generáció - Tranzisztor, drága, optimális kihasználás kellene - Lyukkártya, operátorok kezelik (closed shop), nem optimális a kihasználtság - &! J

- - Resident monitor: Figyelte, hogy mikor fejezödik be egy program, és automatikusan indította a következöt. - Mágnesszalag, offline perifériás J " -> készülék- vagy perifériafüggelten programozás: szabványos perifériafelület alakult ki. x Harmadik generáció - Integrált áramkörök - Szószervezésü nagyszámítógép ( tudományos számításokra ) - Karakterszervezésü kis számítógép: ( nyomtatás, adattovábbítás ) - IBM: 360 Ugyanazt a software családot haszálta minden számítógépen. Így a hwt könnyebb volt szervezni. Olyan oprendszer, ami kis és nagy gépekre is jó. Nagyon hosszú kód. A hw olcsóbb lett, de az sw drágább. - spooling (Simultaneous Peripherial Operation On-line): a nagy kapacitású és gyors RAMok ill a # ! '%% !

egyszerre nem egy, hanem több munkát is lemezre tölt. Ez a megoldás lényegében az off-line perifériás " ása. Pl: nyomtatás (file-ba nyomtatás, majd nyomtatóra). x Multiprogramozás – - Tárgazdálkodás: Amíg egy job perifériára vár, egy másik fut. - DISK megjelenése: véletlen hozzáférésü. (software véletlen hozzáférés: nem kell, hogy egyforma gyors legyen, de lehessen lépegetni ) x Személyi számítógép x Elosztott rendszerek (hálózat) x }" " ! -követelményeket támasztunk " ! " ? prioritásosak) x Nyílt rendszerek Operációs rendszer és környezete Oldal: 14 / 67

Csatlakozási felületek x

x

x

$ & + # Tipikus ember-gép kapcsolat. Arra szolgál, hogy az operációs rendszer ezen keresztül !

felhasz" #

felület kialakításának tipikus fizikai eszköze a '

tartalmazó munkahely. Alkalmazási (programozói) felület: A számítógépen futó, adott feladatokat megoldóprogramok valamilye "# %

% % &" # <{[

ttfutásának és %&"& # ! !"! #

Hardver felület: &" & # &!* %# %

egységes absztrakcióján felül ' ! !%

részeket. Az operációs rendszernek kezelnie kell a rendszerhez kapcsolódó I/O eszközöket, amelyek heterogén csoportokból kerülhetnek ki, és a rendszer élettartama során új eszközök beillesztésére is sor kerülhet.

Számítógép architechtúrák 50"& Egyetlen sínnel renelkezik, amelyet együtt használ a CPU, a memória és az I/O forgalom. A CPU vezérli a =$ " -memória közti blokkátvitelt, az adatforgalaom azonban a !# !! Y> =$

közt jelforgalom biztosított.

Személyi számítógép \ " !

teszi hogy a memória a CPU utasítás !

<{[

adatforgalom számára is rendelkezésre # % "

processzorral rendelkezik, így a grafikus ! Y<-sínt. az IDE és a Y< %

csatlakozásáért.

Oldal: 15 / 67

Szuperszámítógép

Az építkezés hierarchiku

& ' !

hipernódba. Minden CPU saját utasítás- és adatcache-sel rendelkezik. A hipernódhoz egy I/O alrendszer is tartozik. A crossbar kapcsolóhálózat a processzorpárok vaamint az I/O alrendszer hatékony átlapolt ka& ! "'#

A memóriablokkok tartalmazzák a hipernódok saját adatterületét, a közös tár egy adatterületét, valamint a hipernódok & ! % " '

hálózati gyorsítótárak területét. A hipernódokat négy SCI (Scalable Coherent Interface) '

kapcsolja össze. A rendszerben valamennyi proceszor számára rendelkezésre áll a memóriában egy közös címtartomány, amely valójában egy elosztott, koherens gyorsítótárral támogatott memóriával valósul meg. " ! " ' %"

! !" !&!* ! %" " #

A másik alkalmazási st ! ! " ' &

operációs rendszerekkel és programozási nyelvekkel támogatja.

Réteges szerkezet x Hierarchikus egymásra épülés x Minden réteg az alatta lev ! x Q ' ''' ! x maximális kohézió, minimális csatolás x modern operációs rendszerekben nem tiszta rétegek, inkább kevés réteg és „átlógás” Virtuális hardver x Kernelkoncepció ! " ! ' &" ! ! ! Kliens-szerver modell x %&" % % ? ; x ! ményt kap (kliens) Várakozó állapotban aktiválódik az oprendszer, ha x a futó program rendszerhívást hajt végre x & megszakításkérést fogad el x hibamegszakítás (exception) következik be Rendszerhívás után nem tér vissza a hívó programhoz a vezérlés, ha x '% !

x % -igénylés, amit a rendszer éppen nem tud kielégíteni, emiatt a hívónak várakoznia kell x várakozás másik program jelzésére vagy üzenetére, ami még nem érkezett meg, emiatt a hívónak várakoznia kell x * "

x újraütemezés kérése, azaz lemondás a futásról esetleges fontosabb feladatokat megoldó programok javára x <{[ ?{\; ! !"

Egy I/O (B/K)-rendszerhívás végrehajtásának menete: x &" ' ! ! J - a B/K-kérelmet az indításhoz szükséges paraméterekkel a készülék várakozási sorába helyezi, - ha a készülék szabad, elindítja a B/K végrehajtását, Oldal: 16 / 67

-

választ egy futtatható programot, és oda tér vissza, x az operációs rendszer B/K-megszakításokat fogad el, amelyekre reagálva: - {\ %!" '% {\-ra várakozó programot, - ha van várakozó B/K- {\- - " % * %

programra, x a B/K-rendszerhívást kiadó program akkor folytatódik, ha ismét futtathatóvá vált, é &"

választotta futtatásra. " 0"Q # ! ! !" '

' # (ezt abstrakciók kersztül érhetik el cask a felhasználói programok) >0# gyakorlatilag cask hw órával megvalósítható Hibakezelés: ' ' amit az oprendszer tehet x ! ! !' " ! x hibajelzé ! x abortálhatja a hibát okozó programot, x ! %! " !' ? &-handler), x diagnosztizáló programot indíthat. Oprendszer feladata bekapcsoláskor: üres memóriában felépíten ! % #

Kikapcsoláskor: #

2. Folyamatok Folyamat (aka nehézsúlyú folyamat):: 'J ! ' ! operációs rendszer szempontjából: egy végrehajtás alatt álló program x egy logikai processzor tartozik hozzá - végrehajtja a programkódot x egy logikai memória tartozik hozzá - tárolja a programkódot, a változókat és a konstansokat Szál (aka pehelysúlyú folyamat): egy folyamaton belül párhuzamosan futó programrész x saját logikai processzor x közös logikai memória (folyamaton belül) A folyamat létrehozásának okai x '' % !

x gyorsabb a feladat-végrehajtás, x több feladat futhat egyszerre (a felhasználó számára kényelmes), x rendszerstruktúrálási okok: bizonyos feladatokat eleve könyebb több folyamat alkalmazásával #? ' " ;

A folyamatok osztályozása x Független folyamatok Semmilyen módon nem befolyásolják egymás futását. x } %

" % !

x Együttmûköd %

Ezek a folyamatok úgy lettek tervezve, hogy a folyamatok közötti leírása már a programkódban is megjelenik. Információt cserélnek egymással, gyakran csak egy bit erejéig, de más esetekben több megabájt is lehet az adatforgalom. Másik csoportosítás aszerint, hogy a folyamatot ki indította: Oldal: 17 / 67

x Rendszerfolyamatok x Felhasználói folyamatok Folyamat létrehozás + 0# létrehozza a rendszert és a többi folyamatot &" ''

folyamatból állhat (rendszerfolyamatok). A rendszerfolyamatok újabb, felhasználói folyamatokat hoznak létre, a felhasználói folyamatok pedig maguk is létrehozhatnak további felhasználói folyamatokat a logikai processzor % ! ?# % &;#

Statikus vs dinamikus OS x statikus: azok a rendszerek, amelyeknek muködése során - a felépülés és inicializálás kezdeti szakaszátóleltekintve - nem jönnek létre és nem szünnek meg folyamatok. x dinamikus: ' ' ! ! %#

X "Y + " x hiererchikus: % & % '" ! !

" & #

x globális: % * " !

% ' " #

Közös memórián % & " ' %

helyezhet el és adatokat olvashat ki. Mivel a folyamatok egyszerre írhatják/olvashatják a memóriát, a RAM modell % &# Q PRAM (Pipelined RAM) modellt kell kialakítani, melyre a RAM modell '' J

x olvasás-olvasás ütközéskor ugyanazt az eredményt adja mindkét mûvelet. x olvasás-írás : az adott rekesz tartalma felülíródik, az olvasás eredménye vagy az új vagy a régi tartalom, ! #

x írás-írás: a rekesz tartalma vagy az egyik vagy a másik írás eredménye lehet csak, más nem. Tehát az ol { ! ' ! '

'# % " ! " % ? '' &"

fogalmak nem csak a memóriára vonatkoznak, han ' % ;J

kölcsönös kizárás több folyamatban lehetnek olyan kritikus utasítássorozatok, melyeket nem szabad egyszerre végrehajtani, másképp fogalmazva egy rendszerben lehetnek olyan K kritikus szakaszok, melyekben egyszerre csak egy folyamat tartózkodhat. A kritikus szakaszokat a programozó definálja, a szakaszba be/kilépést a kódban ! #

egyidejûség '' % ' ! ! ûleg hajtódjanak végre. Pontosabban: nem léphet ki a folyamat az egyidejû szakaszból,míg a többi folyamat el nem kezdte végrhajtani a saját egyidejû szakaszát. precedencia \' % ! ! #

használatos, ha az egyik folyamat a másik eredményét használja. A kölcsönös kizárás megvalósítása szoftveresen ' ! ! ! %! ! '

konkurrens. Helyes algoritmusok szoftveres PRAM-ra x Dijkstra által pu' %

x ' ! ? # '; "

analógiájára született. A kölcsönös kizárás megvalósítása operációs rendszer szinten x Szemaforral. Általános szemaforJ *# \ J

P(s) belépés: ha a szemafor értéke < 1 akkor vár, ha nem akkor csökkenti eggyel és elkezdi a folyamat végrehajtását. V(s) kilépés: a folyamat lefutása után hívódik meg, a szemafor értékét eggyel növeli. Bináris szemaforJ % ! & %

! ! %! % x 5+ ? % & "' ! % ; Oldal: 18 / 67

x

Esemény

Üzenetváltással Az együttmûködö folyamatok logikai processzorai rendelkeznek egy Küld(cím, folyamat) (Send) és egy Fogad(cím,folyamat) (Receive) utasítással.A Küld hívásának eredménye, hogy a folyamat memóriájának cím részében tárolt adatot elküldi a folyamatnak. A Fogad a folyamat által küldött adatot a saját memóriájának cím rekeszébe teszi. Az üzenetátadás módjai: x Direkt a folyamatok ismerik egymást, és a Küld/Fogad üzenetek közvetlenül a társfolyamatot címezik. x Indirekt a folyamatok egy közös postaládát ismernek, mely általában egy FIFO tároló, egymást nem kell ismerniük. x Aszimmetrikus az egyik folyamat ismeri a másik címét, míg a másik folymat egy saját I/O kaput, portot használ.Kliens/Server folyamatokban használatos. x Csoportkommunikáció a küldõ a folyamatok egy csoportját jelöli meg, mindegyik megkapja az üzenetet. x Üzenetszórás (broadcasting) a csoportkommunikáció azon esete, amikor a küldõ az összes folyamatnak küldi az üzenetet

Kritikus szakasz – kölcsönös kizárás kritikus szakasz: Egy folyamatokból álló rendszerben egy K kritikus szakasz a folyamatok végrehajtási szakaszának egy Sk halmazát jelenti, amely S halmaz bármely két s1 és s2 elemének átlapolt végrehajtása tilos. Más szóval olyan ? ; ! #

kölcsönös kizárás Kölcsönös kizárás esetén egy folyamat csak akkor léphet be egy kritikus szakaszba, ha semmilyen más folyamat " # ' ' " " % !

szakaszt. Ha egy folyamat elhagyja K-t, akkor az esetleges belépésre várakozó folyamatok közül egyetlen beléphet a kritikus szakaszba. (van HW-es támogatás) megvalósítása x minden körülmények között teljesüljön a kölcsönös kizárás x a belépési protokoll döntéshozatala csak a belépésben érdekelt folyamatok részvételét igényelje, azaz a többi folyamat nyugodtan haladhasson tovább x ' ' " % '!

%Z egyik folyamat bevárja a másikat egy adott ponton

Holtpont Definíció: Egy rendszer folyamatainak H halmaza holtpontban van, ha a H halmaz valamennyi folyamata olyan eseményre vár, amit csak egy másik H halmazbeli folyamat válthat ki. Kialakulás feltételei: x Kölcsönös kizárásJ } % ' % & "

használhatnak. x Foglalva várakozás: legyen olyan folyamat mely lefog % ' %

várakozik. x !" -elvételJ % ' % " '" %

nem szabadítják azokat. x Körkörös várakozás: Létezik a rendszerben egy olyan folyamatsorozat, melyben minden folyamat az utána % % % " #

Q % % % % !" # feltétel nemcsak szükséges, de elégséges is. 5+ +

+Y

& # \ % % # Q %'" % '

% # Q % '" %' %

%! !

# % ' ! !

' % # % lálva fedezhetjük fel a holtpontot. Oldal: 19 / 67

Holtpontkezelési stratégiák : x Nem veszünk tudomást a holtpontról (strucc algoritmus) Q ! " & * &

következményei, akkor megérheti ezt a megoldást választani. x Észrevesszük, ha a holtpont kialakult és megpróbáljuk feloldani } % %" %# $

! %! ! % '# x Védekezünk a holtpont kialakulása ellen $

! J ! !

feltételei, így elvileg sem lehet holtpont. Kölcsönös kizárás & J ! '' %rásokat alkalmazunk, ahol ez nem lehetséges, ott a hozzáférést megpróbáljuk oszthatatlan #

Foglalva várakoztatás megszüntetése: Ha minden folyamat betartja a szabályt, miszerint az % zerhívással kéri el, akkor ! % # J % -kihasználtság romlása. !" ' J Q ! * %

vannak, akkor megtehetjük, hogy elvesszük egy adott folya %

% ' %

folyamatnak. Körkörös várakozás J % %

sorszámozásában, minden folyamat csak nagyobb sor * % !

% '# ' ! #

A holtpont elkerülése - bankár algoritmus: %

! !-e holtpont ! # !! ! % ' * ' ! %!

% ! ! % ! max.kérés és a foglal ' még kérhet oszlop is. Ez & % % ! ' %

% % ! '' ' ! # % %

'' % ' si állapotban (foglal nem 0). kommunikációs holtpont: Kliens- &!* %! ? %; ! %

& ' % ' ' "# %! ! %-kiszolgáló lánc záródik, ! % & ! ! ' -esetleg több áttételen keresztül- !

"! # Q % & % !

ki. Éhezés ha % & ! & & ! ' ''! #

Kiéheztetés elkerülésére tisztességes ütemezési stratégiákat lehet alkalmazni (pl. FIFO) T0 -fogyasztó probléma: ' ?# ; ' ?%%;#

% " ' %!

'" # % " 'sségére nincs megkötésünk. Mivel a Buffer & ! ! %% '

feleszabadul egy hely, illetve ha üres, a Fogyasztó várjon, amíg érkezik egy elem. Ugyancsak elvárjuk, hogy az x " '' '

% ! #

Írók–olvasók problémája ? ! ' %; '' #

olvasások cs ' ' '

J & !

! & %' ! ! %' # Precedencia gráf és fork-join Ahhoz képest, hogy akár minden elemi folyamat párhuzamosan futhatna, egy sereg precedenciát í

ábrázolva kapjuk a precedenciagráfot. fork C ! ! ! C címkén folytatódik. Oldal: 20 / 67

join N utasítás pedig N szál összefuttatását oldja meg. A fork-join páros a goto-hoz hasonló anomáliákhoz vezetett (áttekinthetetlen vezérlési szerkezet), így helyette egy strukturált utasítás bevezetését javasolták, a parbegin-parend párt. Processzorütemezés x Preemptív ütemezés: Az oprendszer elveheti a futás jogát az éppen futó folyamattól, és "futásra kész" állapotúvá teheti. Közben egy másik folyamatot indíthat el. x Nem preemptív ütemezés: Az operációs rendszer nem veheti el a futás jogát a folyamattól. A folyamat addig fut, amíg az általa kiadott utasítás hatására állapotot nem vált, azaz csak maga a folyamat válthatja ki az új # ?% % % ";

5 0 0Y" x Legrégebben várakozó (FCFS: First Come First Served): Nem preemptív. A legrégebben várakozó folyamatot % # % %

elején álló folyamatot kezdi futtatni. Hátránya: Nagy ! ! * Y>

% % % # ? ! ;#

x Körbenforgó (RR: Round Robin): # $ %

amikor fut # Q Y> ''

a folyamattól a CPU- % # Q Y> ''

akkor a folyamatokat újraütemezzük, és a futó fo *# Hátránya: !

% ! # * ! * xYx ' *

környezetváltás. Prioritásos ütemezési algoritmusok x [* *"% @!# Job First): # '' '&

% % # % #

%! " '& # x [* % \]!# \0 ]0 !# Az SJF preemptív változata. Ha új % %

! %" % ! *

folyamat löketideje a kisebb. A környezetváltás idejét is figyelembe veszi. x Legjobb válaszarány(HRR: Highest Reponse Ratio): %

%' # ?; " " % #

]* itmusok % % '' ' * ' # ' ' '

kiválasztási algoritmusok is lehetnek. x "Y*"8^#8Y ^YY# A folyamatok prioritása statikus, a folyamattípus ?#J % % %

rendszerstatisztika). Hátrány: kiéheztetés léphet fel. x _ * " 8!^# 8Y !" ^YY# A folyamatokhoz dinamikus prioritás # % % ' Y> '

% '# Q % *

akkor az oprendszer csökkenti a folyamat prioritását. A régóta várakozó folyamatok prioritását az oprendszer megnövelheti (aging). Ütemezési algoritmusok összehasonlítása x A központi egység kihasználtság (CPU utilization): Y> ! %"

folyamatok utasításainak végrehajtására. A kihasználtságot csökkenti amikor a CPU henyél (idle) vagy a rendszeradminisztráció. x Átbocsátó képesség: # ? { ;

x $* +Y

# Egy-egy munkára vonat " ' ! '%

# ?}! +} ;

x _ " #

x _ # &" % - esetleg egy felhasználóval kommunikáló folyamatnak- & !" &"

#

Folyamat állapot – állapotátmenet ábrája

Oldal: 21 / 67

3. Tárkezelés A multiprogramozott rendszerekben a CPU- '' % ! # %

sebességhez egyszerre több folyamatot a központi tárban kell tartani, mert a háttértárról való környezetváltás sebessége nagyon lassú lenne. A központi tár kezelése az operációs rendszer teljes '% " # Statikus logikai-fizikai címleképzés A címleképzés történhet fordítás ' ! % &# Q ''' &

megváltozik, újra kell fordítani. Csak speciális esetekben, ROM-' nál. Szerkesztés közben is történhet a leképzés. Akkor van szükség szerkesztésre, ha a program több független lefordított modulból áll amelyek egymás logikai címeire hivatkoznak. Általában csak a logikai címtartomány egyesítése történik meg a linker segítségével. Betöltés 'J '' ! ! " &! &

módosítja a loader. Dinamikus logikai-fizikai címleképzés ! ! ! ' !"# = & l a konkrét fizikai cím hozárendelés csak utasítás-végrehajtás során van. Bázisrelatív címzés: A program valamennyi címe bázisrelatív & "* ' ' & !!"# $

programot új helyre átmásolva a végrehajtás folytatható. Fizikai cím=bázisregiszter cím+ logikai cím Utasításszámláló-relatív címzés: a bázisrelatívhoz hasonló Késleltetett betöltés < & ' '' & Dinamikus betöltés: Egyes ! # x % "'# !

speciális programrész betölti a memóriába ha nincs benn. Ilyenkor a memóriában a tényleges méretnél kisebb helyet foglal a ! '# " % #

Dinamikus könyvtárbetöltés: A programban a használt rendszerkönyvtárak eljárásai helyett csak hivatkozás van # ! &t a hivatkozáshoz. `+&0" # Csak azok a " "' % # ''

!" * ! ' &

# 'e szükség esetén. Bonyolult, manapság ritkán használják.

Társzervezési módszerek Egypartíciós rendszer Az egypartíciós rendszereknél ' % ! !

operációs rendszeren felüli folytonos címtartományon teljes egészében ez a folyamat futhat. A folyamatok váltása a swapping segítségével történhet. Többpartíciós rendszer Multiprogramozás rögzített partíciókkal %! " ' &" rendszer !# $ &"' % " !#

fokát a partíciók száma korlátozza. { * # kihasználatlan memóriaterület (a partíciókon belül). 8Y &0 0&Qciókkal

Oldal: 22 / 67

} " &"# & ' " * : memória felszabadítása után lyuk marad a partíció helyén (amikor kivesszük a progit a memóriából). Ezen segíthet a szabad helyek tömörítése: (garbage collection) a tár egyik végére rendezzük a szabad területet (rossz hatásfokú). Más % J

x 0+ # ?x x; % #

- 70%-os kihasználtság x "*"0+ : (Next Fit) u % #

- 70%-os kihasználtság, várhatóan gyorsabban talál x %0+ # ? x; '' #

- Látszólag nem pazarol, gyakorlatban csak 50%-os kihasználtság x legrosszabban illeszked# (Worst Fit) a legnagyobb szabad partícióból szakít. - Best-fit anomáliáján felbuzdulva, de ez is 50%-os kihasználtság Tárcsere (swapping) % " ! # < !

tárcserék számát. Átlapolt tárcsere: egy futó folyamattal párhuzamosan folyik egy másik folyamat kivitele illetve egy harmadik behozatala.

Logikai címeken alapuló társzervezési módszerek Szegmensszervezés " ' '' ' i fel. A szegmensszervezés ezt a látásmódot tükrözi, címtranszformációnál a logikai szegmenseket felelteti meg egy-egy blokknak. Blokktáblás séma.(TK 169.o. '; ' ' ! * % ' & # '' ja a blokk ! ' " & # & ' ! '

memóriában van-# % ' !

% ! '! ? &;

x Címtranszformáció szegmensszervezés esetén:

Lapszervezés # ' ! # <

' # % " & % # x !

megválasztása (gyakorlatban 2 hatványa). x Közvetlen leképzés: A folyamatokhoz tartozó minden lap fizikai címe egy laptáblában van. A laptába & '' ' # $ % '

& & ! ' % % !

rész-laptáblát a memóriában tartani. x Asszociatív leképzés: & ' ' !" !

fizikai címeit. Mivel mérete kicsi, tartalmát valamilyen stratégiával frissíteni kell. A valid bit azt mutatja, hogy az adott lap a memóriában van-e. Osztott laphasználat lehetséges az egyes folyamatok közt. A közös lapok csak olvashatók.

Oldal: 23 / 67

x

Címtranszformáció Lapszervezés esetén:

Kombinált szegmens és lapszervezés Q ! ! J memóriában szegmensek vannak ugyan, de '" %# } ' ' ! ' # \

& ' ? % ; ' " t módszer #

Virtuális tárkezelés #$% & A virtuális tárkezelés megengedi és biztosítja, hogy a rendszer folyamataihoz tartozó logikai címtartományoknak csak egy - a folyamat futásához éppen szükséges - része legyen a központi tárban, de ennek ellenére bármelyik folyamat ' ! ! ' ' &#

Q % "' & ! # ' !" " '!

lassú, ezért ezalatt az oprendszer egy másik folyamatot indít, a futót pedig várakozó állapotba helyezi amíg a blokk átvitele megtöténik. A virtuális tárkezelést támogató rendszerek lap- ' # '

! " !

% " % !' !

#

5++"Q + = (1-;$" !

% + !' # ? !' % " ;

' $ % & *+ " , x Igény szerinti lapozás: csak a hivatkozott lapot hozzuk be a tárba. x 5 " & # "' ! % '

lapokra lesz szüksége és azokat is betölti. Lapcsere stratégia (Replacement Strategy) x Optimális (OPT) algoritmus: !

%'# !' ''# Y #

x Legrégebbi lap (FIFO): Azt a lapot cseréli le amelyik legrégebben a tárban van. Hibája hogy a gyakran használt lapokat is lecseréli. Bélády-anomália: Bizonyos esetekben ha növeljük a folyamatokhoz tartozó fizikai memóriakeretek számát, akkor nem csökken, hanem éppen növekszik a laphiba gyakoriság. x Újabb esély (Second Chance): Egy R (referenced - hivatkozva) bitet is nyilvántartunk (egy lap használatkor 1' !! " '

;# Q -et törli, a lapot pedig a lista végére teszi. x Óra algoritmus: Ugyanaz, mint a Second Chance, csak egy ciklikus listával van megvalósítva (innen jön az Óra szó). x Legrégebben nem használt (LRU: Least Recently Used): Rögzítjük, hogy mikor használtuk ? '{ " { & ! ; ''

használtat. Mindegyik megvalósítás nagyon költséges. x Legkevésbé használt (LFU: Least Frequently Used , NFU: Not Frequently Used): Egy SHR van minden laphoz, a MSB-' ' ' # ' !% ' ''

szám van. (Tehát a régebbi használatokat is figyelembe vesszük, egyre kisebb súllyal -> ez az öregítés.) Másik probléma: a frissen behozott lapok SHR- & '% ' ?page locking). Oldal: 24 / 67

x

0 |\#|\# R bitet, és D bitet (dirty: írtunk rá, így nem egyezik ! ; ! #

! * !J

x szükség esetén mindig a folyamat saját munkaterületén belül választ ki lapot kivitelre - lokális lapcsere algoritmus x vagy egész memórián belül keresnek - globális lapcsere algoritmus

Gazdálkodás a fizikai tárral A folyamatok lapigénye x Hány lapot adjunk az egyes folyamatoknak (mekkora legyen a munkahalmaz mérete)? o Ha sok lapot adunk egy folyamatnak, akkor kevesebb folyamatot tudunk a tárban tartani. Ez csökkenti a CPU kihasználtságot. " '' !'#

o Ha kevés lapot adunk egy folyamatnak, akkor állandó laphiba lépne fel. Aminek következtében a CPU-nak nem lesz futtatható folyamata, CPU-tétlenség alakul ki. o A rendszer akkor lesz egyensúlyban, ha egy laphiba kezelése közben nem következik be újabb laphiba. x A gyakori laphibák által okozott teljesítménycsökkenést " nevezzük. Munkahalmaz $!

% ! '

! # ! ' " %#

Lokalitás x > " # ! & % !" ben újra használni fog. x Térbeli lokalitás: ' ! " ! " !

címekre történnek. Dinamikus lokális tárgazdálkodás ! ll a folyamatok hivatkozásainak lokalitásának kihasználására. A dinamikus tárgazdálkodás !' # Q ! % !

a folyamathoz újabb lapot rendel, vagy ha nincs szabad memória, akkor csökkenti a multiprogramozás fokát. Ha a laphiba gyakoriság egy alsó határ alá csökken, akkor elvesz a folyamattól egy lapot. 2 Lapméret Többnyire hardver határozza meg. Ha a lapméret nagy, akkor kisebb a laptábla mérete (kevesebb lap van), de nagyo'' ' # Q & #

Program struktúra A programozó is sokat tehet a rendszer jó teljesítményéért, ha kihasználja a tárkezelés sajátságait (pl. lokalitás).

Fájlrendszerek Az állományok tárolása a lemezen Az operációs rendszer a lemezterületet blokkokban kezeli. A blokkok méretét meghatározza a címek számára fenntartott hely és a lemezterület méretének aránya. A szabad blokkok nyilvántartására használt adatszerkezetek: x Bittérképes ábrázolás: A lemez mindegyik logikai blokkjához egy bitben tárolható, hogy szabad-e. % ' ' # Q ! ' #

x Láncolt listás ábrázolás: Minden szabad blokkból lecsípünk néhány bájtot, itt egy másik szabad blokk címét tároljuk. A láncolt listás bejárás miatt lassú. x Szabad helyek csoportjainak listája: Hasonló az elöbbihez, de a fennmaradó szabad bájtokon további szabad blokkok címét tároljuk. x 5+ " # Egy t' ' ' '"

! # Q ! ' ! #

Az egyes állományokhoz tartozó blokkok tárolásának, lefoglalásának módszerei: x Folytonos terület lefoglalása: A fájlhoz tartozó információt egymás melletti szabad blokkokban tároljuk. A & ' ' # = %

! !# ? ! '' worst-fit, majd first-fit/next-fit és végül Oldal: 25 / 67

nagy telítettség esetén best-fit stratégiát használunk.) Mind soros, mind közvetlen elérése gyors, ezért pl. virtuális tárcsere (swapping) esetén alkalmazzák. x Láncolt tárolás: A szükséges blokkokat egyesével allokáljuk, minden blokkban fenntartva egy helyet a ' # "' & ' # o J ! & ' ' # o QJ & !

% ' # FAT ?% & ';J & " '# Y

' %"' '' '' # $ ? ;

tárban tároljuk -] '' ! # x #

x Indexelt tárolás: Alapötlete, hogy az állományhoz tartozó blokkokat leíró címeket külön adatterületre, az '' # "' áblát tartalmazó blokk(ok) címét kell tárolni o J !

% ¢ ¢

o QJ % ' !

? ; $ J ! ' ? ' % ;

'' '

x Kombinált módszerek: Egyes rendszerek az állomány hozzáférési módja, vagy mérete függvényében más és " ! ''' '# akításával növeljük az adatbiztonságot, viszont csökken az értékes tárolókapacitás. 3# x Fájl attribútumainak módosítása x Új könyvtár létrehozása x Könyvtár törlése x Keresés Hozzáférés szabályozása A hozzáférési jogokat az állomány létrehozója vagy % & %! "

definiálhatja. Az állományokat a folyamatok hozzák létre vagy a felhasználó, aki a folyamatot elindította. Az egyedi hozzáférési jogok a fájlokhoz és könyvtárakhoz tartoznak. A jogosultságok azt szabályozzák, hogy a rendszer egyes %! " # Q * %! " &

csoportokhoz kötni. Tipikus fájl jogosultságok: írás, olvasás, hozzáírás, végrehajtás, törlés. Könyvtárakra: módosítás, törlés, listázás, keresés, új állomány létrehozása. Az oprendszer feladatai az I/O-kezelésben: x Egységes alkalmazói felület kialakítása (application interface): Részletek eltakarása, logikai perifériakezelés ! #

x Egységes csatlakozó felület kialakítása a készülékek számára (device interface) x '" "" "0"*# Perifériák ütemezése; az átvitelek szimultán lebonyolításában a programozottan végrehajtandó feladatok (megszakításkezelés, hibakezelés stb.) megoldása. Rendszerstruktúra (lásd TK 198. oldal, ábra):

A Kernel B/K alrendszere Oldal: 26 / 67

Jellegzetes feladatai: x Perifériák ütemezése: annak a végrehajtási sorrendnek a meghatározása, amelyet a perifériára várakozó átviteli kérelmek végrehajtására alkalmaz a renszer. x Átmenet ?!!5\0"*# o \ ' % &

o Ha a periféria számára blokkosítás szükséges, és az alkalmazás nem blokkokkal dolgozik. o & ' !"#

x Gyorsítótár m"* x Perifériahasználat koordinálása: Kizárolagos perifériahasználat megvalósítása (pl nyomtató, mágnesszalag esetén) x Hibakezelés: !' ' !' !"#

Háttértárak kezelése A számítógéprendszerekben azért alkalmazunk háttértárat, mert: x A központi tár egy bitre jutó ára magas, ezért kapacitása kicsi. x A központi tár a tápfeszültség kikapcsolásával elveszti az adatokat. x Minél nagyobb a tárolási kapacitás annál nagyobbnak kell lennie & !

információegység méretének. Háttértártípusok: ' '

? '' % !% ;#

Az operációs rendszer háttértár- &" '' % !

% ! " ' #

A lemezegység fizikai szervezése Mágneslemezegység felépítése (TK202 ábra): x Sáv (track): egy-egy lemezfelület azon része, amelyet a fej elmozdulás nélkül, a lemez egyetlen körülfordulása mentén elér. x Cilinder (cylinder): a fejtartó szerkezet egy adott pozíciójában leolvasható sávok összesége. x Szektor (sector): Egy- #

Az át % $ 6 x x ? ; – a leghosszabb x % ?& ;

x Az információ átvitelének ideje (transfer time) Szektorok címzése & '' " # % J b= s*(i*t + j) + k , ! ' & & & %

k=szektor száma a sávon belüli (offszet). # Az algoritmusok értékelésének szempontjai: x átbocsátó képesség x

x "

A fejmozgás optimalizálása Sorrendi kiszolgálás(FCFS): \& '& " & " #

[*+%0 ]!# \ az aktuálishoz legközelebbi cilinderre hivatkozó kérést szolgálja ki. " % ! #

Pásztázó (SCAN): \ ! %

iránynak % # '' x & '' #

N lépéses pásztázó (N-SCAN): Egy irányba mozogva csak N olyan kérést szolgál ki, ami a pásztázás elején már # ' ányváltás után történik. Teljesítménye jobb mint a SCAN teljesítménye. Egyirányú (körforgó) pásztázó (C-SCAN): A kérések kiszolgálása mindig csak egyik irányú fejmozgásnál történik. ' ! & '' %* lgálását. 5 [$# Egy irányba mozogva addig megy, amíg már abban az irányban nincs több kérés, ekkor megfordul a fej. Kis terhelésnél SCAN, nagyobb terhelésnél C-SCAN szokott a leghatékonyabb lenni. %7% & Oldal: 27 / 67

Egy cilin ' '!"#

Egyéb szervezési elvek a teljesítmény növelésére x Lemezterület tömörítése (disk compaction, defragmentation) x A gyakran szükséges adatokat több példányban tároljuk (nem mindig hasznos) x Több blokk e

x Blokkok átmeneti tárolása (disk cache) x Adattömörítési eljárások használata (data compression) Az adattárolás megbízhatósága x Adatok mentése (backup) x Átmeneti tár és a háttértár tartalmanák szinkronizálása x Lemezegységek többszörözése (disk shadowing, mirroring, RAID)

% Felhasználói parancsok bevitele, értelmezése. Parancsok végrehajtása. Eredmények, hibák közvetítése, megjelenítése. A felhasználók által használható parancsok típusai { &"# \ % ! & # ] " &"# % " " & ! ?

lehet rendszerparancs vagy felhasználói parancs). % & x * &

x biztonságos parancsok x % &"'

A tapasztalt felhasználó igényei x hatékony parancsok x konfigurálható parancsok x a felhas " ' ! &

Az oprendszer és a felhasználó közötti kommunikáció eszközei x Nem interaktív rendszerek: o Job Control Card x Interaktív, karakteres interfészt biztosító rendszerek: o '

o karakteres terminál x Grafikus be-/kimen J

o %&

o grafikus terminál x Hang be-/kimenet

Az X window rendszer Cél: &" % ' !" '

gépek között. !

*

%

# $ -szerver modell használata. Az X protokoll =% " ?* &"; A hálózati kommunikáció mérséklésére törekszik. Az X window-rendszer koncepciója X munkahely = X display + (1 vagy több) X screen + bemeneti eszközök. Ablakkezelés Bemeneti eszközök kezelése A bemeneti eszközöket az X szerver figyeli, állapotváltozásukkor a szerver esemény üzenettel értesíti a klienst. 3 ; $ ¤ ?' "; % # !

támogatja. Oldal: 28 / 67

Windowing system: a rendszer magja. Window manager: Az ablakok %! " # Session manager: %! " ' % #

4. Védelem és biztonság Folyamatkezelés Az elosztott rendszerek leggyakrabban kliens-szerver modellel és távoli eljáráshívással valósítják meg. Kliens-szerver folyamatok Kliens-szerver modell: a rendszer olyan partícionálása, amely meghatározza a rendszer által nyújtott szolgáltatásokat (szervizeket) a hozzájuk tartozó algoritmusokkal (szerverekkel). Démon folyamatok (daemon process): A *# % ' #

Ezek egy adott TCP vagy UDP porthoz kötött, állandóan futó folyamatok, melyek az adott szolgáltatás állandó ! ' ' ! " rendelnek. Hálózati számítási modell x A kliens alkalmazásoknak tisztában kell lenniük a szerverek pontos címével Elosztott számítási modell x ' * &

nélkül A kliens-szerver kapcsolat kiépítését egy "00Y" "* , a middleware biztosítja. Kötés: A kliens és a szerver közötti kapcsolat kiépítése, melynek során a kliens megtalálja a számára szükséges szolgáltatást nyújtó szervert, és kialakul a kommunikációs kapcsolat. Replikáció (replication): Konkurrens, ugyanolyan szolgáltatásokat nyújtó szerverek üzemeltetése. Caching (átmeneti gyorsítótárak alkalmazása): A kliens által gyakran kért információt egy helyi átmeneti tárolóban helyezzük el a klienshez minél közelebb. Ennek egy speciális fajtája a proxy, mely a webszerverek területén elterjedt. A proxy szerverek hierarchikus rendszert alkotnak. Távoli eljáráshívás - RPC Kliensek és szerverek közötti kommunikáció kialakításának legelterjedtebb módja az RPC (Remote Procedure Call), vagyis távoli eljáráshívás. Az RPC rendszer egy protokoll-leírást és egy programozói interfészt tartalmaz. Egy ! ! ! % #

' kommunikáció adatformátumát határozza meg. Foglalkozik még az átvitel mechanizmusával és az azonosítással is. Az RPC garantálja a kérések továbbítását a célig, illetve a válaszok visszajutását. Tipikus RPC kérés-válasz pár:

Oldal: 29 / 67

Az RPC egységes, kiterjeszett adatreprezentációt (XDR, Extended Data Representation) használ. Ez egy gépfüggetlen adatábrázolási mód, mely bevezet egy formális nyelvet az adatok leírására. J

x egész szám x változó hosszúságú adatfolyam x szöveg x tömb x struktúra Az RPC által nyújtott programozási eszköz az RPC nyelv, mely az XDR formalizmusát követi és alkalmas a szerver interfészének formális leírására. A szálak (threads; ! ! 'b feladatot hajtson végre '# '' * ! ! #

szálak alkalmazása növeli a teljesítményt, megvalósításkor könnyíti a programozók dolgát és segítségével a holpontok re " !"# ! '

logikailag egy szállá foghatjuk össez, ez az RPC-szál (RPC thread). A szálak hátrányai közé tarozik, hogy '' rán a kölcsönös kizárásmegvalósítása érdekében. Amennyiben a szálakat felhasználói szinten valósítják meg (user-level threads), az egész rendszer futása blokkolódhat. Kernel szinten (kernel-level threads) ez a probléma nem áll fent. Léteznek rendszerhívás szempontjából biztonságos (thread-safe) szálak is.

Elosztott rendszerek biztonsági kérdései Az elosztott rendszerek fokozottan ki vannak téve a különféle biztonsági fenyegetéseknek, biztonsági módszerek alkalmazásával % $# % szükség % biztonságpolitika mellett. Mi a biztonság? ' ' J

x Azonosítás (authentication) x Felhatanmazás (authorization) x Titkosítás (encryption) x Rendszer védelem (system protection) Kik a támadók és mik a fenyegetések? TámadóJ ' %&" % "'" #

rendszer valamely biztonsági hibáját használja ki a támadás során, mely lehet a biztonsági módszerek vagy a biztonságpolitika hibája. A támadás módszerei A támadónak hozzá kell férnie a rendszerhez. Ennek legelterjedtebb módjai: x Lehallgatás x Maszkírozás x Üzenetmódosítás x Visszajátszás '' ' " "' . Az elosztott biztonsági rendszer tervezése ' % % % &" & # !

% ! %&" ' ! % '" ' em bizonyosodik. A bizonyításnak formális alapokon kell nyugodnia. 5 : *Tökéletes biztonság nem létezik* Második aranyszabály: A legtöbb biztonsági problémát az emberek viselkedése okozza Titkosítás A biztonsági rendszerek megvalósításában a titkosítási módszerek kulcsszerepet játszanak. Amikor valamilyen információt titkosítunk, akkor olyan transzformációt végzünk rajta, mely az inverz transzformáció ismerete nélkül praktikusan lehetetlenné teszi az információ visszafejtését. A gyakorlatban használt titkosítási algoritmusok két nagy csoportba oszthatók: x Titkos kulcsú o % &

használva. x Nyilvános kulcsú Oldal: 30 / 67

o

A kommunikáló feleknek nem kell bízni egymásban. A &"'

! & kódoló és egy dekódoló kulcsot. A dekódoló kulcsot titokban tartja, a kódoló kulcsot nyilvánosságra hozza. A kodoló kulcs ismeretében nagyon nehéz meghatározni a dekódoló kulcsot (a módszer két nagyon nagy prímszám szorzatának használatán alapul). Hozzáférés-szabályozás x % ! " !

' %! "

körére. Azonosítás Az elosztott rendszer résztv ' !" ! # ¥'

végzi, melyet a többi szolgáltatás felhasználhat a felhasználók és programok azonosítására. Azonosítás és kulcs szétosztás A titkos kulcsok tárolására és elosztására speciális kulcsszervereket lehet használni, nagy gondot fordítva a hitelesítésre. Nyilvános kulcsú titkosítás esetén a feleknek biztosnak kell lenniük, hogy a kulcsok biztosan hitelesek. Ezt elektronikus aláírás használatával lehet szavatolni. X Qrver: Feladata, hogy folyamatpároknak biztonságos módon kulcsot biztosítson a kommunikációhoz. Needham és Schroeder ! " #

$ & #

Az A folyamat akar B-vel & #

irány üzenet A->S A,B,N S->A ¦§¦§ ¨©}« A->B ¦§ ¨© B->A {M}§ A->B {M'}§ « & © & § & # Q % ' ! # $

cimkék ! % ! # $®

!" $-' #

' jegynek nevezzük: ezt A nem tudja értelmezni, csak továbbküldi B-nek. B '' ! -val kell kommunikálni, és a közös kulcsot is. ' ! ' ' !

felhasználni. A jegyeket egyszer használatossá tehetjük, ha egyedi sorszámokat teszünk beléjük.

Oldal: 31 / 67

Algoritmuselmélet Alapdefiníciók:

1. Keresések/Rendezések Lineáris keresés: Rendezett halmazban minden elemet (n db van) megvizsgálunk. Költség legrosszabb --- átlagos esetben: n --- (n/2)+1

Bináris keresés: ! ' ! ! ! ? ; % ?2(n+1)) a lépésszám, ennél jobb nem is lehet – ellenség módszer

Buborék rendezés:

Beszúrásos rendezés:

Lépészszám: Oldal: 32 / 67

Összefésüléses rendezés:

Alapötlet:

' felét, majd a második felét, végül fésüljük össze. Ezt csináljuk rekurzívan.

Hogy elvarrjuk a rekurzió alját, legyen MSORT(A[i;i]) az üres utasítás.

Batcher-féle páros-páratlan összefésülés Összefésüléses rendezés egy változata, párhuzamosítás miatt gyorsabb:

Gyorsrendezés oszd meg és uralkodj: véletlen s ''

PARTÍCIÓ (s)

PARTÍCIÓ(s)

Ládarendezés (binsort)

Radix rendezés & '' ' ti … tk alakú szavak, ahol a ti komponens az Li rendezett típusból való, a rendezés lexikogra± #

x rendezzük a sorozatot az utolsó, a k-adik komponensek szerint ládarendezéssel x a kapottat rendezzük a k1-edik komponensek szerint ládarendezéssel

Oldal: 33 / 67

2. kezetek és elemzésük Kupac Egy (U,<) rendezett halmaz egy S véges részhalmazát szeretnénk tárolni, hogy a beszúrás és a minimális elem törlése (mintör ) hatékony legyen.

Kupacépítés

Kupacépítés költsége: O(n)

Mintör A minimális elem azfgyökérben van, ezt töröljük. A f-' % " ''

felszivárog(f). Költség: O(l)=O(log2n)

Beszúr Új levelet adunk a fához (ügyelve a teljességre), ide tesszük az s elemet. Ezután s-et mozgatjuk felfelé, mindig összehasonlítjuk az apjával. Költség: O(l)=O(log2n)

Kupacos rendezés & ' $< & ' # Költség: O(n)+O(n*log2n) = O(n*log2n)

Tároljuk az U rendezett halmaz elemeit, hogy BESZÚR, TÖRÖL, KERES, MIN, (MAX, TÓLIG) hatékonyak legyenek. bejárás: x preorder – elem, bal részfa, jobb részfa x inorder – bal részfa, elem, jobb részfa x postorder – bal részfa, jobb részfa, elem

Naív algoritmusok KERES(s,S): O(l), ahol l a fa mélysége Összehasonlítjuk s-et S gyökerével s’-# Q ! '' ' ! ''

jobbra. MIN: mindig balra lépünk, amíg lehet O(l) MAX: mindig jobbra lépünk, amíg lehet O(l) TÓLIG(a,b,S): KERES(a,S) -> INORDER a-tól b-ig O(n) BESZÚR(s,S): KERES(s,S)-sel megkeressük hova kerülne és új levelet adunk hozzá O(l) TÖRÖL(s,S): O (l) x ha s levél, akkor töröljük a levelet x ha s-nek egy fia van, akkor s <- fiú(s) Oldal: 34 / 67

x

ha s- % # ! J$AX(bal(s))-t és töröljük yt.

2-3 fa

log3 n d magassága d log2 n levelek száma: 2m-1 (m: szintszám) KERES(x): 4(m) MIN: O(m) – MAX: O(m) – utolsó levél TÓLIG(a,b): O(m + a-b intervallum hossza) BESZÚR(x): O(m) Keres() meghat. a helyét; ha az apjának eddig 2 fia volt – 3 lesz 3 fia volt – csúcsvágás Csúcsvágás: 1 szinttel feljebb az új csúcsot beilleszteni ugyanígy. Ha ez felmegy a gyökérig, ott is kell vágni, új % # TÖRÖL(x): O(m) Ha nem találtuk meg Æ nincs törlés Q & *&

3 gyereke van – töröljük a csúcsot 2 gyereke van van 3 gyerekes testvér: megosztoznak a maradék 4 gyereken nincs: csúcsösszevonás – 1szinttel feljebb törlés

B-fa Egy m- B-fa, röviden Bm-fa egy gyökeres, (lefelé) irányított fa, melyre érvényesek az alábbiaknak: x A gyökér foka legalább 2, kivéve esetleg, ha a fa legfeljebb kétszintes. x $ ' & *& '' % ?m/2) ±a van. x % #

x Egy csúcsnak legfeljebb m ±a lehet. x A tárolni kívánt rekordok itt is a fa leveleiben vannak Szintszám (n a levelek, k a szintek száma):

80 & 0#

Hash Oldal: 35 / 67

Vödrös hash

Hogyan helyezzük az új kulcsot a vödörbe? ' ! ! * ' ? ;# Kulcs szerint rendezve vannak, beszúráskor a helyére tesszük. Keresés a hash-táblában Kiszámítjukh(K)-t A V[h(K)] vödörben keresünk szekvenciálisan, addig megyünk, amig megtaláljuk, vagy véget ér.

Hashelés nyitott címzéssel

x

Lineáris próbálás

x

Álvéletlen próbával

x

Kvadratikus maradék próba

Oldal: 36 / 67

x

$

Hash-függvény x

Osztómódszer

x

Szorzómódszer

3. Gráfalgoritmusok és elemzésük

Éllistás megadás:

Mélységi bejárás Mohó menetelés, addig megy & % #

Oldal: 37 / 67

! "

#

$ %

5*+ "0&"0

Oldal: 38 / 67

Szélességi bejárás

80 "* +Q+ "

Piros-kék algoritmus

Oldal: 39 / 67

ÚNIÓ-HOLVAN adatszerkezet

Oldal: 40 / 67

Legrövidebb út keresése Dijkstra módszer Feladat: Legrövidebb utak problémája (egy forrásból)

D [] : Egy a G csúcsaival indexelt tömb az eljárás során addig megismert legrövidebbs vutak hossza x ett d(s,v) távolságnak ± d(s,v)-t érjük el. Adjecencia mátrixxal megadott esetben:

Éllistás esetben:

Legrövidebb utak nyomonkövetése

Bellmann-Ford módszer

Oldal: 41 / 67

Floyd módszer

Maximális párosítás páros gráfokban Magyar módszer = alternáló utak

@QZ" &Q

Oldal: 42 / 67

4. Bonyolultságelmélet ? 00 ?00 |?9

Karp redukció (visszavezetés): a mi problémánkat visszavezetjük egy ismert NP-teljes problémára; a mi problémánk nehezebb, mint az NP-teljes probléma.

NP-teljes nyelvek

P € NP-teljes, ha NP-' J ' ! NP-nehéz: minden NP-' ' !

Ismert NP-teljes problémák: x x x x x x

´µ¶J ´ ! % ?µ¶ '#; MAXFTL(G,k): G gráfban van k db független pont MAXKLIKK(G,k): G-ben van k pontú teljes részgráf HAMILTON-KÖR: G-ben van H-kör HAMILTON-ÚT: G-ben van H-út GRÁFIZO(G1,G2): G1 izomorf G2-vel (élet élbe,nemélet nemélbe visz)

Oldal: 43 / 67

x x x x x x

2DH: páros gráfban van-e teljes párosítás 3DH: 3 dimenziós házasítás X2C: teljes párosítás általános gráfban UTAZÓÜGYNÖK: lewgkisebb összsúlyú Hamilton út RHÖSSZEG(H,x): H-nak van olyan részhalmaza, amelynek összege x HÁTIZSÁK({a1..ak}értékek, {s1..sk}súlyok, S-teherbírás, E-célérték)

5. Általános algoritmustervezési módszerek Oszd meg és uralkodj A feladatot megpróbáljuk visszavezetni, „felvágni” ugyanezen probléma sokkal kisebb példányira úgy, hogy ezek megoldásából az eredeti probléma megoldása gyorsan összerakható legyen. x bináris kersés x összefésüléses rendezés x gyorsrendezésnél partíciók

Elágazás és korlátozás Feladat visszavezetése egy irányított fára, ezt fázistérnek nevezik. Ezt kellene teljesen bejárni a megoldás megtalálásához. Ez túl nagy, ezért az adott eseteket (fában egy pont) értékelünk és eldöntjük, hogy mi lehet a " # ¶ ' ' '' – korlátozó heurisztika.

Dinamikus programozás Gyarkran valamilyen % ! ! ! #

Lényege, hogy az optimumot (optimális megoldást) alkalmas kisebb részfeladatok optimumából (optimális '"; "' # Ez hasonlít egy táblázat sorról sorra ! % ! ! '

'' ' !

''#

6. " * #

Független élek

Oldal: 44 / 67

Ládapakolás

Utazó ügynök probléma

Oldal: 45 / 67

Szoftveres ismeretek 1. Szoftverfejlesztési folyamat és modelljei A termék élete x Követelmények elemzése Milyen technikai, gazdasági, jogi, társadalmi követelményeket kell kielégíteni ? x Specifikáció A k % % x Tervezés Hogyan kell a formálisan leírt megoldást megcsinálni ? x Implementáció A tényleges lépések végrehajtása x A termék valóban kielégíti-e a követelményeket ? x Karbantartás Milyen javítások, módosítások, fejlesztések szükségesek ?

Követelmény – Specifikáció – Tervezés – Implementáció –

– Karbantartás Vízesés modell - (top-down megközelítés)

Oldal: 46 / 67

Prototípus modell

$ akítása (célja a bizonytalanság csökkentése) Oldal: 47 / 67

• az igények pontosítása • részrendszerek kipróbálása •

%! " " & ! • fogékonyság • '+% *Q .

Inkrementális modell

% '' & ' • '' & & • % ' '' %! " 5 *" – – kisebb kockázat, az igények fokozatos közelítése – bizonytalan esetben is alkalmazható Hátrányok – Lassan készül el teljes rendszer – Soklépéses folyamat Spirálmodell

' 0 " – Igények meghatározása – Alternatívák értékelése, kockázat minimalizálása – módszertan megválasztása – %

A rendszer az egyes lépések során egyre finomodik, egyre több információ áll rendelkezésre. Ha már nincs & ! # 5 *" – kis kockázat – ! %! " ' nytalansága – ! % ' Oldal: 48 / 67

Hátrányok – hosszabb tervezési szakasz Alkalmazás – kockázatos, sok alternatívát tartalmazó esetekben Capability Maturity Model (Képességfejlettségi Modell)

a munkafolyamat menedzsment számára egy józanésszel létrehozott és a szoftverfejlesztés számára 0 +% "" kapcsolatos elképzeléseket tartalmazó alkalmazás. egy közösség által fejlesztett útmutató. A CMM jelenlegi formáját több száz szoftver-

nyerte el. a +% egy modellje. támaszt nyújtó váz a megbízható és konzisztens CMM-* %'& ! #

eljárásokat széles körben használják a szoftvercégek a fejlesztésben és a megbízók a lehetséges szolgáltatókkal kapcsolatos kockázatok felméréséhez.

CMM 5 szintje Szint 5. 4. 3. 2. 1.

Megnevezés Optimalizált Irányított Határozott < Kezdeti

Fókusz ¥" % % % A munkafolyamatok és a szervezett támogatás tervezettsége Projektmenedzsment alapú folyamatok Q

¢! ¢ '

1. Kezdetleges (initial): nem tudunk semmit 2. $ ! ?';J & J & !

és becsülni. 3. Definiált (defined): dokumentált, a cégnek van definiált munkamenete, a munkafolyamatok felépítésébe bele lehet látni. 4. < ?;J % %! ! "

szabályozható 5. x -optimalizáló (optimizing): új technológiákkal és módszerekkel kísérleteznek szabályozott formában, így növelve a hatékonyságot.

Oldal: 49 / 67

Oldal: 50 / 67

Oldal: 51 / 67

Követelmények kezelése és specifikálása

Oldal: 52 / 67

Project tervezet - Project plan x

x x x

x

x

Bevezetés - Introduction El zetes becslések - Project Estimates Kockázat mgmt - Risk Management Határid k – Project Schedule Alkalmazottak - Staff Organization Megvigyel és itrányító mehanizmusok - Tracking and Control Mechanisms

Követelmény specifikáció (Requirements / System Definition) x x

x

x x x

Bevezetés – Introduction Funkcionális és adatmodell - Functional and Data Description Részegység leírások - Subsystem Description Rendszer modellezés és szimulációs eredmények - System Modeling and Simulation Results Project irányítása – ProjectIssues Appendix - Appendices

Adatfolyam ábra (DFD)

Környezeti diagram (Context-Diagram) DFD+ tárolók

Entitás-relációs diagram (ERD)

Viselkedés modell

Oldal: 53 / 67

Architektúrális és részletes tervezés

Oldal: 54 / 67

Oldal: 55 / 67

Oldal: 56 / 67

Oldal: 57 / 67

Oldal: 58 / 67

Verifikáció és validáció Verification: "Are we building the product right ?" – the software should conform to its specification Validation: "Are we building the right product ?" – the software should do what the user really requir es

Software review concerned with analysis of the static system representation to discover problems (static verification) x relatively easy to use x quite inexpensive x can be employed at any stage of the development process x check conformance with a specification but not requirements x cannot check non-functional characteristics

Software testing

Tesztelés típusai x Unit test dik-e ? ! ; x Integration test Összerakva x System test Az egész rendszer x Acceptance test A felhasználóknak is jó-e Tesztelés dimenziói * , = FURPS x Functionality x Usability x Reliability x Performance x Supportability Oldal: 59 / 67

Tesztek a tesztelés dimenziói szerint kifejtve x Functionality o Function: azt csinálja-e, amit kell o Security: de csak azoknak, akiknek szabad x Usability o Esztétika, UI, varázslók, tréning, stb. x Reliability o Integrity: hibamentesség és hibaállóság o Structure: minden kapcsolat megvan-e, minden kapcsolódik-e ahhoz, amihez kell o StressJ -e extrém terhelés alatt x Performance o Benchmark: milyen gyors más ismert megoldásokhoz képest o Contention: versenyhelyzetek lekezelése o Load: milyen hatékony extrém terhelés alatt o ProfileJ x Supportability o Configuration: milyen konfigurációkon és mely feltételek mellett hogy üzemel és milyen funkciói vannak o Installation: milyen konfigurációkra és mely feltételek mellett települ fel

2. Eseményvezértelt programozás alapjai Az alkalmazások többsége manapság már eseményvezérelt. Ez azt jelenti, hogy az alkalmazás bizonyos elemei eseményeket váltanak ki bizonyos sorrendben (például egy gomb megnyomása a felhasználói felületen), amelyekre az alkalmazás más részei reagálnak. A program futása tehát nem szekvenciális. Az eseménykezelés .NET-ben, mint ahogy általában minden más programozói nyelvben (feltéve hogy támogatja azt), a Publisher/Subscriber tervezési mintára épül. Ennek lényege ! '!

& % !# a publikáló osztály elsüti % # .NET-ben az eseménykezelés hátterében a delegátok állnak. Az eseményt publikáló osztály tulajdonképpen egy multicast delegátot definiál, amely a feliratkozott osztályok egy-egy metódusára mutat. Amikor az esemény elsül, a % % " !"# %

" " ezzük.

3. Tervezési minták A tervezési minták a fejlesztés tervezés fázisában segítenek (az analízis minták az analízis fázisában) • [' * ' ' " *%! ! # • Az objektum-orientált tervezési minták a lehetséges osztályok és objektumok közötti összefüggéseket, relációkat írják le Nehéz (ezekben segítenek a patternek): I. Megfelel objektumokat megtalálni, definiálni Objektumok számának, méretének meghatározása Objektum interfészek definiálása Objektum implementálása II. Újrafelhasználás (design for reuse) III. Változtathatóság, kiterjeszthet ség (design for change)

Factory method Célja: x& $! ! ! * ! yra bízzuk.Szokás virtuális konstruktornak is nevezni. Példa: Framework, ami egyszerre több dokumentum kezelését támogatja (mint pl. a Visual Studio) Használjuk, ha Oldal: 60 / 67

x x

' !

Ha egy osztály azt szeretné, hogy leszármazottai határozzák meg azt az objektumot, amit létre kell hoznia

Abstract factory Példa: ' º>< ?' "' "' '#; Használjuk, amikor: x a rendszernek függetlennek kell lennie az általa létrehozott dolgoktól ("termék" objektumok, pl. felhasználói felület elemek) x x

'' &

A rendszernek szorosan összetartozó "termék" objektumok adott családjával kell dolgoznia, és ezt akarjuk kényszeríteni a rendszerben 5 *"# x Elszigeteli a konkrét osztályokat x & &

x &

Hátrányok: x Nehéz új termék hozzáadása. Ekkor az Abstract Factory egész hierarchiáját módosítani kell, mert az interfész rögzíti a létrehozható termékeket x Megjegyzés: ezt bizonyos esetekben ki lehet kerülni

Singleton Célja: Biztosítja, hogy egy osztályból csak egy példányt lehessen létrehozni, és ehhez az egy példányhoz globális hozzáférést biztosít. Megoldás: x % ! & ! ' !

x Biztosítson globális hozzáférést ehhez az egy példányhoz. Az Instance osztály- ? ; ! ! ! ¢tlen" példányt elérni. A Singleton::Instance() x Mindig ugyanazt az objektumot adja vissza x Bárhol leírható ez: o C++ esetén Singleton::Instance() o Java esetén Singleton.GetInstance() o Y» & J #< &

o globális hozzáférés a példányhoz A Singleton konstruktora protected láthatóságú! Ez garantálja, hogy csak a statikus Instance metódushíváson keresztül lehessen példányt létrehozni.

Composite Célja: Rész-egész viszonyban álló objektumokat fastruktúrába rendezi. A kliensek s ! !

' # Példa: [ % ! % ' ! Használjuk, ha x Objektumok rész-egész viszonyát szeretnénk kezelni x A kliensek számára el akarjuk rejteni, hogy egy objektum egyedi objektum vagy kompozit objektum: bizonyos '" #

Proxy Oldal: 61 / 67

Célja: Objektum helyett egy helyettesít objektumot használ, ami szabályozza az objektumhoz való hozzáférést Példa: ? ; Struktúra: x '&J % ' '& ? ;

x Realsubject: a valódi objektum, amit a proxy elrejt x Proxy: helyettesít objektum. Tartalmaz egy referenciát a tényleges objektumra, hogy el tudja azt érni. Szabályozza a hozzáférést a tényleges objektumhoz, feladata lehet a tényleges objektum létrehozása és törlése is. Típusok: x Távoli Proxy: Távoli objektumok lokális megjelenítése átlátszó módon. A kliens nem is érzékeli, hogy a tényleges objektum egy másik címtartományban, vagy egy másik gépen van x } J % ' ! ?# ;

x Védelmi Proxy: A hozzáférést szabályozza különböz jogok esetén x J ' ! ' ' !

végre (pl.:lockolás)

Observer Cél: Q ' " ! % e a konkrét osztályaiktól Példa: MVC vagy Document-View architektúra - A felhasználó megváltoztatja az egyik nézeten az adatokat, hogyan frissítsük a többit? 5 *"# x A modell kódjában csak egy IView lista van, így a modell független az egyes IView-t implementáló osztályoktól. A modell újrafelhasználható! x &! ! #

x ! * # '' m kell ehhez módosítani. x ! ! ' '

anélkül, hogy bármit is tudna róluk. Ez az ún. observer minta lényege Struktúra: x Subject: Tárolja a beregisztrált Observer-eket; Interfészt definiál Observer-ek be- és kiregisztrálására valamint értesítésére x Observer: Interfészt definiál azon objektumok számára, amelyek értesülni szeretnének a Subject-ben ' " ?> ;

x ConcreteSubject: Az observer-ek számára érdekes állapotot tárol; Értesíti a beregisztrált observer-eket, amikor az állapota megváltozik x ConcreteObserver: Referenciát tárol a megfigyelt ConcreteSubject objektumra; Olyan állapotot tárol, amit a megfigyelt ConcreteSubject állapotával konzisztensen kell tartani; Implemetálja az Observer interfészét ?> ; '& ! Y&'& # ''

frissíti a saját állapotát a megfigyelt ConcreteSubject? %

Használjuk, ha: x Amikor egy objektum megváltoztatása maga után vonja más objektumok megváltoztatását, és nem tudjuk, hogy hány objektumról van szó x ' ' ' "

feltételezések nélkül x Megjegyzés: az Observer az egyik leggyakrabban használt minta 5 *"# x Laza kapcsolat a Subject és az Observer között x Üzenetszórás támogatása Hátrányok: x Felesleges Update-ek Oldal: 62 / 67

x

> '& ?' '& ['&JJ>

meghívásakor megadhatja paraméterként, hogy mi változott meg).

bbi modellben a Subject ::Notifyt meghívó Observer-re is meghívódik az Update, holott az változtatta meg a ConcreteSubject állapotát

4. Webes alkalmazások fejlesztése Statikus webalkalmazások o o o

A tartalom állandó, nem tartalmaz szerver oldali logikát Kliens oldali logikát (JavaScriptet) tartalmazhat Újabban: a ritkán változó tartalmú, de dinamikus alapokon nyugvó webalkalmazást is szokás statikusnak nevezni.

Dinamikus webalkalmazások o

Dinamikus webalkalmazás x Szerver oldali logikát tartalmaz x Az oldalakon található információk egy része gyakran adatbázisban tárolódik x Kliens oldali logikát (JavaScript) tartalmazhat

o

Kliens oldal x ]&"Y 0 *+Yo o HTML kódot, HTTP választ tud feldolgozni x Valamilyen szinten implementálja a HTTP szabványt x Kommunikálhat más protokollon is a szerverrel x $0& + " x [ \ * + * " 0 " x Lehet oldalba ágyazott kontroll (Flash, Silverlight) x [* "Q+ % ""&íluslap, szkript stb.) x Futtatja a kliens oldali kódot x Browser sandboxban x A felhasználó akciói visszakerülnek a szerverre: postback vagy roundtrip x Pl. gomb megnyomására HTTP POST vagy URL paraméterek formájában

o

Szerver oldal x ! "X]]?"rést o input x Felhasználó által megadott input (URL, query string, form data) x $ 0 "" x Kliens paraméterei (pl. User-Agent, Accept-Language header) x _ 0 "+Y0"X]]? "

Qo output x Szerver o " + " x $ + "0

o

Állapotkezelést (session ID) valahol meg kell oldani (HTTP nem támogatja) x Valamilyen egyedi azonosító alapján x Kliens oldalon

Oldal: 63 / 67

x x x

x

x

URL paramé éter \%0 Cookie Szerver oldalon x In-process a webszerver memóriájában matban x Külön folyam an x Adatbázisba ASP.NET: web.con nfigban <session> tag

Szinkron és aszinkron felhasználói felület o

Postback lassú o jobb felh használói élmény, interaktivitás kellhet k oldalon x Futtatható kód a kliens x $

& " + " pplet, Flash, Silverlight, .NET WinForms kontroll,, ActiveX x JavaScript, Java ap Jogosultsági problémák a telepítéssel

o

Szinkron végrehajtás: ek (user action) és a szerver oldali feldolgo ozás (request processing) x '+ 0 egymással szinkronban van.

x x

x

o

Sávszélesség Sok adat me egy át a hálózaton, mindig az oldal teljes kódja Szerver terhelés ! "

""0 8 " " l állítani az oldal teljes kódját, még ha csak keevés is változik Felhasználói élmény Blokkolt felh használói felület Várakozás Teljes oldal frissítés: f villanás, scroll context változás

Aszinkron végrehajtás:

x

A felhasználó és a szerver tevékenysége nincs egymáshoz szinkron nizálva

Oldal: 64 / 67

o

AJAX: Asynchronous JavaScript and XML x A Wikipediában az AJAX szónak (http://en.wikipedia.org/wiki/ajax) több, mint 20 jelentése van: X0> ""& %'% Great és Ajax the Lesser], mindketten elestek a trójai háborúban), több focicsapat, négy autótípus, két mozdony, egy ló, egy aszteroida, egy amerikai és egy brit hadihajó, egy tisztítószer, két Marvell képregény figura, három együttes, egy dinoszaurusz faj, egy rakéta típus, egy öblítéses WC típus a XVI. századból, amit természetesen az angolok találtak fel. 80

"%+ 0"& 0 "

forradalmasítják a web programozását és használatát. x Jesse James Garrett *9+Y ""

Oldal: 65 / 67

x

8"*# '" * % " "" "9 Oldal = URL + DOM változások

x

5 *"# Nincs felhasználói felület blokkolás és várakozás Kisebb sávszélességet igényel x Kevesebb adat megy át a hálózaton Csökkentett szerver terhelés x Kevesebb feldolgozás kell szerver oldalon Gyorsabb Jobb felhasználói élmény x \* " x Nincs blokkolás x Nem frissül a teljes oldal, a munkaállapot (scroll context) megmarad x A felhasználói élmény $ <> % " @

x

Hátrányok: Szabvány limitációk x {*@&X]8[88[8&" $0" 0 x Általában nem futtatják a JavaScripteket Permalinkek x Oldal = URL + DOM változások {*+Y""# ry, back, forward x {*008 Forgalom számlálás, méretezés, tesztelés x Mit loggoljunk? Új felhasználói szokások, új design elvárások x Értik a felhasználók? Korlátozott mobil támogatás x {*"@&8[X&\Y%"Y0ámogatás

x

Sok technológia szükséges hozzá &0 Q'@'+Y"

x

quest objektum x XMLHttpReq ok Web Accesshez kellett) x 5 *>5& -ben jelent meg (az Outloo ActiveX objektumként x $** Q%"Y0" x '& Q 0Y" nél szabványosítás alatt x W3C-n 2 Working Draft állapotban x 2007.06.18-án h x http://www.w3.org/TR/XMLHttpRequest/ gébe0*X]]?"" X X]]? x Lényeg ' "" %" x ' % "0*"0 V egy metódust, amely feldolgozza a vállaszt x Visszahív S független x Szerverplatform e origin" policy (IE: "cross-domain and zone policcy" néven) x "Same * * x " Q * P FQDN-nek, portszámnak egyezniee kell x Protokollnak, o

JavaScript 0* 0" &0 9 x ' nete: x Történ B Eich fejlesztette ki 1995-ben, eredetileg Mocha-nak, majd Live x Brendan S Scriptnek hívták "Q x 5 %@ "" { x {*"0& & 0 " x 1997. októberében az IE 4 megjelent és cssak a JS 1.1-et támogatta, miközben a Netscape az 1.2-t. portolta a JS-t JScript néven x Microsoft megjelent a VBScripttel, majd p x 1997. ECMA szabvány: ECMAScript x 1998. ISO szabvány

3. Dynamic HTML (DHTML) és Document Object Model (DOM)) " + + + +Q x ' s *+ x Nem szabványos, H elemek elkérése x HTML F eseményekre x Feliratkozás 5 x 5 Y % "0Y"

Szkript 4.1. Kliens Oldal Oldal: 66 / 67

pl. Javascript 4.2. Szerver oldal pl. PHP

Oldal: 67 / 67

Adatbázisok 1. gyakorlat EK-modellezés Ridzi Péter – [email protected] Feladatok 1) színészeit, forgatókönyvíróit kívánjuk tárolni. juk a hosszukat, megjelenésük dátumát, a megtekintésükhöz ajánlott minimális életkort és a címüket. A r és forgatókönyvírókról tároljuk a nevüket, címüket, személyi és telefonszámukat. A személyi szám egyértel

azonosítja a személyeket. a. Tervez -modellt! b. Az EK-modellben tárolni szeretnénk az egyes színés " #

(feltesszük, hogy egy színész csak egy szerepet alakíthat a filmben)

$#e a diagrammot! c. % imi esetén ki(k) játsszák az áldozato(ka)t, természetfilmeknél pedig azt, hogy milyen ország(ok)ban forgatták . 2) Iskolákat, azokon belüli osztályokat valamint tanárokat és diákokat tartunk nyilván. Az iskolákról tároljuk a nevüket, címüket, igazgatóik kilétét. Az osztályokról tároljuk létszámukat, nevüket,

&' # *+ + uk, hogy melyik osztályokat tanítják, mit tanítanak / $ #$$ * 0# 3

' " 4 a. Tervezze meg az EK-modelleket, válassza meg a kulcsokat! b. Az EK-diagrammban tárolja a munkaviszonyok, hallgatói jogviszonyok kezdetét is. 3) Egy lízing- " ' $

' " $ & / + % $ hátránya? Gondolkodtató feladatok: 1) Az alábbiak közül melyek jelennek meg az EK-modellben és melyek az általa modellezett világban (az EK-modellben milyen formában)? a. egyed b. egyedhalmaz c. kapcsolat d. kapcsolattípus e. attribútum f. attribútumtípus 2) Hozzon egy-egy példát arra, hogy a „pénzt” mint attribútumot, illetve mint egyedet tároljuk. 3) Lehetséges-e? Mondjunk rá példát! Hogyan jelöljük az EK-diagrammon? a. Két egyedhalmaz között több kapcsolathalmazt veszünk fel. b. Egy-egy kapcsolatból több fut egyedek között. c. Egyedhalmaz önmagával van kapcsolatban. ZH- : Tankönyv, 134. oldal, 11. fejezet, 4. feladat

Adatbázisok 2. gyakorlat - Fizikai szervezés 1. Egy 1000 rekordból álló állományt ritka index szervezéssel tárolunk. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell. x Hány rekord fér el egy blokkban? x Hány blokkot foglal el az index struktúra és mennyit a teljes állomány? x Melyik szinten, melyik blokkokban és blokkok között követeljük meg a rendezettséget? x Mennyi ideig tart legfeljebb egy rekord tartalmának kiolvasása, ha feltételezzük, hogy az index x Mennyi ideig tart legfeljebb egy rekord tartalmának kiolvasása, ha az index struktúra nem fér el az 2. Vödrös hash szervezéssel tárolunk egy állományt, melyben a rekordok száma 15000. Egy rekord hossza 120 byte egy blokkba 4000 byte fér el, egy kulcs hossza 25 byte a mutatóé 8 byte. A szervezést 10 vödörrel oldjuk meg. (Feltételezhetjük, hogy a hash függvény egyenletesen osztja el a kulcsokat) x Mekkora az átlagos vödörméret? x Mekkora diszk terület szükséges a teljes struktúra tárolásához (valódi méret illetve felhasznált tárterület)? x ! "" #$ % "" # " &&katalógust a memóriában tároljuk) x ! && $ % " "" # akarjuk megtalálni a keresett rekordot? 3. ' *+++ / / " $ % " % # 6 7 rekordhossz 120 byte, egy blokk kapacitása (a fejrészt nem számítva) 1000 byte. A kulcs 50 byte-os, egy mutatóhoz 20 byte kell. Javasoljon tárolási eljárást a fenti problémára! Mekkora diszkterület szükséges a teljes struktúra tárolásához? 4. ' ":" " ; <$ " < pedig hash algoritmussal. Az állományon néha intervallumkeresést is meg kell valósítani! Melyik szervezési módszert válasszuk, Adjon értelmes alsó becslést a szükséges blokkok számára az alábbi feltételek mellett: x az állomány 3 000 000 rekordból áll x a kulcshossz 45 byte x egy rekord hossza 300 byte x egy mutató hossza 5 byte x egy blokk mérete 4000 byte 5. Egy 10 000 000 rekordból álló állományt szeretnénk B* fa szervezéssel tárolni. A rekordhossz 850 byte, egy blokk kapacitása (a fejrészt nem számítva) 4000 byte. A kulcs 50 byte-os, egy mutatóhoz 18 byte kell. @ % C" ! "" #$ %

/ lokk fér el? 6. Gondolkodtató kérdések x '" % #- < : % %% " " x ! %% " # $ % IK : x Milyen adatszerkezetet tudsz elképzelni egy térkép-szoftver adatbázisának? x Milyen sorrendben kell beszúrnunk a rekordokat egy B* fába ahhoz, hogy a legtöbb helyet pazaroljuk? x @ : % < "% # & C % - " x ! : $ &"$ % < "" & b B* fát építünk az adatbázisunkra? x @ % "

< IK " % < ! C $ "

!# :C$ %

C x Milyen nehézségeink adódnak, ha a töredékblokkokat is fel szeretnénk használni a merevlemezen? x ! C& & " "

x Miért nem beszéltünk arról, hogy blokkon belül hogyan tároljuk az adatokat? x L & # : " ; N O N O hány rekordot jelöl hány rekordot jelöl egy bejegyzése ki egy pointer-érték P < ISAM x L

$ % &# :

/ " %:"" helyezkedne el az adatbázisunk?

!"#$%& 789;<=>BC>; D>BFGJN ON 9QS UN VWXB9`(D ~>GB VWXWDSWZ .>YZ( ^<9FD B>\QD ^<9FD `^ VW`DFZY }<^< ^<9FD 0BB< X9`(D JD< \;D\Z

8(; D>BFGJ [N \9;<=>BC $qw q{|} {>9`>B( q7 0 q^Y
]N ;>D>Z>^ OxxO OxxU Oxx[ Oxx] Oxx Oxx Oxx Oxx Oxx OxOx

8FYBFGJ ON 9QS `^ }<^< 0BB< 7
ON VQD _B<`FD qQB< B>\QD

UN V>B>ZQX `^ 7
'"&(%())*#&+,+)#%)&/0&#)%)#2(#(3)4 • • • • •

}; < D>BFGJ;<9 ZY>D>B( VQDV<; }; XC>`BBFBBJ 9(; 7>BC =FYD>Z < 9( W<9 7>BC VWXB\ }; < =FY
• • •

}; < q^Y 7>BC>; ^ GZ<; >XCD>XC >\>D Y 7>BC>; ^ B>X^^>9 Y9>;

5")&667%&(+*#&+,+)#%8(93#$&7&,&,)#2(#(3)&4 !";<#8)&*)=)()>3&<&=,4 •

•

8MI{U8MSRCNL8MC 8MI{U8MSRCNO8MC 8MI{U8MSRCNL8MC 8MI{U8MSRCNO8MC 8MIJ{U8MSRCNL8MC 8MIJ{U8MSRCNO8MC 8MIJ{U8MSRCNL8MC 8MIJ{U8MSRCNO8MC KKN B(ZYD SYZXFB; \>X Y^W9ZFXWZZFX ZY>\W9^FJB < L8MC O8MC QZ Q8MC ;V>>YQZ^ QZ 9>XFB^<;<^N _ V>9^>; ;YBB \>BC ;V>>YQZ>; 9>XFB^< Y^W9ZFXWZ _ O S<XC L DQZY;V>>YQZ>;>^ =>BC>^^>ZU^S> QDS>B =F9C Y^W9ZFXWZ ;V>>YQZ^ ;<9;

}S<9^WD 9QB;BB ;V>>YQZ>;N Z8\EOFG [ {8\8Z8\ H Z8\EOF I [ {8\8Z8\ H Z8\EOF G [ J{8\8Z8\ H Z8\EOF I [ {8\8Z8\ H J8Z8\EOF I [

}S<9^WD^ ^>YQZ>;N KK L8MC I {O8MC H CNx O8MC I J{O8MC P CNx Q8MC I {O8MC RS CNx

?<&0(%()@ B • • • • • • • • • • •

7 VBXXQZ >XC ;V>>YQZ Y^W9ZFXWZZFX< QZ D>`\Q9C=XD\^US> B ^`ZY ;QY>B9 >XC Y^W9ZFXWZ ZWD;>YQZ >D>`\Q9C=B(FBBU^FZFD< }QZYU^Z D>BFGJDD< ;V>>YQZ^ >XC =X;Z> BB>^S> \FZW`; B>X;Z> >B>\Q9>; ;SFB99>; \>XV>B>B( ZWDD QZ WZYBW;>YQZ 7W9`9; \9QB ;BC>9=<XCJ \S>B>^>;>^W 7;WD ;Q9C>B\>Z> < ZWD QZ \;WD BFGJJB ;>D>Z` ; \ 9<XC<F;W _Y >XC>Z D>BFGJDD< ;V>>YQZ>;D(B FBB<U^Z; \>X =WXC D>`\Q9CBB ;<W^^ D>BFGJ ;Z> S<XC 9<XCW \9^ D>`>^ BB>^S> \;WD B>=>^ ^ 8D>`\Q9C D>BFGJ ZWD QZ WZYBWZYF\< =WXC<9 SZYW9CB D>`>^ D>BFGJ8; D>=>YW 7>BC D>BFGJD< \S>B>^>; 9S>D^FB=<^J; QZ \BC>9 \J`W9 D>`>^ D>BFGJ8; V>B=XC ;V>>YQZ Y^W9ZFXWZ <;;WD < 9>XFB^FDJB \^ \W9`=<^9; BB>^S> >BB>9;>Y( DF9C<9 \ < =>BCY>^ WDWB; V>B < ZWDD QZ WZYBW;^W 7QD^ ZYB;ZQX>Z < Y^W9ZFXWZ ZWD;V9UGJF9FB < ;Q^ V>B^Q^>B 7W9`9; QB`F^ WBC<9 >Z>^>;D> <=WB < ;V>>YQZ GZ<; XC;>^ ^>B>ZU^ \ >Y>;;>B < DWBQ\<

ȂͶǤǣ & ' ' J "* %! &* '

% & * % ! ' & ' '

!" ' & ! ' & &# '' !

" ? " ; %! &* ?& !

'#; ? ! ½ '#; " % ''

& & & % &* #

ǡ± ?/ d" <& P ^ ' ' D W& ;

?<\[Y$=;

x¦<¾\ ¾[Y$ Y$¾= ¾Y¨

# }¿ ' ' &À

# && '

! '' %'

´# %' '' x ' } ! '' ''

" $ 'À

# %' '' * '' x '

Â# ' ´x¿' ¿À Q & & ''

& ' %' '' * '' ´x '

# ' Yx¿' ¿À Q & & ''

& ' %' '' * '' Yx '

Ã# !¿ %& % * & %' ' 'À x ¿

%' À Q ! À

# &" " ' % % " '' ´x

' ! '' *

×±± #

> & ¿ ? %& % *; &

' ' %' ' ?! Yx ;À Q '! À $À

# # $ % ! '" %À

´# Q% ¢& ¢ % 'À $ ' À

# Q% ¢ ¢ % À \' ¿ "À $ & À Q !"À

Â# &" ' ! À & %

' %

# ' %' ! &"À &

' % ¶ % ! '' ' &" '

{

Ã# Q \ ' &" ' À

# \ ' %& % !" À Q %

! " ' %"À

Ä# ? ; ' x

# ' &" & '*'" #

!¿ ! ' '' xÀ

# Yx¿% ' & ´x ! %& % * &# ¿ %!

! & ! !" '' & & '' %

%'" &À

# $ ! ! ' ' ! %' *''

' À '' ! ! %' '' 'À

´# ' %' # * ' %' # $

À

# &" ' ''

À

Q %J \ { { Â# ´#{Â# Â# # #

x

´x¿

´x¿

Yx¿

Yx¿

x ‫ א ׊ ר‬ ¤ & J % ¤¿

x ‫ א ׊ ר‬ ¤ & J % ¤¿

x ‫ א ׊ ר‬ ¤ ‫ ك‬ J ?# ¤ ¾ ;

֜ ?¤ ¾ ;

x ‫ א ׊ ר‬ ¤ & J % ¤¿

x ‫ א ׊ ר‬ ¤ ‫ ك‬ J ?# ¤ ¾ ;

֜ ?¤ ¾ ;

" #$ " & '(

& )

!" !

# $ &&'" ) **+,-. # $ &&'/ **+,-. **+,-. 0 1 0 " !! 2 34 3 !& 56 72 ' "$56! 7 8 ."6!!" ! 2 & 67

* # ' ' '

! 5 !"9

$:

'; ' ' !"# < .$" 56! &' "!

!"

!"=$ !"%

=$ %

!"# 5 " 6 2! !"

56 && < !"#7 > !@" ! :

' 5

;B 0 8 &

+ , ,-# ' $

C @ D66! E ! 6!! & 56&&66 B66 "$ ! ! F!! )6 7 ! 566 ! " 0 0 !5!6!0# :G;5 0G5#G566 0 G 0 !5!6!# G5 0#G5HG66 0 G

. '/-0

C @

& 56 ' 5GI)"< < 46 6! <! ! B !J 2 $ '6!7F !! '56! ! &7 0 0J !5!6!0J 5 0 5J 0# !5!6!8 5 K5J

1'

0 L @ " &
@ ! '56 : <;! @ !! M ! < !

!

! ! ' 6 !" N!)M& ! N!)& 5 8

'OO6 ' / 5 6$ !56 : ;$

$ 26')$ '

72 ' "$56!6')7 J P6) ! !& ! 5 & 36 & &'6 & 7 # 2 !/ 56! ' 46 ! 6 5 / 46 7 K 2 5 ! ' 46 ! @B Q 2 5 ! ! 5 4 7R ! "! B H 2 ! 56! 9S/5 ' ' &&

72 $ 56&& $7 T 6 "! '! )

/ "56 6! ) " 7 0 O 4 <

O" $ &&'6!! ! 5!

' !

P6 72 56 65 !! 56B 00 O 4 <

O" !! "! 6 " $56! 4 ! /

' F! ! ! & 3 5 6 0 '()*+ , 7 '()*+ ' 7

Adatbázisok 6. gyakorlat - Tranzakciókezelés 1. feladat Legális-e az alábbi ütemezés? Ha nem, mit kellene javítani rajta, hogy azzá váljon? 2. feladat Rajzold fel a sorosíthatósági gráfot RLOCK-WLOCK modellben! Mi módosul, ha RLOCK/WLOCK helyett LOCK szerepel? 3. feladat Ellenőrizd, hogy legális-e az alábbi ütemezés! Rajzold meg a sorosíthatósági gráfot, döntsd el, hogy sorosítható-e az ütemezés. Ha igen, adj egy soros ekvivalenst, ha nem, mutasd meg, miért nem. Hogy nézne ki a gráf, ha RLOCKWLOCK modellt használnánk (ahol csak olvasunk, ott RLOCK-kal, ahol írunk (is) ott WLOCK-kal helyettesítjük értelemszerűen a LOCK-ot)? 4. feladat Legális-e az ütemezés? A tranzakciók követik-e a 2PL-t? Hol van az alábbi tranzakciók zárpontja? Mi egy soros ekvivalens ütemezés? 5. feladat Időbélyeges tranzakciókezelést használunk R/W modellben. Jegyezd fel az alábbi sorozat minden művelete után az R(A), R(B), W(A), W(B) értékeit, ha kezdetben mindegyik 0. Mely tranzakciók abortálnak? ri és wi a Ti tranzakció olvasás (r) és írás műveleteit (w) jelöli, és t(Ti) = i. r1(A), w2(B), r3(A), w1(B), r2(A), r4(B), w4(A), w3(B) 6. feladat Oldjuk meg az előbbi feladatot verziókezeléssel kiegészítve! Most mi történik? 7. feladat chekpoint Egy rendszerleállás után a napló vége az alábbi (T1, begin) bejegyzéseket tartalmazza. Melyek a redo helyreállítás (T2, begin) lépései? Mi lesz a helyreállítás után A, B és C értéke? (T2, A, 20) (T2, B, 10) (T1, A, 2) (T3, begin) (T1, C, 5) (T1, commit) (T3, C, 6) (T3, commit) Gondolkodtató feladatok: 1. A naplózás tárhely igényét szeretnénk optimalizálni. Helyes-e a következő érvelés? Mivel egy tranzakciónak csak a COMMIT pontjáig van szüksége a naplóra – hiszen a COMMIT utáni műveletek biztosan lefutnak –, ezért szigorú 2PL alkalmazásával megelőzzük a lavinahatást, és a COMMIT naplózása helyett így a naplóból már törölhetjük az adott tranzakcióhoz tartozó bejegyzéseket (ha garantáljuk ezen törlés atomicitását). 2. Hogyan biztosítja a holtpontmentességet a 2PL? 3. Igaz-e, hogy egy kétfázisú protokoll estén a tranzakciók mindig helyesen futnak le? (Mit jelenthet az, hogy „helyesen”?) 4. Lehet-e konkurensen módosítani egy állományt, amire B* fa épül? Mikor lehet felszabadítani a gyökér elemet fogó zárat? 5. Miért fontos a sorosíthatóság? 6. Egy ütemezés nem sorosítható, ennek ellenére érvényes lehet-e az izolációs elv? 7. Ha a naplófájl tartalmaz minden információt a változásokról, akkor miért kell az adatbázis? 8. Mondj példát kézenfekvő soros ekvivalensre 2PL és időbélyeges tranzakciókezelés esetén? 9. Mikor érdemes 2PL-t és mikor időbélyeges tranzakciókezelést alkalmazni? 10. Mi történik a sorosíthatósági gráffal, ha egy tranzakció abortál? 11. Az időbélyeges tranzakciókezelés miként véd a holtpont ellen? 12. Mondj példát vagy ellenpéldát a következő esetekre! a. Időbélyeges tranzakciókezelés esetén egy tranzakció READ esetén abortál. b. Időbélyeges tranzakciókezelés esetén egy tranzakció WRITE esetén abortál. c. Időbélyeges tranzakciókezelést verziókezeléssel együtt alkalmazunk. Egy tranzakció READ esetén abortál. d. Időbélyeges tranzakciókezelést verziókezeléssel együtt alkalmazunk. Egy tranzakció WRITE esetén abortál. 13. Hogyan tároljuk az időbélyegeket? Mit tudunk mondani a számukra vonatkozóan? Meddig kell fenntartani?

1. feladat

3. feladat:

T1

T2

T3 T1

RLOCK B

T3

(1)

READ B

LOCK A

(3)

RLOCK A

T4 LOCK B

(2)

WLOCK B

LOCK C

WRITE B

(4)

LOCK D

UNLOCK B

(5)

WRITE D

(6)

READ A

READ C

RLOCK A

(7)

READ A

(8)

UNLOCK B

(9)

LOCK E

UNLOCK A

(10)

LOCK D

(11)

READ D

WRITE A UNLOCK D

(12)

2. feladat: T1

T2

T2

T3

T4

(13)

UNLOCK A READ E

(14)

WLOCK A UNLOCK A RLOCK A

UNLOCK C

(15)

READ D

(16)

UNLOCK D

(17)

UNLOCK A RLOCK A UNLOCK A WLOCK A UNLOCK A

4. feladat:

WRITE B

(18)

LOCK C

(19)

LOCK D

(20)

UNLOCK E

(21)

WRITE C

(22)

READ D

(23)

LOCK A

(24) T1

T2

T3

LOCK A LOCK B LOCK C LOCK D LOCK E UNLOCK A UNLOCK D LOCK A

(25)

LOCK B

(26)

READ A

(27)

UNLOCK A

(28)

UNLOCK D

(29)

WRITE B

(30)

LOCK E

(31)

READ E

(32) (33)

LOCK D

UNLOCK B

UNLOCK B LOCK A

(34)

UNLOCK E

UNLOCK E

(35) UNLOCK B UNLOCK C UNLOCK A UNLOCK D

UNLOCK C

(36)

READ A

(37)

UNLOCK A

(38)

LOCK E

(39)

WRITE E

(40)

UNLOCK E

MSC megapack. by Hidden

Recommend Documents