Oper´aci´os rendszerek Varga L´aszl´ o
[email protected] Szegedi Tudom´ anyegyetem
2012-2013-II levelez˝ o tagozat
1
A kurzusr´ol K¨ ovetelm´enyek ismertet´ese ´ ad jegyzete alapj´an. A f´ oli´akat Erd˝ohelyi Bal´azs k´esz´ıtette Makay Arp´ Aj´anlott irodalom: • Andrew S. Tanenbaum - Albert S. Woodhull: Operating Systems; Design and Implementation, Prentice Hall, 2006. Oper´aci´os rendszerek; tervez´es ´es implement´aci´ o, Panem, 2007 • Andrew S. Tanenbaum - Modern Operating Systems 3. ed., Prentice Hall, 2007
2
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Mi egy oper´aci´os rendszer? Egy modern sz´am´ıt´og´ep a k¨ ovetkez˝ o dolgokb´ ol ´all: • Egy vagy t¨ obb processzor • Mem´ oria • Lemezek • Nyomtat´ ok • K¨ ul¨onb¨oz˝o I/O eszk¨oz¨ ok • ...
Ezen komponensek kezel´ese egy szoftver r´eteget ig´enyel – Ez a r´eteg az oper´ aci´ os rendszer
3
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Oper´aci´os Rendszerek helye Sz´am´ıt´og´epes Rendszer + Felhaszn´al´ ok = Egys´eges Tervez´esi Egys´eg. • Sz´ am´ıt´ og´epes Rendszer: hardver, szoftver, h´al´ ozat. • Felhaszn´ al´ok: ember (programoz´ o is), g´ep, program, m´asik
sz´am´ıt´ og´epes rendszer.
4
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Oper´aci´os Rendszerek helye - Szoftver elemek
• Alapszoftverek: ´ altal´anos funkci´ okat biztos´ıtanak • Hardver-k¨ ozeli, pl. driver-ek • H´ al´ ozati, pl. kommunik´aci´ os • Oper´ aci´ os Rendszer (OS) • Seg´ edprogramok: ford´ıt´ ok, egyszer˝ u sz¨ oveg-editorok, adatb´azis-kezel˝ok • Felhaszn´ al´oi v. applik´aci´ os programok: konkr´et probl´ema megold´as´ara
sz¨ uletett program. ´ anos applik´aci´ • Altal´ ok: t´abl´azatkezel˝ ok, sz¨ ovegszerkeszt˝ok, WEB b¨ ong´esz˝ o, ... stb. • C´ elrendszerek: ETR, banki alkalmaz´asok, ... stb.
5
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Oper´aci´os Rendszerek helye
6
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Oper´aci´os rendszerek alapvet˝o feladatai
• A felhaszn´ al´o k´enyelm´enek, v´edelm´enek biztos´ıt´asa = Kiterjesztett
(Virtu´alis) g´ep • Az emberi felhaszn´ al´ o sz´am´ara k´enyelmes kezel´esi funkci´ok;
jogosults´agok kezel´ese • Programok sz´ am´ara fut´as k¨ ozben haszn´alhat´ o elj´ar´asok, f¨ uggv´enyek; a
fut´ o program mem´ oriater¨ ulet´enek v´edelme • A rendszer hat´ ekonys´ag´anak, teljes´ıtm´eny´enek maximaliz´al´asa =
Er˝oforr´as-kezel´es • Hardver er˝ oforr´asok: CPU (processzor), mem´ oria, I/O
(Bemeneti/Kimeneti) eszk¨ oz¨ ok, f´ajlkezel´es, ... stb. • Szoftver er˝ oforr´asok: elj´ar´asok, buffer-ek (´atmeneti t´arol´ok), u ¨zenetek,
szolg´altat´asok, ... stb.
7
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
Oper´aci´os rendszerek alapvet˝o tulajdons´agai • Processzusok (folyamatok) az alapvet˝ o akt´ıv alkot´oelemek • Processzus (proc): v´ egrehajt´as alatt l´ev˝ o program • Processzus l´ etrej¨ on (programbet¨ olt´es, v´egrehajt´as ind´ıt´asa, ...), l´etezik (”fut”), majd megsz˝ unik (exit) • Egyidej˝ uleg t¨obb processzus l´etezik: A processzor (CPU) idej´et meg
kell osztani az egyidej˝ uleg l´etez˝ o procok k¨ oz¨ ott: id˝ooszt´as (time sharing) • Az er˝ oforr´asok centraliz´alt kezel´ese: Az er˝ oforr´asokat a processzusok
(k´er´es¨ ukre) az OS-t˝ol kapj´ak • Esem´ eny-vez´erelt esem´eny megszak´ıt´as 3 esem´ eny feldolgoz´asa 4 esem´ eny kiszolg´al´asa 5 visszat´ er´es a megszak´ıt´as hely´ere 1 2
8
Bevezet´ es
Oper´ aci´ os rendszerek jellemz´ ese
´ Oper´aci´os Rendszer Allatkert • Nagysz´ am´ıt´og´epes (mainframe) oper´aci´ os rendszerek: Nagy I/O
• • • • • • • •
kapacit´as, Sok job v´egrehajt´asa, Batch, tranzakci´ok feldolgoz´asa. Pl: OS/390, UNIX, Linux Szerver oper´aci´os rendszerek: sok user, koz¨ osen haszn´alt hw ´es sw er˝oforr´asok. Pl. Solaris, FreeBSD, Linux, Windows Server 200x T¨obbprocesszoros oper´aci´ os rendszerek, Pl. Windows, Linux PC-s oper´aci´os rendszerek, Pl. Linux, FreeBSD, Windows Handheld oper´aci´os rendszerek: PDA. Pl. Symbian OS, Palm OS Be´agyazott oper´aci´os rendszerek: Tv, h˝ ut˝ o. Pl. QNX, VxWorks ´ Erz´ekel˝o csom´opontos oper´aci´ os rendszerek: T˝ uz ´erz´ekel˝o. Pl: TinyOS Real-time oper´aci´os rendszerek: Hard, soft. Ipari robotok, digit´alis multim´edia eszk¨oz¨ok. Smart card oper´aci´os rendszerek: Java SmartCard 9
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
Gener´aci´ok
• Az els˝ o gener´aci´o: V´akuumcs¨ ovek ´es kapcsol´ ot´abl´ak (1945-1955) • A m´ asodik gener´aci´o: Tranzisztorok ´es k¨ otegelt rendszerek
(1955-1965) • A harmadik gener´ aci´o: Integr´alt ´aramk¨ or¨ ok ´es multiprogramoz´as
(1965-1980) • A negyedik gener´ aci´o: Szem´elyi sz´am´ıt´ og´epek (1980- )
10
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
Az els˝o gener´aci´o V´ akuumcs¨ ovek ´es kapcsol´ ot´ abl´ ak (1945-1955)
• Nincs oper´ aci´os rendszer • Howard Aiken, Neumann J´ anos, J. Presper Eckert, John William
Machley, Konrad Zuse • 1 felhaszn´ al´o, 1 program, fix mem´ oriac´ımek, megb´ızhatatlan hardver
¨ • ”Uresen indul a g´ep”: bootstrap; • Programoz´ o = G´epkezel˝ o = Programok v´egrehajt´as´anak vez´erl˝oje • Programoz´ asi nyelvek ismeretlenek (m´eg assembly sem): bin´aris
k´odol´as • 1950-es ´ evek eleje: lyukk´arty´ak
11
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A m´asodik gener´aci´o Tranzisztorok ´es k¨ otegelt rendszerek (1955-1965)
• Oper´ aci´os rendszer van, rezidens a mem´ ori´aban • Tranzisztorok – megb´ızhat´ o sz´am´ıt´ og´epek • Mainframe / nagysz´ am´ıt´ og´ep • Pap´ıron ´ırt programok – lyukk´ artya – kezel˝ o - k´av´ez´as – eredm´eny –
nyomtat´o – kiviteli terem • Egyidej˝ uleg csak 1 proc • Feladat (job) sorozat (k¨ oteg) v´egrehajt´as´at vez´erli az OS → teljes´ıt˝ok´epess´eg n¨ovekedett • Programoz´ ok t´amogat´as´ara bevezetett megold´asok: • • • •
verem-mem´ oria eszk¨ ozvez´erl˝ ok h´ıvhat´ o OS elj´ar´asok relat´ıv c´ımezhet˝ os´eg
• FORTRAN, ALGOL programoz´ as 12
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A m´asodik gener´aci´o Egy szok´ asos FMS feladat
13
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A m´asodik gener´aci´o Egy korai k¨ otegelt rendszer
(a) (b) (c) (d) (e) (f)
A programoz´o a k´arty´ait az 1401-eshez juttatja A feladatk¨oteg szalagra olvas´asa A g´epkezel˝o ´atviszi a bemeneti szalagot a 7094-eshez Sz´amol´as v´egrehajt´asa A g´epkezel˝o ´atviszi a kimeneti szalagot a 1401-eshez Eredm´eny nyomtat´asa 14
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A harmadik gener´aci´o Integr´ alt ´ aramk¨ or¨ ok ´es multiprogramoz´ as (1965-1980)
• Oper´ aci´os rendszer van, rezidens/tranziens a mem´ori´aban • CPU ´ es I/O ´atfed˝oen k´epes dolgozni - a CPU teljes idej´enek
kihaszn´al´asa csak t¨obb proc egyidej˝ u l´etez´es´evel lehets´eges → multiprogramoz´as • T¨ obb felhaszn´al´o: termin´alok, on-line programv´egrehajt´as • CPU id˝ oszeletel´es (time slicing)
´ • Atmeneti t´arol´as (spooling) • Mem´ oria-part´ıci´ok: minden part´ıci´ oban egym´ast´ ol f¨ uggetlen¨ ul folynak
job k¨otegek v´egrehajt´asai • COBOL, ADA, PASCAL, SIMULA, ... programoz´ as
15
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
Id˝oszeletel´es - Time Slicing
• CPU id˝ oszeletel´es: egy proc csak egy meghat´arozott maxim´alis
id˝ointervallumon kereszt¨ ul haszn´alhatja a CPU-t folyamatosan • Legyen tmax az az id˝ ointervallum, amely alatt egy p proc
folyamatosan birtokolhatja a CPU-t. • Ha tmax letelik: az OS processzus-¨ utemez˝ o alrendszere ´atadja a
CPU-t egy (m´asik) proc-nak; k´es˝ obb p u ´jra kap tmax intervallumot. • tmax kb. 10-20 msec
16
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
´ Atmeneti t´arol´as - Spooling • az I/O adatok el˝ osz¨or gyors h´att´ert´arol´ ora (disk) ker¨ ulnek (spool
ter¨ ulet), a proc innen kapja / ide ´ırja az adatait • jobb perif´ eria (er˝oforr´as)-kihaszn´al´as (olvas´ ok, nyomtat´ok)
17
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
Mem´oria-part´ıci´ok • Statikus: OS indul´ asakor fix darabsz´am´ u (pl.16), fix m´eret˝ u part´ıci´o
k´epz˝odik. Egy program v´egrehajt´as´ahoz megkeres egy szabad ´es elegend˝o m´eret˝ u part´ıci´ ot, amelyben a program v´egrehajt´as´at megkezdi. • Dinamikus: OS egy program v´ egrehajt´as´ahoz a szabad
mem´oriater¨ uletb˝ol k´esz´ıt egy elegend˝ o m´eret˝ u part´ıci´ot, amelyben a program v´egrehajt´as´at megkezdi – a part´ıci´ ok sz´ama ´es m´erete v´altoz´o
18
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A negyedik gener´aci´o Szem´elyi sz´ am´ıt´ og´epek (1980- )
• Oper´ aci´os rendszer van, t¨ obb t´ıpus • LSI ´ aramk¨or¨ok fejl˝od´ese • Kateg´ ori´ak • PC, Workstation: egyetlen felhaszn´ al´ o, egy id˝ oben t¨obb feladat (Pl. Windows, Mac OS, OS/2) • H´ al´ ozati OS: h´al´ ozaton kereszt¨ ul t¨ obb felhaszn´al´o kapcsol´odik, minden felhaszn´al´ o egy id˝ oben t¨ obb feladatot futtathat (Pl. UNIX, LINUX, NT) • Osztott (h´ al´ ozati) OS: egy feladatot egy id˝ oben t¨obb sz´am´ıt´og´epes rendszer v´egez. Er˝ oforr´asok (CPU, Mem´ oria, HDD, ...) megoszt´asa egy feladat elv´egz´es´ehez. (pl. GRID, SETI)
19
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
A negyedik gener´aci´o jellemz˝oi Szem´elyi sz´ am´ıt´ og´epek (1980- )
• Alkalmaz´ asfejleszt´es seg´ıt´ese: Objektum-orient´alt ´es kliens-szerver
m´odszerek. • Hordozhat´ os´ag (hardver-f¨ uggetlens´eg) seg´ıt´ese. Probl´em´ak: grafikus
fel¨ uletek alapjaiban k¨ ul¨ onb¨ oznek. • Egyes szolg´ altat´asok lev´alaszt´asa az OS magj´ar´ ol, a szolg´altat´asok
egym´ast´ol val´o f¨ uggetlens´ege • Spool-technika (cache) hardverrel seg´ıtett ´ es sz´eles k¨orben
alkalmazott (RAM-ban is) adatokra, programokra egyar´ant
20
Bevezet´ es
Az oper´ aci´ os rendszerek t¨ ort´ enete
OS fel¨uletei • Felhaszn´ al´ oi fel¨ ulet (ff): a felhaszn´al´ o (ember) ´es az OS kapcsolati
alrendszer. Parancs´ertelmez˝o (Command Interface, Shell); Grafikus fel¨ ulet • Program fel¨ ulet (pf): proc ´es OS kapcsolati alrendszer Rendszerh´ıv´asok (OS elj´ar´asok, f¨ uggv´enyek; system calls); OS szolg´altat´asok (services)
21
Bevezet´ es
Rendszerh´ıv´ asok
Rendszerh´ıv´asok – System calls
• Processzus kezel´ es (process management) • Jelz´ esek (signals), Esem´enyek (events) kezel´ese • Mem´ oriakezel´es (memory management) • F´ ajl (file), K¨onyvt´ar (directory) ´es F´ajlrendszer (file system) kezel´es • V´ edelem (protection) – adat, user, program, ...
¨ • Uzenetkezel´ es (message handling)
22
Bevezet´ es
Rendszerh´ıv´ asok
Rendszerh´ıv´asok – System calls
1 2 3 4
a h´ıv´o proc-nak joga volt-e h´ıv´as param´eterek ellen˝ orz´ese t´abl´azat rendszer elj´ar´asok kezd˝ o c´ım´et t´arolja vez´erl´es visszaad´asa a proc-nak 23
Bevezet´ es
Rendszerh´ıv´ asok
P´elda: a read(fd, buffer, nbytes) rendszerh´ıv´asa
24
Bevezet´ es
Rendszerh´ıv´ asok
Processzuskezel´es
pid = fork(); // Create a child process identical to the parent pid = waitpid(pid , &statloc , opts ); // Wait for a child to terminate s = wait(&status); // Old version of waitpid s = execve(name, argv, envp); // Replace a process core image exit ( status ); // Terminate process execution and return status size = brk(addr); // Set the size of the data segment pid = getpid(); // Return the caller ’ s process id pid = getpgrp(); // Return the id of the caller ’ s process group pid = setsid (); // Create a new session and return its proc. group id l = ptrace(req, pid , addr, data ); // Used for debugging
25
Bevezet´ es
Rendszerh´ıv´ asok
Szign´alkezel´es
s = sigaction( sig , &act, &oldact); // Define action to take on signals s = sigreturn(&context); // Return from a signal s = sigprocmask(how, &set, &old); // Examine or change the signal mask s = sigpending(set ); // Get the set of blocked signals s = sigsuspend(sigmask); // Replace the signal mask and suspend the process s = kill (pid , sig ); // Send a signal to a process residual = alarm(seconds); // Set the alarm clock s = pause(); // Suspend the caller until the next signal
26
Bevezet´ es
Rendszerh´ıv´ asok
K¨onyvt´ar- ´es f´ajlrendszerkezel´es, v´edelem s s s s s s s s s
= = = = = = = = =
mkdir(name, mode); // Create a new directory rmdir(name); // Remove an empty directory link(name1, name2); // Create a new entry, name2, pointing to name1 unlink(name); // Remove a directory entry mount(special, name, flag ); // Mount a file system umount(special); // Unmount a file system sync(); // Flush all cached blocks to the disk chdir(dirname); // Change the working directory chroot(dirname); // Change the root directory
s = chmod(name, mode); // Change a file’s protection bits uid = getuid (); // Get the caller ’ s uid gid = getgid (); // Get the caller ’ s gid s = setuid(uid ); // Set the caller ’ s uid s = setgid(gid ); // Set the caller ’ s gid s = chown(name, owner, group); // Change a file’s owner and group oldmask = umask(complmode); // Change the mode mask
27
Bevezet´ es
Rendszerh´ıv´ asok
F´ajlkezel´es fd = creat(name, mode); // Obsolete way to create a new file fd = mknod(name, mode, addr); // Create a regular, special , or directory i −node fd = open(file , how, ...); // Open a file for reading , writing or both s = close(fd ); // Close an open file n = read(fd, buffer , nbytes ); // Read data from a file into a buffer n = write(fd, buffer , nbytes ); // Write data from a buffer into a file pos = lseek(fd, offset , whence); // Move the file pointer s = stat(name, &buf); // Get a file ’ s status information s = fstat (fd , &buf); // Get a file ’ s status information fd = dup(fd); // Allocate a new file descriptor for an open file s = pipe(&fd[0]); // Create a pipe s = ioctl (fd , request , argp ); // Perform special operations on a file s = access(name, amode); // Check a file ’ s accessibility s = rename(old, new); // Give a file a new name s = fcntl (fd , cmd, ...); // File locking and other operations
28
Bevezet´ es
Rendszerh´ıv´ asok
Rendszerh´ıv´asok – System calls A Win32 API h´ıv´ asok, amelyek nagyj´ ab´ ol hasonl´ıtanak a UNIX h´ıv´ asokra
29
Bevezet´ es
Az OS strukt´ ur´ aja
OS strukt´ur´ak
• Monolitikus rendszerek • R´ etegelt rendszerek • Virtu´ alis g´epek • Exokernelek • Kliens szerver
30
Bevezet´ es
Az OS strukt´ ur´ aja
Monolitikus rendszerek A ”Nagy o ¨sszevisszas´ ag”
• Legelterjedtebb szervez´ esi m´ od. F˝ oprogram: megh´ıvja a k´ert
szolg´altat´as elj´ar´as´at, szolg´ altat´ o elj´ ar´ asok: teljes´ıtik a rendszerh´ıv´asokat, seg´ ed elj´ ar´ asok: seg´ıtik a szolg´altat´as elj´ar´asokat. • Strukt´ ur´aja a struktur´alatlans´ag • Elj´ ar´asok gy˝ ujtem´enye, b´armelyik h´ıvhatja a m´asikat
31
Bevezet´ es
Az OS strukt´ ur´ aja
R´etegelt OS • Elj´ ar´asok, F¨ uggv´enyek halmaza, amelyek r´etegekbe csoportosulnak • Fel¨ ugyelt elj´ar´as-h´ıv´asok (supervisor calls) • Programv´ egrehajt´as-szintek: norm´al m´ od (az OS elj´ar´asok egy
•
• • • • •
meghat´arozott r´eszhalmaza h´ıvhat´ o; felhaszn´al´ oi programok); kit¨ untetett (supervisor, kernel) m´ od(ok) (speci´alis OS elj´ar´asok is h´ıvhat´oak; rendszerprogramok) Szab´aly a r´etegekre: b´armely n-edik r´etegbeli elj´ar´as csak a k¨ozvetlen ´ alatta l´ev˝o n-1-edik r´eteg elj´ar´asait h´ıvhatja - Attekinthet˝ o elj´ar´asrendszer alak´ıthat´ o ki A r´etegek saj´at (glob´alis) adatter¨ ulettel rendelkezhetnek ´ Attekinthet˝ o adat´araml´as Konfigur´alhat´o: pl. az eszk¨ ozvez´erl˝ ok egy r´etegbe csoportos´ıthat´oak Rezidens, Tranziens r´etegek Egy r´eteg = Virtu´alis (absztrakt) g´ep: a r´etegbeli f¨ uggv´enyek ´altal ny´ ujtott funkci´ok ¨osszess´ege (pl. IBM VM/370) 1-r´eteg˝ u (”monolitikus”), 2-, 3-, ... r´eteg˝ u 32
Bevezet´ es
Az OS strukt´ ur´ aja
Virtu´alis g´epek • Virtu´ alis g´ep monitor a nyers hardveren fut ´es ak´ar t¨obb virtu´alis
g´epet is szolg´altat. • A virtu´ alis g´epek k¨ ul¨onb¨ oz˝ oek is lehetnek. • Pentium processzorokba be´ ep´ıtettek egy virtu´alis 8086 m´odot. • VMWare, Microsoft Virtual PC, Virtual Box • Java Virtual Machine
33
Bevezet´ es
Az OS strukt´ ur´ aja
Kliens/Szerver • Egym´ assal ”kommunik´al´ o” processzusok rendszere • Kommunik´ aci´o: u ¨zenet ad´as/v´etel • Szerver proc: meghat´ arozott szolg´altat´asokat v´egez: termin´al-, web-,
file i/o-, szolg´altat´as-csoportok • Kliens proc: egy szerver proc szolg´ altat´asait veszi ig´enybe; k´er´es =
u ¨zenet (tartalma specifik´alja a pontos k´er´est): termin´al-kliens ; v´alasz =u ¨zenet ¨ • Uzenet = fejl´ ec (header) + tartalom (body) • Header: az u ¨zenet tov´abb´ıt´as´ahoz sz¨ uks´eges inform´aci´ok; c´ımzett
(proc), felad´o, hossz, k´ odol´as, id˝ o-b´elyegz˝ ok, ... • Tartalom: felad´ o ´all´ıtja ¨ ossze, c´ımzett ´ertelmezi; szerkezete pontosan
specifik´alt = kommunik´aci´ os protokoll OS feladata: az u ¨zenetek k¨ozvet´ıt´ese processzusok k¨ oz¨ ott; csak a fejl´eccel kell foglalkoznia 34
Bevezet´ es
Az OS strukt´ ur´ aja
Kliens/szerver modell el˝onyei • Szerver processzusokkal az OS szolg´ altat´asai b´armikor b˝ov´ıthet˝ok –
az OS elj´ar´asokra ´ep¨ ul˝ o r´esze (kernel) sz˝ ukebbre vehet˝o • Szerver programok egym´ ast´ ol teljesen f¨ uggetlen¨ ul programozhat´oak • H´ al´ozaton kereszt¨ ul is alkalmazhat´ o: szerver ´es kliens proc k¨ ul¨on OS
f¨ol¨ott fut, ezek h´al´ozaton kereszt¨ ul cser´elnek u ¨zeneteket
35
Bevezet´ es
Az OS strukt´ ur´ aja
Kliens/szerver modell osztott rendszerekben
Kliensnek nem kell tudnia, hogy a szerver lok´alisan, vagy h´al´ozaton kereszt¨ ul lesz el´erhet˝o
36
Bevezet´ es
Az OS strukt´ ur´ aja
Kliens/szerver programoz´as
• 2-, 3-r´ eteg˝ u alkalmaz´as-szerkezet: a kliens g´epen kliens proc fut, a
sz¨ uks´eges szolg´altat´asokat (h´al´ ozaton kereszt¨ ul) szerver g´ep(ek)t˝ol u ¨zenetek form´aj´aban k´eri • Kliens g´ ep feladata: k´eperny˝ o kezel´ese, felhaszn´al´o akci´oinak
megfelel˝o k´er´esek tov´abb´ıt´asa, v´alaszok fogad´asa • X-termin´ al, Adatb´azis-szerver, WEB, F´ajl-megoszt´as, . . . • ASP – Application Service Provider – T´ avoli Alkalmaz´as Kiszolg´al´o
37
Bevezet´ es
Az OS strukt´ ur´ aja
Oper´aci´os rendszerek alrendszerei • Processzuskezel˝ o alrendszer; process handling • Er˝ oforr´askezel˝o alrendszer; resource handling ( K¨ olcs¨on¨os kiz´ar´as,
¨ Szinkroniz´aci´o, Uzenetk¨ ozvet´ıt´es) • Mem´ oriakezel˝o alrendszer (spec er˝ oforr´as); memory management • Bevitel/Kivitel; Input/Output • F´ ajlkezel˝o alrendszer (spec er˝ oforr´as); file, directory and file system
management • Id˝ okezel´es; time management (spec esem´eny) • V´ edelmi (protection), biztons´agi (security) rendszer • Jelkezel˝ o alrendszer; signal handling • Esem´ enykezel˝o alrendszer; event handling • Felhaszn´ al´oi fel¨ ulet(ek); parancs´ertelmez˝ o (shell) 38
Processzusok
Bevezet´ es
Processzusok
Processzus Szekvenci´alisan v´egrehajt´ od´ o program. • Er˝ oforr´asbirtokl´o (resources) egys´eg; kiz´ar´ olagosan ´es osztottan
haszn´alt er˝oforr´asok • C´ımtartom´ annyal (address space, memory map) rendelkezik; saj´at ´es
(m´as procokkal) osztott mem´ oria (private/shared memory) • V´ egrehajt´asi ´allapota (state) van; IP (USz), Regiszterek, SP, SR, ... • Veremmem´ ori´aja (stack) van; saj´at • Jogosults´ agokkal (privileges) rendelkezik; system/appl proc,
adathozz´af´er´esi jogok
39
Processzusok
Bevezet´ es
Kontextus csere
• T¨ obb egyidej˝ uleg l´etez˝ o processzus - Egyetlen processzor (CPU): A
CPU v´altakozva hajtja v´egre a procok programjait (monoprocesszoros rendszer) • Kontextus csere (Context Switching): A CPU ´ atv´alt a P1 procr´ol a
P2 procra • P1 ´ allapot´at a CPU (hardver) regisztereib˝ ol menteni kell az erre a
c´elra fenntartott mem´ oriater¨ uletre; IP, SP, stb. • P2 kor´ abban mem´ori´aba mentett ´allapot´at helyre kell ´all´ıtani a CPU
regisztereiben • T¨ obbprocesszoros (multiprocesszoros) rendszerben is sz¨ uks´eges (n
proc, m CPU). Mindegyik CPU-n v´egre kell hajtani a cser´et.
40
Processzusok
Bevezet´ es
Processzusmodell
(a) N´egy program multiprogramoz´asa. (b) N´egy f¨ uggetlen, szekvenci´alis processzus elm´eleti modellje. (c) Minden id˝ opillanatban csak egy program akt´ıv.
41
Processzusok
Bevezet´ es
Mem´oriat´erk´ep • Programsz¨ oveg: Konstans (text) • Adat: Konstansok (text), V´ altoz´ ok • Verem (adat + vez´ erl´esi inform´aci´ ok): Lok´alis (elj´ar´ason bel¨ ul
´erv´enyes) v´altoz´ok; Last-in-First-out (LIFO) kezel´es; Push/Pop • Dinamikus v´ altoz´ok: Heap: new/delete (C++); new/dispose (Pascal)
42
Processzusok
Bevezet´ es
Processzusok ´allapotai
• Fut´ o (Running): A proc birtokolja a CPU-t. • Fut´ ask´ esz (Ready): k´eszen ´all a fut´asra, de ideiglenesen le´all´ıtott´ak,
hogy egy m´asik processzus futhasson. • Blokkolt (Blocked): er˝ oforr´asra v´arakozik, pl. egy input m˝ uvelet
eredm´eny´ere • Seg´ ed´allapotok: inici´alis (megjelen´eskor), termin´alis (befejez´eskor),
akt´ıv, felf¨ uggesztett (hosszabb id˝ ore felf¨ uggeszt´es, pl. mem´oria sz˝ uk¨oss´ege miatt).
43
Processzusok
Bevezet´ es
Processzusok ´allapot´atmenetei
1
A processzus bemeneti adatra v´arva blokkol
2
Az u ¨temez˝o m´asik processzust szemelt ki
3
Az u ¨temez˝o ezt a processzust szemelte ki
4
A bemeneti adat el´erhet˝ o
44
Processzusok
Bevezet´ es
Processzus le´ır´asa Processzust´abl´azat A proc nyilv´antart´as´ara, tulajdons´againak le´ır´as´ara szolg´al´o mem´oriater¨ ulet (Proc Table, Proc Control Block, PCB) Tartalma • Azonos´ıt´ o – procid: egy´ertelm˝ u, hivatkoz´asi sorsz´am • L´ etrehoz´o proc azonos´ıt´ oja; procok fastrukt´ ur´at alkotnak • Mem´ oriat´erk´ep; l´etrej¨ ottekor, k´es˝ obb v´altozik ´ • Allapot/Al´ allapot; id˝ oben v´altozik • Jogosults´ agok, priorit´as; l´etrehoz´ o ´all´ıtja be • Birtokolt er˝ oforr´asok; kiz´ar´ olagosan, osztottan haszn´alhat´o er˝oforr´asok; pl. a nyitott f´ajlok nyilv´antart´asa • K´ ert, de m´eg meg nem kapott er˝ oforr´asok • CPU ´ allapot kontextuscser´ehez; Usz, Verempointerek, Regiszterek, ... tartalm´anak t´arol´as´ara • Sz´ aml´az´asi, statisztikai inform´aci´ ok... 45
Processzusok
Bevezet´ es
Processzus le´ır´asa
Az egyidej˝ uleg l´etez˝o procok le´ır´asai (PCB-k) a processzus le´ır´asok l´anc´ara vannak f˝ uzve. Proc l´etrej¨ottekor a PCB a l´ancra f˝ uz˝ odik (pl. a v´eg´ere). Proc megsz˝ untekor a PCB l´ancszem t¨ orl˝ odik a l´ancr´ ol. M˝ uveletek a l´ancon • Egy proc gyermekeinek keres´ ese pl. a sz¨ ul˝ o megsz˝ un´esekor a
fastrukt´ ura meg˝orz´es´ehez • Fut´ ask´esz ´allapot´ u procok keres´ese pl. a k¨ ovetkez˝o id˝ointervallumra a
CPU kioszt´as´ahoz • Er˝ oforr´ast ig´enyelt processzusok keres´ese pl. az er˝oforr´as oda´ıt´el´esekor
46
Processzusok
Bevezet´ es
A processzus t´abla (PCB) n´eh´any tipikus mez˝oje
47
Processzusok
Bevezet´ es
Processzus l´etrehoz´as´anak l´ep´esei
1
Mem´oriater¨ ulet foglal´asa a PCB sz´am´ara
2
PCB kit¨olt´ese inici´alis adatokkal; kezdeti mem´ oriat´erk´ep, ´allapot = inici´alis, kiz´ar´olagosan haszn´alhat´ o er˝ oforr´asok lefoglal´asa, CPU ´allapot USz = ind´ıt´asi c´ım, jogosults´agok a l´etrehoz´o jogosults´agaib´ol,...
3
Programsz¨oveg, adatok, verem sz´am´ara mem´ oriafoglal´as, bet¨olt´es (ha kell; ezt ´altal´aban a l´etrehoz´ o feladat´anak tekinti az OS)
4
A PCB procok l´anc´ara f˝ uz´ese, ´allapot = fut´ask´esz. Ett˝ol kezdve a proc osztozik a CPU-n.
48
Processzusok
Bevezet´ es
Processzus l´etrehoz´asa - C (UNIX)
int fork(void); A l´etrehoz´o proc t¨ok´eletes m´asolat´at k´esz´ıti el. A fork() ut´an a k´et proc ugyanazzal a mem´oriak´eppel, k¨ ornyezeti sztringekkel, nyitott f´ajlokkal fog rendelkezni.
Mindk´et proc programja k¨ ozvetlen¨ ul a fork() ut´an folytat´odik, de el´agaz´as programozhat´o: • pid=fork() > 0, akkor a sz¨ ul˝ or˝ ol van sz´ o, pid a gyermek azonos´ıt´oja • pid=fork() == 0, akkor a gyermekr˝ ol van sz´ o • pid=fork() < 0, akkor error, sikertelen a gyermek l´ etrehoz´asa
49
Processzusok
Bevezet´ es
Processzus l´etrehoz´asa - C (UNIX)
Programv´azlat int pid if (pid if (pid if (pid
= fork (); < 0) { exit (1); } // hiba == 0) { exec(); } // gyermek sikeres > 0) {...} // sz¨ ul˝ o folytatja munk´ aj´ at
Alkalmaz´as Sz¨ ul˝ o – Gyermek egy cs¨ov¨ on (pipe) kereszt¨ ul kommunik´al; sz¨ ul˝o egy sz¨ oveget ´ır a cs˝obe, gyermek a sz¨ oveget feldolgozza (transzform´alja), pl. makro-processzork´ent
50
Processzusok
Bevezet´ es
Processzusok befejez´ese
• Szab´ alyos kil´ep´es (exit(0)) • Kil´ ep´es hiba miatt hibak´ od jelz´essel a l´etrehoz´ o fel´e (exit(hibak´od)) • Kil´ ep´es v´egzetes hiba miatt (Pl. illeg´alis utas´ıt´as, null´aval val´o oszt´as,
hivatkoz´as nem l´etez˝o mem´ oriac´ımre, stb.) • Egy m´ asik processzus megsemmis´ıti (kill() + jogosults´agok)
51
Processzusok
Bevezet´ es
Processzus megsz¨untet´ese
A megsz¨ untet´es l´ep´esei (a l´etrehoz´as ford´ıtott sorrendj´eben): 1
A gyermek procok megsz¨ untet´ese (rekurz´ıv) vagy m´as sz¨ ul˝oh¨oz csatol´asa
2
A PCB procok l´anc´ar´ ol lev´etele, ´allapot = termin´alis. Ett˝ol kezdve a proc nem osztozik a CPU-n.
3
A megsz˝ un´eskor a proc birtok´aban l´ev˝ o er˝ oforr´asok felszabad´ıt´asa (a PCB-beli nyilv´antart´as szerint, pl. nyitott f´ajlok lez´ar´asa)
4
A mem´oriat´erk´epnek megfelel˝ o mem´ oriater¨ uletek felszabad´ıt´asa
5
A PCB mem´oriater¨ ulet´enek felszabad´ıt´asa
52
Processzusok
Sz´ alak
Sz´alak / Fonalak • Sz´ al (thread, lightweight proc) = szekvenci´alisan v´egrehajt´od´o
program, proc hozza l´etre • De osztozik a l´ etrehoz´ o proc er˝ oforr´asain, c´ımtartom´any´an,
jogosults´again • Viszont van saj´ at ´allapota, verme • Kezel´ ese az OS r´esz´er˝ ol a procn´al egyszer˝ ubb, jelent˝os r´eszben a programoz´o felel˝oss´ege
53
Processzusok
Sz´ alak
Processzusok ´es sz´alak
Processzus elemei C´ımtartom´any Glob´alis v´altoz´ok Megnyitott f´ajlok Gyermekprocesszusok F¨ ugg˝oben l´ev˝o ´ebreszt˝ok Szign´alok ´es szign´alkezel˝ ok Elsz´amol´asi inform´aci´o
Sz´al elemei Utas´ıt´assz´aml´al´o Regiszterek Verem ´ Allapot
54
Processzusok
Sz´ alak
Sz´alak megval´os´ıt´asa A felhaszn´ al´ o kezeli a sz´alakat egy sz´al-csomag (f¨ uggv´enyk¨onyvt´ar) seg´ıts´eg´evel. A kernel nem tud semmit a sz´alakr´ ol. Megval´os´ıthat´o olyan oper´aci´os rendszeren is, amely nem t´amogatja a sz´alakat. A kernel tud a sz´alakr´ol ´es ˝ o kezeli azokat: sz´al-t´abl´azat a kernelben; sz´alak l´etrehoz´asa, megsz˝ untet´ese kernelh´ıv´asokkal t¨ ort´enik. Sz´al blokkol´od´asa eset´en, az OS egy m´asik fut´ask´esz sz´alat v´alaszt, de nem biztos, hogy ugyanabb´ol a processzusb´ ol.
55
Processzusok
Processzusok kommunik´ aci´ oja
Versenyhelyzetek P´elda: h´att´ernyomtat´as. Ha egy processzus nyomtatni akar, beteszi a f´ajl nev´et egy h´att´erkatal´ogusba. A nyomtat´ o d´emon ezt rendszeresen ellen˝ orzi, ´es elv´egzi a nyomtat´ast, majd t¨ orli a bejegyz´est. 1
2
A processzus kiolvassa az in k¨ oz¨ os v´altoz´ ot ´es elt´arolja lok´alisan ´ Oramegszak´ ıt´as k¨ovetkezik be, ´es B processzus kap CPU-t
3
B processzus kiolvassa in-t, beleteszi a f´ajl nev´et, n¨oveli in-t, teszi a dolg´at...
4
A ism´et futni kezd, beleteszi a kiolvasott rekeszbe a f´ajl nev´et, megn¨ oveli in-t
Versenyhelyzet (race condition) Processzusok k¨oz¨os adatokat olvasnak ´es a v´egeredm´eny att´ol f¨ ugg, hogy ki ´es pontosan mikor fut. 56
Processzusok
Processzusok kommunik´ aci´ oja
K¨olcs¨on¨os kiz´ar´as K¨ olcs¨ on¨ os kiz´ ar´ as (mutual exclusion): Ha egy processzus haszn´al egy megosztott er˝oforr´ast, akkor a t¨ obbi processzus tart´ ozkodjon ett˝ol. Kett˝ o vagy t¨obb processzus egy-egy szakasza nem lehet ´atfed˝o: p1 proc k1 szakasza ´es p2 proc k2 szakasza ´atfed˝ oen nem v´egrehajthat´o. k1 ´es k2 egym´asra n´ezve kritikus szekci´ ok. Szab´alyok: 1
Legfeljebb egy proc lehet kritikus szekci´ oj´aban
2
Kritikus szekci´on k´ıv¨ uli proc nem befoly´asolhatja m´asik proc kritikus szekci´oba l´ep´es´et
3
V´eges id˝on bel¨ ul b´armely kritikus szekci´ oba l´epni k´ıv´an´o proc bel´ephet
4
A processzusok ”sebess´ege” k¨ oz¨ omb¨ os 57
Processzusok
Processzusok kommunik´ aci´ oja
K¨olcs¨on¨os kiz´ar´as kezel´ese kritikus szekci´okkal
A k¨olcs¨on¨os kiz´ar´as megold´asa egy´ertelm˝ uen az oper´aci´os rendszer feladata. 58
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek
Entry elj´ ar´ as: a kritikus szekci´ o el˝ ott kell megh´ıvnia a programoz´onak. Ig´eny az OS fel´e, hogy a proc be akar l´epni. Az OS majd eld¨ onti, hogy mikor enged be. Exit elj´ ar´ as: kil´ep´es ut´an kell megh´ıvni. Jelz´es az OS fel´e, hogy v´eget ´ert a kritikus szekci´ o.
59
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Hardver m´odszerek Interruptok tilt´ asa
Entry: Disable (); // minden megszak´ıt´ as tilt´ asa k: ... Exit : Enable (); // megszak´ıt´ as enged´elyez´ese
A k kritikus szekci´oban a processzus u ¨temez˝ o nem jut CPU-hoz, ´ıgy p-t˝ol nem veheti el a CPU-t. k csak r¨ovid lehet, mert p nem saj´at´ıthatja ki a CPU-t hossz´ u id˝ore. Nemcsak az u ¨temez˝o, hanem pl. az esem´eny-kiszolg´al´o procok sem jutnak CPU-hoz – vesz´elyes.
60
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Hardver m´odszerek Test and Set Lock - TSL utas´ıt´ as
TSL rx, lock Beolvassa a lock mem´oriasz´ o tartalm´at rx-be, ´es nem nulla ´ert´eket ´ır erre a mem´oriac´ımre u ´gy, hogy az utas´ıt´as befejez´es´eig m´as processzor nem ´erheti el a mem´ori´at.
Entry: TSL reg, lock // reg:=lock; lock:=1 CMP reg, #0 JNE Entry k: ... Exit : MOV lock,0 // lock:=0
61
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Peterson ”udvariass´agi” m´odszere 1981
i = 1,2; j = 2,1; int Turn; int MyFlag i = 0;
// k¨ oz¨ os v´ altoz´ o // saj´ at v´ altoz´ o
Entry i : MyFlag i = 1; // pi be akar l´epni Turn = j; // pj bel´ephet, ha akar wait while(Turn == j and MyFlag j); k i : ... Exit i : MyFlag i = 0; // pi kil´epett ...
• Tfh. egy sor v´ egrehajt´asa k¨ ozben a proc a CPU-t nem vesz´ıti el. • Elv: a proc jelzi, hogy ˝ o szeretne bel´epni, de el˝ ore engedi a m´asikat • H´ atr´anya: csak 2 processzus eseten m˝ uk¨ odik, k¨ oz¨os v´altoz´ok
62
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Peterson m´odszere Megval´ os´ıt´ as C-ben
#define N 2 int turn ; int interested [N];
// number of processes // whose turn is it ? // all values initially 0 (FALSE)
void enter region ( int process ) {// process is 0 or 1 int other ; // number of the other process other = 1 − process; // the opposite of process interested [ process ] = TRUE; // show that you are interested turn = process; // set flag while (turn == process && interested[other] == TRUE) ; } void leave region ( int process ) {// process : who is leaving interested [ process ] = FALSE; // indicate departure from crit . reg . }
63
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Lamport ”sorsz´am” m´odszere 1974 i = 1,2, ...; int N = 1; int MyNo i = 0;
// sorsz´ am-t¨ omb // saj´ at sorsz´ am-v´ altoz´ o
Entry i : MyNo i = N++; //pi egyedi bel´ep´esi sorsz´ amot kap wait while(MyNo i != min j(MyNo j, MyNo j != 0)); ki : ... Exit i : MyNo i = 0; // pi kil´epett ...
• Elv: Minden proc h´ uz egy sorsz´amot. Bel´ep´eskor addig v´ar, am´ıg a
sorsz´ama a legkisebb nem lesz a ki nem szolg´altak k¨oz¨ ul. • El˝ onye: tetsz˝oleges sz´am´ u proc lehet, nem kell a t¨obbi proc v´altoz´oit
piszk´alni • Megval´ os´ıt´as rendszerh´ıv´asokkal, ´es blokkol´assal 64
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Dijkstra f´ele bin´aris szemafor int S = 1; // glob´ alis szemafor v´ altoz´ o Entry: P(S): wait while(S == 0); S = 0; k: ... Exit : V(S): S = 1; // p kilepett
• Elv: Tev´ ekeny v´arakoz´as am´ıg S ´ert´eke 0. Amint S nem nulla,
azonnal null´ara v´altoztatja ´es ut´ana l´ep be a kritikus szekci´oba. • El˝ onye: ak´arh´any processzusra m˝ uk¨ odik, egy glob´alis v´altoz´o, i-t˝ol
f¨ uggetlen. • H´ atr´anya: v´arakoz´as CPU id˝ ot ig´enyel • Megval´ os´ıt´as rendszerh´ıv´asokkal, ´es blokkol´assal
65
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Szemafor ´ anos´ıtott eset Altal´
Legfeljebb n proc lehet egyidej˝ uleg kritikus szekci´ oj´aban int S = n;
// glob´ alis szemafor v´ altoz´ o
P(S): wait while(S == 0); S = S − 1; V(S): S = S + 1; // p kil´epett
A mutex egy olyan v´altoz´ o, amely k´etf´ele ´allapotban lehet: z´arolt, vagy nem z´arolt. Bin´aris szemafor.
66
Processzusok
Processzusok kommunik´ aci´ oja
Entry-Exit m´odszerek - Szemafor Altat´ as - ´ebreszt´es (Sleep - Wakeup) implement´ aci´ o Entry: if (S == 0) { // sleep insert (MySelf) into QueueS ; block(MySelf); } else S = 0; ki : ... Exit : if (QueueS is Empty) S = 1; else { // wakeup p from QueueS p = remove(head(QueueS )); ready(p); }
• Az Entry ´ es Exit alatt a proc nem vesz´ıtheti el a CPU-t. • Elv: Ha a szemafor nulla, akkor a proc beilleszti mag´ at a v´arakoz´o
processzusok sor´aba, ´es blokkolja is mag´at. • El˝ onye: nincs akt´ıv v´arakoz´as • H´ atr´anya: a m´asik processzuson m´ ulik, hogy fel´ebred-e az alv´o. 67
Processzusok
Processzusok kommunik´ aci´ oja
Hoare monitor 1974
Monitor Elj´ar´asok, v´altoz´o ´es adatszerkezetek egy¨ uttese, egy speci´alis modulba o¨sszegy˝ ujtve, hogy haszn´alhat´ o legyen a k¨ olcs¨ on¨ os kiz´ar´as megval´os´ıt´as´ara.
• Minden id˝ opillanatban csak egyetlen processzus lehet akt´ıv a
monitorban. • A processzusok h´ıvhatj´ ak a monitor elj´ar´asait, de nem ´erhetik el a
bels˝o adatszerkezet´et. • Programoz´ asi nyelvi konstrukci´ o, azaz m´ar a ford´ıt´o tudja, hogy
speci´alisan kell kezelni. ´ mutex vagy szemafor. • Megval´ os´ıt´asa a ford´ıt´ o programt´ ol f¨ ugg. Alt. 68
Processzusok
Processzusok kommunik´ aci´ oja
Hoare monitor 1974 monitor example int i ; // condition c; // producer(x) { ... wait(c ); } consumer(x) { ... signal (c ); } end monitor;
glob´ alis minden elj´ ar´ asra ´ allapot- (felt´etel-) v´ altoz´ o ...
...
• wait(c): alv´ o (blokkolt) ´allapotba ker¨ ul a v´egrehajt´o proc. • signal(c): a c miatt alv´ o procot (procokat) fel´ebreszti. signal(c) csak
elj´ar´as utols´o utas´ıt´asa lehet, v´egrehajt´as´aval kil´ep az elj´ar´asb´ol. • Az elj´ ar´ast¨orzsek egym´asra n´ezve kritikus szekci´ ok 69
Processzusok
Processzusok kommunik´ aci´ oja
Processzusok kommunik´aci´oja
Processzusok egy¨ uttm˝ uk¨od´es´enek m´ odszerei • Adatok cser´ eje (cs˝ovezet´ek – pipe, f´ajlok, adatb´azis)
¨ • Uzenetek ad´asa – v´etele • K¨ oz¨os adatter¨ uletek (osztott mem´ oria – shared memory) • Kliens – szerver modell
70
Processzusok
Processzusok kommunik´ aci´ oja
Cs˝ovezet´ek – pipe pipeline (char ∗process1 , char ∗process2) { // pointers to program names int fd [2]; // pipe vector as two file descriptors pipe(&fd [0]); // create a pipe if ( fork () != 0) { // the parent process executes these statements close (fd [0]); // process 1 does not need to read from pipe close (STD OUT); // prepare for new standard output dup(fd [1]); // set standard output to fd [1] close (fd [1]); // this file descriptor not needed any more execl (process1 , process1 , 0); // calling process finished } else { // the child process executes these statements close (fd [1]); // process 2 does not need to write to pipe close (STD IN); // prepare for new standard input dup(fd [0]); // set standard input to fd [0] close (fd [0]); // this file descriptor not needed any more execl (process2 , process2 , 0); // calling process finished } } 71
Processzusok
Processzusok kommunik´ aci´ oja
¨ Uzenetportok Az u ¨zenetek egy l´ancra (FIFO) f˝ uzve t´arol´ odnak L´anc feje: u ¨zenetport – MsgPort typedef struct { Message ∗head; int type; char ∗name; MsgPort ∗reply port ; } MsgPort;
// // // //
els˝ ou ¨zenetre mutat´ o pointer a port/¨ uzenetek t´ıpusa u ¨zenetport neve esetleg a v´ alasz-port c´ıme
L´ancszem: u ¨zenet – Message typedef struct { Message ∗next; // a l´ ancon k¨ ovetkez˝ ou ¨zenet c´ıme int lenght ; // az u ¨zenet (teljes) hossza char message text [1]; // az u ¨zenet (t´enyleges) sz¨ ovege } Message;
72
Processzusok
Processzusok kommunik´ aci´ oja
¨ Uzenetportok
M˝ uveletek: MsgPort ∗CreatePort(char ∗name, int type = 0, MsgPort ∗reply port = 0); MsgPort ∗FindPort(char ∗name); void SendMessage(MsgPort ∗p, Message ∗m); Message ∗ ReceiveMessage(MsgPort ∗p); // blokkol, ha p u ¨res int TestPort(MsgPort ∗p);
// = 0, ha p u ¨res
73
Processzusok
Processzusok kommunik´ aci´ oja
¨ Uzenetport haszn´alata Ad´ o proc ... MsgPort ∗mp = CreatePort(”portom”); // port l´etrej¨ on Message m = ...; // u ¨zenet tartalm´ anak kit¨ olt´ese SendMessage(mp, &m); // u ¨zenet elk¨ uld´ese ...
Vev˝ o proc ... MsgPort ∗mp = FindPort(”portom”); // port megkeres´ese Message ∗m = ReceiveMessage(mp); // u ¨zenet olvas´ asa if (m) { ...; // u ¨zenet feldolgoz´ asa } ...
Mem´oriafoglal´asi probl´em´ak lehetnek! Pl. Ad´ o foglal, vev˝o felszabad´ıt, vagy objektumorient´alt oszt´alyok haszn´alat´aval. 74
Processzusok
Processzusok kommunik´ aci´ oja
Ciklikus u¨zenetbufferek
B t´arol´o n db u ¨zenet t´arol´as´ara alkalmas c0, c1, ..., cn-1 cell´ak, u ¨resek vagy foglaltak M˝ uveletek: • send(B, m): az m u ¨zenetet a cj u ¨res cell´aba helyezi, j = mink(k mod
n; ck u ¨res); blokkol, ha nincs u ¨res cella; cj foglalt lesz. • m = receive(B): a cj foglalt cell´ ab´ ol az u ¨zenetet kiadja, j = mink(k
mod n; ck foglalt); blokkol, ha nincs foglalt cella; cj u ¨res lesz. • min: FIFO ´ ertelemben a ”legkor´abban felt¨ olt¨ ott/ki¨ ur´ıtett” cella
Pl. cs˝ovezet´ek (pipe) implement´alhat´ o ciklikus u ¨zenetbufferrel
75
Processzusok
Klasszikus IPC-probl´ em´ ak
´ Etkez˝ o filoz´ofusok
76
Processzusok
Klasszikus IPC-probl´ em´ ak
´ Etkez˝ o filoz´ofusok probl´ema egy hib´as megold´asa
#define N 5
// number of philosophers
void philosopher ( int i ) { // i : philosopher number, from 0 to 4 while (TRUE) { think (); // philosopher is thinking take fork ( i ); // take left fork take fork (( i +1) % N); // take right fork ; % is modulo operator eat (); // yum−yum, spaghetti put fork ( i ); // put left fork back on the table put fork (( i +1) % N); // put right fork back on the table } }
Holtpontot eredm´enyezhet.
77
Processzusok
Klasszikus IPC-probl´ em´ ak
´ Etkez˝ o filoz´ofusok probl´ema egyik megold´asa #define N 5 // number of philosophers #define LEFT ( i +N−1)%N // number of i’s left neighbor #define RIGHT ( i +1)%N // number of i ’ s right neighbor #define THINKING 0 // philosopher is thinking #define HUNGRY 1 // philosopher is trying to get forks #define EATING 2 // philosopher is eating typedef int semaphore; // semaphores are a special kind of int int state [N]; // array to keep track of everyone’ s state semaphore mutex = 1; // mutual exclusion for critical regions semaphore s[N]; // one semaphore per philosopher void philosopher ( int i ) { while (TRUE) { think (); take forks ( i ); eat (); put forks ( i ); } }
// // // // // //
i : philosopher number, from 0 to N−1 repeat forever philosopher is thinking acquire two forks or block yum−yum, spaghetti put both forks back on table
78
Processzusok
Klasszikus IPC-probl´ em´ ak
´ Etkez˝ o filoz´ofusok probl´ema egyik megold´asa void take forks ( int i ) { down(&mutex); state [ i ] = HUNGRY; test ( i ); up(&mutex); down(&s[i ]); }
// // // // // //
i : philosopher number, from 0 to N−1 enter critical region record fact that philosopher i is hungry try to acquire 2 forks exit critical region block if forks were not acquired
void put forks ( i ) { down(&mutex); state [ i ] = THINKING; test (LEFT); test (RIGHT); up(&mutex); }
// // // // // //
i : philosopher number, from 0 to N−1 enter critical region philosopher has finished eating see if left neighbor can now eat see if right neighbor can now eat exit critical region
void test ( i ) { // i : philosopher number, from 0 to N−1 if ( state [ i ] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state [ i ] = EATING; up(&s[i ]); } } 79
Processzusok
Klasszikus IPC-probl´ em´ ak
Gy´art´o-fogyaszt´o probl´ema Korl´ atos t´ arol´ o probl´ema (bounded buffer problem)
Gy´ art´ o-fogyaszt´ o probl´ ema (producer-consumer problem): K´ep proc osztozik egy k¨oz¨os, r¨ogz´ıtett m´eret˝ u t´arol´ on. A gy´art´ o adatokat tesz bele, a m´asik, a fogyaszt´o, kiveszi azokat. A na´ıv megold´as versenyhelyzetet eredm´enyezhet. Pl. tekints¨ uk a k¨ ovetkez˝o esem´enysorozatot. 1
A fogyaszt´o meg´allap´ıtja, hogy a t´arol´ ou ¨res, de miel˝ott elmenne aludni elvesz´ıti a CPU-t.
2
Gy´art´o gy´art egy elemet, majd jelz´est k¨ uld a fogyaszt´onak, hogy ´ebredjen fel.
3
Mivel a fogyaszt´o nem alszik, az u ¨zenet hat´astalan.
4
A gy´art´o u ´jabb elemeket gy´art, majd a t´arol´ o betelt´evel elmegy aludni.
5
A fogyaszt´o visszakapja a CPU-t, ´es elmegy aludni. 80
Processzusok
Klasszikus IPC-probl´ em´ ak
Gy´art´o-fogyaszt´o probl´ema hib´as megold´asa #define N 100 // number of slots in the buffer int count = 0; // number of items in the buffer void producer(void) { int item; while (TRUE){ // repeat forever item = produce item(); // generate next item if (count == N) sleep(); // if buffer is full , go to sleep insert item (item ); // put item in buffer count = count + 1; // increment count of items in buffer if (count == 1) wakeup(consumer); // was buffer empty? } } void consumer(void) { int item; while (TRUE) { // repeat forever if (count == 0) sleep(); // if buffer is empty, got to sleep item = remove item(); // take item out of buffer count = count − 1; // decrement count of items in buffer if (count == N − 1) wakeup(producer); // was buffer full? consume item(item); // print item } } 81
Processzusok
Klasszikus IPC-probl´ em´ ak
Gy´art´o-fogyaszt´o probl´ema szemaforok haszn´alat´aval #define N 100 // number of slots in the buffer /pipe typedef int semaphore;// semaphores are a special kind of int semaphore mutex = 1; // controls access to critical region semaphore empty = N; // counts empty buffer slots semaphore full = 0; // counts full buffer slots void producer( int item) { down(&empty); // decrement empty count down(&mutex); // enter critical region enter item (item ); // put new item in buffer up(&mutex); // leave critical region up(&full ); // increment count of full slots } void consumer(int &item) { down(&full); // decrement full count down(&mutex); // enter critical region remove item(item); // take item from buffer up(&mutex); // leave critical region up(&empty); // increment count of empty slots }
82
Processzusok
Klasszikus IPC-probl´ em´ ak
Az olvas´ok ´es ´ır´ok probl´ema
Olvas´ ok ´ es ´ır´ ok probl´ ema (readers and writers problem): T¨obb proc egym´assal versengve ´ırja ´es olvassa ugyanazt az adatot. Megengedett az egyidej˝ u olvas´as, de ha egy proc ´ırni akar, akkor m´as procok se nem ´ırhatnak se nem olvashatnak. P´elda: adatb´azisok, f´ajlok, h´al´ ozat, ... stb.
Ha folyamatos az olvas´ok ut´anp´ otl´asa, az ´ır´ ok ´eheznek. Megold´as: ´erkez´esi sorrend betart´asa. K¨ ovetkezm´eny: hat´ekonys´ag cs¨ okken.
83
Processzusok
Klasszikus IPC-probl´ em´ ak
Az olvas´ok ´es ´ır´ok probl´ema szemaforok haszn´alat´aval typedef int semaphore; semaphore mutex = 1; semaphore db = 1; int rc = 0;
// // // //
use your imagination controls access to ’ rc ’ controls access to the data base # of processes reading or wanting to
void reader ( record &rec) { down(&mutex); // get exclusive access to ’ rc ’ rc = rc + 1; // one reader more now if (rc == 1) down(&db); // if this is the first reader ... up(&mutex); // release exclusive access to ’ rc ’ read data base (rec ); // access the data down(&mutex); // get exclusive access to ’ rc ’ rc = rc − 1; // one reader fewer now if (rc == 0) up(&db); // if this is the last reader ... up(&mutex); // release exclusive access to ’ rc ’ } void writer ( record rec) { down(&db); // get exclusive access write data base (rec ); // update the data up(&db); // release exclusive access } 84
Processzusok
¨ Utemez´ es
¨ Utemez´ es ¨ Utemez´ es feladata (process scheduling) Egy adott id˝opontban l´etez˝ o, fut´ask´esz ´allapot´ u procok k¨oz¨ ul egy kiv´alaszt´asa, amely a k¨ovetkez˝ o id˝ ointervallumban a CPU-t birtokolja. Mikor kell u ¨temezni? • Amikor egy processzus befejez˝ odik. • Amikor egy processzus blokkol´ odik (Pl. I/O m˝ uvelet miatt)
Mikor lehet u ¨temezni? • Amikor u ´j processzus j¨ on l´etre. • Amikor I/O megszak´ıt´ as k¨ ovetkezik be. • Amikor id˝ oz´ıt˝omegszak´ıt´as k¨ ovetkezik be.
85
Processzusok
¨ Utemez´ es
¨ Utemez´ es c´eljai • P´ artatlans´ag (fair): indokolatlanul a t¨ obbi proc k´ar´ara ne r´eszes¨ ulj¨on • • • • • • • •
proc el˝onyben CPU kihaszn´alts´ag: j´ o legyen Er˝oforr´askihaszn´alts´ag: (mem´ oria, I/O eszk¨ oz¨ ok, ...) j´o legyen ´ Atfut´ asi id˝o: (egy proc l´etrej¨ ott´et˝ ol megsz˝ unt´eig az ig´enyelt CPU id˝o ar´any´aban) min´el r¨ovidebb legyen ´ Atereszt˝ ok´epess´eg: egys´egnyi id˝ o alatt min´el t¨ obb proc teljes¨ ulj¨on V´alaszid˝o: (interakt´ıv procok) j´ o legyen Megb´ızhat´os´ag: a proc ´atfut´asi ideje ne nagyon f¨ uggj¨on az id˝ot˝ol (a t¨obbi, egyidej˝ uleg l´etez˝ o proct´ ol) El˝orejelezhet˝os´eg: pontosan el˝ ore jelezhet˝ o ´es szab´alyos u ¨temez´es. F˝oleg multim´edia rendszerekben fontos Rezsi (overhead) alacsony legyen: kiv´alaszt´ o algoritmus nem lehet t´ ul bonyolult 86
Processzusok
¨ Utemez´ es
Proc u¨temez´es param´eterei • • • •
Proc oszt´alyok: Batch, Interakt´ıv, Real-time Proc priorit´as: R¨ogz´ıtett (l´etrej¨ ott´et˝ ol), V´altoz´ o (¨ utemez˝o v´altoztatja) Proc t´ıpus: CPU-intenz´ıv (sz´amol´ os), Er˝ oforr´as-ig´enyes (pl. sok I/O) Real-time felt´etelek: Egy esem´enyt kiszolg´al´ o proc feladat´at korl´atozott id˝ointervallum alatt teljes´ıtheti • Dinamikus inform´ aci´ok (¨ utemez˝ o gy˝ ujti) Pl: Eddig haszn´alt ¨ossz-CPU id˝o, max. mem´oria, er˝ oforr´as-k´er´esek gyakoris´aga vagy Valamely szempont szerint a proc ”elhanyagolts´aga”, pl. interakt´ıv proc r´eg nem kapott CPU-t.
87
Processzusok
¨ Utemez´ es
¨ Utemez´ es k¨otegelt rendszerekben
Sorrendi u ¨temez´ es (First-Come First-Served): olyan sorrendben kapj´ak meg a procok a CPU-t amilyen sorrendben k´erik. Nem megszak´ıthat´o. Legr¨ ovidebb feladat el˝ osz¨ or (Shortest Job First): tfh. a fut´asi id˝o el˝ore ismert.
Legr¨ ovidebb marad´ ek fut´ asi idej˝ u el˝ osz¨ or (Shortest Remaining Time Next)
88
Processzusok
¨ Utemez´ es
¨ Utemez˝ o algoritmusok
Round Robin: Procok sorba (FIFO) rendezettek; mindig a sorban els˝o, fut´ask´esz kapja a CPU-t, ha elveszti, a sor v´eg´ere ker¨ ul. Oszt´alyonk´ent lehet egy-egy sor
89
Processzusok
¨ Utemez´ es
¨ Utemez˝ o algoritmusok Tiszta priorit´ asos: Mindig a legmagasabb priorit´as´ u, fut´ask´esz proc kapja a CPU-t. Priorit´asi oszt´alyokba sorolhat´ ok a procok; a priorit´asos algoritmus oszt´alyon bel¨ ul ´erv´enyes¨ ul, oszt´alyok k¨ oz¨ ott m´as szempont d¨ont.
90
Processzusok
¨ Utemez´ es
¨ Utemez˝ o algoritmusok Aging (n¨ovekv˝o priorit´asos): Priorit´asos algoritmus + ha egy fut´ask´esz proc nem v´alaszt´odik ki, n˝ o a priorit´asa Feedback (visszacsatol´asos): Priorit´asos algoritmus + ha a CPU id˝oszelet lej´arta miatt veszti el a proc a CPU-t, cs¨ okken a priorit´asa, ha er˝ oforr´as-k´er´es miatt, marad a priorit´asa. A sz´amol´ os ´es I/O ig´enyes procok kiegyenl´ıt˝odnek Sorsj´ at´ ek (Lottery): A processzusok sorsjegyet kapnak, u ¨temez´es = sorsh´ uz´as. Priorit´as szimul´alhat´ o t¨ obb sorsjeggyel. Garant´ alt: n proc eset´en mindegyiknek j´ar a
letezesiido n
CPU id˝o.
91
Processzusok
¨ Utemez´ es
¨ Utemez˝ o algoritmusok Fair share (ar´anyos): A procok oszt´alyokba sorol´ odnak; minden oszt´aly meghat´arozott ar´anyban r´eszes¨ ul az ¨ ossz-CPU id˝ ob˝ ol. Pl. 4 user mindegyike 25% CPU-t kap f¨ uggetlen¨ ul az ´altaluk futtatott procok sz´am´at´ol. Az u ¨temez˝o m´eri az egyes oszt´alyokbeli procokra ford´ıtott ¨ossz-CPU id˝ot; ha egy oszt´aly elmarad ar´any´at´ ol, abb´ ol az oszt´alyb´ ol v´alaszt (ha tud). Oszt´alyon bel¨ uli v´alaszt´as m´as szempont szerint Real-time felt´ etelek: Ha ismert minden e esem´eny maxim´alis megengedett kiszolg´al´asi ideje (temax ), az e bek¨ ovetkez´es´enek ideje (te0 ), az e kiszolg´al´o proc´anak id˝ oig´enye (te ), akkor azt a procot v´alasztja ki, amelyiknek a legkevesebb ideje maradt a hozz´a tartoz´ o esem´eny kiszolg´al´as´ara mine (te0 + temax − te ) 92
Processzusok
¨ Utemez´ es
Proc u¨temez´es elm´elete
Szelekci´ os f¨ uggv´ eny: int f(p, w, e, s); ahol p: proc priorit´asa w: proc eddig a rendszerben elt¨ olt¨ ott ¨ osszideje e: a proc ´altal eddig elhaszn´alt ¨ ossz CPU id˝ o s: a proc ´altal ig´enyelt ¨ossz CPU id˝ o f f f f
´ert´ek´et minden akt´ıv procra kisz´amolom, az ´ert´ek szerint d¨ont¨ok ∼ max(w) ∼ FIFO ∼ const ∼ RoundRobin ∼ min(s) ∼ Shortest Process First
93
Processzusok
Petri s´ ema
Petri s´ema Procok szinkroniz´aci´oj´anak grafikus ´abr´azol´as´ara haszn´alhat´o, matematikai elm´elete is van. Akci´ o: egy szekvenci´alisan v´egrehajtand´ o programr´eszlet (pl. f¨ uggv´eny). Be- ´ es kimenetek: az akci´ ok bemenetei ill. kimenetei (karika) Felt´ etelek: az akci´ok v´egrehajt´as´anak felt´etelei (nyilak) Petri-f´ele szinkroniz´aci´os s´ema Akci´ ok bemeneteiken ´es kimeneteiken ¨ osszek¨ ot¨ ott h´al´ ozata (gr´afja) Az a akci´ o v´ egrehajthat´ o: ha minden bemenet´en legal´abb 1 pont van. Az a akci´ o v´ egrehajt´ asa: minden bemenet´er˝ol 1 pont levon´ odik, minden kimenet´ehez 1 pont hozz´aad´ odik. 94
Processzusok
Petri s´ ema
Petri s´ema
Kezd˝ o´ allapot: a s´em´aban a bemeneteken ´es kimeneteken kezd˝o-pontok elhelyezve. V´ eg´ allapot: a s´em´aban nincs v´egrehajthat´ o akci´ o. V´ egrehajt´ as: az akci´ok lehets´eges v´egrehajt´asaival kapott s´ema- (´allapot-) sorozat kezd˝ob˝ol v´eg´allapotig.
95
Processzusok
Petri s´ ema
Petri s´ema P´elda: Kritikus szekci´ ok
96
Holtpontok
Er˝ oforr´ asok
Er˝oforr´asok Er˝ oforr´ as (osztottan haszn´alt er˝ oforr´as): amit ugyanabban az id˝oben csak egy processzus haszn´alhat. Egy proc k´eri az er˝ oforr´ast, haszn´alja, majd felszabad´ıtja. ... Request (...); // k´er´es ... // haszn´ alat Release (...); // felszabad´ıt´ as ...
Lehetnek: 1
Hardver/Sw er˝oforr´asok.
2
Megszak´ıthat´ o er˝oforr´as: elvehet˝ o az azt birtokl´o proct´ol hiba bek¨ovetkezte n´elk¨ ul (pl. mem´ oria). Megszak´ıthatatlan er˝oforr´as: elv´etele a tulajdonos´at´ ol hib´at eredm´enyez (pl. CD-´ır´o)
97
Holtpontok
Er˝ oforr´ asok
Er˝oforr´as oszt´alyok
Er˝ oforr´as-oszt´aly (eo) Hasonl´o tulajdons´ag´ u, hasonl´ oan kezelend˝ o er˝ oforr´asok egy¨ uttese
K´ eszlet: eo elemei, az elemek le´ır´asai. V´ arakoz´ o sor: blokkolt ´allapot´ u procok sora; er˝oforr´ast k´ertek, de m´eg nem kapt´ak meg. Allok´ ator: eo-beli er˝oforr´as k´er´est/felszabad´ıt´ast teljes´ıt˝ o OS elj´ar´asok
98
Holtpontok
Er˝ oforr´ asok
Er˝oforr´as oszt´alyok le´ır´asa
• Azonos´ıt´ o: res id • L´ etrehoz´o proc: proc id • K´ eszlet list´aja (l´anc): 1) Jellemz˝ ok le´ır´asa, pl. mem kezd˝oc´ım, hossz;
´ k´eszlet-elem 2) Szabad/foglalt, mely proc foglalja; 3) Uj bel´eptet˝o/t¨orl˝o elj´ar´as • V´ arakoz´o lista: Proc id, Er˝ oforr´as-k´er´es param´eterei (pl. k´ert mem
hossza), Bel´ep´esi id˝opont, ... • Allok´ ator elj´ar´asok: Request, Release elj´ar´as-c´ımek
99
Holtpontok
Er˝ oforr´ asok
Er˝oforr´as k´er´es/felszabad´ıt´as Request(res id, e-specifik´ aci´ o,&e-id); 1
A k´er˝o proc blokkolt ´allapotba hoz´asa
2
A k´er˝o proc v´arakoz´o list´aba helyez´ese
3
A v´arakoz´o lista v´egign´ez´ese; ha egy proc (kor´abbi) k´er´ese teljes´ıthet˝o, akkor: 1) e-id kit¨ olt´ese 2) e-id k´eszletbeli er˝oforr´as foglalts´ag´anak bejegyz´ese 3) proc fut´ask´esz ´allapotba hoz´asa 4) proc t¨orl´ese a v´arakoz´o sorb´ ol
4
Vez´erl´es ´atad´asa a proc u ¨temez˝ onek
Release(res id, e-id); 1
e-id k´eszletbeli er˝oforr´as szabads´ag´anak bejegyz´ese
2
ugyanaz mint Request 3.
3
visszat´er´es (return) a h´ıv´ o proc-hoz 100
Holtpontok
A holtpont alapelvei
Holtpont Holtpont (Deadlock) Procok egy halmaza egym´as birtok´aban l´ev˝ o er˝ oforr´asokra v´arakozik – o¨r¨ okre. P´eld´ak: • v1, v2 glob´ alis v´altoz´ ok. p1 ´ır v1-be, k¨ ozben olvasni akar v2-b˝ol, p2 ´ır v2-be, k¨ozben olvasni akar v1-b˝ ol. Holtpont kialakulhat akkor is ha alkalmazzuk a k¨olcs¨on¨ os kiz´ar´as m´ odszereit v1-re ´es v2-re k¨ ul¨on-k¨ ul¨on. Megold´as: v1-et ´es v2-t ¨ osszefogjuk egy rekordba, ´es azt v´edj¨ uk. • K´ et proc: mindkett˝o szkennel ´es CD-re ´ır. Az egyik a szkennert, a m´asik a CD-´ır´ot foglalja le hamarabb, majd megpr´ob´alja a m´asikat is. • Egy adatb´ azisrendszerben: ha A proc z´arolja R1 rekordot, B proc R2-t, majd mindkett˝ o megpr´ ob´alja z´arolni a m´asik´et. • 4 aut´ o egyenrang´ u utak keresztez˝ od´es´eben 101
Holtpontok
A holtpont alapelvei
Holtpont kialakul´as´anak felt´etelei
Az al´abbi felt´etelek mindegyik´enek teljes¨ ulnie kell egy holtpontban. 1
K¨ olcs¨ on¨ os kiz´ ar´ as (Mutual Exclusion) felt´etel: Egy er˝oforr´ast egy pillanatban csak max egy proc haszn´alhat.
2
Birtokl´ as ´ es v´ arakoz´ as (Hold and Wait) felt´etel: er˝oforr´ast birtokl´o proc k´erhet u ´jabb er˝oforr´ast.
3
Megszak´ıthatatlans´ ag (No preemption) felt´etel: Csak a birtokl´o proc szabad´ıthatja fel a birtok´aban l´ev˝ o er˝ oforr´asokat.
4
Ciklikus v´ arakoz´ as (Circular wait) felt´etel: T¨ obb procb´ol ´all´o l´anc, amelynek mindegyik proca a l´ancban k¨ ovetkez˝ o proc ´altal birtokolt er˝oforr´asra v´ar.
102
Holtpontok
A holtpont alapelvei
Az er˝oforr´as-lefoglal´as gr´af Resource allocation graph
• A gr´ af cs´ ucsai: processzusok (k¨ or) ´es er˝ oforr´asok (n´egyzet) • Er˝ oforr´asb´ol processzusba mutat´ o ´el: a proc birtokolja az er˝oforr´ast. • Processzusb´ ol er˝oforr´asba mutat´ o ´el: a proc v´arakozik az er˝oforr´asra,
´allapota blokkolt. • Egy gr´ afbeli k¨or azt jelenti holtpont van.
103
Holtpontok
A holtpont alapelvei
P´elda holtpont el˝ofordul´as´ara
104
Holtpontok
A holtpont alapelvei
P´elda holtpont elker¨ul´es´ere
105
Holtpontok
A holtpont alapelvei
Holtpont kezel´ese
Lehets´eges strat´egi´ak: • Felt´ etelezz¨ uk, hogy nem alakul ki (strucc politika - Ostrich
algoritmus). A rendszergazda feladata a ”gyan´ usan ¨oreg” procok megsz¨ untet´ese (Unix) • Felismer´ es ´es helyre´all´ıt´as (detection and recovery). • Elker¨ ul´es (avoidance). • Megel˝ oz´es (prevention). Megakad´alyozzuk a l´etrej¨ott´et azzal, hogy
korl´atozzuk a procok er˝ oforr´ashoz jut´as´at – er˝ oforr´as-kihaszn´alts´ag romlik
106
Holtpontok
Felismer´ es ´ es helyre´ all´ıt´ as
Felismer´es ´es helyre´all´ıt´as Felismer´ es • T´ıpusonk´ ent egy er˝oforr´as: k¨ or detekt´al´asa az er˝ oforr´as-lefoglal´asi
gr´afban • T´ıpusonk´ ent t¨obb er˝oforr´as
Helyre´ all´ıt´ as • Az er˝ oforr´as ideiglenes elv´etel´evel. • Rollbackel. A proc ´ allapot´ar´ ol ment´esek k´esz¨ ulnek, bmelyikhez vissza
lehet t´erni. • Valamely proc megsz¨ untet´es´evel.
107
Holtpontok
A holtpont elker¨ ul´ ese
A holtpont elker¨ul´ese
A procok az er˝oforr´asokat nem egyszerre, hanem k¨ ul¨ on-k¨ ul¨on k´erik. Minden k´er´es eset´en d¨onteni kell, hogy az er˝ oforr´as oda´ıt´elhet˝o-e vagy sem. A holtpont elker¨ ulhet˝ o, ha mind´ıg a helyes d¨ ont´est hozzuk.
M´ odszerek: • Er˝ oforr´as-p´alyag¨orb´ek • Bank´ ar algoritmus
108
Holtpontok
A holtpont elker¨ ul´ ese
Er˝oforr´as-p´alyag¨orb´ek K´etprocesszus´ u er˝ oforr´ as-p´ alyag¨ orb´ek
109
Holtpontok
A holtpont elker¨ ul´ ese
A bank´ar algoritmus A bank´ ar algoritmus egyetlen er˝ oforr´ asra
110
Holtpontok
A holtpont elker¨ ul´ ese
A bank´ar algoritmus A bank´ ar algoritmus t¨ obbp´eld´ anyos er˝ oforr´ ast´ıpusok eset´en
111
Holtpontok
Holtpont megel˝ oz´ ese
Holtpont megel˝oz´ese A k¨ olcs¨on¨os kiz´ar´as megakad´alyoz´asa • Pr´ ob´aljuk minimaliz´alni az er˝ oforr´ashoz hozz´af´er˝ o procok sz´am´at (pl.
printer daemon) • Csak akkor ´ıt´ elj¨ uk oda az er˝ oforr´ast, amikor sz¨ uks´eges (pl. spool-f´ajl
lez´ar´asakor es nem a megnyit´asakor) Hold and Wait megakad´alyoz´asa • Szab´ aly: proc nem k´erhet er˝ oforr´ast, ha birtokol er˝oforr´ast. • Enyh´ıt´ es: egyszerre k´erhet t¨ obb er˝ oforr´ast. • K¨ ovetkezm´eny: ´eheztet´es, rossz er˝ oforr´as kihaszn´alts´ag. • M´ odos´ıt´as: megk¨ovetelj¨ uk, hogy k´er´es el˝ ott engedje el a birtokolt
er˝oforr´asokat, ´es egyszerre k´erje vissza ˝ oket 112
Holtpontok
Holtpont megel˝ oz´ ese
Holtpont megel˝oz´ese Megszak´ıthatatlans´ag megakad´alyoz´asa: • Er˝ oforr´asok er˝oszakos elv´etele • Virtualiz´ aci´o • H´ atr´any: nem mindig lehets´eges
Cirkularit´as megakad´alyoz´asa: er˝ oforr´asok sorba-rendez´ese • < e0 , e1 , ..., eN−1 > az eo k´ eszlet. • Szab´ aly: ha pi az ej er˝ oforr´ast k´eri, nem birtokolhat ek -t, ha k > j. • Szab´ aly: ha pi az ej er˝ oforr´asr´ ol lemond, nem birtokolhat ek -t, ha
k >j
113
Holtpontok
Tov´ abbi probl´ emak¨ or¨ ok
Tov´abbi probl´emak¨or¨ok K´ et-f´ azis´ u z´ arol´ as (Two-Phase Locking): 1. f´azis: a rekordok z´arol´asa egyenk´ent. Ha valamelyik sikertelen, felszabad´ıtja a kor´abbiakat, ´es u ´jra kezdi. Ha minden z´arol´as sikeres, akkor a 2. f´azisban elv´egzi a m˝ uveletet ´es felszabad´ıt. H´atr´any: nem mindig alkalmazhat´ o: pl. h´al´ ozatok eset´eben nem m˝ uk¨odik Kommunik´ aci´ os holtpont: A ´es B procok h´al´ ozaton kommunik´alnak k´er´es-v´alasz form´aj´aban. Ha egy u ¨zenet elv´esz, akkor holtpont alakul ki. Megold´as: timeout + protokollok. ´ Eheztet´ es (Starvation): Ha egy proc soha nem kapja meg a k´ert er˝ oforr´as´at, mert a kioszt´askor m´asok r´eszes¨ ulnek el˝ onyben. Megold´as: FIFO sor haszn´alata
114
Mem´ oriakezel´ es
Mem´oriakezel´es
Proc mem´ori´aja: Sz¨ oveg (v´altozatlan): program + konstansok; Adat (v´altoz´o): statikus + verem + heap Feladatok: • Szabad/foglalt ter¨ uletek nyilv´antart´asa • Mem´ oria-ig´enyek kiel´eg´ıt´ese (dinamikus mem´ oria) • Csere (swap): mem´ oria – h´att´ert´ar k¨ oz¨ otti csere • Mem´ oria-v´edelem
115
Mem´ oriakezel´ es
T¨obbszint˝u mem´oria
116
Mem´ oriakezel´ es
Mem´oriakezel´es Feladatok proc l´etrehoz´asakor: • Indul´ o/max mem´oria biztos´ıt´asa • Statikus/dinamikus part´ıci´ ok • Reallok´ aci´o: bet¨olt´esi c´ımnek megfelel˝ oen ´atc´ımz´es • B´ azis-relat´ıv c´ımz´es
Feladatok menet k¨ozben: • Logikai → fizikai c´ım transzform´ aci´ o • Dinamikus mem´ oriak´er´esek/felszabad´ıt´asok • Csere • V´ edelem (b´azis hat´arc´ım)
117
Mem´ oriakezel´ es
Alapvet˝ o mem´ oriakezel´ es
Monoprogramoz´as csere ´es lapoz´as n´elk¨ul Egy id˝oben csak egy program fut. A mem´ oria megoszlik az OS ´es a program k¨oz¨ott.
(a) nagysz´am´ıt´og´epeken volt jellemz˝ o, ma m´ar ritka (b) k´ezi sz´am´ıt´og´epek, be´agyazott rendszerek (c) korai szem´elyi sz´am´ıt´og´epek (pl. MS-DOS) 118
Mem´ oriakezel´ es
Alapvet˝ o mem´ oriakezel´ es
Multiprogramoz´as r¨ogz´ıtett m´eret˝u part´ıci´okkal Az u ´j proc abba a v´arakoz´asi sorba ker¨ ul, amelyik a legkisebb azok k¨oz¨ol, amelyikbe belef´er.
H´atr´any: sok kicsi, de kev´es nagy proc eset´en kihaszn´alatlan mem´oria. Jav´ıt´as: egy v´arakoz´asi sor. 119
Mem´ oriakezel´ es
Alapvet˝ o mem´ oriakezel´ es
Mem´oriakezel´es
Gyakran nincs elegend˝o hely a mem´ ori´aban az ¨ osszes proc sz´am´ara, ez´ert n´emelyiket a lemezen kell tartani. • Csere (swapping): a procokat teljes eg´ esz´eben mozgatja a mem´oria
´es a lemez k¨oz¨ott. • Virtu´ alis mem´ oria: procok akkor is futhatnak, ha csak r´eszeik
vannak a mem´ori´aban.
120
Mem´ oriakezel´ es
Csere
Csere V´altoz´o part´ıci´oj´ u rendszerekben a part´ıci´ ok sz´ama, helye ´es m´erete dinamikusan v´altozik.
Mem´ oriat¨ om¨ or´ıt´ es (memory compaction): elapr´ oz´ odott lyukak osszeolvaszt´asa. CPU-ig´enyes m˝ ¨ uvelet. 121
Mem´ oriakezel´ es
Csere
Csere A processzusok m´erete fut´as k¨ ozben v´altozhat:
122
Mem´ oriakezel´ es
Csere
Mem´oriakezel´es bitt´erk´eppel A mem´ori´at allok´ aci´ os egys´ egekre osztjuk. Mindegyikhez tartozik egy bit a bitt´erk´epen: 0 = szabad, 1 = foglalt. Fontos az allok´aci´os egys´eg m´erete. Ha kicsi, akkor a bitt´erk´ep nagy. Ha nagy, akkor sok mem´oria veszhet el a procok utols´ o egys´eg´eb˝ol.
123
Mem´ oriakezel´ es
Csere
Mem´oriakezel´es l´ancolt list´akkal A szabad ´es a foglalt elemeket l´ancolt list´aban t´aroljuk.
Processzus megsz˝ un´ese eset´en a list´at is karban kell tartani:
124
Mem´ oriakezel´ es
Csere
Mem´oriakezel´es l´ancolt list´akkal
Algoritmusok a mem´oria lefoglal´as´ara u ´j procok sz´am´ara: • First fit: els˝ o megfelel˝ o m´eret˝ u v´alaszt´asa. Gyors, de apr´oz. • Next fit: az utols´ o tal´alatt´ ol ind´ıtja a keres´est. Rosszabb mint a first
fit. • Best fit: a legkisebb alkalmas lyukat keresi meg a teljes list´ aban.
Lass´ u, apr´oz. • Worst fit: a legnagyobb lyukat v´ alasztja. Nem olyan j´o, mint a t¨obbi.
Jav´ıt´asi lehet˝os´egek: K¨ ul¨on lista a lyukaknak, m´eret szerinti rendez´es. K¨ ul¨ on lista a leggyakrabban k´ert m´ereteknek: quick fit.
125
Mem´ oriakezel´ es
Virtu´ alis mem´ oria
Virtu´alis mem´oria A program, az adat ´es a verem egy¨ uttes m´erete meghaladhatja a fizikai mem´oria mennyis´eg´et. Az OS csak a program ´eppen haszn´alt r´eszeit tartja a mem´ori´aban. A virtu´ alis c´ımek nem ker¨ ulnek k¨ ozvetlen¨ ul a mem´ orias´ınre, hanem a mem´ oriakezel˝ o egys´ egbe (Memory Management Unit - MMU) ker¨ ulnek, amely elv´egzi a lek´epez´est a fizikai c´ımekre.
126
Mem´ oriakezel´ es
Virtu´ alis mem´ oria
Lapt´abla
A virtu´alis c´ımt´er egys´egei a lapok (virtual page), ezeknek megfelel˝o egys´eg a fizikai mem´ori´aban a lapkeret (page frame).
127
Mem´ oriakezel´ es
Virtu´ alis mem´ oria
Az MMU m˝uk¨od´ese 16 darab 4 KB-os lap eset´en:
128
Mem´ oriakezel´ es
Virtu´ alis mem´ oria
T¨obbszint˝u lapt´abl´ak
32 bites c´ım k´et lapt´ablamez˝ovel,
Egy k´etszint˝ u lapt´abla:
129
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
Lapcser´el´esi algoritmusok Laphiba (page fault): a lap nincs a mem´ ori´aban, teh´at be kell t¨olteni. Teend˝ok lapcsere eset´en: 1
Ki kell v´alasztani egy lapot, amelyik hely´ere az u ´jat fogjuk bet¨olteni.
2 3
Kiv´alasztott lap tartalm´anak ment´ese (ha sz¨ uks´eges) ´ laptartalom bet¨olt´ese Uj
4
Lapt´abla c´ım kit¨olt´ese
5
A laphib´at okoz´o utas´ıt´as u ´jrakezd´ese
Feladat: a felszabad´ıtand´o lap kiv´alaszt´asa. Sorozatos rossz v´alaszt´as eset´en: ´alland´ o lapcsere (verg˝od´es).
130
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
Az optim´alis lapcser´el´esi algoritmus
Minden lapot megjel¨olhet¨ unk azzal a sz´ammal, hogy h´any utas´ıt´as m´ ulva hivatkozunk r´a legk¨ozelebb. V´alasszuk a legnagyobb sz´ammal jel¨ olt lapot!
Probl´ema: nem lehet megval´ os´ıtani.
131
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
Az NRU lapcser´el´esi algoritmus Minden laphoz 2 ´allapotbit tartozik: az M minden ´ır´askor, az R minden hivatkoz´askor 1-re ´all´ıt´odik. Az R bitet id˝ onk´ent null´azzuk (pl. oramegszak´ıt´as). 4 oszt´aly lehets´eges: ´ 1
nem ´ırt, nem olvasott
2
´ırt, nem olvasott
3
nem ´ırt, olvasott
4
´ırt, olvasott
Az NRU (Not Recently Used) algoritmus v´eletlenszer˝ uen v´alaszt egy lapot a fenti sorrend szerint a nem u ¨res oszt´alyok k¨ oz¨ ul. Tulajdons´agai: egyszer˝ u, k¨ ozepesen hat´ekony implement´alhat´os´ag, j´o teljes´ıtm´eny. 132
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
A FIFO lapcser´el´esi algoritmus
Az OS egy FIFO (First-In, First-Out) list´aban t´arolja a mem´ori´aban l´ev˝o lapokat. Lista elej´en van a legr´egebbi lap. Laphiba eset´en: az els˝o lapot kidobja, az u ´j lapot a lista v´eg´ere f˝ uzi. H´atr´any: gyakran haszn´alt lapok ugyan´ ugy kiker¨ ulnek, mint a ritk´an haszn´altak.
133
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
A m´asodik lehet˝os´eg lapcser´el´esi algoritmus
M´ asodik lehet˝ os´ eg (second chance): A FIFO egyszer˝ u m´odos´ıt´asa, ha a sor elej´en lev˝o lap R bitje 1, akkor kinull´azzuk ´es visszarakjuk a sor v´eg´ere.
134
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
Az ´ora lapcser´el´esi algoritmus Az ´ ora lapcser´el´esi algoritmus l´enyeg´eben csak implement´aci´oban k¨ ul¨ onb¨ozik a m´asodik lehet˝ os´eg algoritmust´ ol.
135
Mem´ oriakezel´ es
Lapcser´ el´ esi algoritmusok
Az LRU lapcser´el´esi algoritmus LRU (Least Recently Used): Laphiba eset´en a legr´egebben nem haszn´alt lapot dobjuk ki. Megval´ os´ıt´asi lehet˝ os´egek: • FIFO sor. Minden hivatkoz´ askor a lapot ´attessz¨ uk a sor v´eg´ere. • Spec harvder: 1 k¨ oz¨os sz´aml´al´ o, amit minden hivatkoz´askor n¨ovel¨ unk, majd let´aroljuk a hivatkozott laphoz. Laphiba eset´en a legkisebb sz´aml´al´oval rendelkez˝ o lapot kell eldobni. • n lapkeret eset´ en egy n × n bitm´atrixot kezel¨ unk. k lapkeretre hivatkoz´as eset´en a k-adik sort 1-esre, a k-adik oszlopot 0-ra ´all´ıtjuk. LRU lap: a legkisebb bin´aris ´ert´ek˝ u sor. P´elda: 0, 1, 2, 3, 2, ...
136
Mem´ oriakezel´ es
Szegment´ al´ as
Szegment´al´as Szegmensek: egym´ast´ol f¨ uggetlen c´ımterek. 2D mem´oria. • 0-t´ ol valamilyen max.-ig c´ımezhet˝ o. • K¨ ul¨onb¨oz˝o szegmensek elt´er˝ o hossz´ uak, m´eret¨ uk v´altozhat. • A c´ımek 2 r´ eszb˝ol ´allnak: szegmens sz´ama, szegmensen bel¨ uli c´ım.
137
Mem´ oriakezel´ es
Szegment´ al´ as
Szegment´al´as tulajdons´agai
El˝ ony¨ok: • V´ altoz´o m´eret˝ u adatszerkezetek k¨ onnyen kezelhet˝oek. • Programok linkel´ ese egyszer˝ u, ha minden elj´ar´as k¨ ul¨on szegmensbe
ker¨ ul: u ´jraford´ıt´as eset´en csak a megv´altozott szegmenseket kell kicser´elni. • F¨ uggv´eny-k¨onyvt´arak k¨ onnyen megoszthat´ ok proc-ok k¨oz¨ott (pl.
grafikus k¨onyvt´arak csak egyszer vannak a mem´ ori´aban). • K¨ ul¨onb¨oz˝o v´edelmi szintek alak´ıthat´ oak ki.
H´atr´any: a programoz´onak tudnia kell, hogy ezt a technik´at haszn´alja.
138
Be- ´ es kivitel
Az I/O-hardver alapelvei
I/O eszk¨oz¨ok
Blokkos eszk¨ oz: az inform´aci´ ot adott m´eret˝ u blokkokban t´arolja ´es a blokkok egym´ast´ol f¨ uggetlen¨ ul ´ırhat´ ok ´es olvashat´ ok (seek m˝ uvelet). Szok´asos blokkm´eret: 512 b´ajt ´es 32768 b´ajt k¨ oz¨ ott. Pl: lemez. Karakteres eszk¨ oz: struktur´alatlan karakterfolyam, nem c´ımezhet˝o ´es nincsen seek sem. Pl: nyomtat´ o, h´al´ ozati interf´esz, eg´er.
139
Be- ´ es kivitel
Az I/O-hardver alapelvei
Eszk¨ozvez´erl˝ok
140
Be- ´ es kivitel
Az I/O-hardver alapelvei
Mem´orialek´epez´es˝u I/O Kommunik´aci´o az eszk¨ozvez´erl˝ ovel: regisztereken kereszt¨ ul. (a) I/O kapun kereszt¨ ul: IN reg, port utas´ıt´as a regiszterbe olvas, OUT port, reg a portba ´ır. (b) Mem´ orialek´ epez´ es˝ u I/O: a vez´erl˝ oregiszterek a mem´oria adott hely´en tal´alhat´oak, m´asra nem haszn´alhat´ oak (c) Hibrid megold´as. Pl. a Pentium: 640K-1M adatpufferek + I/O kapuk.
141
Be- ´ es kivitel
Az I/O-hardver alapelvei
Megszak´ıt´asok
A vez´erl˝o egy megszak´ıt´ason (IRQ - Interrupt ReQuest) kereszt¨ ul jelzi egy esem´eny bek¨ovetkezt´et (”m˝ uvelet elv´egezve” vagy ”adat k´eszen ´all”) Pentiumos PC-n max 15 input lehets´eges, n´eh´any el˝ ore behuzalozott (pl. billenty˝ uzet) Plug’n Play: a BIOS ind´ıt´asi id˝ oben rendeli hozz´a az IRQ megszak´ıt´ask´er´est az eszk¨ oz¨ okh¨ oz.
142
Be- ´ es kivitel
Az I/O-hardver alapelvei
K¨ozvetlen mem´oriael´er´es (DMA) CPU feladata: adat´atvitel kezdem´enyez´ese. Param´eterek: Adat´atvitel ´ ir´anya (Be/Ki), Adatok mem´ oriabeli kezd˝ oc´ıme, Atviteli adatmennyis´eg (b´ajtsz´am). Eszk¨ ozvez´ erl˝ o feladata: CPU-t´ ol f¨ uggetlen¨ ul az adat´atvitel megval´os´ıt´asa. Az adat´atvitel sor´an/v´eg´en az ´atviteli ´allapot lek´erdezhet˝o, Hiba/Befejez´es eset´en megszak´ıt´as, ´allapotinform´aci´ ok k¨ozl´ese a kezdem´enyez˝o proccal.
143
Be- ´ es kivitel
Az I/O-hardver alapelvei
I/O v´egrehajt´asi szintjei C´ elok: Egys´eges (felhaszn´al´ oi) programoz´asi fel¨ ulet, Eszk¨oz¨okre val´o hivatkoz´as egys´eges´ıt´ese, Blokkm´erett˝ ol, fizikai fel´ep´ıt´est˝ol, pufferez´est˝ol val´ o f¨ uggetlens´eg, Egys´eges hibakezel´es, Osztott haszn´alat adminisztr´aci´oj´at´ol val´o f¨ uggetlens´eg.
144
Be- ´ es kivitel
Lemezek
Lemezes egys´egek C´ımz´es: • CHS (Cylinder, Head, Sector), Sug´ ar, fej
´es sz¨og megad´as´aval. Pl. IDE. • LBA (Logical Block Address), minden
szektornak k¨ ul¨on azonos´ıt´ o. Pl. SCSI, EIDE. ´ Atviteli id˝ok:
Cilinder, P´alya, Szektor
• Keres´ esi (seek): cilinderek k¨ oz¨ otti ugr´as • Fordul´ asi (rotation): szektorok k¨ oz¨ otti fordul´as
´ • Atviteli (transfer): adat´ır´asi/olvas´asi id˝ o Adat´atvitel optimaliz´al´asa • Fordul´ asi, ´atviteli id˝ ok adottak • Keres´ esi id˝o befoly´asolhat´ o az ´atviteli k´er´esek kiszolg´al´asi
sorrendj´enek meghat´aroz´as´aval 145
Be- ´ es kivitel
Lemezek
Lemezfej-¨utemez˝o algoritmusok Els˝ o k´ er´ es - els˝ o kiszolg´ al´ as (First-Come, First-Served) Legk¨ ozelebbit keres els˝ ok´ ent (Shortest Seek First)
146
Be- ´ es kivitel
Lemezek
Lemezfej-¨utemez˝o algoritmusok Liftes algoritmus (elevator algorithm)
P´ aly´ ank´ enti pufferol´ as (Track-at-a-Time Caching)
147
Be- ´ es kivitel
Lemezek
Lemezek kezel´ese Szabad/Foglalt szektorok nyilv´antart´asa: Bitt´erk´ep vagy L´ancol´as Hibakezel´es: • Adathiba: Hibajelz˝ o/Hibajav´ıt´ o k´ odol´as • Keres´ esi hiba: szektorbejegyz´esek (henger/p´alya/szektor) • Kop´ as-k´ım´el´es: motor ki/be • Cser´ elhet˝o adathordoz´ o: csere figyel´ese, ´ır´as befejezetts´ege
F´ajlrendszerek - form´az´as
148
Be- ´ es kivitel
´ ak Or´
´ (timer) Ora A hardver
Hw: oszcill´ator sz´aml´al´oval, ´ orajellel (tick)
149
Be- ´ es kivitel
´ ak Or´
Pontos id˝o sz´am´ıt´asa A szoftver
Probl´ema: 60Hz-es ´orajellel ´es 32 bites t´arol´ oval kb. 2 ´evig m´erhetj¨ uk az id˝ ot. Lehet˝os´egek: (a) 64 bites t´arol´o (b) m´asodperceket m´er¨ unk (c) rendszerind´ıt´ast´ol sz´amoljuk az ´ orajeleket
150
Be- ´ es kivitel
Termin´ alok
Termin´alhardver Termin´alok csoportjai: 1
T´arc´ımlek´epez´eses csatol´ o
2
RS-232-es interface
3
h´al´ozati csatol´o
151
F´ ajlrendszerek
F´ajlrendszerek C´ el: Nagym´eret˝ u adathalmazok t´arol´asa, Processzusokat ”t´ ul´el˝o” adatok, T¨ obb proc ”egyidej˝ u” hozz´af´erhet˝ os´ege az adatokhoz Szerkezet szerint: (a) B´ajtsorozat: Aktu´alis poz´ıci´ o, b´ajtonk´ent/soronk´ent ´ır´as/olvas´as (b) Rekordsorozat: Mez˝ok (field), kulcsmez˝ o, rekordonk´enti ´ır´as/olvas´as (c) Fa-strukt´ ura
152
F´ ajlrendszerek
F´ajlt´ıpusok
K¨ oz¨ ons´ eges f´ ajlok: ASCII vagy bin´aris K¨ onyvt´ arak: rendszerf´ajlok a f´ajlrendszer szerkezet´enek megval´os´ıt´as´ahoz. Karakterspecifikus f´ ajlok: a soros I/O eszk¨ oz¨ ok modellez´es´ere (Pl. termin´al, nyomtat´o, h´al´ozat) Blokkspecifikus f´ ajlok: m´agneslemezegys´egek
153
F´ ajlrendszerek
F´ajlt´ıpusok
154
F´ ajlrendszerek
F´ajlel´er´es
Szekvenci´ alis el´ er´ es (sequential access): A processzusok megadott sorrendben olvass´ak a file-okat, a sorrendt˝ ol elt´erni nem lehet. Kezd´es az els˝ o b´ajtn´al/rekordn´al. Pl. M´agnesszalagok.
K¨ ozvetlen el´ er´ es (random access): A b´ajtok/rekordok tetsz˝oleges sorrendben olvashat´oak. read ´es seek m˝ uveletek.
155
F´ ajlrendszerek
´ Allom´ anyok
F´ajlattrib´utumok Minden f´ajlnak van neve ´es adattartalma. Ezen fel¨ ul attrib´ utumok vagy metaadatok lehetnek: • L´ etrehoz´o, tulajdonos • Tulajdonos/Csoport/B´ arki jogok • ´Ir´ asi/olvas´asi/l´athat´os´agi/v´egrehajthat´asi jog • L´ etes´ıt´esi/Hozz´afordul´asi/M´ odos´ıt´asi id˝ opontok • Bin´ aris/Sz¨oveg/Program jelz´es • M´ eret/Rekordsz´am/Rekordm´eret • Rendszer/Rejtett/Arch´ıv jelz˝ ok • Z´ arolt (lock)
156
F´ ajlrendszerek
´ Allom´ anyok
F´ajlm˝uveletek L´etes´ıt´es: File l´etrej¨ott´enek bejegyz´ese, attrib´ utumok be´all´ıt´asa T¨ orl´es: Lemezter¨ ulet felszabad´ıt´asa Megnyit´as: Attrib´ utumok beolvas´asa, n´eh´any lemezc´ım bet¨olt´ese Lez´ar´as: Bels˝o mem´oria ter¨ ulet felszabad´ıt´asa, utols´ o blokk ki´ır´asa Olvas´as: Adatok bet¨olt´ese a mem-ba akt. poz-t´ ol. ´Ir´as: Aktu´alis poz´ıci´ot´ol az adatok fel¨ ul´ır´asa. Hozz´atold´as: Csak a file v´eg´ehez lehet Pozicion´al´as: Aktu´alis poz´ıci´ o be´all´ıt´asa Attrib´ utum lek´erdez´es: Feladatok elv´egz´es´ehez sz¨ uks´eges inform´aci´ok Attrib´ utum be´all´ıt´as: Pl. v´edelmi m´ od ´ Atnevez´es: N´ev megv´altoztat´asa vagy m´asol´as ´es t¨ orl´es Z´arol´as: Egyszerre csak egy proc. f´erhet a f´aljhoz vagy annak egy r´esz´ehez 157
F´ ajlrendszerek
´ Allom´ anyok
F´ajlm˝uveletek FILE∗ fopen (char∗ filename , char∗ mode ); // l´etrehoz´ as, megnyit´ as int fclose ( FILE∗ stream ); // lez´ ar´ as int fflush ( FILE ∗ stream ); // buffer f´ ajlba ´ır´ asa size t fread ( void∗ ptr , size t size , size t count, FILE ∗ stream ); size t fwrite ( void∗ ptr , size t size , size t count, FILE ∗ stream ); int int int int char∗ int
fprintf ( FILE∗ stream, char∗ format, ... ); // form´ azott ´ır´ as fputs ( char∗ str , FILE∗ stream ); // sztring ´ır´ as fputc ( int character , FILE∗ stream ); // karakter ´ır´ as fscanf ( FILE∗ stream, char ∗ format, ... ); // form´ azott olvas´ as fgets ( char∗ str , int num, FILE∗ stream ); // sztring olvas´ as fgetc ( FILE∗ stream ); // karakter olvas´ as
int fseek ( FILE∗ stream, long int offset , int origin ); //poz´ıcion´ al´ as long int ftell ( FILE∗ stream ); // poz´ıci´ o lek´erdez´ese int feof ( FILE∗ stream ); // v´ege?
158
F´ ajlrendszerek
K¨ onyvt´ arak
K¨onyvt´arszerkezetek Egyszer˝ u k¨ onyvt´ arszerkezet: Egyetlen k¨ onyvt´ar (a), vagy felhaszn´al´onk´ent k¨ ul¨on k¨onyvt´ar (b). Pl. be´agyazott rendszerek, PDA-k, digit´alis f´enyk´epez˝og´epek. Hierarchikus k¨ onyvt´ arszerkezet: tetsz˝ oleges sz´am´ u alk¨onyvt´ar (c). Pl. modern PC-k, f´ajlszerverek.
159
F´ ajlrendszerek
K¨ onyvt´ arak
´ Utvonal megad´asa Abszol´ ut vs. relat´ıv u ´tvonal
160
F´ ajlrendszerek
K¨ onyvt´ arak
K¨onyvt´ari m˝uveletek
´ u L´etrehoz´as (create). Uj, ¨res k¨ onyvt´ar T¨ orl´es (delete). Csak u ¨res k¨ onyvt´ar Megnyit´as (opendir). Olvashat´ o lesz a k¨ onyvt´ar, Pl. list´az´as Lez´ar´as (closedir). Olvas´as ut´an a mem´ oria felszabad´ıt´asa Olvas´as: (readdir). k¨onyvt´ari bejegyz´es olvas´asa ´ Atnevez´ es (rename). Hasonl´ oan a file-okhoz Kapcsol´as (link). Merev kapcsolatok l´etrehoz´asa (hard link). Lekapcsol´as (unlink). Egy k¨ onyvt´ari bejegyz´es t¨ orl´ese
161
F´ ajlrendszerek
F´ ajlrendszerek megval´ os´ıt´ asa
F´ajlrendszerszerkezet MBR (Master Boot Record) A lemez 0. szektora. A BIOS bet¨olti ´es v´egrehajtja az MBR-ben l´ev˝ o k´ odot. Az MBR program keresi meg az akt´ıv part´ıci´ot, majd beolvassa ´es elind´ıtja a part´ıci´ o els˝ o blokkj´at. Part´ıci´ os t´ abla: Az MBR v´eg´en, tartalmazza a part´ıci´ok kezdet´enek ´es v´eg´enek c´ımeit. Els˝ odleges part´ıci´ o max 4 db (PC-n). Egy kiterjesztett part´ıci´ o tartalmazhat tetsz˝ oleges sz´am´ u logikai part´ıci´ ot.
162
F´ ajlrendszerek
F´ ajlrendszerek megval´ os´ıt´ asa
F´ajlrendszerszerkezet Part´ıci´ ok
Ind´ıt´ oblokk (Boot block): a part´ıci´ o els˝ o blokkja, feladata, hogy bet¨oltse a part´ıci´on l´ev˝o os-t. Szuperblokk: tartalmazza a f´ajlrendszer adatait. Szabadter¨ uletkezel˝ o: inf´ o a szabad blokkokr´ ol. I-node t´ abla: minden f´ajlhoz egy bejegyz´es: attrib´ utumok ´es az adatblokkok.
163
F´ ajlrendszerek
F´ ajlrendszerek megval´ os´ıt´ asa
F´ajlok megval´os´ıt´asa Egym´ ast k¨ ovet˝ o blokkok sorozata. El˝ ony: egyszer˝ u megval´os´ıt´as, elegend˝o az els˝o blokkot ´es a hosszt t´arolni, gyors olvas´as. H´atr´any: szabad ter¨ uletek elapr´oz´odnak, m´eretet l´etrehoz´askor ismerni kell. Pl. m´agnesszalagok, CD, DVD L´ ancolt list´ ak. Lemezblokkokat l´ancra f˝ uzz¨ uk, az els˝ o sz´o a k¨ovetkez˝o blokkra mutat. utols´o blokkban bels˝ o t¨ oredezetts´eg. El˝ony: nincs elapr´oz´od´as, szekvenci´alis olvas´as egyszer˝ u. H´atr´any: k¨ozvetlen el´er´es lass´ u a sok fej-poz´ıcion´al´as miatt, adatok m´erete nem kett˝ohatv´any.
164
F´ ajlrendszerek
F´ ajlrendszerek megval´ os´ıt´ asa
F´ajlok megval´os´ıt´asa
L´ ancolt list´ ak a mem´ ori´ aban. FAT (File Allocation Table). El˝ ony: nincs elapr´oz´od´as, olvas´as gyors, teljes blokk haszn´alhat´o. H´atr´any: a lemez m´eret´evel egy¨ utt n˝o a t´abla m´erete. Ha a lemez 20GB, ´es a blokkm´eret 1KB, akkor a t´abla m´erete 80MB (32 bites bejegyz´esek eset´en). Pl. MS-DOS: FAT16, Windows 98: FAT32 (28-bites)
165
F´ ajlrendszerek
F´ ajlrendszerek megval´ os´ıt´ asa
F´ajlok megval´os´ıt´asa I-nodeok. El˝ony: Csak a nyitott f´ajlok i-nodejai vannak a mem´ori´aban, a mem´oriak¨olts´eg nem f¨ ugg a lemez m´eret´et˝ ol. H´atr´any: Hossz´ u f´ajlok eset´en indirekt blokkokat kell alkalmazni.
166
F´ ajlrendszerek
K¨ onyvt´ arak megval´ os´ıt´ asa
K¨onyvt´arak megval´os´ıt´asa Gy¨ ok´erk¨onyvt´ar helye: • R¨ ogz´ıtett helyen a part´ıci´ on bel¨ ul • Unix: szuperblokk tartalmazza az I-nodet´ abla hely´et, aminek els˝o bejegyz´ese a gy¨ok´erk¨ onyvt´ar • Windows XP: bootszektor tartalmazza az MFT-t (Master File Table) Hol t´aroljuk az attrib´ utumokat: (a) A k¨onyvt´ari bejegyz´esben (b) K¨ ul¨on adatszerkezetben (pl. i-node)
167
F´ ajlrendszerek
P´ eld´ ak f´ ajlrendszerekre
K¨onyvt´arak megval´os´ıt´asa MS-DOS k¨ onyvt´ arak
MS-DOS k¨onyvt´arbejegyz´es:
168
F´ ajlrendszerek
P´ eld´ ak f´ ajlrendszerekre
K¨onyvt´arak megval´os´ıt´asa Windows 98 k¨ onyvt´ arak
Windows 98 alap k¨onyvt´arbejegyz´es:
Hossz´ u f´ajln´ev a Windows 98-ban:
169
F´ ajlrendszerek
P´ eld´ ak f´ ajlrendszerekre
K¨onyvt´arak megval´os´ıt´asa UNIX V7 k¨ onyvt´ arak
Unix-k¨onyvt´arbejegyz´es:
A /usr/ast/mbox keres´es´enek l´ep´esei:
170
F´ ajlrendszerek
P´ eld´ ak f´ ajlrendszerekre
K¨onyvt´arak megval´os´ıt´asa NTFS k¨ onyvt´ arak
Tulajdons´agok: • 255 karakteres file nevek ´ es 32 767 karakteres u ´tvonalak • Unicode a file nevek k´ epz´es´ehez, de: probl´em´as a rendez´es • Kv´ ota • V´ edelem, titkos´ıt´as • Adatt¨ om¨or´ıt´es
Probl´em´ak megold´asa attrib´ utumok bevezet´ese: A file nem m´as mint attrib´ utumok gy˝ ujtem´enye. Az adat is egyfajta attrib´ utum. T¨obb adatsor is lehets´eges. Master File Table (MFT): minden f´ajl sz´am´ara tartalmaz egy bejegyz´est. Egy bejegyz´es 16 attrib´ utumot tartalmazhat, mindegyik max 1KB. Egyes attrib´ utumok lehetnek mutat´ ok, u ´jabb attrib´ utumokra. 171
F´ ajlrendszerek
Lemezter¨ ulet-kezel´ es
Blokkm´eret Hogyan v´alasszuk meg a lemez-blokkok m´eret´et? • Ha t´ ul nagy, akkor a kicsi f´ajlok sok ter¨ uletet foglalnak. • Ha t´ ul kicsi, akkor lass´ u lesz az olvas´as (sok poz´ıcion´al´as) Mekkora egy ´atlagos f´ajl? • 1984-ben kb. 1KB • 2005-ben 2475 b´ ajt (medi´an) Felt´etelezz¨ uk, hogy minden f´ajl m´erete 2KB:
Teh´at a 4KB j´o v´alaszt´as, de Pl. UNIX-ban 1KB az ´altal´anos. 172
F´ ajlrendszerek
Lemezter¨ ulet-kezel´ es
Szabad blokkok nyilv´antart´asa K´et m´odszer haszn´alnak sz´elesk¨ orben: (a) Szabad blokkok l´ancolt list´aban (b) Bitt´erk´ep
173
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
Ment´esek
Ment´es c´elja: Helyre´all´ıt´as katasztr´ ofa eset´en vagy hiba eset´en. Hossz´ u id˝ o, nagy hely ig´eny Inkrement´ alis ment´es: Teljes ment´es havonta vagy hetente. Naponta csak azokat a file-okat kell menteni, amelyek megv´altoztak a teljes ment´es ota. Csak az utols´o ment´es ´ ´ ota megv´altozott file-okat mentj¨ uk. Bonyolult a helyre´all´ıt´as: El˝ osz¨ or a teljes ment´est kell vissza´all´ıtani Azt´an az inkrement´alis ment´eseket ford´ıtott sorrendben T¨ om¨or´ıt´es
174
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
Ment´esek Fizikai ment´ es: 0. blokk-t´ ol minden blokk ki´ır´asa egy szalagra. Nem haszn´alt blokkok? Ki kell ´ırni a sorsz´am´at is a blokknak. Hib´as blokkok ment´ese vagy blokkok ´atrendez´ese? El˝ onye: Egyszer˝ u ´es nagyon gyors. H´atr´anya: nem lehet f´ajlokat/k¨ onyvt´arakat kihagyni, nem inkrement´alis, nem lehet egyedi f´ajlokat helyre´all´ıtani.
Logikai ment´ es: Egy vagy t¨ obb kijel¨ olt k¨ onyvt´arban l´ev˝o file-t ´es k¨ onyvt´arat ment rekurz´ıvan. Menteni kell a file u ´tvonal´at, a k¨ onyvt´arszerkezetet, az attrib´ utumokat. El˝ onye: Egyszer˝ uem helyre lehet ´all´ıtani egyedi file-okat ´es k¨ onyvt´arakat. H´atr´anya: szabad blokkok list´aj´at k¨ ul¨ on kell kezelni, merev l´ancokat csak egyszer szabad helyre´all´ıtani.
175
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
File-rendszerek konzisztenci´aja Konzisztencia s´er¨ ulhet ha pl. nem minden m´ odosult blokk ker¨ ult ki´ır´asra a rendszer ¨osszeoml´asakor. A hiba kritikus lehet, ha a blokk egy i-csom´opont, vagy k¨onyvt´ari bejegyz´es, vagy szabadlista-elem. Unix – fsck Windows – checkdisk/scandisk Konzisztencia-ellen˝orz´esek lehetnek • Heurisztik´ an alapul´o: t´ ul sok f´ajl egy k¨ onyvt´arban, gyan´ us
jogosults´agok, illeg´alis i-node sz´amok, stb... • Blokk • F´ ajl
176
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
Blokk-konzisztencia ellen˝orz´es K´et t´abl´azatot ´ep´ıt: 1) H´any file-ban fordul el˝ o a blokk az i-csom´opontok alapj´an 2) H´anyszor fordul el˝ o a blokk a szabad list´aban. (a) (b) (c) (d)
Minden blokk vagy az egyik vagy a m´asik t´abl´azatban fordul el˝o Hi´anyz´o blokk Duplik´alt szabad blokk Duplik´alt adatblokk
177
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
F´ajl-konzisztencia ellen˝orz´es
Gy¨ ok´erk¨onyvt´art´ol indulva rekurz´ıvan bej´arjuk a f´ajlrendszert, minden file eset´en n¨ovel¨ unk egy f´ajlhoz tartoz´ o sz´aml´al´ ot. ¨ Osszevetj¨ uk az i-csom´opontban t´arolt l´ancsz´ammal. • Ha az i-csom´ opontban t´arolt ´ert´ek nagyobb: Az i-csom´opont nem
t¨orl˝odne az utols´o f´ajl t¨ orl´esekor sem. T´arhely kapacit´asa cs¨okken. Jav´ıt´as: Az i-csom´opont sz´aml´al´ oj´at a helyes ´ert´ekre kell ´all´ıtani. • Ha az i-csom´ opontban t´arolt ´ert´ek kisebb: K´et k¨ onyvt´ari bejegyz´es
ugyanahhoz a file-hoz van kapcsolva. Ak´armelyik bejegyz´est t¨or¨olve az i-csom´opont sz´aml´al´ oja 0-v´a v´alna, ´es t¨ or¨ oln´e az adatokat. Jav´ıt´as: i-node beli ´ert´eket jav´ıtjuk.
178
F´ ajlrendszerek
F´ ajlrendszerek megb´ızhat´ os´ aga
V´ ege
179
