API tools faq
paste
garnettkg

os1 kol1

garnettkg
Apr 22nd, 2016
468
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 192.76 KB | None | 0 0
raw download clone embed print report
  1. Predavanje 1a: Computer-System Structures
  2. Operacije računarskog sistema
  3. I/O operacije
  4. Struktura memorije
  5. Hijerarhija memorije
  6. Hardverska zaštita
  7. Glavna arhitektura sistema
  8. Arhitektura računarskog sistema
  9. Operacije računarskog sistema
  10. I/O uređaji i CPU
  11. moze se izvršavati
  12. konkurentno
  13.  
  14. CPU izolacija od I/O (3 uslova)
  15. 1. svaki uređaj kontroler ima lokalni bafer
  16. 2. DMA
  17. 3. Signal prekida (Interrupt controller)
  18. Interrupt Time Line for Single Process Doing Output
  19. Dve I/O Metode
  20. Direktan pristup memoriji (DMA)
  21. Koristi se za I/O uredjaje velike brzine
  22. omogucava brz prenos informacija
  23. između periferija i memorije.
  24.  
  25. DMA Uredjaj kontroler prenosi pakete podataka
  26. iz bafera
  27. direktno u glavnu memoriju
  28. bez koriscenja CPU-a
  29.  
  30. Jedan prekid
  31. je češći po bloku
  32. nego po bajtu.
  33. Struktura memorije
  34. Glavna memorija:
  35. veliki memorijski medijum
  36. kome CPU može pristupati direktno
  37.  
  38. Sekundarna memorija:
  39. nastavak glavne memorije
  40. koja obezbeđuje veliki dugotrajni memorijski prostor
  41.  
  42. Magnetni diskovi:
  43. čvrst metal ili staklene ploče
  44. omotani sa magnetnim materijalom po kojem se može pisati
  45. Površina diska je logički podeljena na staze,
  46. koji su podeljeni na sektore
  47. Disk kontroler obavlja
  48. logičku interakciju između uređaja i računara
  49. Mehanizam pomeranja glave diska
  50. Hijerarhija memorijskih uređaja
  51. Keširanje (Caching)
  52. Koriste ga memorije velike brzine
  53. da čuvaju podatke kojima se skoro pristupalo
  54.  
  55. Zahteva tehniku (policy) za upravljanje kešom
  56.  
  57. Keširanje predstavlja još jedan nivo u memorijskoj hijerarhiji.
  58.  
  59. Ovo zahteva da podaci
  60. koji su istovremeno memorisani
  61. u više od jednog nivoa
  62. da budu konsistentani
  63. Migracija A iz diska u registar
  64. Hardverska zaštita
  65. Dual mode operacija (user – kernel)
  66.  
  67. I/O zaštita
  68.  
  69. Memorijska zaštita
  70.  
  71. CPU zaštita
  72. Dvomodna operacija
  73.  
  74. 1. Korisnički mod:
  75. izvršenje obavlja korisnik
  76.  
  77. 2. Monitor mod
  78. (kao kernelski mod ili sistemski mod)
  79. izvršenje obavlja operativni sistem
  80. Dvomodna operacija
  81. Mode-bit se ubacuje u računarski hardver da ukaže na trenutni mod:
  82. monitor (0)
  83. ili
  84. user (1)
  85. Kada se javi greška ili prekid hardver se prebacuje u monitor mod
  86. I/O zaštita
  87. Sve I/O instrukcije su privilegovane instrukcije.
  88.  
  89. Mora se osigurati
  90. da korisnički program
  91. nikad ne dobije kontrolu
  92. nad računarom u monitor modu
  93. (npr., korisnički program koji, kao deo njegovog izvršavanja,
  94. memoriše nove adrese u IVT)
  95. Korišćenje sistemskih poziva za izvršavanje I/O operacija
  96. Memorijska zaštita
  97. Mora se obezbediti memorijska zaštita za:
  98. IVT (vektor prekida)
  99. interrupt service routines
  100. kernel
  101. user processes
  102.  
  103. Memorijska zaštita:
  104. ubacije dva registra
  105. koji određuju prostor adresa
  106. kojima program može pristupiti:
  107. Base register – opisuje najmanju fizičku memorijsku adresu.
  108. Limit register – sadrži veličinu prostora
  109.  
  110. Korišćenje Base i Limit registara
  111. Hardverska adresna zaštita
  112. CPU zaštita
  113. Timer (real time clock):
  114. Obezbeđuje računarske prekide posle određenog perioda
  115. osigurava operativnom sistemu održavanje kontrole.
  116.  
  117. Timer (real time clock) se dekrementira na svaki otkucaj sata
  118. Kada brojač dostigne vrednost 0, nastaje prekid
  119.  
  120. Timer se obično koristi za implementaciju time sharing-a.
  121.  
  122. Timer se takođe koristi za računanje trenutnog vremena
  123. Load-timer je privilegovana instrukcija
  124. Mrežna struktura
  125. Local Area Networks (LAN)
  126.  
  127. Wide Area Networks (WAN)
  128. LAN struktura
  129. WAN struktura
  130.  
  131.  
  132. Predavanje 1b: Uvod u OS
  133. Šta je operativni sistem?
  134.  
  135. Veliki računarski sistemi (Mainframe Systems)
  136.  
  137. Desktop sistemi
  138.  
  139. Višeprocesorski sistemi (Multiprocessor Systems)
  140.  
  141. Distribuirani sistemi
  142.  
  143. Udruženi sistemi (Clustered Systems)
  144.  
  145. Sistemi za upravljanje u realnom vremenu
  146.  
  147. Ručni sistemi (Handheld Systems)
  148.  
  149. Računarsko okruženje (Computing Environments)
  150. Šta je operativni sistem?
  151. OS je program koji predstavlja
  152. posrednika
  153. između
  154. korisnika računara
  155. i
  156. računarskog hardvera
  157. Prikaz delova operativnog sistema
  158. Komponente računarskog sistema
  159. Hardver:
  160. osnovni računarski resursi (CPU, memorija, I/O uređaji)
  161.  
  162. Operativni sistem:
  163. kontroliše i koordinara korišćenje hardvera
  164. između različitih aplikativnih programa
  165. za različite korisnike
  166.  
  167. Aplikativni programi:
  168. određuju
  169. koji resursi sistema se koriste
  170. za rešavanje računarskih problema korisnika
  171. (prevodioci, baze podataka, video igre, poslovni programi)
  172.  
  173. 4. Korisnici (ljudi, mašine, ostali računari)
  174.  
  175. Definicija operativnog sistema
  176. OS kao upravljač resursa:
  177. upravlja
  178. dodeljuje resurse
  179. kontroliše računarski hardver
  180.  
  181. OS kao virtuelna mašina:
  182. izvršava korisničke programe
  183.  
  184. rešava korisničke probleme na lakši način.
  185.  
  186. čini računarski sistem pogodnim za korišćenje
  187.  
  188. Funkcije operativnog sistema
  189. Sekvenciranje poslova (s jednog na drugi)
  190. Upravljanje poslovima i interpretacija komandnog jezika
  191. Rukovanje greškama
  192. Rukovanje I/O operacijama
  193. Rukovanje prekidima
  194. Raspoređivanje poslova
  195. Upravljanje resursima
  196. Zaštita i sigurnost (protection and security)
  197. Višestruki pristup
  198.  
  199. Dodatne funkcije:
  200. Korisnički interfejs
  201. Obračun
  202. Karakteristike operativnog sistema
  203. Konkurentnost (postojanje više procesa)
  204.  
  205. Deoba resursa (Resource Sharing)
  206.  
  207. Dugotrajna memorija (diskovi: magnetic, flash, SSD)
  208.  
  209. Determinističan u odnosu na rezultate/ Nedeterminističan u odnosu na opterećenje
  210.  
  211. Poželjne osobine:
  212. Efikasnost
  213. Pouzdanost
  214. Mogućnost održavanja
  215. Prihvatljiva veličina
  216. Poželjne osobine
  217. Efikasnost
  218. srednje vreme između grupnih (batch) poslova
  219. Vreme (%) iskorišćenosti procesora
  220. vreme prolaska za grupne poslove
  221. vreme odziva (za interaktivne sisteme)
  222. iskorišćenost resursa
  223. propusna moć (poslova/sat, transakcija/min)
  224. e=Tuseful/Total; o=Tsystem/Total; e+o=1
  225.  
  226. Pouzdanost
  227. p je verovatnoća greške, f je funkcija stanja
  228. p e [0,1]; f=1-p
  229.  
  230. Mogućnost održavanja
  231. jednostavan za održavanje sa malim brojem ljudi koji će raditi na održavanju
  232.  
  233. Prihvatljiva veličina
  234. Tipovi operativnih sistema -1
  235.  
  236. Kriterijum 1. (broj korisnika)
  237. jednokorisnički OS (DOS, MS-Windows 3.xx, 95, 98)
  238. višekorisnički OS (UNIX)
  239.  
  240. Kriterijum 2. (broj simultanih procesa)
  241. jednoprocesni OS (DOS)
  242. višeprocesni OS (UNIX, MS-Windows)
  243.  
  244. Kriterijum 3. Kombinacija 1+2
  245. jednoprocesni, jednokorisnički OS
  246. višeprocesni, jednokorisnički OS
  247. višeprocesni, višekorisnički OS
  248.  
  249. Tipovi operativnih sistema -2
  250.  
  251. Kriterijum 4. (obrada poslova)
  252. Sistemi sa grupnom obradom (batch)
  253. Interaktivni sistemi
  254. Kombinovani sistemi
  255.  
  256. Kriterijum 5. (distribucija resursa)
  257. Centralizovani OS
  258. Mrežni OS
  259. Distribuirani OS
  260.  
  261. Kriterijum 6. (namena)
  262. OS opšte namene
  263. OS specijalne namene
  264.  
  265. Tipovi operativnih sistema -3
  266.  
  267. Kriterijum 7. (funkcionalne osobine)
  268. Veliki računarski sistemi (mainframe)
  269. Sistemi sa deljenim vremenom (timesharing)
  270. Desktop sistemi
  271. Višeprocesorski sistemi
  272. Mrežni OS
  273. Distribuirani sistemi
  274. Udruženi sistemi (clusters)
  275. Sistemi za upravljanje u realnom vremenu
  276. Ručni sistemi (handheld)
  277.  
  278. Veliki računarski sistemi
  279. Vreme pripreme se smanjuje grupisanjem sličnih poslova (batch)
  280.  
  281. Automatsko sekvenciranje poslova (AJS)
  282. (bez operatora)
  283. automatski prebacuje kontrolu
  284. sa jednog posla na drugi.
  285.  
  286. Rezidentni monitor (za AJS)
  287. početna kontrola je u monitoru (kernel)
  288. kontroliše prenos poslova
  289. kad se posao završi, kontrola se prenosi u monitor
  290. Raspored memorije za grupni sistem
  291. Multiprogramiranje (grupni sistemi)
  292. Osobine OS-a potrebne za multiprogramiranje
  293. I/O rutine podržane od sistema
  294.  
  295. Upravljač memorijom:
  296. sistem mora dodeliti memoriju
  297. za nekoliko poslova
  298.  
  299. CPU raspoređivanje:
  300. sistem mora izabrati
  301. između nekoliko poslova spremnih za odvijanje.
  302.  
  303. Dodela uređaja
  304. Sistemi sa deljenim vremenom– Interaktivno računanje
  305. CPU se deli
  306. između nekoliko poslova
  307. koji se nalaze u memoriji i na disku
  308. (CPU se dodeljuje procesu samo ako je proces u memoriji).
  309.  
  310. Proces može da se suspenduje van memorije na disk (vm)
  311.  
  312.  
  313. On-line komunikacija između korisnika i sistema je uspostavljena na sledeći način;
  314. kad operativni sistem završi izvršavanje jedne naredbe,
  315. onda očekuje sledeću “kontrolnu naredbu” od korisnika.
  316.  
  317. Vreme odziva je što je moguće kraće
  318.  
  319. Desktop sistemi
  320. Lični računar (PC):
  321. računarski sietem namenjen za jednog korisnika.
  322.  
  323. I/O uređaji – tastatura, miš, monitor, mali štampači
  324.  
  325. Podesni za rad i okrenuti korisniku (user friendly)
  326.  
  327. Mogu da prihvaju tehnologije razvijene za veće operativne sisteme
  328. vrlo često pojedinac sam koristi računar
  329. i nema potrebu za naprednom korišćenjem CPU-a
  330.  
  331. Ovde spadaju nekoliko različitih tipova operativnih sistema (Windows, MacOS, UNIX, Linux)
  332. Paralelni sistemi
  333. Multiprocesorski sistemi:
  334. sa više od jednog CPU
  335. u zatvorenoj komunikaciji
  336.  
  337. Čvrsto-povezan grupni sistem:
  338. procesori dele memoriju i sistemski časovnik;
  339. komunikacija se obično odvija
  340. preko deljive memorije
  341.  
  342. Prednosti paralelnih sistema:
  343. Povećanje brzine (manje od Nx, CPU sinhronizacija)
  344. Ekonomičnost (isto napajanje, memorija, I/O)
  345. Povećanje pouzdanosti
  346. Paralelni sistemi
  347. Simetrično multiprocesiranje (SMP)
  348. svaki procesor izvršava
  349. identičnu kopiju operativnog sistema.
  350.  
  351. veliki broj procesa se može izvršavati
  352. po jedan na svakom CPU bez gubitka performansi
  353.  
  354. mnogi moderni operativni sistemi podržavaju SMP
  355.  
  356. Asimetrično multiprocesiranje
  357. Svaki procesor ima dodeljen specifičan zadatak;
  358. glavni procesor raspoređuje i dodeljuje poslove
  359. ostalim procesorima.
  360.  
  361. Uglavnom se koristi u ekstremno velikim sistemima
  362. Arhitektura simetričnog multiprocesiranja
  363. Taksonomija za paralelne računare
  364. Proširena taksonomija
  365. UMA simetrična multiprocesorska arhitektura
  366. NUMA
  367. CC-NUMA
  368. Sun Fire E25K NUMA Multiprocessor
  369. Distribuirani sistemi
  370. Distribuira izračunavanje
  371. između nekoliko fizičkih procesora
  372.  
  373. Labavo-povezani grupni sistem
  374. svaki procesor ima svoju lokalnu memoriju
  375. procesori komuniciraju između sebe
  376. putem raznih komunikacionih linija
  377. kao što su magistrale velike brzine ili telefonske linije
  378.  
  379. Prednosti distribuiranih sistema:
  380. deljenje resursa
  381. ubrzavanje izračunavanja – load sharing
  382. pouzdanost
  383. komunikacije
  384. Distribuirani sistemi
  385. Zahtevaju mrežnu infrastrukturu
  386.  
  387. LAN ili WAN
  388.  
  389. Mogu biti realizovani kao klijent-server ili peer-to-peer sistemi.
  390.  
  391. U klijent-server arhitekturi postoje:
  392. Serveri za izračunavanje (Compute server)
  393. Serveri podataka (File server)
  394. Serveri za štampače (Printer server)
  395.  
  396.  
  397. Struktura klijent-server sistema
  398. BlueGene
  399.  
  400. Realizacija BlueGene
  401.  
  402. Red Storm
  403. Baziran na 64bit AMD Opteron CPU
  404. 3 operaciona moda
  405.  
  406. poboljšan momrijski protok
  407.  
  408. sadrži mrežni CPU u sebi
  409. RedStorm realizacija
  410. BlueGene v Red Storm
  411. Klasteri (Cluster computing)
  412. 100-1000 PC
  413.  
  414. osetno jeftiniji u odnosu na MPP
  415.  
  416. koriste:
  417. Internet mrežu
  418. i
  419. PC komponente
  420.  
  421. centalizovani i decentralizovani
  422. Google-arhitektura
  423. Udruženi sistemi (Clustered Systems)
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430. Udruženi sistemi se sastoje od dva ili više sistema koji dele storage
  431.  
  432. Obezbeđuju visoku pouzdanost (Nema zastoja)
  433.  
  434. asimetrično udruživanje:
  435. jedan server izvršava aplikaciju
  436. dok
  437. su ostali serveri neaktivni = prateći serveri (monitoring servers).
  438.  
  439. simetričnom udruživanje:
  440. svi serveri izvršavaju aplikaciju/aplikacije
  441. (svi izvrčavaju i prate rad ostalih).
  442. Real-Time sistemi
  443. Često se koriste kao kontrolni uređaji
  444. u aplikacijama specijalne namene, kao što su:
  445. kontrolisanje naučnih eksperimenata
  446. sistemi za medicinsku grafiku
  447. sistemi za industrijsku kontrolu
  448. specijalni grafički sistemi
  449. Imaju precizno definisana vremenska ograničenja
  450.  
  451. Real-Time sistemi mogu biti:
  452. hard real-time (nema diska)
  453. soft real-time (realni OS)
  454. Real-Time sistemi
  455.  
  456. Hard real-time:
  457. sekundarna memorija ograničena ili otsutna,
  458. podaci se čuvaju u RAM ili read-only memory (ROM)
  459. nema diska, tastature, ekrana, miša..
  460. nema standardnih funkcija OS
  461.  
  462. Soft real-time
  463. procesi u realnom vremenu i obični procesi
  464. mnogi OS su soft real-time
  465. limitirana upotreba u industrijskoj kontroli ili robotici
  466. upotreba u aplikacijama
  467. (multimedia, virtual reality)
  468. zahteva napredne osobine operativnih sistema
  469. Ručni sistemi (Handheld Systems)
  470. Personal Digital Assistants (PDAs)
  471.  
  472. Mobilni telefoni
  473.  
  474. Karakteristike:
  475. Ograničena memorija
  476. Spori procesori
  477. Mala veličina ekrana
  478. Migracija operativnih sistema i osobine
  479. Računarsko okruženje (Computing Environments)
  480. Tradicionalno okruženje
  481. desk-top
  482. ili
  483. time-sharing sistemi
  484.  
  485. Web-bazirano okruženje
  486.  
  487. Ugrađeno okruženje (embeded, real time)
  488.  
  489.  
  490.  
  491.  
  492. Predavanje 3: Strukture operativnih sistema
  493. Komponente sistema
  494. Servisi operativnog sistema
  495. Sistemski pozivi
  496. Sistemski programi
  497. Struktura sistema
  498. Virtuelna mašina
  499. Dizajn sistema i implementacija
  500. Generacije sistema
  501. Opšte komponente sistema
  502. Upravljanje procesima (Process Management)
  503. Upravljanje memorijom (Main Memory Management)
  504. Upravljanje podacima (File Management)
  505. Upravljanje uIazom i izlazom (I/O System Management)
  506. Upravljanje sekundarnom memorijom (Secondary Management)
  507. Umrežavanje (Networking)
  508. Zaštita (Protection System)
  509. Korisnički interfejs (Command-Interpreter System)
  510.  
  511. Upravljanje procesima
  512. Proces je program koji se izvršava
  513. Proces traži izvesne resurse, da završi zadatak:
  514. CPU vreme
  515. memoriju
  516. datoteke
  517. I/O uređaje
  518.  
  519. Operatvni sistem je odgovoran za sledeće aktivnosti u vezi sa upravljanjem procesa:
  520. Kreiranje i brisanje procesa.
  521. Suspenzija i nastavak procesa.
  522. Obezbeđuje mehanizme za:
  523. sinhronizaciju procesa
  524. komunikaciju među procesima
  525. Upravljanje memorijom
  526. Memorija je veliki niz reči ili bajtova,
  527. svaki sa svojom adresom
  528. To je spremište za brz pristup podacima
  529. deljiv za CPU i I/O uređaje
  530.  
  531. Glavna memorija je privremeni uređaj za skladištenje
  532. Ona gubi svoj sadržaj u slučaju da se sistem obori
  533.  
  534. Operativni sistem je odgovoran za sledeće aktivnosti u vezi sa upravljanjem memorijom:
  535. Čuva evidenciju koji deo memorije se trenutno koristi i ko je koristi
  536. Odlučuje koji prices će biti učitan kada memorijski prostor bude dostupan
  537. Dodeljuje i oduzima memorijski prostor po potrebi
  538. Upravljanje podacima
  539. Datoteka je skup povezanih informacija definisan od strane njenog tvorca
  540. Uopšteno, datoteke predstavljaju:
  541. programe
  542. podatke
  543.  
  544. Operativni sistem je odgovoran za sledeće aktivnosti u vezi sa upravljanjem datotekama:
  545. Kreiranje datoteke i njeno brisanje.
  546. Kreiranje direktorijuma i njegovo brisanje.
  547. Pruža podršku za rukovanje datotekama i direktorijumima.
  548. Mapira datoteke u sekundarnoj memoriji
  549. Pravi kopiju datoteke na trajnoj (ne privremenoj) memorji.
  550. Upravljanje ulazom i izlazom
  551. I/O sistem se sastoji od:
  552.  
  553. 1. Komponente za upravljanje memorijom
  554. buffering
  555. caching
  556. spooling system
  557.  
  558.  
  559. 2. Opšti drajveri za uređaje
  560.  
  561. 3. Drajveri za određeni hardver
  562. Upravljanje sekundarnom memorijom
  563. Pošto je glavna memorija (primarna memorija) privremena
  564. i suviše mala da prihvati sve podatke i programe za stalno,
  565. računarski sistem mora obezbediti sekundarnu memoriju u koju kopira podatke iz glavne memorije
  566.  
  567. Mnogi moderni računarski sistemi koriste diskove
  568. kao osnovni memorijski medijum,
  569. za programe i podatke
  570.  
  571. Operativni sistem je odgovoran za sledeće aktivnosti u vezi sa upravljanjem sekundarnom memorijom:
  572. Upravljanje slobodnim prostorom
  573. Dodela memorije
  574. Disk scheduling
  575. Umrežavanje (Distribuirani sistemi)
  576. Distribuirani sistem je:
  577. skup procesora
  578. koji ne dele memoriju ili sistemski časovnik
  579. svaki procesor ima svoju lokalnu memoriju
  580.  
  581. Procesori se u sistemu spajaju kroz komunikacionu mrežu
  582.  
  583. Komunikacija se odvija korišćenjem protokola
  584.  
  585. Distribuirani sistem obezbeđuje korisniku da pristupa raznim resursima sistema
  586.  
  587. Pristup deljenim resursima obezbeđuje:
  588. Brže izračunavanje
  589. Povećanu upotrebljivost podataka
  590. Veću pouzdanost
  591. Zaštita
  592. Zaštita predstavlja mehanizam
  593. koji kontroliše pristup
  594. programa
  595. procesa
  596. korisnika
  597. sistemu i korisničkim resursima.
  598.  
  599. Mehanizam za zaštitu mora:
  600.  
  601. praviti razliku između
  602. autorizovane i
  603. neautorizovane upotrebe
  604.  
  605. obezbediti način da to sprovede
  606. Korisnički interfejs (UI)
  607. Tekstualni korisnički interfejs
  608. komandna linija
  609. shell (u UNIX-u)
  610.  
  611. Mnoge komande se operativnom sistemu zadaju preko kontrolnih naredbi koje obavljaju:
  612. kreiranje procesa i upravljanje
  613. upravljanje ulazom i izlazom
  614. upravljanje sekundarnom memorijom
  615. upravljanje glavnom memorijom
  616. pristup sistemu datoteka
  617. zaštita
  618. umrežavanje
  619. GUI
  620. Servisi operativnog sistema
  621. Izvršavanje programa:
  622. sposobnost sistema
  623. da učita program u memoriju i
  624. da ga pokrene
  625.  
  626. I/O operacije:
  627. pošto korisnički programi nemogu da izvršavaju I/O operacije direktno,
  628. operativni sistem mora obezbediti neki način da izvrši I/O operacije
  629.  
  630. Rukovanje sistemom datoteka:
  631. sposobnost programa da čita, upisuje, kreira, i briše datoteke
  632.  
  633. Komunikacija:
  634. razmena informacija između procesa koji se uzvršavaju
  635. na istom računaru ili
  636. na različitim sistemima koji su umreženi
  637. Implementira se preko deljene memorije ili sistema poruka
  638.  
  639. Otkrivanje grešaka:
  640. garantuje ispravno izračunavanje
  641. tako što otkriva greške u CPU i memoriji, u I/O uređajima, ili u korisničkim programima
  642. Sistemski pozivi (System Calls)
  643. Sistemski pozivi obezbeđuju interfejs
  644. između programa koji se izvršava i operativnog sistema
  645. Generalno, realizuju se u asembleskom jeziku.
  646. Noviji programski jezici za sistemsko programiranje
  647. takođe omogućavaju realizaciju sistemskih poziva u C, C++
  648.  
  649. Postoje tri generalna metoda za prosleđivanje parametara između programa koji se izvršava i operativnog sistema.
  650. 1. Prosleđivanje parametara u registrima procesora
  651. 2. Postavljanjem parametara u memorijskoj tabeli, a adresa tabele se prosleđuje u registru procesora.
  652. 3. Postavljanjem parametara na vrh steka (push), koje operativni sistem skida sa steka.
  653. Passing of Parameters As A Table
  654. Tipovi sistemskih poziva
  655. Kontrola procesa
  656.  
  657. Upravljanje datotekama
  658.  
  659. Upravljanje uređajima
  660.  
  661. Rukovanje informacijama
  662.  
  663. Komunikacije
  664. MS-DOS Execution
  665. UNIX Running Multiple Programs
  666. Komunikacioni modeli
  667. Unutrašnja struktura OS-a
  668. Monolitni sistemi (Monolithic Systems)
  669. velika zbrka (big mess)
  670. nema slojeva, nema ograničenog pristupa
  671. parametri sistemskog poziva se smeštaju u određena mesta
  672.  
  673. Slojevita realizacija (Layered systems)
  674.  
  675. Mikrokernel arhitektura
  676.  
  677. Klijent-server arhitektura
  678.  
  679. Slojevita realizacija
  680. Operativni sistem je podeljen na različite slojeve (layer):
  681. svaki sloj se gradi na slojeve ispod njega
  682. Najniži sloj (sloj 0), je hardver
  683. najviši (sloj N) je korisnički interfejs
  684.  
  685. Sa ovakvim modularnim konceptom,
  686. slojevi koriste
  687. funkcije i servise
  688. jedino sa nižih nivoa
  689. Sloj operativnog sistema
  690. Struktura MS-DOS sistema
  691. MS-DOS
  692. velika funkcionalnost
  693. u malom prostoru
  694. nije podeljen na module
  695.  
  696. Iako MS-DOS ima neku strukturu,
  697. njegov interfejs i nivo funkcionalnosti
  698. nisu dobro odvojeni
  699. MS-DOS slojevita struktura
  700. Mikrokernel sistemska struktura
  701. Mnoge funkcije kernela se pomeraju u korisnički prostor
  702.  
  703. Korisnički moduli komuniciraju između sebe koristeći sistem poruka (message passing)
  704.  
  705. Dobre osobine:
  706. - kernel se lako proširuje i optimizuje
  707. - sistem se lako prenosi na drugu računarsku arhitekturu
  708. - mnogo je pouzdaniju (manje koda se izvršava u kernelskom modu)
  709. - mnogo je sigurniji
  710. Struktura UNIX sistema
  711.  
  712. UNIX operativni sistem ima ograničenu strukturu.
  713.  
  714. UNIX OS se sastoji od 2 odvojena dela.
  715. 1. Sistemski programi
  716. 2. Kernel
  717. se sastoji od:
  718. interfejsa sistemskih poziva na višem nivou
  719. fizičkog hardvera na nižem
  720. Obezbeđuje podršku za:
  721. sistem datoteka
  722. CPU raspoređivanje
  723. upravljanje memorijom
  724. i ostale funkcije operativnog sistema
  725. veliki broj funkcija za jedan nivo
  726. Struktura UNIX sistema
  727. OS/2 slojevita struktura
  728. Windows NT Client-Server Structure
  729. Virtuelne mašine
  730. Virtuelna mašina je zasnovana
  731. na slojevitoj organizaciji
  732. Tretira
  733. realni hardver i realni kernel
  734. kao da su hardver za operativni sistem koji predstavlja
  735.  
  736. Virtelna mašina obezbeđuje
  737. identičan interfejs
  738. kao da je realni hardver ispod virtuelne mašine
  739.  
  740. Operativni sistem stvara iluziju
  741. o višestrukim procesima ili OS
  742. koji se izvršavaju na svom virtuelnom procesoru
  743. i svojoj virtuelnoj memoriji.
  744. Virtuelne mašine (2)
  745. Resursi računara
  746. se dele
  747. da kreiraju virtuelne mašine.
  748.  
  749. 1. CPU scheduling može stvoriti iluziju da korisnici imaju svoj procesor
  750.  
  751. 2. Spooling i sistem datoteka
  752. može obezbediti virtuelne čitače kartica
  753. i virtuelne linijske štampače.
  754.  
  755. 3. Vremenski deljeni korisnički terminal
  756. radi
  757. kao konzola za operatera virtuelne mašine
  758. Koncept virtuelne mašine
  759. Prednosti i mane virtuelnih mašina
  760. Koncept virtuelne mašine obezbeđuje
  761. kompletnu zaštitu sistemskih resursa
  762. pošto su sve virtuelne mašine izolovane od ostalih virtuelnih mašina
  763. Ova izolacija, sprečava direktno deljenje resursa
  764.  
  765. Virtuelne mašine su perfektan razvojni sistem
  766. za realizaciju novih operativnih sistema
  767. Sistem se razvija na virtuelnoj mašini
  768. a ne na realnoj
  769. i nemože doći do narušavanja normalnih sistemskih operacija
  770.  
  771. Koncept virtuelne mašine je komplikovan za realizaciju
  772. zato što treba egzaktno
  773. simulirati hardver koga reprezentuje virtulena mašina
  774. Ciljevi kod projektovanja OS-a
  775. Korisnički ciljevi: operativni sistem treba da bude podesan za:
  776. korišćenje
  777. lak za učenje
  778. pouzdan
  779. bezbedan
  780. brz
  781.  
  782. Sistemski ciljevi – operativni sistem treba da bude jednostavan za:
  783. projektovanje
  784. implementaciju i održavanje
  785. fleksibilan
  786. pouzdan
  787. bez grešaka
  788. efikasan
  789. Implementacija operativnog sistema
  790. Tradicionalno, operativni sistemi su pisani na asemblerskom jeziku
  791. Danas se operativni sistemi pišu u višim programskim jezicima.
  792.  
  793. Implementacija u višem programskom jeziku:
  794. izvorni kod se mnogo brže piše
  795. izvorni kod je mnogo kompaktiniji
  796. Kod se lakše razume i lakše se otklanjaju greške (debug)
  797.  
  798. Operativni sistem napisan na višem programskom jeziku se mnogo lakše prenosi na drugu računarsku arhitekturu, odnosno drugu vrstu procesora.
  799. Generisanje operativnog sistema (SYSGEN)
  800. Operativni sistemi se generišu da rade
  801. za više klasa računara;
  802. operativni sistem mora da se konfiguriše za svaku klasu procesora, posebno.
  803.  
  804. SYSGEN program obezbeđuje informacije:
  805. za hardversku konfiguraciju
  806. za koju će se generisati operativni sistem.
  807.  
  808. Booting – strartovanje operativnog sistema punjenjem kernela sa diska u memoriju.
  809.  
  810. Bootstrap program – kod koji se čuva u ROM-u
  811. sposoban je da:
  812. locira kernel
  813. napuni kernel u memoriju
  814. otpočne izvršenje
  815.  
  816.  
  817. Uvod u procese
  818. Pojam procesa
  819.  
  820. Raspoređivanje procesa
  821.  
  822. Operacije nad procesima
  823.  
  824. Saradnja među procesima
  825.  
  826. Interprocesna komunikacija (IPC)
  827.  
  828. Komunikacija u klijent-server sistemima
  829. Pojam procesa
  830. Operativni sistem izvršava mnoštvo programa:
  831. Grupni sistemi – jobs - poslovi
  832. Time-shared sistemi – korisnički programi ili zadaci (tasks)
  833. U literaturi se termini job, task i process koriste identično.
  834.  
  835. 1. def: Proces je program u stanju izvršavanja (running)
  836. (kontekst procesa: proces se izvršava u svom kontekstu).
  837. Proces sadrži:
  838. CPU registre {programski brojač i ostali CPU registri}
  839. Memorijsku sekciju
  840. tekst
  841. stek (stack)
  842. sekcija podataka
  843. I/O resursi: {datoteke, I/O uređaji}
  844. OS struktura
  845. 2. def: Proces je unija 4 konteksta:
  846. Register context
  847. Memory context
  848. IO context
  849. OS kontext
  850. Stanja procesa
  851. U toku izvršavanja proces menja stanja:
  852.  
  853. New (novi): Proces je upravo kreiran.
  854.  
  855. Ready (spreman): Proces je spreman za rad ali čeka da mu se dodeli CPU.
  856.  
  857. Running (izvršava se): Procesove Instrukcije se upravo izvršavaju (odnosi se na CPU)
  858.  
  859. Waiting (čekanje): Proces čeka da se neki događaj izvrši.
  860.  
  861. Terminated (završio): Proces je završio izvršavanje.
  862. Dijagram stanja procesa
  863. Running stanje i Dual-Mode Operation
  864. Mode Bit se ubacuje u računarski hardver
  865. da ukazuje na trenutni mode:
  866. monitor mode (0)
  867. ili
  868. user mod (1)
  869. Kada se javi greška ili prekid hardver prebacije u monitor mod.
  870. Sistemski pozivi
  871.  
  872. PCB (Process Control Block)
  873. Informacije vezane za svaki proces:
  874.  
  875. Stanje procesa
  876.  
  877. Programski brojač
  878.  
  879. Sadržaj CPU registara
  880.  
  881. Informacije o memoriji procesa
  882.  
  883. Lista otvorenih datoteka
  884.  
  885. Statističke informacije
  886.  
  887. Status I/O resursa
  888. PCB (Process Control Block)
  889. CPU prebacivanje od procesa do procesa
  890. Queue: red čekanja
  891. Red čekanja za poslove (Job queue):
  892. obuhvata sve procese u sistemu
  893.  
  894. Red čekanja za spremne procese (Ready queue):
  895. obuhvata sve procese
  896. smeštene u glavnoj memoriji
  897. spremne i čekaju na izvršenje
  898.  
  899. Redovi čekanja za I/O uređaje (Device queues):
  900. obuhvata procese koji
  901. čekaju na dodelu I/O uređaja
  902.  
  903. Proces se kreće između različitih redova čekanja
  904. Ready Queue and Various I/O Device Queues
  905. Prikaz raspoređivanja procesa
  906. Raspoređivači (Schedulers)
  907. Long-term (dugi, dugoročni) raspoređivač
  908. (ili raspoređivač poslova):
  909. selektuje procese
  910. i dovodi ih
  911. u red čekanja za spremne poslove (Ready queue)
  912.  
  913. Short-term (kratki, kratkoročni) raspoređivač
  914. (ili CPU raspoređivač):
  915. seletuje proces
  916. koji će se sledeći izvršiti
  917. i dodeljuje mu CPU
  918. Blok dijagram za medium-term (srednji) raspoređivač
  919. Raspoređivači (Schedulers)
  920. kratkoročni raspoređivač se poziva veoma često
  921. (millisekunde)  (mora biti brz).
  922.  
  923. dugoročni raspoređivač se ne poziva često
  924. (sekunde, minuti)  (može biti spor).
  925.  
  926. dugoročni raspoređivač reguliše stepen multiprogramiranja
  927.  
  928. Procese možemo podeliti:
  929. I/O intenzivne procese (IO bound process):
  930. najveći deo njihovog vremena izvršavanja otpada na I/O cikluse,
  931. relativno mala upotreba CPU
  932.  
  933. CPU intenzivne procese (CPU bound process):
  934. najveći deo svog vremena korsite na CPU izračunavanja,
  935. veoma velika upotreba CPU
  936. Prebacivanje konteksta (Context Switch)
  937. Kada se CPU prebacuje na drugi proces
  938. sistem mora sačuvati stanje starog procesa
  939. i
  940. učitati sačuvano stanje za novi proces
  941.  
  942. Prebacivanje konteksta (Context switch) =
  943. pamti stanje starog procesa
  944. +
  945. učitava sačuvano stanje novog procesa
  946.  
  947. Prebacivanje konteksta je gubitak vremena (overhead);
  948. sistem ne može raditi koristan posao dok prebacuje
  949.  
  950. Vreme zavisi od hardverskih performansi
  951. Kreiranje procesa (Process Creation)
  952. Kreiranje:
  953. Roditelj proces kreira dete proces
  954. koji, dalje kreira druge procese
  955. i formira stablo procesa
  956.  
  957. Deljenje resursa (Resource sharing)
  958. Roditelj i dete procesi dele sve resurse
  959. Dete proces deli podskup od roditeljskih resursa
  960. Roditelj i dete proces ne dele resurse
  961.  
  962. Izvršavanje (Execution)
  963. Roditelj i dete procesi se izvršavaju konkurentno
  964. Rioditelj proces čeka da dete proces završi aktivnosti
  965.  
  966. Kreiranje procesa
  967. Memorijski adresni prostor
  968. Dete proces kopira adresni prostor roditelja
  969. Dete proces dobija program koji puni njegov adresni prostor.
  970.  
  971. UNIX primeri
  972.  
  973. fork sistemski poziv kreira novi proces
  974.  
  975. exec sistemski poziv se koristi posle fork
  976. koji puni adresni prostor novim programom
  977. Kreiranje procesa (fork)
  978.  
  979. /* fork drugi proces*/
  980. pid = fork ();
  981.  
  982. if (pid == 0 )
  983. { /*dete proces*/
  984. execlp(“/bin/ls”, “ls”, NULL);
  985. }
  986.  
  987. else /*roditelj proces*/
  988.  
  989. /*roditelj će čekati da dete završi*/
  990. wait(NULL);
  991. printf(“Dete je završilo");
  992. exit (0);
  993. } }
  994. Stablo procesa na UNIX sistemu
  995. Završetak procesa (Process Termination)
  996. (exit) = normal termination
  997. Proces izvršava poslednju aktivnost i
  998. traži od operativnog sistema da ga obriše (exit)
  999. Dete proces vraća izlazne podatke roditelju (preko wait)
  1000. Resursi koji su pripadali procesu detetu se oslobađaju
  1001.  
  1002. (abort) = abnormal termination
  1003. Roditelj proces može prekinuti izvršavanje dece procesa, ako:
  1004. Dete proces je prekoračilo dodeljene resurse
  1005. Aktivnost koju obavlja dete proces nije više potrebna
  1006. Ako proces roditelj završi aktivnosti:
  1007. neki operativni sistemi ne dozvoljavaju da dete proces nastavi sa izvršavanjem ako je roditelj završio
  1008. Nasilno prekidanje (Cascading termination)
  1009. Saradnja među procesima
  1010. Nezavisni procesi:
  1011. nemogu uticati ili ne trpe uticaj
  1012. od strane drugih procesa.
  1013. (ne dele podatke, ili resurse)
  1014.  
  1015. Kooperativni procesi:
  1016. mogu uticati ili da se na njih utiče
  1017. od strane drugih procesa.
  1018. (dele podatke, ill resurse)
  1019.  
  1020. Prednosti saradnje među procesima:
  1021. Deljenje informacija
  1022. Ubrzavanje rada
  1023. Modularnost
  1024. Pogodnost
  1025. Problem Proizvođač-Potrošač
  1026. Paradigma za kooperativne procese,
  1027. proizvođač proces proizvodi informacije
  1028. potrošač koji troši informacije
  1029. Bafer (buffer)
  1030. bafer beskonačnog kapaciteta (unbounded-buffer) nema ograničenje u veličini bafera.
  1031. ograničeni bafer (bounded-buffer) ima ograničenu veličinu bafera
  1032.  
  1033. Sinhronizacija procesa:
  1034. turn
  1035. flags
  1036. semaphores
  1037. monitor
  1038. IPC (sistem poruka)
  1039. Bounded-Buffer – Rešenje za deljenje memorije
  1040. Deljeni podaci
  1041. #define BUFFER_SIZE N
  1042. typedef struct
  1043. {
  1044. . . .
  1045. } item;
  1046. item buffer[BUFFER_SIZE];
  1047. int in = 0; #first free buffer position
  1048. int out = 0; #first full buffer position
  1049.  
  1050. Rešenje je tačno, ali može koristiti samo BUFFER_SIZE-1 elemenata
  1051. Bounded-Buffer – Proces proizvođač
  1052.  
  1053. item nextProduced; int in = 0; #in ->first free buffer position
  1054. int out = 0; #out->first full buffer position
  1055. while (1)
  1056. {
  1057. while (((in + 1) % BUFFER_SIZE) == out)
  1058.  
  1059. ; /* buffer is full, do nothing */
  1060.  
  1061. buffer[in] = nextProduced;
  1062.  
  1063. in = (in + 1) % BUFFER_SIZE;
  1064.  
  1065. }
  1066.  
  1067.  
  1068. Bounded-Buffer – Proces potrošač
  1069.  
  1070. item nextConsumed; int in = 0; #first free buffer position
  1071. int out = 0; #first full buffer position
  1072.  
  1073. while (1)
  1074. {
  1075.  
  1076. while (in == out) #empty
  1077. ; /* do nothing */
  1078.  
  1079. nextConsumed = buffer[out];
  1080.  
  1081. out = (out + 1) % BUFFER_SIZE;
  1082. }
  1083.  
  1084.  
  1085.  
  1086.  
  1087. Interprocesna komunikacija (IPC)
  1088. Mehanizam za procese koji omogućava da:
  1089. komuniciraju
  1090.  
  1091. sinhronizuju njihove akcije
  1092.  
  1093. Tri metode:
  1094. signali (UNIX)
  1095.  
  1096. deljena memorija
  1097.  
  1098. sistem poruka
  1099. Komunikacioni model
  1100. (IPC): poruke
  1101. Sistem poruka:
  1102. procesi razmenjuju poruke
  1103. procesi komuniciraju sa ostalim procesima
  1104. bez deljenja memorije
  1105.  
  1106. IPC sistem obezbeđuje dve operacije:
  1107. slanje poruke (send message) – poruke fiksne ili promenljive veličine
  1108. prijem poruke (receive message)
  1109.  
  1110. Ako procesi P i Q žele da komuniciraju, oni trebaju da:
  1111. uspostave komunikacioni link između njih
  1112. poruke razmenjuju preko send/receive operacija
  1113.  
  1114. Implementacija komunikacionog linka:
  1115. fizička (npr., deljena memorija, hardverska magistrala)
  1116. logička (npr., logičke osobine)
  1117. Pitanja vezana za implementaciju
  1118. Kako su linkovi uspostavljeni?
  1119.  
  1120. Da li se linku mogu pridružiti više od dva procesa?
  1121.  
  1122. Koliko linkova može postojati
  1123. između svakog para komunikacionih procesa?
  1124.  
  1125. Šta je kapacitet linka?
  1126.  
  1127. Da li je veličina poruke koju link može preneti: fiksna ili promenljiva?
  1128.  
  1129. Da li je link unidirectional ili bi-directional?
  1130. Direktna komunikacija
  1131. Procesi trebaju da imaju ime i to svaki različito:
  1132. send (P, message) – poslaće poruku procesu P
  1133.  
  1134. receive (Q, message) – primiće poruku od procesa Q
  1135.  
  1136. Osobine direktne komunikacije:
  1137.  
  1138. Veze se uspostavljaju automatski
  1139.  
  1140. Veza je udružena sa tačno jednim parom komunikacionih procesa
  1141.  
  1142. Između svakog para postoji tačno jedna veza
  1143.  
  1144. Veza može biti unidirectional, ali se koristi i bi-directional
  1145. Indirektna komunikacija
  1146. Poruke se šalju i primaju preko poštanskih sadučića (mailboxes)
  1147. (ili preko portova)
  1148.  
  1149. Svako sanduče ima jedinstven id
  1150.  
  1151. Procesi mogu komunicirati samo ako dele sanduče
  1152.  
  1153. Osobine indirektne komunikacije:
  1154.  
  1155. Veza se uspostavlja samo ako procesi dele zajedničko sanduče
  1156.  
  1157. Vezi se mogu pridružiti više procesa
  1158.  
  1159. Između svakog para može postojati više različitih veza
  1160.  
  1161. Veza može biti unidirectional ili bi-directional.
  1162. Indirektna komunikacija
  1163. Operacije
  1164. kreiranje novog sandučeta
  1165.  
  1166. slanje i primanje poruka kroz sanduče
  1167.  
  1168. brisanje sandučeta
  1169.  
  1170. Naredbe za slanje:
  1171.  
  1172. send(A, message) – poslaće poruku u sanduče A
  1173.  
  1174. receive(A, message) – primiće poruku iz sanduče A
  1175. Indirektna komunikacija
  1176. Deljenje sandučeta
  1177. P1, P2, i P3 dele sanduče A.
  1178. P1, šalje; P2 i P3 primaju.
  1179. Ko je dobio poruku?
  1180.  
  1181. Rešenje:
  1182. 1. Dozvoliti da se link uspostavlja između najviše dva procesa
  1183.  
  1184. 2. Dozvoliti da samo jedan proces može obaviti prijem u jednom trenutku
  1185.  
  1186. 3. Dozvoliti da sistem proizvoljno bira primaoca
  1187. Pošiljaoc je obavestio ko je bio primaoc.
  1188. Sinhronizacija
  1189. Sistem poruka može biti blokirajući ili neblokirajući
  1190.  
  1191. blokirajući funkcioniše sinhrono
  1192.  
  1193. neblokirajući funkcioniše asinhrono
  1194.  
  1195. slanje i primanje poruka može biti:
  1196. blokirajuće
  1197. ili
  1198. neblokirajuće
  1199. Baferisanje
  1200. Message Buffer = Red u kom poruka čeka ;
  1201. realizacija na jedan od 3 načina:
  1202. Nulti kapacitet (Zero capacity): 0 poruka se čeka Pošiljalac mora čekati primaoca (rendezvous).
  1203.  
  1204. Ograničen kapacitet (Bounded capacity): ograničena dužina na n poruka Pošiljalac mora da sačeka ako je bafer pun
  1205.  
  1206. Neograničen kapacitet (Unbounded capacity) – neograničena dužina Pošiljalac nikad ne čeka
  1207.  
  1208. Potvrda: (P proces šalje poruku procesu Q)
  1209. Proces P Proces Q
  1210. send(Q, message) receive(P, messages)
  1211. receive(Q, message) send(P, “acknowledgment”)
  1212.  
  1213. Osobine poruka
  1214. Postoje tri vrste poruka koje razmenjuju procesi:
  1215. Fiksne veličine
  1216. Promenljive veličine
  1217. Tipske poruke
  1218.  
  1219. Druge osobine (waiting):
  1220. Nikad ne čeka
  1221. Čeka za odgovor (moguć deadlock)
  1222.  
  1223. Izgubljene poruke (lost messages)
  1224. otkrivanje
  1225. ponovno prenošenje
  1226.  
  1227. Komunikacija u klijent-server sistemima
  1228. Sockets
  1229.  
  1230. Poziv udaljene procedure (Remote Procedure Calls -RPC)
  1231.  
  1232.  
  1233. Sockets
  1234. BSD način za IPC između različitih mašina
  1235.  
  1236. Socket se definiše kao krajnja tačka komunikacije
  1237.  
  1238. Socket = Povezuje IP adresu i port
  1239.  
  1240. Socket 161.25.19.8:1625 se obraća
  1241. portu 1625
  1242. na hostu 161.25.19.8
  1243.  
  1244. Komunikacija se odvija između para socketa
  1245. Socket model
  1246. Socket komunikacija
  1247. Poziv udaljene procedure (RPC)
  1248. Poziv udaljene procedure (RPC) je abstrakcija poziva procedure
  1249. između procesa na mrežnom sistemu
  1250.  
  1251. Stubovi: klijentska strana je proxy za aktuelnu proceduru na serveru
  1252.  
  1253. Stub klijentske strane:
  1254. pronalazi server
  1255. šalje parametre
  1256.  
  1257. Stub serverske strane:
  1258. prima ovu poruku
  1259. raspakuje parametre
  1260. izvršava proceduru na serveru.
  1261. Izvršavanje RPC
  1262.  
  1263.  
  1264.  
  1265. Niti (Threads)
  1266. Opšti pregled
  1267.  
  1268. Višenitni modeli (Multithreading Models)
  1269.  
  1270. Osobine niti
  1271.  
  1272. Pthreads
  1273.  
  1274. Solaris 2 niti
  1275.  
  1276. Windows 2000 niti
  1277.  
  1278. Linux niti
  1279.  
  1280. Jedno-nitni i više-nitni procesi
  1281. Editor (single/multi threaded)
  1282. Web-Browser (single/multi threaded)
  1283. Dobre osobine
  1284. Vreme odziva (Responsiveness)
  1285. Deljenje resursa (Resource Sharing)
  1286. Ekonomičnost
  1287. Bolje iskorišćenje višeprocesorske arhitekture
  1288. Korisničke niti (User Threads)
  1289. Nitima upravlja korisnička biblioteka za niti
  1290. Primeri:
  1291. - POSIX Pthreads
  1292.  
  1293. - Mach C-threads
  1294.  
  1295. - Solaris threads
  1296. Kernelske niti (Kernel Threads)
  1297. Podržava ih kernel
  1298. Primeri:
  1299. - Windows 95/98/NT/2000
  1300.  
  1301. - Solaris
  1302.  
  1303. - Tru64 UNIX
  1304.  
  1305. - BeOS
  1306.  
  1307. - Linux
  1308. Višenitni modeli
  1309. Više u jednu (Many-to-One)
  1310. Jedna u jednu (One-to-One)
  1311. Više u više (Many-to-Many)
  1312.  
  1313. Model više u jednu
  1314. Više korisničkih niti
  1315. mapira se u
  1316. jednu kernelsku nit
  1317. Koristi se na sistemima koji ne podržavaju kernelske niti
  1318. Model više u jednu
  1319. Model jedna u jednu
  1320. Svaka korisnička nit se mapira u kernelsku nit
  1321. Primeri:
  1322.  
  1323. - Windows 95/98/NT/2000
  1324.  
  1325. - OS/2
  1326. Model jedna u jednu
  1327. Model više u više
  1328. Dozvoljava da više korisničkih niti
  1329. bude mapirano
  1330. u više kernelskih niti
  1331.  
  1332. Dozvoljava operativnom sistemu
  1333. da kreira
  1334. dovoljan broj kernelskih niti
  1335.  
  1336. Solaris 2
  1337.  
  1338. Windows NT/2000 sa ThreadFiber paketom
  1339. Model više u više
  1340. Osobine niti
  1341. Fork() i exec() sistemski pozivi
  1342.  
  1343. Prekidanje niti
  1344.  
  1345. Upravljanje signalima
  1346.  
  1347. Gomile niti (Thread pools)
  1348.  
  1349. Specifični podaci za nit (Thread specific data)
  1350. Pthreads
  1351. POSIX standard (IEEE 1003.1c) = pravila za:
  1352. kreiranje niti
  1353. i
  1354. njihovu sinhronizaciju
  1355.  
  1356. Postoji API i Pthread biblioteka na korisničkom nivou, koja programeru omogućava kreiranje niti
  1357.  
  1358. Prihvaćeni su u UNIX operativnim sistemima
  1359.  
  1360. Solaris 2 niti
  1361. Solaris procesi
  1362. Windows 2000 niti
  1363. Primenjuju one-to-one mapiranje
  1364.  
  1365. Svaka nit sadrži:
  1366. - nit id
  1367. - registarski set
  1368. - korisnički stek i kernelski stek
  1369. - mesto za privatne poruke
  1370. Linux niti
  1371. Linux koristi termin tasks umesto threads
  1372.  
  1373. Kreiranje niti se izvršava kroz clone() sistemski poziv.
  1374.  
  1375. Clone() dozvoljava
  1376. da dete proces deli adresni prostor
  1377. sa roditeljem procesom
  1378.  
  1379.  
  1380.  
  1381. Raspoređivanje procesa (CPU Scheduling)
  1382. Osnovni koncepti
  1383.  
  1384. Kriterijumi za raspoređivanje
  1385.  
  1386. Algoritmi za raspoređivanje
  1387.  
  1388. Raspoređivanje u višeprocesorskoj okolini
  1389.  
  1390. Raspoređivanje u realnom vremenu
  1391.  
  1392. Ispitivanje algoritama
  1393. Osnovni koncepti
  1394. Maksimalno iskorišćenje CPU-a
  1395. postiže se
  1396. multiprogramiranjem
  1397.  
  1398. CPU–I/O Burst Cycle:
  1399. Izvršavanje procesa se sastoji od
  1400. ciklusa CPU izvršavanja
  1401. i
  1402. ciklusa čekanja na I/O operacije
  1403.  
  1404. CPU burst distribucija
  1405.  
  1406. malo dugačkih-burst procesa
  1407.  
  1408. mnogo kratkih-burst procesa
  1409. Naizmenična sekvenca CPU i I/O Bursts
  1410. Histogram CPU-burst vremena
  1411. CPU raspoređivač (CPU Scheduler)
  1412. Selektuje iz reda čekanja procese u memoriju
  1413. koji su spremni da se izvrše,
  1414. i dodeljuje CPU jednom od njih
  1415.  
  1416.  
  1417. CPU raspoređivanje se dešava kada se proces:
  1418. 1. Prebacuje iz stanja izvršavanja u blokirano stanje
  1419.  
  1420. 2. Prebacuje iz stanja izvršavanja u stanje spremnosti
  1421.  
  1422. 3. Prebacuje iz blokiranog stanja u stanje spremnosti
  1423.  
  1424. 4. Završi svoje aktivnosti
  1425.  
  1426. Raspoređivanje koje se dešava pod okolnostima 1 i 4 je bez prekidanja (non-preemptive)
  1427.  
  1428. Raspoređivanje pod drugim okolnostima je preemptive
  1429. Dispečer (Dispatcher)
  1430. Dispečer modul
  1431. daje kontrolu CPU procesu
  1432. koji je izabran od strane kratkoročnog raspoređivača
  1433.  
  1434. Funkcije dispečera:
  1435. prebacivanje konteksta
  1436.  
  1437. prebacivanje u korisnički režim rada
  1438.  
  1439. skok na odgovarajuću lokaciju izabranog procesa koji će omogućiti njegovo izvršavanje
  1440.  
  1441. Kašnjenje dispečera (Dispatch latency):
  1442. vreme koje je potrebno dispečeru
  1443. da zaustavi jedan proces i
  1444. startuje izvršavanje drugog.
  1445. Kriterijumi za raspoređivanje
  1446. Iskorišćenje CPU
  1447. održavati CPU zauzetim (busy) kad god je moguće
  1448.  
  1449. Propusna moć (Throughput):
  1450. broj procesa izvršenih u jedinici vremena
  1451.  
  1452. Vreme za kompletiranje procesa (Turnaround time, TA, ATA):
  1453. ukupna količina vremena potrebna da se izvrši jedan proces
  1454.  
  1455. Vreme čekanja (Waiting time, WT, AWT) –
  1456. ukupno vreme koje proces provede u redu čekanja spremnih procesa (ready queue)
  1457.  
  1458. Vreme odziva (Response time)
  1459. vreme kada se uputi neki zahtev
  1460. pa do pojave prvih rezultatata procesa
  1461. Optimizacija kriterijuma
  1462. Maksimalno iskorišćenje CPU-a
  1463.  
  1464. Maksimalna propusna moć
  1465.  
  1466. Minimalno vreme za kompletiranje procesa
  1467.  
  1468. Minimalno vreme čekanja
  1469.  
  1470. Mininimalno vreme odziva
  1471. Algoritmi
  1472. FCFS
  1473.  
  1474. SJF <-> SRTF
  1475.  
  1476. RR
  1477.  
  1478. Priority
  1479.  
  1480. Multilevel
  1481. First-Come, First-Served (FCFS) raspoređivanje
  1482. Proces Vreme izvršavanja
  1483. P1 24
  1484. P2 3
  1485. P3 3
  1486. Pretpostavimo da procesi dolaze sledećim redom: P1 , P2 , P3 Gantt karta za raspoređivanje je:
  1487.  
  1488. Vreme čekanja za P1 = 0; P2 = 24; P3 = 27
  1489.  
  1490. Srednje vreme čekanja: (0 + 24 + 27)/3 = 17
  1491. FCFS raspoređivanje
  1492. Pretpostavimo da procesi dolaze sledećim redom:
  1493. P2 , P3 , P1 .
  1494. Gantt karta za raspoređivanje je:
  1495.  
  1496.  
  1497.  
  1498.  
  1499.  
  1500.  
  1501. Vreme čekanja za P1 = 6; P2 = 0; P3 = 3
  1502.  
  1503. Srednje vreme čekanja: (6 + 0 + 3)/3 = 3
  1504.  
  1505. Mnogo bolje nego prošli slučaj (AWT je bio 17)
  1506.  
  1507. Efekat konvoja:
  1508. kratki procesi
  1509. iza
  1510. dugačkih procesa
  1511. Shortest-Job-First (SJF) raspoređivanje
  1512. Svaki proces određuje dužinu svog sledećeg CPU ciklusa
  1513.  
  1514. Ove dužine služe za raspoređivanje procesa sa najkraćim vremenom
  1515.  
  1516. Dve šeme:
  1517. SJF: bez pretpražnjenja (nonpreemptive):
  1518. kada je CPU dat procesu
  1519. N emože biti oduzet
  1520. dok se proces ne izvrši do kraja.
  1521.  
  1522. SRTF: sa pretpražnjenjem (preemptive):
  1523. ako dođe novi proces
  1524. sa vremenom izvršavanja manjim od
  1525. preostalog vremena izvršavanja tekućeg procesa,
  1526. nastaje predpražnjenje.
  1527.  
  1528. Ova šema je poznata kao Shortest-Remaining-Time-First (SRTF)
  1529.  
  1530. SJF je optimalan – daje najmanje srednje vreme čekanja za dati skup procesa.
  1531. Određivanje dužine sledećeg CPU ciklusa
  1532. Može se samo proceniti dužina
  1533.  
  1534. Procena se obavlja tako što se
  1535. na bazi svih prethodnih CPU ciklusa,
  1536. odredi eksponencijalna srednja vrednost
  1537.  
  1538.  
  1539.  
  1540. Primer eksponencijalne srednje vrednosti
  1541.  =0
  1542. n+1 = n
  1543. Skorija istorija se neračuna (stvarne dužine nemaju efekta)
  1544.  
  1545.  =1
  1546. n+1 = tn
  1547. Samo poslednji CPU ciklus se računa
  1548.  
  1549. Ako proširimo formulu dobijamo:
  1550. n+1 =  tn+(1 - )  tn -1 + …
  1551. +(1 -  )j  tn -j + …
  1552. +(1 -  )n t0 +(1 -  )n+10
  1553.  
  1554. Ako su oba  i (1 - ) manje od ili jednako 1,
  1555. svaki sledeći termin
  1556. je manje težine od prethodnika
  1557. Procena trajanja sledećeg CPU ciklusa
  1558. Primer SJF bez pretpražnjenja
  1559. novo raspoređivanje: samo kad proces završi
  1560. Proces Vreme nailaska Vreme izvršavanja
  1561. P1 0.0 7
  1562. P2 2.0 4
  1563. P3 4.0 1
  1564. P4 5.0 4
  1565. SJF (non-preemptive)
  1566.  
  1567.  
  1568.  
  1569.  
  1570.  
  1571.  
  1572. Srednje vreme čekanja = (0 + 6 + 3 + 7)/4 = 4
  1573. (gleda se vreme nailaska)
  1574. za P2 i P4, se primenjuje algoritam FIFO
  1575. Primer SJF sa pretpražnjenjem (SRFT)
  1576. novo raspoređivanje: kad proces završi i kad naidje novi proces
  1577. pogledati u ready queue: svaki novi proces izaziva novo rasporedjivanje
  1578.  
  1579. Proces Vreme nailaska Vreme izvršavanja
  1580. P1 0.0 7
  1581. P2 2.0 4
  1582. P3 4.0 1
  1583. P4 5.0 4
  1584. SJF (sa pretpražnjenjem)
  1585.  
  1586.  
  1587.  
  1588.  
  1589. srednje vreme čekanja = (9 + 1 + 0 +2)/4 = 3
  1590. pogledati u ready queue: svaki novi proces izaziva novo rasporedjivanje
  1591. Prioriteno raspoređivanje
  1592. Prioritet (ceo broj) se dodeljuje svakom procesu
  1593.  
  1594. CPU alocira proces sa najvećim prioritetom (manji broj  veći prioritet)
  1595. sa pretpražnjenjem
  1596. bez pretpražnjenja
  1597.  
  1598. SJF je prioritetno raspoređivanje
  1599. gde je prioritet obrnuto proporcionalna funkcija od dužine trajanja sledećeg CPU ciklusa
  1600.  
  1601. Problem  zakucavanje
  1602. proces niskog prioriteta se možda nikad ne izvrši
  1603.  
  1604. Rešenje  Aging
  1605. sa vremenom čekanja raste prioritet procesa
  1606. Round Robin (RR)
  1607. Svaki proces ima malu količinu vremena (vremenski kvantum)
  1608. obično 10-100 millisekundi
  1609. Kada ovo vreme istekne
  1610. proces se prekida
  1611. i
  1612. ubacuje na kraju reda čekanja
  1613.  
  1614. Ako imamo
  1615. n procesa u redu čekanja i
  1616. ako je vremenski kvantum q, onda:
  1617. svakom procesu pripada procesor u odnosu 1/n
  1618. nijedan proces ne čeka više od (n-1)*q vremena na sledeći vremenski kvantum.
  1619.  
  1620. Performanse
  1621. veći q  FIFO
  1622. manji q  maksimalno ravnomerna raspodela CPU, ali i veoma često prebacivanje konteksta između procesa, a to znači veliki gubitak korisnog vremena .
  1623. Primer RR gde je vremenskim kvantum = 20
  1624. Proces Vreme izvršavanja
  1625. P1 53
  1626. P2 17
  1627. P3 68
  1628. P4 24
  1629. Gantt karta za raspoređivanje je:
  1630. Karakteristično,
  1631. veće srednje vreme završetka procesa u odnosu na SJF,
  1632. ali i bolje vreme odziva
  1633. Time Quantum and Context Switch Time
  1634. Turnaround Time Varies With The Time Quantum
  1635. Raspoređivanje u više redova
  1636. Red čekanja je podeljen u različite redove:
  1637. foreground (interactive)
  1638. background (batch)
  1639.  
  1640. Svaki red čekanja ima poseban algoritam za raspoređivanje:
  1641. foreground – RR
  1642. background – FCFS
  1643.  
  1644. Raspoređivanje između redova može biti:
  1645. Prioriteno raspoređivanje;
  1646. (npr., opslužuje sve iz prvog plana a onda iz drugog plana).
  1647. Mogućnost zakucavanja.
  1648.  
  1649. Time Slice (Deo vremena)
  1650. svaki red dobija procesor na neko vreme
  1651. a u tom vremenu selektuju se procesi iz tog reda;
  1652. npr., 80% za interaktivno red (RR)
  1653. 20% za pozadinski red (FCFS)
  1654. Raspoređivanje u više redova
  1655. Povratna sprega između redova čekanja
  1656. Proces se može pomerati između različitih redova;
  1657. aging može biti implementiran na sledeći način:
  1658.  
  1659. Multilevel-feedback-queue raspoređivač je definisan sledećim parametrima:
  1660. broj redova
  1661.  
  1662. raspoređivanje algoritama za svaki red
  1663.  
  1664. metod za određivanje kada proces može da pređe u red višeg prioriteta
  1665.  
  1666. metod za određivanje kada proces može da pređe u red nižeg prioriteta
  1667.  
  1668. metod koji određuje u koji će red proces ući po kreiranju
  1669. Primer Multilevel Feedback Queue
  1670. Tri reda:
  1671. Q0 – vremenski kvantum 8 milisekunde (RR)
  1672. Q1 – vremenski kvantum 16 milisekunde (RR)
  1673. Q2 – FCFS
  1674.  
  1675. Raspoređivanje
  1676. Novi posao ulazi u red Q0 koji je serviran uz pomoć FCFS.
  1677. Kada dobije CPU, posao ima 8 milisekunde.
  1678. Ako nije završio za 8 milisekunde, posao se pomera u red Q1
  1679.  
  1680. U red Q1 posao je opet serviran FCFS i dobija 16 dodatnih milisekundi
  1681.  
  1682. Ako još uvek nije završio, on je preempted i pomera se u red Q2.
  1683. Multilevel Feedback Queues-example
  1684.  
  1685. Višeprocesorsko raspoređivanje
  1686. CPU raspoređivanje je kompleksnije kad je dostupno više CPU-a
  1687. SMP: Homogeni procesori su u SMP
  1688. Svi CPU su identični
  1689. Pitanje je?
  1690. jedan isti ready queue (za sve procesore)
  1691. ili
  1692. poseban ready queue (za svaki CPU)
  1693. Load sharing
  1694. Svaki CPU = poseban ready queue,
  1695. jedan CPU može biti neaktivan
  1696. drugi veoma zauzet=>isti ready queue
  1697. U istoj oblasti podataka, svaki CPU mora biti programiran veoma pažljivo
  1698.  
  1699. Asimetrično multiprocesiranje:
  1700. svaki CPU ima specifičan cilj (jedan od njih je master)
  1701. samo jedan procesor ima pristup strukturama sistema podataka,
  1702. olakšava potrebu za deljenjem podataka
  1703. Rapoređivanje u realnom vremenu
  1704. Hard real-time systems:
  1705. zahteva da izvršavaju kritične poslove
  1706. u garantovanom vremenskom roku
  1707. Samo u sistemima bez diskova i virtuelne memorije
  1708.  
  1709. Soft real-time systems:
  1710. zahtevaju da im se
  1711. kritični procesi izvršavaju prioritetnije
  1712. nego drugi
  1713.  
  1714. Zahteva prioritetno raspoređivanje
  1715.  
  1716. Dispečersko kašnjenje mora da bude veoma malo
  1717.  
  1718. Vreme za dispečer (Dispatch Latency)
  1719. Ispitivanje algoritama
  1720. Simulacija: Deterministic modeling:
  1721. uzima poseban predeterminisan workload
  1722. i
  1723. definiše performanse svakog algoritma
  1724. za taj workload
  1725.  
  1726. Modeli za redove:
  1727. Broj redova, prioritet, pravila
  1728. Dužina
  1729. Nailazak procesa
  1730. Algoritam
  1731.  
  1732. Implementacija
  1733. Procena CPU raspoređivanja simulacijom
  1734.  
  1735.  
  1736.  
  1737.  
  1738.  
  1739. Sinhronizacija procesa
  1740. Pozadina
  1741.  
  1742. Problem kritične sekcije
  1743.  
  1744. Hardverska sinhronizacija
  1745.  
  1746. Semafori
  1747.  
  1748. Klasični problemi sinhronizacije
  1749.  
  1750. Kritični regioni
  1751.  
  1752. Monitori
  1753.  
  1754. Pozadina
  1755. Konkurentni pristup deljenim podacima
  1756. može dovesti do nekonzistencije podataka
  1757.  
  1758. Održavanje konzistencije podataka
  1759. zahteva mehanizme koji će da osiguraju
  1760. izvršavanje kooperativnih procesa u poretku (in order)
  1761.  
  1762. Solucija deljene memorije za problem bounded-buffer
  1763. dozvoljava više n – 1 elemenata u baferu
  1764. u isto vreme
  1765.  
  1766. Rešenje, gde se koriste svih N bafera, nije jednostavno
  1767. Pretpostavimo da želimo da izmenimo kôd za proizvođač-potrošač:
  1768. dodajući promenljivu counter
  1769. inicijalizovan na 0
  1770. inkrementiran svaki put kada se novi element doda u bafer
  1771. dekrementiran svaki put kada je elemenat izbačen iz bafera
  1772. Bounded-Buffer
  1773. Deljeni podaci (shared data)
  1774. in pokazuje na sledeći slobodan bafer
  1775. out pokazuje na prvi pun bafer
  1776. counter++ proizvođač; counter-- potrošač;
  1777.  
  1778. #define BUFFER_SIZE 10
  1779.  
  1780. typedef struct {
  1781. . . .
  1782. } item;
  1783.  
  1784. item buffer[BUFFER_SIZE];
  1785. int in = 0;
  1786. int out = 0;
  1787. int counter = 0;
  1788.  
  1789. Bounded-Buffer
  1790. Proces proizvođač
  1791.  
  1792. item nextProduced;
  1793. while (1) {
  1794. while (counter == BUFFER_SIZE)
  1795. ; /* ništa ne radi, bafer je pun */
  1796.  
  1797. buffer[in] = nextProduced;
  1798. in = (in + 1) % BUFFER_SIZE;
  1799. counter++;
  1800. }
  1801.  
  1802.  
  1803. Bounded-Buffer
  1804. Proces potrošač
  1805.  
  1806. item nextConsumed;
  1807. while (1) {
  1808. while (counter == 0)
  1809. ; /* ništa ne radi, bafer je prazan */
  1810.  
  1811. nextConsumed = buffer[out];
  1812. out = (out + 1) % BUFFER_SIZE;
  1813. counter--;
  1814. }
  1815.  
  1816.  
  1817.  
  1818. Bounded Buffer
  1819. Naredbe counter++; counter--; moraju se izvršavati atomski
  1820.  
  1821. Atomska operacija znači
  1822. operacija koja je u celosti izvršena
  1823. bez prekida
  1824. Bounded Buffer
  1825. Naredba “counter++” može biti implementirana u mašinskom jeziku kao: register1 = counter
  1826. register1 = register1 + 1 counter = register1
  1827. Naredba “counter--” može biti implementirana kao: register2 = counter register2 = register2 – 1 counter = register2
  1828. Bounded Buffer
  1829. Ako obojica, proizvođač i potrošač
  1830. pokušaju da ažuriraju bafer (brojač) konkurentno,
  1831. asemblerske naredbe mogu imati preklapanje (interleaving)
  1832.  
  1833. Interleaving zavisi od toga
  1834. kako su proizvođač i potrošač procesi raspoređeni
  1835. Bounded Buffer
  1836. Imamo counter inicijalizovan na 5
  1837. counter++; counter--;
  1838. Jedan od redosleda naredbi je: proizvođač: register1 = counter (register1 = 5) proizvođač: register1 = register1 + 1 (register1 = 6)
  1839. potrošač: register2 = counter (register2 = 5) potrošač: register2 = register2 – 1 (register2 = 4)
  1840. proizvođač: counter = register1 (counter = 6) potrošač: counter = register2 (counter = 4)
  1841. Vrednost counter može biti 4 ili 6,
  1842. gde tačan rezultat moze biti 5
  1843. Stanje trke (Race Condition)
  1844. Stanje trke:
  1845. Situacija gde više procesa
  1846. Pristupaju i upravljaju deljenim podacima konkurentno
  1847.  
  1848. Konačna vrednost deljenih podataka
  1849. zavisi od toga
  1850. koji proces završava poslednji
  1851.  
  1852. Da bi se izbeglo stanje trke,
  1853. konkurentni procesi
  1854. moraju biti sinhronizovani
  1855. Problem kritične sekcije (Critical section)
  1856. n procesa
  1857. svi se takmiče da koriste neke od deljenih podataka
  1858.  
  1859. Svaki proces ima deo koda,
  1860. zvani kritična sekcija,
  1861. u kome pristupa deljenim podacima
  1862.  
  1863. Problem:
  1864.  
  1865. kad je jedan proces udje u svoju kritičnu sekciju,
  1866.  
  1867. ni jedan drugi proces be sme da udje u svoju kritičnu sekciju
  1868. Rešenje problema kritične sekcije
  1869. Međusobno isključenje (Mutual Exclusion).
  1870. Ako se proces Pi izvršava u svojoj kritičnoj sekciji,
  1871. onda ni jedan drugi proces
  1872. ne može da se izvršava u istoj kritičnoj sekciji
  1873.  
  1874. Progres (Progress)
  1875. Ako se nijedan proces ne izvršava u svojoj kritičnoj sekciji a
  1876. postoje neki procesi koji žele da uđu u svoju kritičnu sekciju, onda selekcija procesa koji hoće da udje u kritičnu sekciju
  1877. nemože biti odložena u nedogled
  1878.  
  1879. Ograničeno čekanje (Bounded Waiting)
  1880. Ograničenje (bound) mora postojati
  1881. od trenutka kada proces da zahtev da uđe u svoju kritičnu sekciju
  1882. sve dok zahtev ne bude prihvaćen
  1883.  
  1884.  
  1885.  
  1886. Pretpostavka je da se svaki proces izvršava na nonzero brzini
  1887. Nema pretpostavke vezane za relativnu brzinu n procesa.
  1888. Inicijalni pokušaj za rešenje problema
  1889. Samo 2 procesa, P0 i P1
  1890.  
  1891. Generalna struktura procesa Pi (drugi proces Pj)
  1892.  
  1893. do {
  1894. entry section
  1895. critical section
  1896. exit section
  1897. reminder section
  1898. } while (1);
  1899.  
  1900. Procesi mogu deliti neke zajedničke promenljive
  1901. da sinhronizuju njihove akcije
  1902. Algoritam 1 (strict alternation)
  1903. Deljene promenljive:
  1904. int turn; initially turn = 0
  1905. if turn = i  Pi može ući u svojoj kritičnoj sekciji
  1906.  
  1907. Proces P0 Proces P1
  1908. do { do {
  1909. while (turn != 0) ; /*(entry section)*/ while (turn != 1) ;
  1910. critical section critical section
  1911. turn = 1; /*exit section*/ turn = 0;
  1912. ……reminder section …… reminder section
  1913. } while (1); } while (1);
  1914.  
  1915. Zadovoljava međusobno isključenje, ali ne progres (P0, P1, P0, P1)
  1916. (ako P1 ne uđe u svoj CS, P0 nikad neće ući)
  1917. Algorithm 2 (No SA, but wrong)
  1918. Deljene promenljive
  1919. boolean flag[2]; initially flag [0] = flag [1] = false.
  1920. flag [i] = true  Pi spreman da uđe u kritičnoj sekciji
  1921.  
  1922. Proces Pi
  1923. do {
  1924. flag[i] = true; while (flag[j]) ; critical section
  1925. flag [i] = false;
  1926. remainder section
  1927. } while (1);
  1928.  
  1929. Zadovoljava međusobno isključenje, ali ne progress
  1930. T0: P0 postavlja flag[0]=true; CPU je preempt-ovan u P1
  1931. T1: P1 postavlja flag[1]=true; oba procesa se blokiraju zauvek
  1932.  
  1933. Algoritam 3 Dekker-Peterson
  1934. Kombinovane deljene promenljive algoritma 1 i 2.
  1935.  
  1936. Proces Pi
  1937. do {
  1938. flag [i] = true; turn = j; /* daje šansu drugom procesu*/ while (flag [j] and turn = j) ;
  1939.  
  1940. critical section
  1941.  
  1942. flag [i] = false;
  1943.  
  1944. remainder section
  1945. } while (1);
  1946.  
  1947. Sva tri zahteva se ispunavaju;
  1948. rešava problem kritične sekcije za dva procesa.
  1949. Bakery Algorithm
  1950. Pre ulaska u kritičnu sekciju,
  1951. proces dobija broj
  1952.  
  1953. Onaj koji ima najmanji broj ulazi u kritičnu sekciju
  1954.  
  1955. Ako procesi Pi i Pj dobiju isti broj,
  1956. if i < j, (i, j predstavlja vreme kreiranja procesa, ili PID)
  1957. onda Pi se prvi izvršava; a ako ne Pj je se prvi izvršava
  1958. (prim. proces dobije broj,
  1959. onda je uspavan proces sa istim brojem probuđen)
  1960.  
  1961. Šema brojeva uvek generiše brojeve od najmanjeg do najvećeg;
  1962. prim., 1,2,3,3,3,3,4,5...
  1963. Bakery Algorithm
  1964. Notiranje < lexicographical order (ticket #, process id #)
  1965.  
  1966. (a,b) < (c,d)
  1967. if a < c
  1968. ili
  1969. if a = c and b < d
  1970.  
  1971. max (a0,…, an-1) je broj k, tako da k  ai for i - 0, …, n – 1
  1972.  
  1973. Deljeni podaci:
  1974. boolean choosing[n];
  1975. int number[n];
  1976.  
  1977. Strukture podataka su inicijalizovane na false i 0 respektivno
  1978. Bakery Algorithm
  1979. do {
  1980.  
  1981. choosing[i] = true; #čeka da dobije broj
  1982. number[i] = max(number[0], number[1], …, number [n – 1])+1;
  1983. choosing[i] = false;
  1984.  
  1985. for (j = 0; j < n; j++) {
  1986. while (choosing[j]) ;
  1987. while ((number[j] != 0) && (number[j],j) < (number[i],i))) ;
  1988. }
  1989. critical section
  1990.  
  1991. number[i] = 0;
  1992.  
  1993. remainder section
  1994.  
  1995. } while (1);
  1996. Hardverska sinhronizacija
  1997. Testira i modifikuje sadržaj reči, atomski
  1998.  
  1999.  
  2000. boolean TestAndSet(boolean &target)
  2001. {
  2002. boolean rv = target;
  2003.  
  2004. target = true;
  2005.  
  2006. return rv;
  2007. }
  2008. Međusobno isključenje sa Test-and-Set
  2009. Deljeni podaci: boolean lock = false;
  2010. Proces Pi
  2011. do {
  2012. while (TestAndSet(lock)) ;
  2013. critical section
  2014. lock = false;
  2015. remainder section
  2016. }
  2017. Hardverska sinhronizacija
  2018. Atomska razmena dve promenljive
  2019. void Swap(boolean &a, boolean &b)
  2020. {
  2021. boolean temp = a;
  2022. a = b;
  2023. b = temp;
  2024. }
  2025. Međusobno isključenje sa razmenom
  2026. Deljeni podaci (inicijalizovani na false): boolean lock;
  2027.  
  2028. Proces Pi
  2029. do {
  2030. key = true;
  2031. while (key == true) Swap(lock,key);
  2032. critical section
  2033. lock = false;
  2034. remainder section
  2035. }
  2036. Semafori
  2037. Alat za sinhronizaciju koji ne zahteva busy waiting
  2038.  
  2039. Semafor S, integer promenljiva
  2040.  
  2041. može biti dostupan samo preko
  2042. dve atomske operacije:
  2043. wait (S):
  2044. while S 0 do no-op; S--;
  2045. signal (S):
  2046. S++;
  2047. Kritična sekcija n Procesa
  2048. Deljeni podaci:
  2049. semaphore mutex; //initially mutex = 1
  2050. Proces Pi: do {
  2051. wait(mutex);
  2052. critical section
  2053.  
  2054. signal(mutex);
  2055. remainder section
  2056. } while (1);
  2057.  
  2058.  
  2059. Implementacija semafora
  2060. Definisati semafor kao zapis
  2061.  
  2062. typedef struct {
  2063. int value; struct process *L; } semaphore;
  2064. Pretpostavlja dve jednostavne operacije:
  2065. block
  2066. prekida proces.
  2067.  
  2068. wakeup(P)
  2069. nastavlja izvršavanje blokiranog procesa P
  2070. Implementacija
  2071. Semafor operacije su sad definisane kao:
  2072. wait(S): S.value--;
  2073. if (S.value < 0)
  2074. {
  2075. add this process to S.L; block;
  2076. }
  2077. signal(S): S.value++;
  2078. if (S.value <= 0)
  2079. {
  2080. remove a process P from S.L; wakeup(P);
  2081. #but which one {FIFO, LIFO, priority}
  2082. }
  2083. Semafor kao glavni alat za sinhronizaciju
  2084. Izvršava se B u Pj samo kad se A izvrsi u Pi
  2085.  
  2086. Koristi se semafor flag inicijalizovan na 0
  2087.  
  2088. Kod:
  2089. Pi Pj
  2090.  
  2091. A wait(flag)
  2092. signal(flag) B
  2093. Zastoj i zakucavanje
  2094. Deadlock – dva ili više procesa beskonačno čekaju
  2095. na događaj koji se nikada neće dogoditi.
  2096.  
  2097. Neka S i Q budu dva semafora inicijalizovana na 1
  2098. Zastoj nastupa ako P0 (wait(S), onda P1 (wait(Q), sledeće čekanje stavlja proces u stanje zastoja
  2099. P0 P1
  2100. 1. wait(S); 2. wait(Q);
  2101. wait(Q); wait(S);
  2102. ...... ........
  2103. signal(S); signal(Q);
  2104. signal(Q) signal(S);
  2105.  
  2106.  
  2107. Zakucavanje – beskonacno blokiranje
  2108. Proces nikad nemože da se pomeri
  2109. iz semafor queue
  2110. u kojem je bio suspendovan
  2111. Dva tipa semafora
  2112. Brojački semafor:
  2113. integer vrednost nema ograničenje u domenu
  2114.  
  2115. Binarni semafor:
  2116. integer vrednost je ograničen samo izmedju 0 i 1;
  2117. može biti jednostavniji za inplementaciju
  2118.  
  2119. Može se inplementirati
  2120. brojački semafor S
  2121. kao binarni semafor
  2122. Klasični problemi sinhronizacije
  2123. Problem ograničenog bafera
  2124.  
  2125. Problem čitalaca i pisaca
  2126. Večera filozofa
  2127. Problem ograničenog bafera
  2128. Deljeni podaci semaphore full, empty, mutex; Initially: full = 0, empty = n, mutex = 1
  2129.  
  2130. empty: broji prazne bafere
  2131.  
  2132. full: broji pune bafere
  2133. Problem ograničenog bafera Proizvođač-proces
  2134.  
  2135. do {
  2136. …
  2137. produce an item in nextp
  2138. …
  2139. wait(empty); /*buffer full*/
  2140.  
  2141. wait(mutex); /* ulaz u kritičnu sekciju*/
  2142. …
  2143. add nextp to buffer
  2144. …
  2145. signal(mutex); /*oslobodi bafer i kritičnu sekciju*/
  2146.  
  2147. signal(full); /*uvećaj broj popunjenih elemenata u baferu*/
  2148. } while (1);
  2149.  
  2150. Problem ograničenog bafera Potrošač proces
  2151.  
  2152. do {
  2153. wait(full); /* bafer prazan*/
  2154. wait(mutex); /*ulaz u kritičnu sekciju*/
  2155. …
  2156. remove an item from buffer to nextc
  2157. …
  2158. signal(mutex); /*oslobodi bafer i kritičnu sekciju*/
  2159. signal(empty); /*uvećaj broj slobodnih mesta*/
  2160. …
  2161. consume the item in nextc
  2162. …
  2163. } while (1);
  2164. Problem čitalaca i pisaca
  2165.  
  2166. Pravila: (tipični deljeni fajlovi ili zapisi)
  2167. samo jedan pisac u jedinici vremena (pisac ima ekskluzivan pristup)
  2168. vise čitalaca, simultano
  2169. kad je pisac aktivan, nijedan čitalac nemoze imati pristup
  2170. kad je neki čitalac aktivan, nijedan pisac nema pristup
  2171.  
  2172. Deljeni podaci semaphore mutex, wrt; Initially mutex = 1, wrt = 1, readcount = 0
  2173.  
  2174. wrt = mutex za čitaoce i pisce
  2175.  
  2176. mutex = mutex za readcount update
  2177.  
  2178. readcount = broj procesa koji čita objekat
  2179. Problem čitalaca i pisca (writer proces)
  2180. wait(wrt); /* no readers*/
  2181. …
  2182. writing is performed
  2183. …
  2184. signal(wrt);
  2185. Problem čitalaca i pisca (reader proces)
  2186.  
  2187. wait(mutex);
  2188. readcount++;
  2189. if (readcount == 1) wait(wrt); /* prvi reader, čeka writer /*
  2190. else continue /*nije prvi, ima readers*/
  2191. signal(mutex);
  2192. …
  2193. reading is performed
  2194. …
  2195.  
  2196. wait(mutex);
  2197. readcount--;
  2198. if (readcount == 0) signal(wrt); #no readers, freeing wrt
  2199.  
  2200. signal(mutex); go to transactions
  2201. Večera filozofa
  2202. Deljni podaci semaphore chopstick[5];
  2203. Inicijalno sve vrednosti su 1
  2204. Večera filozofa
  2205. Filozof i:
  2206. do {
  2207. wait(chopstick[i])
  2208. wait(chopstick[(i+1) % 5])
  2209. …
  2210. eat
  2211. …
  2212. signal(chopstick[i]);
  2213. signal(chopstick[(i+1) % 5]);
  2214. …
  2215. think
  2216. …
  2217. } while (1);
  2218. Kritični regioni
  2219. Konstrukcija sinhronizacije visokog nivoa
  2220.  
  2221. Zajednička promenljiva v tipa T, je deklarisana kao:
  2222. v: shared T
  2223.  
  2224. Promenljivoj v se može pristupati samo unutar regiona naredbi S
  2225. region v when B do S gde je B logički izraz
  2226.  
  2227. Dok se naredba S izvršava,
  2228. nijedan drugi proces nemože pristupiti promenljivoj v
  2229.  
  2230. Kritični regioni
  2231. Regioni koje se oslanaju na istu deljenu promenljivu (v)
  2232. isključuju jedan drugog u vremenu
  2233. Uslovni kritični regioni
  2234.  
  2235. Kad proces pokuša da izvrši naredbu regiona,
  2236. logički izraz B se ispituje:
  2237. Ako je B true
  2238. naredba S se izvršava
  2239. Ako je B false
  2240. proces se blokira dok B ne postane true
  2241. i
  2242. nema drugih proces u tom regionu koji je asociran sa v
  2243. Primer – Bounded Buffer
  2244. Deljeni podaci:
  2245. struct buffer #all in structure is shared
  2246. {
  2247. int pool[n];
  2248. int count, in, out;
  2249. }
  2250. Bounded Buffer (Proizvođač proces)
  2251. Proizvođač proces ubacuje nextp u zajednički bafer
  2252. region buffer when( count < n)
  2253. { pool[in] = nextp; in:= (in+1) % n; count++; }
  2254.  
  2255. Bounded Buffer (Potrošač proces)
  2256. Proces potrošač pomera element iz zajedničkog bafera i postavlja u nextc
  2257. region buffer when (count > 0)
  2258. {
  2259. nextc = pool[out]; out = (out+1) % n; count--; }
  2260. Monitori
  2261. Konstrukcija sinhronizacije visokog nivoa koja omogućava sigurno deljenje jednog apstraktnog tipa podatka među konkurentnim procesima.
  2262. monitor monitor-name
  2263. {
  2264. shared variable declarations
  2265. procedure body P1 (…) {
  2266. . . .
  2267. }
  2268. procedure body P2 (…) {
  2269. . . .
  2270. }
  2271. procedure body Pn (…) {
  2272. . . .
  2273. }
  2274. {
  2275. initialization code
  2276. }
  2277. }
  2278. Monitori
  2279. Da bi se dozvolilo procesu da čeka u monitoru,
  2280. uslovna promenljiva mora biti deklarisana, kao
  2281. condition x, y;
  2282.  
  2283. Uslovna promenljiva može biti upotrebljena samo sa operacijama wait i signal:
  2284. Operacija
  2285. x.wait();
  2286. znači da proces koji je pozvao operaciju se suspenduje
  2287. sve dok drugi proces ne pozove kontra operaciju
  2288. x.signal();
  2289.  
  2290. x.signal operacija će odblokirati tačno jedan suspendovan proces.
  2291. Ako nema suspendovanih procesa, onda signal operacija nema efekta.
  2292. Šematski prikaz na monitor
  2293. Monitor With Condition Variables
  2294. Primer - Večera filozofa
  2295. monitor dp
  2296. {
  2297. enum {thinking, hungry, eating} state[5];
  2298. condition self[5];
  2299.  
  2300. void pickup(int i) // following slides
  2301. void putdown(int i) // following slides
  2302. void test(int i) // following slides
  2303.  
  2304. void init()
  2305. {
  2306. for (int i = 0; i < 5; i++)
  2307. state[i] = thinking; //init code
  2308. }
  2309. }
  2310. Večera filozofa
  2311. void pickup(int i)
  2312. {
  2313. state[i] = hungry;
  2314. test[i];
  2315. if (state[i] != eating)
  2316. self[i].wait();
  2317. }
  2318.  
  2319. void putdown(int i)
  2320. {
  2321. state[i] = thinking;
  2322. // testira levog i desnog komsiju
  2323. test((i+4) % 5); /*daje šansu levom komšiji da jede*/
  2324. test((i+1) % 5); /* daje šansu desnom komšiji da jede */
  2325. }
  2326. Večera filozofa
  2327. void test(int i)
  2328. {
  2329. if((state[(I + 4)%5] != eating) && (state[i] == hungry)&&(state[(i +1) % 5] !=eating))
  2330. {
  2331. state[i] = eating;
  2332. self[i].signal();
  2333. }
  2334. }
  2335.  
  2336. Večera filozofa
  2337. each philosopher do it:
  2338.  
  2339. dp.pickup(i)
  2340. …..
  2341. eat
  2342.  
  2343. dp.putdown(i)
  2344.  
  2345.  
  2346.  
  2347.  
  2348. Zastoji (Deadlocks)
  2349. Sistemski model
  2350.  
  2351. Karakterizacija zastoja
  2352.  
  2353. Metodi upravljanja zastojem
  2354.  
  2355. Prevencija od zastoja (Deadlock Prevention)
  2356.  
  2357. Izbegavanje zastoja (Deadlock Avoidance)
  2358.  
  2359. Detekcija zastoja (Deadlock Detection)
  2360.  
  2361. Oporavak od zastoja (Recovery from Deadlock)
  2362.  
  2363. Kombinovan pristup za uklanjanje zastoja
  2364. Problem zastoja
  2365. Zastoj: Skup blokiranih procesa:
  2366. svaki proces drži resurs
  2367. i čeka da uzme resurs
  2368. koji drži drugi proces
  2369. Primer
  2370. Sistem ima 2 trake.
  2371. P1 i P2 drže po jednu traku
  2372. i oba procesa žele i drugu
  2373.  
  2374. Primer
  2375. semafori A i B, inicijalizovani na 1
  2376.  
  2377. P0 P1
  2378. wait (A); wait(B)
  2379. wait (B); wait(A)
  2380.  
  2381. Problem prelaska preko mosta
  2382. Saobraćaj je samo u jednom smeru.
  2383. Svaki deo mosta možemo videti kao resurs.
  2384. Ako se pojavi zastoj, to možemo rešiti ako se jedan automobil vrati nazad (preempt resources and rollback).
  2385. Više automobila treba vratiti nazad ako nastane zastoj.
  2386. Zakucavanje je moguće
  2387. Sistemski model
  2388. Resursi tipa R1, R2, . . ., Rm
  2389. CPU ciklusi, memorijski prostor, I/O uređaji
  2390.  
  2391. Svaki resurs tipa Ri ima Wi instancu
  2392.  
  2393. Svaki proces koristi resurs na sledeći način:
  2394. zahtev (request)
  2395. korišćenje (use)
  2396. oslobađanje (release)
  2397. Karakterizacija zastoja
  2398. 1. Mutual exclusion (Međusobno isključenje): samo jedan proces u jednom trenutku može koristiti resurs.
  2399.  
  2400. 2. Hold and wait (Drži i čekaj): proces drži jedan resurs a istovremeno čeka dobijanje resursa koji koristi neki drugi proces.
  2401.  
  2402. 3. No preemption (Nema otimačine): resurs se može osloboditi samo kada proces koji ga koristi završi svoj posao.
  2403.  
  2404. 4. Circular wait (Kružno čekanje): postoji skup procesa {P0, P1, …, Pn} koji čekaju resurs u sledećem poretku:
  2405. P0 čeka na resurs koji drži P1,
  2406. P1 čeka na resurs koji drži P2, …,
  2407. Pn–1 čeka na resurs koji drži Pn,
  2408. Pn čeka na resurs koji drži P0
  2409.  
  2410. Graf dodeljenih resursa
  2411. V sadrži dva skupa:
  2412. P = {P1, P2, …, Pn}, skup se sastoji od svih procesa u sistemu
  2413. R = {R1, R2, …, Rm}, skup se sastoji od svih resursa u sistemu
  2414.  
  2415. strelica zahteva: P1  Rj
  2416.  
  2417. strelica alokacije: Rj  Pi
  2418. Graf dodeljenih resursa
  2419. Proces
  2420. Resurs sa 4 instance
  2421.  
  2422.  
  2423. Pi zahteva instancu Rj
  2424.  
  2425.  
  2426. Pi drži instancu Rj
  2427. Graf dodeljenih resursa
  2428. Graf dodeljenih resursa sa zastojem
  2429. Graf dodeljenih resursa – kružni tok bez zastoja
  2430. Osnovne činjenice
  2431. Ako graf ne sadrži kružni tok  nema zastoja
  2432. Ako graf sadrži kružni tok 
  2433. ako resursi u kružnom toku sadrže samo jednu instancu,
  2434. Nastupio je zastoj
  2435.  
  2436. ako resursi u kružnom toku sadrže više instanci,
  2437. moguć je zastoj
  2438. Metodi upravljanja zastojem
  2439. 1. Obezbeđuju da sistem nikada ne uđe u stanje zastoja.
  2440.  
  2441. 2. Dozvoljava da ako sistem uđe u zastoj, da iz njega izađe
  2442. 3. Ignoriše probleme pretvara se da se zastoji nikad ne javljaju u sistemu; ovo koriste mnogi operativni sistemi, uključujući i UNIX.
  2443. Prevencija zastoja
  2444. Međusobno isključenje – nepotrebno za deljive resurse; obavezno za nedeljive resurse
  2445.  
  2446. Drži i čekaj (hold and wait)– ukoliko proces zahteva neki resurs, nema prava da drži neki drugi resurs (resources)
  2447. Proces traži i alocira sve svoje resurse pre početka izvršavanja
  2448. ili
  2449. proces može tražiti resurs samo pod uslovom da ne drži ni jedan drugi
  2450.  
  2451. Mala iskorišćenost resursa; zakucavanje moguce
  2452. Prevencija zastoja
  2453. Nema pretpražnjenja (no preemption):
  2454. Ako proces drži neki resurs,
  2455. a traži drugi resurs koga ne može trenutno da dobije,
  2456. onda proces treba da otpusti sve dosadašnje zauzete resurse
  2457.  
  2458. Oslobodjeni resursi se ubacuju na listu resursa za koje proces čeka
  2459.  
  2460. Proces će se restartovati samo kada bude mogao da povrati stare resurse, kao i da dobije nove koji su mu trebali
  2461. Kružno čekanje:
  2462. uvede se poredak označavanja svih resursa
  2463. natera se da svaki proces zahteva resurse
  2464. u strogo rastućem redu
  2465. Izbegavanje zastoja (Deadlock avoidance )
  2466. Najprostiji i najviše korišćeni model zahteva od svakog procesa da objavi maximalni broj resoursa koji će mu možda trebati.
  2467. Algoritam izbegavanja zastoja
  2468. dinamički ispituje trenutno stanje dodeljenih resursa
  2469. tako da osigura da sistem
  2470. nikada ne uđe u stanje cirkularnog čekanja
  2471. Pod stanjem dodeljenih resursa
  2472. podrazumeva se stanje definisano brojem:
  2473. raspoloživih
  2474. dodeljenih
  2475. maksimalno traženih resursa
  2476. u jednom trenutku vremena
  2477. Bezbedno stanje (Safe State)
  2478. Kada proces traži neki resurs, sistem mora da proceni da li će dodela tog resursa ostaviti sistem u bezbednom stanju (safe state)
  2479. Sistem je u bezbednom stanju ako postoji bezbedna sekvenca svih procesa
  2480. Sekvenca <P1, P2, …, Pn> je bezbedna ako za svaki proces Pi, resursi koje Pi može još tražiti, mogu zadovoljiti iz:
  2481. trenutno raspoloživih resursa + resursi koji pripadaju svim Pj, sa j<I.
  2482. (svi procesi startovani pre njega)
  2483. Ako resursi koje traži proces Pi nisu trenutno raspoloživi, tada će Pi da čeka dok prethodni procesi Pj ne završe svoje poslove
  2484.  
  2485. Kada Pj završi, Pi može dobiti traženi resurs, izvršiti, vratiti deljeni resurs i završiti svoj posao
  2486.  
  2487. Kada je Pi završi, Pi+1 može dobiti traženi resurs, itd
  2488. Činjenično stanje
  2489. Ako je sistem u bezbednom stanju  nema zastoja
  2490. Ako sistem je u ne-bezbednom stanju  postoji mogućnost zastoja
  2491. Izbegavanje 
  2492. osigurava da sistem
  2493. nikad ne uđe u ne-bezbedno stanje
  2494. Bezbedno, Nebezbedno , Zastoj stanje
  2495. Resource-Allocation Graph Algorithm
  2496. Mogući zahtev Pi  Rj (claim edge)
  2497. znači da proces Pj može zahtevati resurs Rj;
  2498. predstavljeno isprekidanom linijom
  2499.  
  2500. Mogući zahtev preći će u realni zahtev kada proces zahteva resurs
  2501.  
  2502. Kada se takav resurs otpusti od procesa, strelica dodele opet prelazi u strelicu mogućih zahteva
  2503. Svi mogući zahtevi za resurse moraju biti poznati unapred sistemu
  2504. Resource-Allocation Graph For Deadlock Avoidance
  2505. Unsafe State In Resource-Allocation Graph
  2506. Bankarski algoritam
  2507. Više instanci
  2508.  
  2509. Svaki proces unapred mora deklarisati maksimalan broj instanci.
  2510. Kada proces zahteva resurse možda će trebati da sačeka
  2511. Kada proces dobije sve njegove resurse mora mora da ih vrati u nekom konačnom vremenu
  2512. Strukture podataka za bankarski algoritam
  2513. Vektor raspoloživosti: Vektor dužine m. Ako je element available [j] = k, tada je k instanci resoursa Rj raspoloživo
  2514.  
  2515. Matrica maksimalnih zahteva: Ako je Max [i,j] = k, tada proces Pi može tražiti najviše k instanci resoursa Rj
  2516.  
  2517. Matrica alokacije: Ako je Allocation[i,j] = k tada je proces Pi trenutno dobio k instanci resursa Rj.
  2518.  
  2519. Matrica potreba: Ako je Need[i,j] = k, tada proces Pi može tražiti još k instanci resursa Rj da završi njegov posao
  2520. Need [i,j] = Max[i,j] – Allocation [i,j].
  2521. Bezbednosni algoritam (Safety Algorithm)
  2522. 1. Neka Work i Finish budu vektori dužine m i n, respektivno. Inicijalizacija:
  2523. Work = Available
  2524. Finish [i] = false for i - 1,3, …, n.
  2525. 2. Pronalaženje procesa Pi koji može da zadovolji svoje potrebe:
  2526. (a) Finish [i] = false
  2527. (b) Needi  Work /*trazi manje od raspolozivih R*/
  2528. Ako nema takvih procesa idi na korak 4
  2529.  
  2530. Work = Work + Allocationi vraća resurse Finish[i] = true (proces završio)
  2531. Idi na korak 2
  2532.  
  2533. 4. Ako je Finish [i] == true za svako i, tada je sistem u stabilnom stanju.
  2534. Algoritam za zahtevanje resursa
  2535. Requesti = vektor trenutnih zahteva za proces Pi.
  2536. Ako je Requesti [j] = k tada proces Pi traži k instanci resoursa Rj.
  2537. Ako je Requesti  Needi idi na korak 2. Ukoliko ovo nije ispunjeno postavlja se greška , zato što proces traži više od onoga što je specificirao kao maksimalan zahtev .
  2538.  
  2539. Ako je Requesti  Available, idi na korak 3. U suprotnom proces Pi mora da čeka, resursi nisu raspoloživi
  2540.  
  2541. 3. Zamislite da ste dodelili resurse procesu Pi po sledećoj formuli :
  2542. Available = Available - Requesti;
  2543. Allocationi = Allocationi + Requesti;
  2544. Needi = Needi – Requesti;
  2545.  
  2546. Ako je stanje stabilno  resursi će biti dodeljeni procesu Pi.
  2547. Ako stanje nije stabilno  Pi mora da čeka, i resursi se vraćaju u staro stanje
  2548. Primer bankarskog algoritma
  2549. 5 procesa P0 do P4;
  2550. 3 resoursa:
  2551. A (10 instanci), B (5instanci), i C (7 instanci)
  2552. Stanje sistema u trenutku T0:
  2553. Allocation Max Available
  2554. A B C A B C A B C
  2555. P0 0 1 0 7 5 3 3 3 2
  2556. P1 2 0 0 3 2 2
  2557. P2 3 0 2 9 0 2
  2558. P3 2 1 1 2 2 2
  2559. P4 0 0 2 4 3 3
  2560. Primer
  2561. Stanje matrice potreba Need[] se definiše kao:
  2562. Max[] – Allocation[]
  2563. Need Available
  2564. A B C A B C
  2565. P0 7 4 3 3 3 2
  2566. P1 1 2 2
  2567. P2 6 0 0
  2568. P3 0 1 1
  2569. P4 4 3 1
  2570. Sistem je u bezbednom stanju u sekvenci < P1, P3, P4, P2, P0> a uvek se polazi od procesa sa manjim zahtevima.
  2571. (pogledaj te najmanje zahteve P1.P3..)
  2572. Primer gde P1 zahteva (1,0,2)
  2573. Proverava se da li je Request  Available (1,0,2)  (3,3,2)  true.
  2574. Allocation Need Available
  2575. A B C A B C A B C
  2576. P0 0 1 0 7 4 3 2 3 0
  2577. P1 3 0 2 0 2 0
  2578. P2 3 0 1 6 0 0
  2579. P3 2 1 1 0 1 1
  2580. P4 0 0 2 4 3 1
  2581. Izvrši se bankarski algoritam i dokaže da postoji sekvenca <P1, P3, P4, P0, P2> koja će zadovoljiti uslove stabilnosti.
  2582. Da li se može odobriti zahtev procesu P4 (3,3,0)? (ne < od raspoloživog)
  2583. Da li se može odobriti zahtev procesu P0 (0,2,0)?(ne, ne-bezbedno)
  2584.  
  2585. Detekcija zastoja (Deadlock Detection)
  2586. Ako sistem uđe u stanje zastoja
  2587. Algoritam za detekciju zastoja
  2588. Algoritam za oporavak
  2589. Detekcija kad resursi imaju samo jednu instancu
  2590. Pruža wait-for graf:
  2591. Čvorovi su samo procesi
  2592. Pi  Pj ako Pi čeka na Pj.
  2593. Algoritam se periodično pozove da pretraži krugove u grafu
  2594. Algoritam detektuje krugove u grafu
  2595. preko n2 operacija,
  2596. gde je n broj strelica u grafu
  2597. Graf alokacije resursa i Wait-for graf
  2598. Detekcija kad resursi imaju više instanci
  2599. Vektor raspoloživosti: Vector dužine m. Ako je element available[j] = k, tada je k instanci resursa Rj rasploživo .
  2600. Matrica alokacije: Ako je Allocation[i,j] = k tada je proces Pi trenutno dobio k instanci resursa Rj.
  2601. Matrica trenutnih zahteva: Matrica ukazuje na trenutne zahteve procesa. Ako je Request [i,j] = k, tada proces Pi trenutno traži k instanci resursa Rj.
  2602. Algoritam za detekciju
  2603. 1. Neka Work i Finish budu vektori dužine m i n, respektivno Inicijalizacija:
  2604. (a) Work = Available
  2605. (b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] = false;otherwise, Finish[i] = true
  2606.  
  2607. 2. Pronalazi se proces koji može da zadovolji sve potrebe:
  2608. (a) Finish[i] == false
  2609. (b) Requesti  Work
  2610. Ako takvi ne postoje, idi na korak 4
  2611.  
  2612. Algoritam za detekciju
  2613. 3. Work = Work + Allocationi Finish[i] = true idi na korak 2
  2614. 4. Ako je Finish[i] == false, za bilo koji proces i, 1  i  n, tada je sistem u stanju zastoja
  2615. Preciznije, ako je Finish[i] == false, tada je Pi u zastoju
  2616.  
  2617. Primer algoritma za detekciju
  2618. Pet procesa od P0 do P4;
  2619. tri resursa tipa A (7 instanci), B (2 instance), i C (6 instanci)
  2620. Stanje sistema u trenutku T0:
  2621. Allocation Request Available
  2622. A B C A B C A B C
  2623. P0 0 1 0 0 0 0 0 0 0
  2624. P1 2 0 0 2 0 2
  2625. P2 3 0 3 0 0 0
  2626. P3 2 1 1 1 0 0
  2627. P4 0 0 2 0 0 2
  2628.  
  2629. Sekvenca <P0, P2, P3, P1, P4> koja bi dovela da bude rezultat Finish[i] = true za sve procese i
  2630. Primer 2
  2631. P2 traži jednu instancu resursa C
  2632. Request
  2633. A B C
  2634. P0 0 0 0
  2635. P1 2 0 1
  2636. P2 0 0 1
  2637. P3 1 0 0
  2638. P4 0 0 2
  2639. Stanje sistema?
  2640. P0 ima najmanje prohteva i ako bi završio svoje i vratio resurse, stanje raspoloživih resursa bi bilo (0,1,0) a iza toga nemamo proces koji može da zadovolji svoje potrebe
  2641. Zastoj postoji, zaglavljeni su procesi P1, P2, P3 i P4
  2642. Korišćenje algoritma za detekciju
  2643. Kada, i koliko često, pozvati algoritam za detekciju zavisi od toga:
  2644. Koliko često se zastoj dešava ?
  2645. Koliko procesa je zahvaćeno zastojom ?
  2646.  
  2647.  
  2648. Zastoj se mora detektovati
  2649. jer su svi procesi i svi resursi u njima zaglavljeni,
  2650. ali zahteva prilično veliko vreme za detekciju
  2651. pa se ne sme pozivati veoma često
  2652. Oporavak od zastoja: Prekidanje procesa
  2653. Prekid svih zaglavljenih procesa
  2654. Prekid samo jednog procesa dok se ne razbije krug
  2655. Po kom redu se prekidaju procesi?
  2656. Prioritet procesa
  2657. Koliko dugo proces već radi, odnosno šta mu je ostalo do završetka
  2658. Koje resurse proces koristi
  2659. Koje resurse proces traži da kompletrira aktivnost
  2660. Koliko procesa je potrebno prekinuti
  2661. Da li su to interaktivni ili grupni procesi?
  2662. Oporavak od zastoja: Oduzimanje resursa
  2663. Biranje žrtve:
  2664. najmanji gubitak
  2665. Oporavak procesa (Rollback):
  2666. proces se vraća u bezbedno stanje,
  2667. ponovo se pokreće iz tog stanja.
  2668. Zakucavanje (Starvation):
  2669. neki proces možda uvek bude biran kao žrtva,
  2670. zbog toga se neće dugo izvršiti
  2671. Kombinovan pristup za uklanjanje zastoja
  2672. Kombinacija tri osnovna pristupa:
  2673. prevencija
  2674. izbegavanje
  2675. detekcija
  2676. dopušta korišćenje najpovoljnijeg pristupa za svaki resurs u sistemu
  2677. Podeljeni resursi u hierarhijski poređanim klasama
  2678. Koristi se najodgovarajuća tehnika za uklanjanje zastoja u svakoj klasi
  2679. Zastoj u saobraćaju
  2680.  
  2681.  
  2682.  
  2683. Virtuelna memorija
  2684. Background
  2685.  
  2686. Učitavanje stranica prema potrebi (Demand Paging)
  2687.  
  2688. Kreiranje procesa (Process Creation)
  2689.  
  2690. Zamena stranica (Page Replacement)
  2691.  
  2692. Alokacija okvira po procesima (Allocation of Frames)
  2693.  
  2694. Thrashing
  2695.  
  2696.  
  2697. Background
  2698. Osnovna zamisao:
  2699. Omogućava da se izvrši proces koji je samo delimično u memoriji
  2700. Deo procesa je u memoriji (onaj koji se trenutno koristi)
  2701. Ostatak programa je na disku (swap ili exe datoteka)
  2702.  
  2703. Program > Fizičke Memorije
  2704. VM nije jednostavna za implementaciju
  2705. VM može smanjiti performanse
  2706.  
  2707. Virtuelna memorija:
  2708. odvajanje korisničke logičke memorije od fizičke memorije.
  2709. Potrebno je da samo deo programa bude u memoriji da bi se izvršavao.
  2710.  
  2711. Zbog toga logički adresni prostor može biti mnogo veći od fizičkog adresnog prostora.
  2712.  
  2713. Omogućava da više procesa dele adresni prostor
  2714.  
  2715. Omogućava mnogo efikasnije kreiranje procesa
  2716. Virtuelna memorija je veća od fizičke memorije
  2717. Realizacija virtuelne memorije
  2718. Virtuelna memorija se najčešće realizuje preko sledećih tehnika:
  2719.  
  2720. Učitavanje stranica prema potrebi
  2721. (Demand paging)
  2722.  
  2723. Učitavanje segmenata prema potrebi
  2724. (Demand segmentation)
  2725.  
  2726. Učitavanje stranica prema potrebi
  2727. Učitava stranicu u memoriju samo kada je potrebna
  2728. lazy swapper (lenji razmenjivač)
  2729. potrebno je manje I/O operacija
  2730.  
  2731. potrebno je manje memorije
  2732.  
  2733. brži odziv
  2734.  
  2735. više korisnika
  2736. Postoje dva velika problema:
  2737. 1. Algoritam alokacije okvira
  2738. 2. Algoritam zamene stranica
  2739.  
  2740. Stranica je potrebna  prebacuje se u memoriju
  2741. ako je nevažeća referenca  prekid
  2742. ako nije u memoriji  prebacuje se u memoriju  restart
  2743. Prenos stranica u kontinualni prostor na disku
  2744. Valid-Invalid Bit
  2745. Za svaki ulaz u tabelu stranica
  2746. asociran je valid–invalid bit is (1  u memoriji, 0  nije u memoriji)
  2747. Valid–invalid bit je inicijalizovan na 0 za sve ulaze
  2748. Primer tabele stranica:
  2749.  
  2750.  
  2751. Tabela stranica kada neke stranice nisu u glavnoj memoriji
  2752. Greška u stranicenju (Page Fault)
  2753. PF rutina ima zadatak,
  2754. da stranicu sa diska
  2755. prebaci u memoriju
  2756. PF rutina proverava da li je referenca validna ili invalidna:
  2757. ako je referenca nevalidna  proces se prekida
  2758. ako je validna učitava se u memoriju
  2759. Uzima prazan okvir
  2760. Zamenjuje stranicu za okvir
  2761. Resetuje tabele, validation bit = 1
  2762. Instrukcija se restartuje: (carefully)
  2763. pomeranje bloka
  2764.  
  2765. automatsko inkrementiranje/dekrementiranje lokacije
  2766. Koraci u manipulisanju sa PF-om
  2767. Šta se događa ako nema slobodnih okvira?
  2768. Zamena stranica:
  2769. nađe se jedna stranicu u memoriji
  2770. koja se ne koristi,
  2771. upiše se na disk, a potom se oslobodi njena memorija
  2772.  
  2773. algoritam za najbolje performanse
  2774. traži se algoritam
  2775. koji daje rezultat
  2776. sa najmanjim brojem grešaka u stranici.
  2777. Ista stranica može biti dovedena u memoriju nekoliko puta
  2778. Performanse DP tehnike
  2779. PF: 0  p  1.0
  2780. ako je p = 0  nema grešaka u stranici
  2781. ako je p = 1  svaka referenca ima grešku (trashing)
  2782.  
  2783. Effective Access Time (EAT)
  2784. EAT= (1 – p) x memory access + p x (Page Fault time)
  2785.  
  2786. Page Fault time = page fault overhead
  2787.  
  2788. + swap page out /* if write*/
  2789. + swap page in
  2790.  
  2791. + restart overhead
  2792. Page Fault
  2793. 1. Servisiranje PF prekida
  2794. prekidni signal PF izaziva prelazak u operativni sistem
  2795. čuvanje konteksta prekinutog procesa (registri procesora)
  2796. određivanje da li je prekidni signal izazvan PF greškom
  2797.  
  2798. 2. Čitanje stranice
  2799. disk I/O izazva čekanje, tj. blokadu PF rutine
  2800. dok se čeka na disk CPU se daje nekom drugom
  2801. prekidni signal koji znači da je disk I/O operacija završena
  2802. određivanje da li je disk I/O prekidni signal
  2803.  
  2804. 3. Restrartovanje procesa koji je izazvao PF
  2805. korekcija tabele stranica
  2806. obnova konteksta procesa
  2807.  
  2808. Primer DP
  2809. Vreme pristupa memoriji MC = 1 mikrosekunda = 1000nsec
  2810. Proces punjenja stranice u memoriju može uključiti dve I/O
  2811. stranica koja je zamenjena
  2812. ukoliko je promenjena dok je bila u memoriji
  2813. ponovo se upisuje na disk.
  2814.  
  2815. ->1 ili 2 disk I/O operacije ->prosek =1.5 disk I/O
  2816.  
  2817. Vreme razmene stranica = 10 msec = 10,000 microsekundi
  2818.  
  2819. EAT = (1 – p) x 1 + p (15000)
  2820. 1 + 15000p (microsec)
  2821. Kreiranje procesa
  2822. Virtuelna memorija može dosta pomoći
  2823. u toku
  2824. kreiranja procesa:
  2825. - Copy-on-Write
  2826. - Memorijski mapirane datoteke (Memory-Mapped Files)
  2827. Copy-on-Write
  2828. Copy-on-Write (COW)
  2829. omogućava da roditelji i dete proces
  2830. inicijalno
  2831. dele iste stranice u memoriji
  2832.  
  2833. Ako bilo koji proces
  2834. pokuša da modifikuje deljenu stranicu,
  2835. tada će se prvo kreirati kopija za tu stranicu
  2836.  
  2837. COW omogućava mnogo efikasnije kreiranje procesa
  2838. tako što se samo modifikovane stranice kopiraju
  2839.  
  2840. Kod dodele novih stanica,
  2841. poželjno je da one budu prazne, to se postiže tehnikom
  2842. koja puni nule u okvir koji se dodeljuje (zero-fill-on-demand)
  2843. Memorijski mapirane datoteke
  2844. Memorijski mapirana I/O datoteka omogućava da se
  2845. I/O datotekama pristupa
  2846. preko memorijskih referenci
  2847. tako što se deo virtuelnog memorijskog prostora
  2848. dodeli datotekama
  2849.  
  2850. Inicijalni pristup datoteci se odvija preko DP tehnike
  2851. koja će izazvati PF grešku
  2852. i kao rezultat te greške
  2853. deo datoteke će se učitati u memoriju
  2854.  
  2855. Sledeći čitanje/upis u/iz datoteke
  2856. se tretira
  2857. kao običan pristup memoriji.
  2858.  
  2859. Pristup datoteci je uprošćen (brži)
  2860. ako se I/O datoteci pristupa kroz memoriju
  2861. češće nego preko
  2862. read() write() sistemskih poziva
  2863.  
  2864. Deljenje datoteke: omogućava da više procesa
  2865. mogu deliti istu datoteku
  2866. tako što se datoteka učita u memoriju
  2867. Memorijski mapirane datoteke
  2868. Zamena stranica
  2869. Kod alociranja memorije
  2870. pojavljuje se veliki broj PF grešaka,
  2871. tada se koristi zamena stranica
  2872. Koristi se dirty bit
  2873. koji opisuje da je stranica modifikovana
  2874. na disk se upisuju samo modifikovane stranice
  2875. Zamena stranica kompletira razdvajanje između logičke i fizičke memorije:
  2876. velika virtuelna memorija
  2877. se koristi samo kada je
  2878. fizička memorija mala
  2879. Zamena stranica
  2880. Opis zamene stranica
  2881. Potrebno je pronaći lokaciju na disku gde je smeštena stranica
  2882. Traži se slobodan okvir: - Ako ima slobodnih okvira uzima se jedan od njih - Ako nema nijednog slobodnog, pomoću algoritama za zamenjivanje stranica izabra se žrtva: okvir koji će biti zamenjen
  2883. Željena stranica se učitava u oslobođeni okvir. Tabele stranica i okvira se ažuriraju
  2884.  
  2885. Proces se restartuje
  2886.  
  2887. Pažljivo sa:
  2888. pomeranjem instrukcija
  2889. ili
  2890. automatskim inkrementiranjem/dekrementiranjem
  2891. Zamena stranica
  2892. Algoritmi za zamenu stranica
  2893. Potrebna je najmanja verovatnoća PF grešaka
  2894.  
  2895. Prilikom evaulacije algoritama
  2896. definiše se ulazna sekvenca referenci
  2897. i
  2898. na datoj veličini fizičke memorije
  2899. analizira se broj PF grešaka
  2900.  
  2901. U svim primerima, memorijske reference su
  2902. 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  2903. Graph of Page Faults Versus The Number of Frames
  2904. First-In-First-Out (FIFO) Algorithm
  2905. Najstarija stranica će biti zamenjena
  2906. Niz memorijskih refernci: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  2907. 3 okvira (3 stranice po procesu istovremeno mogu biti u memoriji)
  2908.  
  2909.  
  2910.  
  2911.  
  2912. 4 okvira
  2913. FIFO zamena – Belady anomalija
  2914. više okvira  manje PF
  2915. FIFO algoritam za zamenu stranica
  2916. Belady anomalija
  2917. Optimalni algoritam
  2918. Zamenjuje stranice
  2919. koje se neće koristiti
  2920. najduže vremena od svih.
  2921.  
  2922. primer sa 4 okvira
  2923. 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  2924. OPT je najbolji mogući algoritam, ali na žalost ne može se implementirati.
  2925. Ne postoji način da operativni sistem dođe do potrebne informacije o tome, kada će koja stranica biti potrebna.
  2926. Optimalni algoritam za zamenu stranica
  2927. Least Recently Used (LRU) Algorithm
  2928. Zamenjuje se stranica za koju je proteklo najviše vremena od kada se nije koristila
  2929. Niz memorijskih refernci: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  2930. Realizacija pomoću brojača (timer)
  2931. Svaka stranica ima svoj interni registar;
  2932. svaki put kada se pristupi stranici,
  2933. sadržaj casovnika kopira se u interni registar
  2934. Kada dođe do PF prekida,
  2935. algoritam pregleda sve interne registre
  2936. i bira stranicu čiji je broj najmanji.
  2937. (što znači da najduže nije korišćena)
  2938.  
  2939. LRU algoritam za zamenu stranica
  2940. LRU Algoritam (2)
  2941. Realizacija pomoću steka:
  2942. formira se stek koji opisuje redosled pristupanja stranicama
  2943. (head list & tail list):
  2944. Nakon PF prekida:
  2945. bira se stranica sa vrha steka
  2946. na njeno mesto se stavlja stranica kojoj se pristupa
  2947.  
  2948. Ova realizacija je veoma spora jer se pri svakom pristupu memoriji stek ažurira.
  2949. Algoritam LRU – realizacija pomoću steka
  2950. Aproksimativni LRU algoritmi
  2951. Reference bit
  2952. Za svaki ulaz u tabeli stranica postoji referentni bit, inicijalizovan na 0
  2953. Kada se stranica referencira, bit se setuje na 1
  2954. Nakon određenog vremena R bit se briše pomoću tajmerskih prekida
  2955. Nema informacije o redosledu korišćenja okvira
  2956.  
  2957. Druga šansa (second chance)
  2958. FIFO baziran
  2959. Koristi R bit
  2960. Kada treba izbaciti stranicu, uzima se zadnja iz reda čekanja, i pogleda R bit:
  2961. Ako stranica ima referenti bit R = 1, tada:
  2962. se R setuje na 0
  2963. a stranica se ostavlja u memoriji
  2964. zatim se gleda sledeća stranica na kraju reda
  2965. Druga šansa – realizacija pomoću kružnog reda čekanja
  2966. Klase stranica
  2967. Na osnovu vrednosti R i M bitova okvire delimo u 4 klase:
  2968.  
  2969. clasa 0. (0,0) stranica nije ni korišćena ni modifikovana
  2970.  
  2971. clasa 1. (0,1) stranica nije korišćena ali je modifikovana
  2972.  
  2973. clasa 2. (1,0) stranica je korišćena ali nije modifikovana
  2974.  
  2975. clasa 3. (1,1) stranica je i korišćena i modifikovana
  2976.  
  2977.  
  2978. Stranica za zamenu je svaka stranica u najnižoj klasi
  2979.  
  2980. Svaka klasa sa više stranica je FIFO bazirana
  2981. Brojački algoritmi
  2982. Čuva informaciju koliko je puta
  2983. svaka stranica bila referencirana
  2984.  
  2985. LFU Algoritam:
  2986. zamenjuje stranicu koja ima najmanji broj referenci
  2987.  
  2988. MFU Algoritam:
  2989. baziran na činjenici
  2990. da je stranica sa najmanjim brojem referenci
  2991. verovatno upravo učitana
  2992. i
  2993. upravo treba da se sačuva
  2994. Alokacija okvira
  2995. Svaki proces zahteva minimalan broj stranica.
  2996. Minimalni broj okvira po procesu zavisi od procesorske arhitekture
  2997.  
  2998. Primer:
  2999. IBM 370 – 6 pages to handle SS MOVE instruction:
  3000. instruction is 6 bytes, might span 2 pages.
  3001. 2 pages to handle from.
  3002. 2 pages to handle to.
  3003.  
  3004. Dve najvažnije šeme za alokaciju.
  3005. fiksna alokacija
  3006. prioritetna alokacija
  3007. Fiksna alokacija
  3008. Jednaka alokacija:
  3009. npr., ako ima 100 okvira i 5 procesa, svaki dobija 20 stranica.
  3010.  
  3011. Proporcionalna alokacija:
  3012. Svakom procesu pripašće sledeći broj okvira:
  3013. Prioritetna alokacija
  3014. Koristi šemu za proporcionalnu alokaciju
  3015. upotrebljavajući
  3016. prioritet umesto veličine.
  3017. Ako proces Pi generiše PF, postoje dva načina za zamenu
  3018.  
  3019. 1. bira za zamenu
  3020. jedan od njegovih okvira.
  3021.  
  3022. 2. bira za zamenu okvir
  3023. čiji proces ima najmanji prioritet.
  3024. Globalna i lokalna zamena stranica
  3025.  
  3026. Globalna zamena:
  3027. proces bira bilo koji okvir
  3028. iz cele fizičke memorije;
  3029. jedan proces može uzeti okvir od drugog.
  3030.  
  3031. Lokalna zamena:
  3032. svaki proces bira
  3033. samo okvire koji su mu dodeljeni
  3034. Thrashing
  3035. Ako proces nema “dovoljno” stranica,
  3036. pojava PF grešaka je veoma česta
  3037.  
  3038. Razmatrajmo sledeći slučaj:
  3039. ako je stepen iskorišćenja CPU-a previše mali
  3040. operativni sistem
  3041. povećava stepen multiprogramiranja
  3042. tako što aktivira nove proces.
  3043.  
  3044. Thrashing  pojava čestog razmenjivanja stranica
  3045.  
  3046. Thrashing  proces je zauzet zamenom stranica
  3047. Proces troši više vremena za straničenje nego za izvršavanje
  3048. Thrashing
  3049. Kako se izbegava trashing efekat? Model lokalnosti
  3050. Lokalnost je skup stranica koje proces koristi zajedno u jednom intervalu vremena
  3051. Proces može menjati svoje lokalnosti
  3052. Lokalnosti se mogu preklapati.
  3053.  
  3054. Zašto nastupa thrashing efekat?  suma lokalnosti > ukupne fizičke memorije
  3055. Radni model (Working-Set Model)
  3056. Radni model (Working-Set Model)
  3057.   prozor radnog skupa  fiksni broj referenciranih stranica
  3058.  
  3059. Primer: 10,000 instrukcija (memorijskih refernci)
  3060.  
  3061. WSSi (veličina radnog skupa procesa Pi) =
  3062. ukupan broj stranica
  3063. koje proces traži u vremenskom prozoru 
  3064.  
  3065. D =  WSSi  ukupna veličina radnog prostora
  3066.  
  3067. Ako je D > m  Thrashing
  3068.  
  3069. Kada D dođe do veličine sistemske memorije,
  3070. pojedini procesi treba da se suspenduju na disk
  3071. Keeping Track of the Working Set
  3072. Aprokcimaci preko Tajmera + referentni bit
  3073.  
  3074. Primer:  = 10,000
  3075. Tajmer pravi prekide posle svakih 5000 vremeskih jedinica.
  3076. U memoriji se čuvaju 2 bita za svaku stranicu
  3077. Uvek kada tajmer napravi prekid
  3078. kopira i setuje vrednost svih referentnih bitova na 0.
  3079. Ako je jedan od bitova u memoriji = 1  stranica je u radnom skupu.
  3080.  
  3081. Zašto ovo nije kompletno ispravno?
  3082.  
  3083. Poboljšanje =
  3084. 10 bita
  3085. i
  3086. prekid svakih 1000 vremenskih jedinica
  3087. Broj PF grešaka u funkciji broja okvira
  3088. Uspostavlja se “prihvatljiva” PF učestanost.
  3089. Ako je aktuelna učestanost mala, proces gubi okvir (ima ih mnogo)
  3090. Ako je aktuelna učestanost velika, proces dobija okvir (dodeljeno mu je malo okvira)
  3091. Dopunska razmatranja
  3092. Prepaging
  3093. DP=veliki broj PF grešaka pri startovanju programa
  3094. Prepaging je pokušaj da se spreči ovo inicijalno straničenje
  3095. Primer:
  3096. obnoviće ceo radni skup prethodno suspendovanog procesa
  3097.  
  3098. Veličina stranice
  3099. Fragmentacija (manja stranica=>manja fragmentacija)
  3100. veličina tabele stranica
  3101. I/O overhead (zahteva veće stranice)
  3102. Lokalnost (bolja rezolucija, bolja lokalnost, smanjen PF)
  3103. Tipične stranice:512, 1K, 2K, 4K
  3104. Dopunska razmatranja (2)
  3105. TLB efikasnost:
  3106. Količina dostupne memorije u TLB
  3107.  
  3108. TLB efikasnost = (TLB Size) X (Page Size)
  3109.  
  3110. Idealno,
  3111. radni skup svakog procesa se memoriše u TLB.
  3112. U protivnom,
  3113. postoji visok stepen PF grešaka.
  3114. Povećanje veličine TLB-a
  3115. Povećanje veličine stranice.
  3116. Ovo može dovesti do povećane fragmentacije
  3117. mada ne zahtevaju sve aplikacije velike stranice
  3118.  
  3119. Obezbediti stranice različitih veličina
  3120. Ovo omogućava aplikacijama
  3121. da traže veće stranice
  3122. i da ih koriste
  3123. bez povećanja fragmentacije
  3124. Dopunska razmatranja (3)
  3125. Struktura programa
  3126. int A[][] = new int[1024][1024];
  3127. Each row is stored in one page
  3128.  
  3129. Program 1 for (j = 0; j < A.length; j++) for (i = 0; i < A.length; i++) A[i,j] = 0; 1024 x 1024 page faults
  3130.  
  3131. Program 2 for (i = 0; i < A.length; i++) for (j = 0; j < A.length; j++) A[i,j] = 0;
  3132. 1024 page faults
  3133. Dopunska razmatranja (3)
  3134. Struktura programa
  3135. int A[][] = new int[1024][1024];
  3136. Each row is stored in one page
  3137.  
  3138. Program 1
  3139. for (j = 0; j < A.length; j++) for (i = 0; i < A.length; i++)
  3140. A[i,j] = 0;
  3141. 1024 x 1024 page faults
  3142.  
  3143. Dopunska razmatranja (3)
  3144. Struktura programa
  3145. int A[][] = new int[1024][1024];
  3146. Each row is stored in one page
  3147.  
  3148. Program 2
  3149. for (i = 0; i < A.length; i++) for (j = 0; j < A.length; j++) A[i,j] = 0;
  3150. 1024 page faults
  3151.  
  3152.  
  3153. Dopunska razmatranja (4)
  3154. Dok proces obavlja I/O transfer
  3155. Može biti suspendovan
  3156. Stranica za I/O transfer može biti dodeljena drugom procesu
  3157. Postoje dva rešenja za ovaj problem
  3158. I/O se nikad ne izvršavaja korisničkoj memoriji nego u kernelskim baferima
  3159. Mehanizam za zaključavanje stranice
  3160.  
  3161. I/O zaključavanje:
  3162. Stranice mogu biti zaključane u memoriji
  3163.  
  3164. I/O zaključavanje
  3165. Stranice koje se koriste za kopiranje datoteke sa uređaja
  3166. trebaju biti zaključane od buduće selekcije
  3167. u algoritma za zamenu stranica.
  3168. Razlog zbog čega okviri koji se koriste za I/O trebaju biti u memoriji
  3169.  
  3170.  
  3171.  
  3172. Upravljanje memorijom
  3173. Background
  3174.  
  3175. Razmena (Swapping)
  3176.  
  3177. Kontinualna alokacija (Contiguous Allocation)
  3178.  
  3179. Diskontinualna alokacija (Discontinuous Allocation)
  3180.  
  3181. Straničenje (Paging)
  3182.  
  3183. Segmentcija
  3184.  
  3185. Segmentacija sa straničenjem
  3186.  
  3187. Pregled
  3188. Background
  3189. Memorija je jedan od fundamentalnih delova OS
  3190.  
  3191. Glavne funkcije memorijskog menadžera:
  3192.  
  3193. 1. Vodi računa o korišćenju memorije
  3194.  
  3195. 2. Dodeljuje memoriju procesima kad je zatraže
  3196.  
  3197. 3. Oslobađa memoriju od procesa kad završe svoje aktivnosti
  3198.  
  3199. 4. Vrši razmenu između memorije i diska
  3200. kada glavna memorija nije dovoljno velika
  3201. da sadrži sve procese
  3202. Background
  3203. Program se mora učitati
  3204. u memoriju
  3205. unutar adresnog prostora novostvorenog procesa
  3206.  
  3207. Ulazni red (Input queue):
  3208. kolekcija procesa na disku
  3209. koja čeka povratak u memoriju
  3210. i nastavak izvršenja
  3211. Korisnički program
  3212. prolazi preko više faza
  3213. dok ne dođe do izvršavanja
  3214. Vezivanje adresa
  3215. 1. Adrese u izvornom programu
  3216. su simboličke
  3217. (npr. X)
  3218. 2. Prevodilac (Compiler)
  3219. vezuje ove simboličke adrese
  3220. za relokatibilne adrese
  3221. (npr. promenljiva count se vezuje na lokaciju na adresi 14 u odnosu na početak modula)
  3222.  
  3223. 3. Punilac (Loader)
  3224. pretvara ove relokatibilne adrese
  3225. u apsolutne adrese
  3226. (npr. 74014)
  3227.  
  3228. Vezivanje (Binding) = mapiranje iz jednog adresnog prostora u drugi
  3229. Vezivanje adresa
  3230. Vezivanje
  3231. instrukcija i podataka na memorijske adrese
  3232. može se izvršiti na tri različita načina:
  3233.  
  3234. 1. Vreme prevođenja (Compile time):
  3235. Kako nije poznato gde će proces koji će izvršavati,
  3236. generisani kod biti smešten u memoriji;
  3237. prevodilac generiše relativne, a ne apsolutne adrese
  3238.  
  3239. 2. Vreme učitavanja u memoriju (Load time):
  3240. Povezivač i punilac na bazi relokatibilnog koda
  3241. generišu apsolutne adrese i pune memoriju programom
  3242.  
  3243. 3. Vreme izvršavanja (Execution time):
  3244. Za vreme izvršavanja,
  3245. proces se može pomerati
  3246. s jednog memorijskog segmenta na drugi.
  3247. Zahteva hardversku podršku za adresno mapiranje
  3248. Višefazno procesiranje korisničkog programa
  3249. Logički i fizički adresni prostor
  3250. Koncept logičkog adresnog prostora
  3251. bazirano na razdvojenim fizičkim adresni prostorima
  3252. ima centralnu ulogu u upravljanju memorijom.
  3253.  
  3254. Logička adresa:
  3255. generisana od strane CPU;
  3256. u fazi izvršavanja naziva se i virtuelna adresa
  3257. Fizička adresa:
  3258. adresa same memorijske jedinice
  3259. Logičke i fizičke adrese su potpuno iste
  3260. u fazi prevođenja
  3261. u fazi učitavanja
  3262.  
  3263. Logičke i fizičke adrese
  3264. se razlikuju u fazi izvršavanja
  3265. Jedinica za upravljanje memorijom (MMU-Memory Management Unit)
  3266. MMU: Hardverski uređaj koji mapira
  3267. virtuelni adresni prostor u fizički
  3268. U naj-prostijoj MMU šemi,
  3269. vrednost u relokacionom registru
  3270. se sabira sa logičkom adresom koju generiše program
  3271. i tako se dobija fizička adresa
  3272. Korisnički program
  3273. uvek počinje od nulte adrese;
  3274. i ne treba da vodi računa o svom fizičkom prostoru.
  3275. Mapiranje pomoću relokacionog registra
  3276. Razmena (Swapping)
  3277. Proces se može
  3278. privremeno prebaciti iz memorije na disk,
  3279. i onda
  3280. ponovo vratiti u memoriju da bi nastavio izvršavanje
  3281.  
  3282. Vraćanje u memoriju:
  3283. brzi disk, dovoljno veliki
  3284. da prihvati kopije za sve memorijske slike za sve korisnike;
  3285. potrebno je obezbediti direktni pristup za ove memorijske slike
  3286.  
  3287. swap out, swap in:
  3288. razmenjivanje se koristi u prioritetnim šemama za raspoređivanje procesa;
  3289. procesi niskog prioriteta se upisuju na disk dok se
  3290. procesi visokog prioriteta učitavaju u memoriju i izvršavaju
  3291. Najveći deo vremena u ciklusima razmene otpada na prenos podataka;
  3292. trajanje jedne razmene
  3293. zavisi od količine podataka za prenos, karakteristika diskova i hardvera
  3294.  
  3295. Modifikovana verzija razmenjivanja postoji na svim OS, npr., UNIX, Linux, i Windows
  3296. Šematski prikaz razmene
  3297. Dinamičko učitavanje (Dynamic Loading)
  3298. Rutina se puni u memoriju samo kada je program pozove
  3299.  
  3300. Bolja iskorišćenost memorijskog prostora;
  3301. nepotrebne rutine se ne učitavaju u memoriju
  3302.  
  3303. Korisno je kod:
  3304. velikih programa
  3305. jer se u memoriju smeštaju
  3306. samo potrebni delovi programa.
  3307.  
  3308. Ne zahteva specijalnu podršku
  3309. od operativnog sistema
  3310. programer projektuje programe da koriste dinamičko punjenje
  3311. Preklapanje (Overlays)
  3312. Overlay čuva u memoriji
  3313. samo one delove programa
  3314. koji su potrebni u tom trenutku
  3315. Koristi se kada je proces veći
  3316. od memorije koja mu je dodeljena
  3317. Implementira je programer,
  3318. ne postoji specijalna podrška operativnog sistema
  3319. konkretnu strukturu overlay delova definiše programer
  3320. Preklapanje kod dvoprolaznog asemblera
  3321. Dinamičko povezivanje (Dynamic Linking)
  3322. Linkovanje je odloženo za kasnije, u toku izvršavanja
  3323.  
  3324. Malo parče koda za svaki poziv sistemske biblioteke,
  3325. stub,
  3326. pokazuje kako da se locira odgovarajuća sistemska rutina
  3327.  
  3328. Stub
  3329. puni rutinu u memoriju
  3330. i
  3331. izvršava je
  3332.  
  3333. Operativni sistem obezbeđuje da
  3334. da istu sistemsku rutinu koja je u memoriji
  3335. mogu koristititi više procesa.
  3336.  
  3337. Dinamičko povezivanje je naročito korisno za sistemske biblioteke.
  3338. Tipovi memorijiskih alokacija
  3339.  
  3340. Razlikujemo različite tipove memorijske alokacije na osnovu:
  3341. Efektivnosti
  3342. Složenosti
  3343. Hardvrske podrške
  3344.  
  3345. Kontinualna alokacija:
  3346. Single-programming
  3347. Bare
  3348. Resident Monitor
  3349. Multiprogramming
  3350. MFT
  3351. MVT
  3352.  
  3353. Diskontinualna alokacija:
  3354. Paging
  3355. Segmentation
  3356. Kontinualna alokacija za jedan proces
  3357.  
  3358. Bare machine
  3359.  
  3360.  
  3361.  
  3362. Dve particije: Resident Monitor + User area
  3363. Rezidentni deo operativnog sistema
  3364. se obično čuva u nižoj memoriji
  3365. sa tabelom prekidnih rutina
  3366. Korisnički procesi se drže u višoj memoriji
  3367.  
  3368.  
  3369. Kontinualna alokacija
  3370. Multiprogramming:
  3371. više korisničkih programa se čuvaju u memoriju,
  3372. istovremeno
  3373. bez mešanja
  3374.  
  3375. Alokacija uz pomoć particija
  3376.  
  3377. relokacioni registar
  3378. se koristi da zaštiti
  3379. korisničke procese između sebe,
  3380. i
  3381. operativnog sistema od korisničkih procesa.
  3382. relokacioni registar
  3383. sadrži najnižu adresu procesa;
  3384. limit registar
  3385. sadrži maksimalan opseg logičkih adresa procesa
  3386. svaka logička adresa treba biti manja od limit registra.
  3387. Hardverska podrška za relokacione i limit registre
  3388. Kontinualna alokacija (MFT)
  3389. MFT = Multiprogramming with Fixed Partitions
  3390. (fiksni broj zadataka)
  3391. Idealna za multiprogramiranje sistema sa grupnom obradom
  3392.  
  3393. Memorija se deli na N particija fiksne veličine
  3394. {multiply input Q, single input Q}
  3395.  
  3396. Novi proces
  3397. se smešta u najmanju moguću particiju
  3398. uvek postoji neiskorišćenost memorije (interna fragmentacija)
  3399. Kontinualna alokacija (MFT)
  3400. Višestruki redovi (Multiple Queues)
  3401. mali neiskorišćen prostor
  3402. procesi mogu čekati, dok su velike particije neiskorištene
  3403. Jedinstveni red (Single Queue)
  3404. bolja iskorišćenost particija
  3405. veliki neiskorišćen prostor (mali procesi u velikim particijama)
  3406. Kontinualna alokacija (MFT)
  3407. U sistemima sa deljenjem vremena (time-sharing)
  3408. više korisnika
  3409. više procesa
  3410. zahtevaju više od raspoložive memorije (swapping)
  3411.  
  3412. U sistemima sa deljenjem vremena dolazni procesi su:
  3413. previše mali ili previše veliki
  3414. menjaju se u vremenu (promenljive veličine)
  3415. procesi mogu da rastu u vremenu (podaci i stek)
  3416.  
  3417. Obe osobine su nepovoljna za MFT=>
  3418. mnogo neiskorišćenog prostora u particijama => novi MVT
  3419.  
  3420. MFT je neupotrebljiv;
  3421. => novi MVT
  3422.  
  3423. Kontinualna alokacija (MVT)
  3424. Multiple-partition allocation
  3425. šupljina (hole): slobodni kontinualni deo memorije
  3426. šupljine raznih veličina su razbacane po memoriji
  3427.  
  3428. Kad proces naiđe,
  3429. traži se šupljina dovoljno velika
  3430. da preuzme proces
  3431.  
  3432. Operativni sistem vodi evidenciju o: a) alociranim particijama b) slobodnim particijama (šupljine)
  3433. Upravljanje memorijom (slobodna lista)
  3434. Bit mape (Bit Maps)
  3435. Alocirani delovi memorije + bit mapa (0=free, 1=allocated)
  3436. Ako je alocirani deo manji => bit mapa je veća
  3437.  
  3438. Povezane liste (Linked Lists)
  3439. Povezana lista slogova = Proces (Šupljina) { start, dužina}
  3440.  
  3441.  
  3442.  
  3443. Zasebne liste za šupljine sa istim veličinama => tabela sa N ulaza:
  3444. traženje šupljine je brzo, ali je spajanje šupljina veoma teško
  3445.  
  3446. Sistem udruženih parova (Buddy Systems)
  3447. MM koristi listu slobodnih blokova veličine 1,2, 4, 8, 16, 32 ….
  3448. (za 1MB = 21 liste)
  3449. Cilj=2k, svi procesi trebaju imati veličinu približno 2k
  3450. brzo pretraživanje i spajanje šupljina
  3451. ali je dominantna neiskorišćenost prostora
  3452. Sistem udruženih parova (Buddy Systems)
  3453.  
  3454. Algoritmi za izbor prazne particije
  3455. 1. First-fit:
  3456. Procesu se alocira prva šupljina koja je dovoljno velika
  3457.  
  3458. 2. Best-fit:
  3459. Alocira se najmanja šupljina koja je dovoljno velika za proces;
  3460. pretražuju se cela lista, osim ako nije sređene po veličini
  3461. u ostatku ostavlja najmanju moguću šupljinu
  3462. => ideja za worst fit
  3463.  
  3464. 3. Worst-fit:
  3465. Procesu se dodeljuje najveća moguća šupljina;
  3466. opet se pretražuje cela lista
  3467. u ostatku ostavlja najveću moguću šupljinu
  3468. Fragmentacija
  3469. Eksterna fragmentacija – ukupan memorijski prostor može da zadovolji zahtev procesa ali nije kontinualan
  3470.  
  3471. Interna fragmentacija – alocirana memorija može biti veća od zahtevane memorije procesa, ono što je preostalo od alocirane memorije se ne koristi za ništa.
  3472.  
  3473. Eksterna fragmentacija se može smanjiti sažimanjem
  3474. Cilj sažimanja je da se ispremešta sadržaj memorije kako bi se dobile veće šupljine
  3475. Sažimanje je moguće samo ako je relokacija programa dinamička i radi se u vreme izvršavanja
  3476. I/O problem
  3477. opadaju performanse sistema, jer se procesi prekidaju,
  3478. i privremeno prebacuju na disk
  3479. Diskontinualna alokacija
  3480. Straničenje (Paging)
  3481.  
  3482. Segmentacija (Segmentation)
  3483.  
  3484. Kombinacija:
  3485. Straničenje sa segmentacijom
  3486. Segmentacija sa straničenjem
  3487.  
  3488. Straničenje (Paging)
  3489. Logički adresni prostor procesa mora biti kontinualan;
  3490. ali
  3491. fizički adresni prostor procesa ne mora biti kontinualan;
  3492. fizička memorija je dodeljena procesu kad god je raspoloživa
  3493.  
  3494. Fizička memorija se podeli na blokove fiksne veličine koji se nazivaju okviri (frames)
  3495. (veličina je stepen broja 2, između 512 B i 8192 B)
  3496.  
  3497. Logički adresni prostor se podeli na blokove iste veličine koje se nazivaju stranice (pages)
  3498.  
  3499. Za pokretanje programa veličine n stranica:
  3500. potrebno je pronaći n slobodnih okvira
  3501. učitati program
  3502.  
  3503.  
  3504. Tabela stranica (page table) prevodi logičke u fizičke adrese
  3505.  
  3506. Interna fragmentacija
  3507. Straničenje (2)
  3508. Adresa koju generiše CPU podeljena je na:
  3509.  
  3510. Broj stranice (Page number) (p):
  3511. koristi se kao indeks u tabeli stranica
  3512. koja sadrži
  3513. baznu adresu fizičke stranice, okvira
  3514. Pomeraj unutar stranice (Page offset) (d):
  3515. u kombinaciji sa baznom adresom
  3516. definiše
  3517. punu fizičku adresu
  3518. koja se šalje memorijskoj jedinici
  3519. Metoda straničenja
  3520. Primer straničenja
  3521. Primer straničenja
  3522. Slobodni okviri (Free Frames)
  3523. Implementacija tabele stranica
  3524. Tabela stranica se čuva u glavnoj memoriji
  3525.  
  3526. Page-table base register (PTBR)
  3527. pokazuje na tabelu stranica
  3528.  
  3529. Page-table length register (PRLR)
  3530. ukazuje na veličinu tabele stranica
  3531.  
  3532. U ovakvoj šemi
  3533. svaka korisnička memorijska referenca
  3534. se odvija preko dve memorijske reference
  3535. jedna za tabelu stranica i druga za pristup željenoj referenci
  3536.  
  3537. Problem dvostrukog pristupanja memoriji se rešava
  3538. korišćenjem specijalne keš strukture
  3539. koja se naziva
  3540. translation look-aside buffers (TLB)
  3541. Asocijativna memorija
  3542. Asocijativna memorija – paralelno pretraživanje
  3543.  
  3544.  
  3545.  
  3546.  
  3547.  
  3548. Prevođenje adresa (A´, A´´)
  3549. Ako je A´ u asocijativnom registru, (hit)
  3550. uzmi okvir # (tj A´´)
  3551.  
  3552. Ako nije (miss)
  3553. uzmi okvir #
  3554. iz tabele stranica u memoriji
  3555.  
  3556. Hardversko straničenje sa TLB-om
  3557. Efektivno vreme pristupa
  3558. Asocijativno pretraživanje =  vremenskih jedinica
  3559.  
  3560. Pretpostavimo da je vreme trajanja jednog memorijskog ciklusa MC mikrosekundi
  3561.  
  3562. Hit ratio:
  3563. procenat vremena
  3564. vreme koje je potrebno da se pronađe broj stranice u asocijativnim registrima;
  3565. povezan sa brojem asocijativnih registara.
  3566.  
  3567. Hit ratio = 
  3568.  
  3569. Effective Access Time (EAT)= Thit + (1- )Tmiss
  3570.  
  3571. EAT =  (MC + ) + (1 – )(2MC + )
  3572. = 2MC +  – MC
  3573.  
  3574. Zaštita memorije
  3575. Zaštita memorije postiže se
  3576. uvođenjem bitova
  3577. sa specijalnim značenjem
  3578. uz svaki okvir
  3579. Valid-invalid bit se čuvaju u tabeli stranica:
  3580.  
  3581. “valid” ukazuje da je stranica
  3582. u logičkom adresnom prostoru procesa,
  3583. pa je tako to važeća stranica
  3584.  
  3585. “invalid” ukazuje da stranica
  3586. nije u logičkom adresnom prostoru procesa
  3587. Valid (v) or Invalid (i) Bit In A Page Table
  3588. Struktura tabele stranica
  3589. Hijerarhijsko straničenje (Hierarchical Paging)
  3590.  
  3591. Heš bazirane tabele stranica (Hashed Page Tables)
  3592.  
  3593. Invertovane tabele stranica (Inverted Page Tables)
  3594. Hijerarhijsko straničenje
  3595. Podeliti logički adresni prostor
  3596. u
  3597. više tabela stranica
  3598.  
  3599. Jednostavna tehnika
  3600. je straničenje u dva nivoa
  3601. (two-level page table)
  3602. Straničenje u dva nivoa
  3603. Logička adresa (na 32-bitoj mašini sa veličinom stranice 4K) je podeljena na:
  3604. broj stranice koji se sastoji od 20 bitova
  3605. ofset stranice koji se sastoji od 12 bitova
  3606. Kada se primeni tabela stranica, broj stranice se dalje deli na:
  3607. 10-bita za broj stranice
  3608. 10-bita za offset stranice
  3609. Iz toga sledi, logička adresa:
  3610. gde je:
  3611. p1 indeks u spoljnoj tabeli stranica
  3612. p2 je pozicija u selektovanoj untrašnjoj stranici
  3613. Prikaz straničenja u dva nivoa
  3614. Šema prevođenja adresa
  3615. Šema prevođenja adresa za
  3616. straničenje u dva nivoa na 32-bitoj arhitekturi
  3617. Heš bazirane tabele stranica
  3618. Koristi se kod adresnih prostora koji su > 32 bita
  3619.  
  3620. Virtuelni broj stranice se dobija iz heširane tabele stranica
  3621. Ova tabela stranica sadrži:
  3622. povezanu listu elemenata
  3623. koji imaju istu vrednost heš funkcije.
  3624.  
  3625. Virtuelni brojevi stranica se upoređuju
  3626. u ovom nizu
  3627. i traži se odgovarajući broj
  3628. Kada se pronađe odgovarajući virtuelni broj,
  3629. dobijamo vrednost fizičke stranice
  3630. Heš bazirane tabele stranica
  3631. Invertovane tabele stranica
  3632. Jedan ulaz za svaki okvir ili fizičku stranicu memorije
  3633.  
  3634. Ulaz se sastoji od:
  3635. virtuelne adrese stranice
  3636. koja je pridružena ovoj memorijskoj lokaciji,
  3637. sa informacijom o procesu koji je dobio tu stranicu PID
  3638.  
  3639. Smanjuje se memorija potrebna da uskladišti svaku tabelu stranica,
  3640. ali se
  3641. povećava vreme potrebno za pretraživanje tabele
  3642. jer se pretražuje cela tabela.
  3643.  
  3644. Zbog toga se kotisti heš tabela da ograniči pretraživanje
  3645. Invertovane tabele stranica
  3646. Deljive stranice (Shared Pages)
  3647. Deljivi kod
  3648. Jedna kopija read-only (reentrant) koda
  3649. deli se između procesa (npr., tekst editori, kompajleri, grafički sistemi)
  3650. deljivi kod treba biti na istoj fizičkoj lokaciji
  3651. u logičkom adresnom prostoru svih procesa
  3652. Privatni kod i podaci
  3653. svaki proces čuva odvojenu kopiju koda i podataka
  3654. stranice za privatni kod i podaci mogu biti bilo gde
  3655. u logičkom adresnom prostoru.
  3656. Deljive stranice
  3657. Segmentacija
  3658. Šema za upravljanje memorijom
  3659. koja podržava
  3660. korisnički pogled na memoriju
  3661.  
  3662. Program je kolekcija segmenata
  3663.  
  3664. Segment je logička jedinica kao što je:
  3665. glavni program
  3666. procedura
  3667. funkcija
  3668. metod
  3669. objekat
  3670. localne promenljive, globalne promenljive,
  3671. blok
  3672. stek
  3673. tabela simbola, nizovi
  3674. Logički izgled programa
  3675. Logički izgled segmentacije
  3676. Arhitektura segmentacije
  3677. Logička adresa se sastoji od dva dela:
  3678. <segment-number, offset>
  3679.  
  3680. Tabela segmenata – mapiranje dvodimenzionalnih fizičkih adresa;
  3681. Svaki ulaz u tabeli sadrži:
  3682. bazna adresa segmenta:
  3683. defniše početnu fizičku adresu segmenta u memoriji
  3684. ograničenje segmenata:
  3685. definiše dužinu segmenta
  3686.  
  3687. Segment-table base register (STBR)
  3688. pokazuje na lokaciju u memoriji gde je smeštena tabela segmenata
  3689.  
  3690. Segment-table length register (STLR)
  3691. predstavlja broj segmenata koje koristi program;
  3692. broj segmenata je ispravan ako je s < STLR.
  3693. Arhitektura segmentacije (2)
  3694. Relokacija:
  3695. dinamičko, preko tabele segmenata
  3696. Deljenje:
  3697. deljivi segmenti
  3698. isti broj segmenata
  3699. Alokacija:
  3700. first fit/best fit
  3701. eksterna fragmentacija
  3702. Arhitektura segmentacije (3)
  3703. Zaštita.
  3704. Za svaki ulaz u tabelu segmenata asocira se:
  3705. validation bit = 0  nepravilan segment
  3706. read/write/execute privilegije
  3707.  
  3708. Zaštita je povezana sa segmentima;
  3709. deljenje koda se odvija u nivoima segmenata.
  3710.  
  3711. Pošto segmenti variraju u vremenu,
  3712. alokacija memorije ima problem dinamičke alokacije.
  3713.  
  3714. Primer segmentacije prikazan je u sledećem dijagramu
  3715. Hardverska segmentacija
  3716. Primer segmentacije
  3717. Deljivi segmenti
  3718. Segmentacija sa straničenjem – MULTICS
  3719. MULTICS sistem rešava probleme
  3720. eksterne fragmentacije i
  3721. velikog vremena za pretraživanje
  3722. uz pomoć straničenja segmenata
  3723. Ovo rešenje se razlikuje od čiste segmentacije
  3724. u tome što se na ulazu u tabelu segmenata
  3725. ne nalazi bazna adresa segmenta,
  3726. ali
  3727. se nalazi bazna adresa tabele stranica za taj segment.
  3728. Prevođenje adresa - MULTICS
  3729. Segmentacija sa straničenjem – Intel 386
  3730. Kao što je prikazano na sledećem diagramu,
  3731. Intel 386
  3732. koristi
  3733. segmentaciju sa straničenjem
  3734. sa šemom za straničenje u dva nivoa
  3735. Prevođenje adresa - Intel 30386
  3736. Zaključak
  3737. MM šeme
  3738. {Bare, Resident Monitor,MFT,MVT, Straničenje, Segmentacija}
  3739.  
  3740. Hardverska podrška
  3741. RM, MFT=MVT registar ili par ograničenih registara
  3742. P&S zahteva tabele mapiranja
  3743.  
  3744. Performanse
  3745. Prostije šeme su brže
  3746. P&S potreban je hardverski akcelerator, registri, CPU-TLB
  3747.  
  3748. Fragmentacija
  3749. MFT i straničenje pate od interne fragmentacije (fiksna veličina prostora)
  3750. MVT i segmentacija pate od eksterne fragmentacije
  3751. Zaključak
  3752.  
  3753. Pomeranje
  3754. Logička adresa se može pomerati dinamično,
  3755. za vreme izvršavanja.
  3756. To je potrebno za kompakciju memorije
  3757.  
  3758. Swapping
  3759. Svaki algoritam može imati ugrađen swapping
  3760.  
  3761. Deljenje
  3762. deljenje obično zahteva da bude korišćemo ili straničenje ili segmentacija,
  3763. da obezbedi male pakete informacija (stranice ili segmente)
  3764. koji mogu biti deljeni.
  3765.  
  3766. Zaštita
  3767. valid/invalid bit
  3768. read only, execute only, r/w
  3769.  
  3770.  
  3771.  
  3772.  
  3773. Realizacija sistema datoteka
  3774. Struktura sistema datoteka
  3775.  
  3776. Realizacija sistema datoteka
  3777.  
  3778. Realizacija direktorijuma
  3779.  
  3780. Alokaciona metoda
  3781.  
  3782. Upravljanje slobodnim prostorom
  3783.  
  3784. Efikasnost i performanse
  3785.  
  3786. Oporavak (Recovery)
  3787.  
  3788. Log-Structured File Systems
  3789. Struktura sistema datoteka
  3790. Struktura datoteka:
  3791. Logical storage unit
  3792. Skup povezanih informacija
  3793.  
  3794. (FS) Sistem datoteka se nalazi na sekundarnoj memoriji (diskovi)
  3795.  
  3796. FS Sistem datoteka je organizovan u slojevima.
  3797.  
  3798. Kontrolni blok datoteke (FCB):
  3799. memorijska struktura
  3800. koja sadrži informacije o datoteci
  3801. Sistem datoteka realizovan u slojevima
  3802. Strukture podataka neophodne za realizaciju sistema datoteka
  3803. Disk
  3804.  
  3805. BCB (boot control block, MBR,MPT)
  3806.  
  3807. Sistemi datoteka
  3808.  
  3809. kontroni blok particije (superblock, BPB)
  3810.  
  3811. kontrolne strukture za alokaciju datoteka (FAT table, inode table, MFT)
  3812.  
  3813. direktorijumske strukture
  3814.  
  3815. FCB (file-info)
  3816. Memorijske strukture podataka
  3817. tabele otvorenih datoteka:
  3818. na sistemskom nivou
  3819. po procesu
  3820.  
  3821. keš za direktorijume = nedavno korišćeni blokovi direktorijuma
  3822.  
  3823. keš za metapodatke =nedavno korišćene strukture metapodataka
  3824.  
  3825. keš za datoteke
  3826.  
  3827. strukture za upravljanje slobodnim prostorom
  3828. Memorijske strukture podataka
  3829. Virtuelni sistem datoteka
  3830. Virtuelni sistem datoteka (VFS)
  3831. predstavlja
  3832. jedan objektno orjentisani način
  3833. realizacije sistema datoteka
  3834.  
  3835. VFS omogućava
  3836. da isti sistemski poziv (API)
  3837. bude korišćen
  3838. za različite tipove sistema datoteka
  3839.  
  3840. API je u VFS interfejsu,
  3841. a ne u bilo kom drugom sistemu datoteka
  3842. Virtuelni sistem datoteka – šematski prikaz
  3843. Realizacija direktorijuma
  3844. 1. Linearna lista
  3845. linearna lista imena datoteka sa pokazivačem na blokove podataka
  3846. jednostavna šema
  3847. dugo pretraživanje
  3848. 2. Hash tabela:
  3849. linearna lista sa hash tabelom
  3850. smanjuje vreme pretraživanja direktorijuma
  3851. kolizije
  3852. fiksne veličine
  3853.  
  3854. 3. B-trees (B+ or B-)
  3855. Alokaciona metoda
  3856. Alokaciona metoda
  3857. predstavlja način
  3858. na koji se blokovi diska
  3859. dodeljuju datoteci:
  3860.  
  3861. Kontinualna alokacija
  3862.  
  3863. Povezana alokacija
  3864.  
  3865. Indeksna alokacija
  3866. Kontinualna alokacija
  3867. Svaka datoteka zauzima
  3868. kontinualne blokove
  3869. na disku
  3870. Prosta metoda, FCB (file-info) jednostavan, sastoji se od:
  3871. početne adrese (blok #)
  3872. dužine (broj blokova)
  3873.  
  3874. Proizvoljan pristup (random access)
  3875. (direktan pristup bilo kom delu datoteke)
  3876.  
  3877. Rasipanje memorijskog prostora
  3878. (za datoteku odmah mora dodeliti ukupni adresni prostor)
  3879.  
  3880. Datoteka ne može da raste
  3881. Kontinualna alokacija prostora na disku
  3882. Problemi kod kontinualne alokacije
  3883. Eksterna fragmentacija i kompakcija
  3884. Dinamička alokacija memorije:
  3885. First fit (prva šupljina koja je dovoljno velika)
  3886. Best fit (najmanja šupljina)
  3887. Worst fit (najveća moguća šupljina)
  3888.  
  3889. Glavni problem=creation:
  3890. proces mora da zna veličinu datoteke koja će biti formirana
  3891. to veoma je teško proceniti u trenutku formiranja
  3892.  
  3893. Ako je alociran suviše mali prostor =>a datoteka treba da raste
  3894. Postoje 2 mogućnosti:
  3895. 01. Proces će se završiti sa porukom o grešci
  3896.  
  3897. 02. Kopiraće datoteku u veću šupljinu i osloboditi prošlu
  3898. Extent metoda
  3899. Mnogi noviiji sistemi datoteka (npr. VFS)
  3900. koriste modifikovanu
  3901. metodu kontinualne alokacije
  3902.  
  3903. Sistem datoteka baziran na extent metodi
  3904. alocira blokove na disku
  3905. u celinama-extents
  3906.  
  3907. Extent je celina sastavljena od kontinualnih blokova na disku
  3908. extent je jedinica promenljive veličine
  3909. extent se koristi za alokaciju datoteke
  3910. datoteka se sastoji od jednog ili više extent-a
  3911. Povezana alokacija
  3912. Svaka datoteka dobija povezanu listu blokova
  3913. blokovi mogu biti razbacani svugde po disku
  3914. Povezana alokacija
  3915. Povezana alokacija (2)
  3916. Prosta metoda, FCB zahteva samo početnu adresu
  3917.  
  3918. Sistem za upravljanje slobodnim prostorom:
  3919. nema rasipanja memorijskog prostora
  3920.  
  3921. Ne postoji random pristup
  3922. nemože direktno pristupiti
  3923. bilo kom delu datoteke
  3924. bez prethodne analize
  3925.  
  3926. Prednosti i mane povezane alokacije
  3927. Prednosti:
  3928. Nema problema sa eksternom fragmentacijom
  3929. Kreiranje datoteke: nije potrebno definisati veličinu datoteke
  3930. Datoteka može da raste dok ima slobodnih blokova
  3931. Nikada nije neophodan kompaktan prostor na disku
  3932.  
  3933. Nedostaci:
  3934. Datoteke su razbacane, ali su i pokazivači na blokove razbacani
  3935. Usporeno pretraživanje zbog sekvencijalnog pristupa
  3936. Loše za proizvoljno pristupanje datoteci
  3937. Loše za pristupanje velikim datotekama
  3938. Pokazivači => gubitak prostora
  3939. Pouzdanost =loši pokazivači mogu stvoriti mnoge greške FS
  3940. File-Allocation Table
  3941. Primer FAT tabele
  3942. Primer: primer.txt = {5, 14, 70, 130}
  3943. FCB FAT Data area
  3944. Indeksna alokacija
  3945. Svakoj datoteci se dodeljuje indeksni blok
  3946. koji sadrži sve informacije o prostornom rasporedu datoteke
  3947. Logički prikaz
  3948. Primer indeksne alokacije
  3949. Indeksna alokacija (2)
  3950. Potrebna je indeksna tabela
  3951.  
  3952. Random pristup
  3953.  
  3954. Dinamički pristup
  3955. nema eksternu fragmentaciju
  3956. ali ima
  3957. gubitak prostora (index blocks)
  3958. Indeksna alokacija – mapiranje
  3959. UNIX FS
  3960. FS Layout DATA area FCB Inode
  3961. UNIX (4KB po bloku)
  3962. Poređenje
  3963. Kontinualna alokacija
  3964. najbrža jer posle čitanja FCB,
  3965. prelazi se na direktno čitanje datoteke
  3966.  
  3967. Linkovana alokacija
  3968. dobra za sekvencijalan pristup
  3969. čita blok i čita sledeći pokazivač
  3970. dva puta pristupa disku za jedan blok datoteke
  3971.  
  3972. veoma loša za direktan pristup
  3973. za i-ti blok može zahtevati i čitanja diska
  3974.  
  3975.  
  3976. Kao rezultat, neki sistemi podržavaju
  3977. direktan pristup korišćenjem CA
  3978. sekvencijalan pristup korišćenjem LA
  3979.  
  3980. Poređenje
  3981.  
  3982. Indeksna alokacija je najkompleksnija
  3983.  
  3984. Performanse IA zavise od:
  3985. strukture indeksa i strukture memorije
  3986. veličine datoteke
  3987. pozicije potrebnih blokova
  3988. direktni blok je brži
  3989. indirektni blok je sporiji
  3990.  
  3991. Kombinacija CA+IA
  3992. za manje datoteke = CA
  3993. za veće datoteke = IA
  3994. Upravljanje slobodnim prostorom
  3995. Bit vector (n blocks)
  3996. Linkovane liste
  3997. Upravljanje slobodnim prostorom(2)
  3998.  
  3999. Modifikacije:
  4000.  
  4001. 1. Grupisanje
  4002. U prvom bloku se čuvju pokazivači
  4003. na sledećih N-1 slobodnih blokova
  4004. Dok N-ti na sledeći free information block
  4005.  
  4006. 2. Brojanje (Counting)
  4007. adresa slobodnih blokova (pointer)
  4008. +
  4009. broj slobodnih blokova u blizini
  4010. Efikasnost i performanse
  4011. Efikasnost zavisi od:
  4012.  
  4013. Disk-alokacije i algoritama direktorijuma
  4014.  
  4015. tipova podataka koji se čuvaju u direktorijumskim ulazima
  4016.  
  4017. Performanse:
  4018. disk keš:
  4019. posebni delovi u glavnoj memoriji za blokove koji se često koriste
  4020.  
  4021. free-behind and read-ahead:
  4022. tehnike za optimizaciju sekvencijalnog pristupa
  4023.  
  4024. unapređenje performansi PC-ja
  4025. tako što se odvoji deo u memoriji kao virtualni disk,
  4026. ili RAM disk
  4027. Razne komponente keša
  4028. Keš za stranice
  4029. Keš za stranice
  4030. kešira stranice
  4031. a ne blokove na disku
  4032. korišćenjem tehnike virtualne memorije
  4033.  
  4034. Memorijski mapirane datoteke koriste stranični keš
  4035.  
  4036. Datoteke: I/O Drajveri
  4037. kroz sistem datoteka
  4038. koriste baferski (disk) keš
  4039.  
  4040. Ovo je predstavljeno na sledećoj slici:
  4041. I/O Without a Unified Buffer Cache
  4042. Unified Buffer Cache
  4043. Unified buffer cache
  4044.  
  4045. koristi isti keš za stranice
  4046. da kešira obe:
  4047. memorijski mapirane stranice
  4048. i
  4049. datoteke (običan FS I/O)
  4050. I/O Using a Unified Buffer Cache
  4051. Buffer Cache
  4052. Podela keša
  4053.  
  4054. Alokacija keša (Cache allocation)
  4055.  
  4056. Razmena podataka u kešu (Cache replacement)
  4057.  
  4058. Tehnika upisa podataka (Write techniques)
  4059.  
  4060. Cache coherency for DFS
  4061.  
  4062.  
  4063. Podela keša
  4064. Organizacija keša
  4065. Svaki deo keša ima ima svoju organizaciju
  4066.  
  4067. Keš direktorijuma =
  4068. nedavno korišćeni direktorijumski blokovi
  4069. sortirani po imenu
  4070.  
  4071. Keš metapodataka =
  4072. nedavno korišćeni metapodaci
  4073. sortirani po broju metapodatka (broj inoda)
  4074.  
  4075. Keš za datoteke
  4076. Keš za definicuju blokova (2**N blokova diska)
  4077. Algoritam za alokaciju/pretraživanje
  4078. Standardna šema
  4079.  
  4080. Razmenjivanje podataka u kešu
  4081. Svi delovi keša su ograničene veličine
  4082.  
  4083. Razmenjivanje podataka u kešu je neophodno
  4084.  
  4085. Tehnike za razmenjivanje podataka u kešu
  4086. LRU
  4087. LFU
  4088. LRFU
  4089.  
  4090. Veoma složen za DFS, Internet, proxy caching …
  4091.  
  4092. Kombinacija vrednosti (prostor x starost, vreme uzimanja podataka)
  4093.  
  4094. Tehnike upisa
  4095. Keš bez mogućnostu upisa = niske performanse
  4096.  
  4097. Dve metode
  4098. Write-through (sinhronizovani upis)
  4099. Siguran sistem, bez gubitka podataka, ali sa niskim performansama
  4100. Write-back (odloženi upis)
  4101. Visoke performanse, ali postoji gubitak podataka u slučaju da sistem bude oboren
  4102. Tehnike odloženog upisa
  4103. Upis nakon zatvaranja (Write on eject)
  4104. Pražnjenje bafera (Flushing)
  4105. Log-approach
  4106. Log for meta data, only = JFS
  4107. Total log = LFS
  4108. Journaling –LOG approach
  4109. svi metapodacii se ažuriraju (t)  u jednom velikom logu
  4110. JFS - Log Structured File Systems
  4111. Log structured (or journaling) file systems
  4112. snimaju svako ažuriranje sistema datoteka
  4113. kao transakciju
  4114.  
  4115. Sve transakcije se upisuju u log
  4116. transakcija se izvršava
  4117. samo kada je upisana u log
  4118. Međutim, sistem datoteka se možda ne može odmah ažurirati
  4119.  
  4120. Transakcije u log
  4121. se asinhrono upisuju u sistem datoteka.
  4122. kada je sistem datoteka modifikovan,
  4123. transakcija se briše iz loga.
  4124.  
  4125. U slučaju obaranja sistema,
  4126. sve postojeće transakcije u logu
  4127. trebaju da nastave da funkcionišu
  4128. Oporavak (Recovery)
  4129. Keširanje i obaranje sistema
  4130. mogu prouzrokovati
  4131. oštećenje podataka
  4132.  
  4133. Provera konzistencije:
  4134. uporedjuje podat ke u strukturi direktorijuma
  4135. sa blokovima podataka na disku
  4136. pokušava da locira nekonzistentne podatke
  4137.  
  4138. [cache data] must be = [disk data]
  4139.  
  4140. U slučaju obaranja sistema podaci mogu biti oštećeni
  4141. Koristiti sistemske programe
  4142. za pravljenje kopije podataka sa diska na drugi memorijski uređaj
  4143. (flopi disk, magnetna traka).
  4144. Oporavak izgubljenih datoteka
  4145. prebacivanjem
  4146. sa bekapa
  4147.  
  4148.  
  4149.  
  4150. Interfejs za sistem datoteka
  4151. Pojam datoteke (File Concept)
  4152. Metode pristupa (Access Methods)
  4153. Struktura direktorijuma (Directory Structure)
  4154.  
  4155. Aktiviranje sistema datoteka (File System Mounting)
  4156.  
  4157. Deljenje datoteka (File Sharing)
  4158. Zaštita (Protection)
  4159. Pojam datoteke
  4160. Definicije:
  4161. 1. Kontinulan logički adresni prostor
  4162. (logička jedinica diska)
  4163.  
  4164. 2. Datoteka je imenovana kolekcija povezanih informacija
  4165. koji se čuva
  4166. na disku
  4167.  
  4168. 3. Datoteka je sekvenca bitova, bajtova, linija ili zapisa
  4169. čije značenje
  4170. je definisano od strane kreatora datoteke.
  4171. Pojam datoteke
  4172. Tipovi datoteka (content):
  4173. data {brojčani, karakter, binarni, bit mape}
  4174. program (exe files)
  4175.  
  4176. Tipovi datoteka (support)
  4177. podrška od strane OS ili od strane aplikacija
  4178. UNIX koncept =
  4179. ne postoje tipovi datoteka u OS
  4180. maksimalna fleksibilnost datoteka
  4181. aplikacije podržavaju svoje tipove datoteka
  4182.  
  4183. Oblik
  4184. slobodni oblik (npr. tekstualna datoteka)
  4185. rigidni oblik (npr. baza podataka)
  4186.  
  4187. Logička struktura datoteka
  4188. 1. None (Nema je): kolekcija reči, bajtova
  4189.  
  4190. 2. Jednostavna logička struktura
  4191. Zapisi
  4192. Fiksne dužine
  4193. Promenljive dužine
  4194.  
  4195. 3. Složene strukture
  4196. Formatirani dokumenti
  4197.  
  4198. Može se simulirati
  4199. umetanjem kontrolnih znakova
  4200. u datoteke
  4201. bez logičke strukture.
  4202.  
  4203. Ko odlučuje (pruža podršku):
  4204. Operativni sistem
  4205. Program-aplikacija
  4206. Atributi datoteka
  4207. Ime (Name)
  4208. jedina informacija koja se održava u formi koju može da čita čovek.
  4209. Tip (Type)
  4210. dopuna za sisteme koji podržavaju različite tipove podataka.
  4211. Lokacija (Location)
  4212. pokazivač na lokaciju datoteke na disku.
  4213. Veličina (Size)
  4214. trenutna veličina datoteke.
  4215.  
  4216. Zaštita (Protection)
  4217. kontroliše ko može čitati, upisivati i izvršavati datoteku.
  4218.  
  4219. Vreme, datum i korisnička identifikacija
  4220. podaci za zaštitu, sigurnost i kontrolu korišćenja datoteke.
  4221.  
  4222. Atributi-Informacije o datotekama
  4223. se čuvaju u strukturi direktorijuma,
  4224. koji je se nalazi na disku
  4225. Operacije nad datotekama
  4226. Kreiranje (Create)
  4227. (dva koraka=dodeli prostor + upisuje u direktorijum)
  4228.  
  4229. Upis (Write)
  4230. (ime ili fd, bafer u kome se nalazi informacija o upisu)
  4231. sistem za svaku otvorenu datoteku, čuva ukazivač za ciklus upisa koji se stalno ažurira
  4232.  
  4233. Čitanje (Read)
  4234. (ime ili fd, bafer u koji će se čitati datoteka )
  4235. R/W =trenutni pokazivač na otvorenu datoteku
  4236. čita trenutni pokazivač, upisuje trenutni pokazivač
  4237.  
  4238. Pozicioniranje unutar datoteke
  4239. file seek (nema transfera podataka)
  4240.  
  4241. Brisanje (Delete)
  4242. (oslobađa zauzeti prostor + uklanja FCB)
  4243.  
  4244. Odsecanje (Truncate)
  4245. postojeća datoteka se smanjuje
  4246. oslobađa se prostor
  4247. Operacije nad datotekama
  4248. Otvaranje(Fi) (Open)
  4249. pretražuje se direktorijumska struktura na disku
  4250. kada se nađe kontrolni blok datoteke
  4251. upisuje se u glavnu sistemsku tabelu
  4252.  
  4253. provera sigurnosti
  4254. način pristupa (kreiranje, ro, rw)
  4255. za višekorisnički OS kao što je UNIX=> dve tabele + brojač
  4256. tabela otvorenih datoteka za svaki proces (per process file table)
  4257. sistemska tabela otvorenih datoteka (system wide file table)
  4258.  
  4259.  
  4260. Zatvaranje(Fi) (Close)
  4261. kontrolni blok datoteke iz memorije se ažurira
  4262. ponovo upisuje na disk (ako je modifikovan)
  4263. Tipovi datoteka – ime, ekstenzija
  4264. Metode pristupa datotekama
  4265. Sekvencijalan pristup datoteci (tape model)
  4266. tekući pokazivač (cp)
  4267. čitanje sledećeg bloka + vrednost cp se ažurira
  4268. upis u sledeći blok + vrednost cp se ažurira
  4269.  
  4270. reset (premotavanje)
  4271.  
  4272. ne postoji mogućnost prepisivanja
  4273.  
  4274. Editori i prevodioci koriste ovaj način pristupa datotekama
  4275.  
  4276. Metode pristupa datotekama
  4277.  
  4278. Direktan pristup datoteci (disk model)
  4279. (datoteka = N blokova)
  4280. svakom bloku se može pristupiti u bilo koje vreme
  4281.  
  4282. pristup = N-om bloku
  4283. čitanje n-tog bloka
  4284. upis u n-ti blok
  4285.  
  4286. pozicioniranje na n-ti blok
  4287. čitanje sledećeg bloka
  4288. upis u sledeći blok (kao kod sekvencijalnog modela)
  4289.  
  4290. prepiši n
  4291.  
  4292. n = relativan broj blokova u datoteci
  4293. Sekvencijalan pristup datoteci
  4294. Simulacija sekvencijalnog pristupa preko direktnog pristupa
  4295. Indeksno-sekvencijalni pristup datoteci
  4296. Struktura direktorijuma
  4297. Kolekcija nodova
  4298. sadrži
  4299. informacije o svim datotekama
  4300. Organizacija sistema datoteka
  4301. Information in a Directory Entry (file-info) ili FCB
  4302. Ime
  4303. Tip (za OS koji podržavaju različite tipove)
  4304. Adrese ( layout datoteka)
  4305. Trenutna dužina (size)
  4306. Maksimalna dužina
  4307. Datum poslednjeg pristupa (za arhiviranje)
  4308. Datum poslednje promene
  4309. ID vlasnika
  4310. Informacije o zaštiti
  4311.  
  4312. Sadržaj
  4313. Različite informacije za različite OS
  4314. Efikasna pretraga (B-trees, hashing)
  4315. Operacije nad direktorijumima
  4316. Pretraživanje datoteka
  4317.  
  4318. Kreiranje datoteke
  4319.  
  4320. Brisanje datoteke
  4321.  
  4322. Listanje sadržaja direktorijuma
  4323.  
  4324. Promena imena datoteke
  4325.  
  4326. Arhiviranje
  4327. Logička organizacija direktorijuma
  4328. Efikasnost:
  4329. brzo lociranje datoteke.
  4330.  
  4331. Imenovanje datoteka:
  4332. podesan način, koji korisniku omogućava davanje imena.
  4333. Dva korisnika mogu imati
  4334. isto ime za različite datoteke.
  4335. Ista datoteka može imati
  4336. nekoliko različitih imena (links).
  4337.  
  4338. Grupisanje:
  4339. logičko grupisanje datoteka po osobinama,
  4340. (npr., svi Java programi, sve igre, …)
  4341. Struktura sa jednim nivoom
  4342. Jedan direktorijum za sve korisnike
  4343. Struktura sa dva nivoa
  4344. Posebni direktorijum za svakog korisnika (dva nivoa)
  4345. Stablo direktorijuma
  4346. Stablo direktorijuma (2)
  4347. Efikasno pretraživanje
  4348.  
  4349. Mogućnost grupisanja
  4350. Trenutni direktorijum (radni direktorijum)
  4351. cd /spell/mail/prog
  4352. type list
  4353.  
  4354. Apsolutna ili relativna putanja i ime
  4355.  
  4356. Stablo direktorijuma (3)
  4357. Kreiranje nove datoteke se obavlja u tekućem direktorijumu
  4358.  
  4359. Brisanje datoteke
  4360. rm <ime datoteke>
  4361.  
  4362. Kreiranje novog poddirektorijuma se obavlja u trekućem direktorijumu
  4363. mkdir <ime direktorijuma>
  4364. Primer: ako je tekući direktorijum /mail
  4365. mkdir count
  4366.  
  4367. Brisanje direktorijuma = samo ako je prazan
  4368. Acyclic-Graph Directories (deljenje prostora)
  4369. Potreba za deljenjem datoteka (ista datoteka pod različitim imenima)
  4370. Deljenje direktorijuma i datoteka
  4371. Link = pokazivač na druge datoteke u poddirektorijumu
  4372. Acyclic-Graph Directories (2)
  4373. Problem brisanja linkovanih datoteka
  4374. If dict deletes list  dangling pointer (there a link)
  4375.  
  4376. Rešenja:
  4377. Free deletion (good for symbolic links)
  4378.  
  4379. Deletion only after all references are deleted
  4380.  
  4381. Reference file or number of links count
  4382.  
  4383. Entry-hold-count solution
  4384. General Graph Directory
  4385. General Graph Directory (2)
  4386. Kako da obezbedimo da ne dođe do pojave krugova?
  4387.  
  4388. 1. ne dozvoliti linkovanje između direktorijuma
  4389. Dozvoliti linkovanje samo datoteka
  4390.  
  4391. 2. garbage collection
  4392.  
  4393. 3. algoritam za otkrivanje krugova
  4394. pre kreiranja novog linka
  4395. koristi se algoritam za detekciju krugova
  4396. da kontorliše da li je sve u redu
  4397. Aktiviranje sistema datoteka
  4398. Sistem datoteka
  4399. mora biti aktiviran
  4400. pre korišćenja
  4401.  
  4402. Neaktivan sistem datoteka
  4403. se montira (mount)
  4404. na tačku za montiranje (MPD)
  4405. (a) Existing. (b) Unmounted Partition
  4406. Mount Point
  4407. Deljenje datoteka (između korisnika)
  4408. Deljenje datoteka
  4409. na višekorisničkim sistemima
  4410. je veoma korisno
  4411.  
  4412. Deljenje se može obaviti
  4413. preko
  4414. bezbedne šeme
  4415. Na distribuiranim sistemima,
  4416. datoteke mogu biti deljene
  4417. kroz mrežu
  4418. Network File System (NFS)
  4419. je deljenje daoteka
  4420. u distribuiranim uslovima
  4421. Zaštita
  4422. Tipovi zaštite:
  4423. totalna zabrana
  4424. totalna sloboda
  4425. kontrolisani pristup
  4426.  
  4427. Lista kontrole pristupa (Access Control List)
  4428. totalna lista
  4429. sažeta lista
  4430.  
  4431. Vlasnik/kreator datoteke treba biti sposoban da kontroliše:
  4432. šta može biti urađeno
  4433. i od koga
  4434. Tipovi pristupa:
  4435. Čitanje (Read)
  4436. Upis (Write)
  4437. Izvršavanje (Execute)
  4438. Dodavanje (Append)
  4439. Brisanje (Delete)
  4440. Listanje atributa datoteke (List)
  4441. Liste pristupa i grupe (UNIX)
  4442. način pristupa: read, write, execute
  4443. tri kategorije korisnika:
  4444. RWX
  4445. a) owner access 7  1 1 1 RWX
  4446. b) group access 6  1 1 0
  4447. RWX
  4448. c) public access 1  0 0 1
  4449. Pitati manadžera da dozvoli kreiranje grupe (jedinstveno ime), npr. G, i dodati neke korisnike u grupu
  4450. Za pojedinu datoteku (npr. igra) ili poddirektorijum, definisati svojstven pristup
  4451.  
  4452.  
  4453.  
  4454.  
  4455.  
  4456. Ulazno/Izlazni (I/O) Sistemi
  4457. I/O Ulazno/Izlazni Hardver
  4458.  
  4459. Aplikacijski I/O Interfejs
  4460.  
  4461. Kernelski I/O Podsistem
  4462.  
  4463. Pretvaranje I/O Zahteva u Hardverske Operacije
  4464.  
  4465. Tokovi Podataka (Streams)
  4466.  
  4467. Performanse
  4468. I/O Hardver
  4469. Opšte kategorije I/O uređaja:
  4470. memorijski uređaji
  4471. uređaji za prenos podataka
  4472. uređaji za korisnički intrefejs
  4473.  
  4474. Opšti koncepti:
  4475. Controller (host adapter) realizovan kao:
  4476. port (4 vrste registara :kontrolni, statusni, ulazni za podatke, izlazni za podatke )
  4477. magistrala (jedan uređaj priključen na sistem-daisy chain ili direktno deljenje podataka)
  4478.  
  4479. I/O instrukcije za kontrolu uređaja
  4480.  
  4481. I/O uređaji poseduju adrese, koje se koriste za:
  4482. direktne I/O instrukcije
  4483. memorijski mapirane I/O instrukcije
  4484. Tipična Struktura Magistrale ko PC-a
  4485. Lokacije Portova I/O Uređaja Kod PC-a (partial)
  4486. Tehnika Prozivanja (polling) PIO
  4487.  
  4488. Određivanje stanja korišćenjem statusnog registra, bits:
  4489. zauzeto(busy)
  4490. greska(error)
  4491.  
  4492. Čekanje dok kontroler ne bude spreman-slobodan (free)
  4493. busy bit
  4494.  
  4495. Zadavanje komandi:
  4496. postavljanje komandnog koda u komandni registar
  4497. postavljanje podatka u izlazni registar (ako je izlazna komanda-write)
  4498. postavljanje command-ready bita
  4499.  
  4500. Izvršenje komande (sa mogučim transferom podataka)
  4501. busy bit je postavljen svo vreme
  4502.  
  4503. Čekanje na kraj komande
  4504. busy bit
  4505.  
  4506.  
  4507. Prozivanje = Busy-čekanje u petlji:
  4508. Da kontroler bude spreman
  4509. Izvršenje komande
  4510.  
  4511. Prekidi (Interrupts)
  4512. CPU poseduje prekidnu liniju
  4513. koja se aktivira
  4514. od strane I/O uređaja
  4515. ISR: Rutina za obradu prihvata prekidne signale
  4516. Maskirajući IRQ se mogu
  4517. ignorisati
  4518. odložiti (deffer)
  4519. IVT: Vektor tabela prekida
  4520. Poziva odgovarajuće rutine za obradu prioritetnih prekida
  4521. zasnovana na prioritetu
  4522. izvršava neke nemaskirane prekide
  4523.  
  4524. Prekidni mehanizam takođe se koristi za:
  4525. izuzetke (exception)
  4526. Software interrupts
  4527. Prekid-Odvijanje I/O Ciklusa
  4528. Vektor Tabela Događaja Kod Intel Pentium Procesora
  4529. Direktan Pristup Memoriji (DMA)
  4530. PIO=Programirani I/O
  4531. Za svaki transfer podataka, PIO zahteva dve faze:
  4532. čekanje u petlji da podaci budu spremni
  4533. transfer podataka
  4534.  
  4535. DMA:Koristi se da bi se izbegao
  4536. programirani I/O
  4537. za veće transfere podataka
  4538. Zahteva DMA controller
  4539. Oslobađa CPU
  4540. od prenosa podataka
  4541. DMA prenosi direktno podatke
  4542. između I/O uređaja i memorije
  4543. Šest Koraka Izvođenja DMA Transfera
  4544. Aplikacijski I/O Interfejs
  4545. I/O sistemski pozivi su:
  4546. visokog nivoa, generalni
  4547.  
  4548.  
  4549. Device-driver layer
  4550. Karakteristike uređaja su sakrivene
  4551. u specijalnim modulima kernela koji se nazivaju drajveri
  4552.  
  4553. Podela uređaja:
  4554. Po načinu transfera podataka - na blok i karakter uređaje
  4555. Po metodi pristupa - sekvencijalni i uređaje sa direktnim ili slučajnim prisitupom
  4556. Po deljivosti - na deljive i nedeljve
  4557. Po brzini - brzi i spori
  4558. Po mogućnosti upisa - read-write, read only, or write only
  4559. Struktura I/O Kernela
  4560. Karakteristike I/O Uređaja
  4561. Blok i Karakter Uređaji
  4562. Blok uređaji se odnose na diskove
  4563. rade sa blokovima podataka
  4564.  
  4565. koriste komande: read, write, seek
  4566.  
  4567. koriste sirov(raw) I/O pristup sistemu ili pristup preko sistemske cache memorije
  4568. memorija-moguć je mapirani pristup datotekama
  4569. Karakter uređaji koriste tastaturu, miš, serijske portove
  4570. rade u režimu bajt po bajt
  4571.  
  4572. koriste komande: get, put
  4573.  
  4574. biblioteke
  4575. smeštene su na vrhu
  4576. dozvoljavaju editovanje po liniji
  4577. Mrežni Uređaji
  4578. Razlikuju se od
  4579. blok i karakter uređaja
  4580. zato što poseduju sopstveni interfejs socket
  4581.  
  4582. Unix i Windows NT/9i/2000 sadrže socket interfejs
  4583. razdvajaju mrezni protokol
  4584. od mrežnih operacija
  4585. sadrže select funkcionalnost
  4586.  
  4587. Mehanizmi za mrežne interfejse
  4588. pipes
  4589. FIFO
  4590. streams
  4591. redovi za poruke (message queue)
  4592. mailboxes
  4593. Časovnik i Tajmer
  4594. Obezbeđuju:
  4595. trenutno vreme
  4596. proteklo vreme
  4597. tajmerski okidač (trigger function)
  4598. Programibilni intervalski tajmeri se koriste za:
  4599. merenje proteklog vremena
  4600. periodične prekide
  4601. ioctl (na UNIX-u) pokriva
  4602. sporedne aspekte I/O
  4603. kao što su clock i tajmeri
  4604. Blokirajuće i Ne-blokirajuće I/O Operacije
  4605. Blokirajući:
  4606. proces se blokira i čeka sve dok se ne kompletira I/O operacija
  4607. Lako za korišćenje i razumevanje
  4608. Nedovoljan za neke potrebe
  4609. Neblokirajući:
  4610. I/O poziv vraća onoliko bajtova koliko je dostupno
  4611. korisnički interfejs, kopiranje podataka (buffered I/O)
  4612. ostvareno preko višenitnih procesa (multi-threading)
  4613. brzo odgovara sa brojem pročitanih ili upisanih bajtova
  4614. Asinhroni:
  4615. I/O pozivi vraćaju kontrolu procesu u istom trenutku
  4616. Proces se odvija dok se I/O izvršava
  4617. teško za korišćenje
  4618. I/O podsistem označava procesu kada je I/O završen
  4619. Kernelski I/O Podsistem
  4620. 1. Raspoređivanje (Scheduling)
  4621. poredak I/O zahteva prispelih u per-device reda čekanja
  4622. operativni sistemi optimzuju red izvršenja
  4623.  
  4624. 2. Baferisanje (Buffering) –
  4625. smešta privremeno podatke u memoriju
  4626. dok se obavlja
  4627. njihov transfer između uređaja
  4628.  
  4629. Baferisanje se koristi da bi se :
  4630. prevazišle razlike u brzini uređaja
  4631. prevazišle razlike u veličini transfera između uređaja
  4632. održala semantika kopiranja “copy semantics”
  4633. Sun Enterprise 6000 Device-Transfer Rates
  4634. Kernelski I/O Podsistem
  4635. 3. Keširanje:
  4636. brza memorija koja čuva kopije podataka
  4637. Uvek samo kopije
  4638. Ključno je za performanse
  4639. 4. Spool tehnika:
  4640. bafer koji čuva izlazne podatke za uređaj
  4641. ako uređaj može da pošalje samo jedan zahtev u tom trenutku
  4642. npr. Štampač
  4643.  
  4644. 5. Rezervacija uređaja –
  4645. omogućava ekskluzivni pristup uređaju
  4646. Sistemski pozivi za dodeljivanje i razdeljivanje
  4647. Motrenje na zastoje
  4648. Upravljanje greškama
  4649. OS može da se oporavi od greške:
  4650. čitanja diska
  4651. nedostupnosti uređaja
  4652. privremenog neuspelog upisa
  4653. Uglavnom vraća:
  4654. broj greške
  4655. ili
  4656. kod
  4657. kada I/O zahtev neuspe
  4658. System error logs
  4659. čuvaju izveštaje o problemima (problem reports)
  4660. Kernelske Strukture Podataka
  4661. Kernel mora da čuva informacije o stanju I/O komponenti,
  4662. kao što su:
  4663. tabela otvorenih datoteka
  4664. mrežne konekcije
  4665. stanja kareakter uređaja
  4666. Većina kompleksnih struktura podataka čuvaju informacije za:
  4667. baferisanje
  4668. dodeljivanje memorije
  4669. “prljavi” blokovi
  4670. neki OS koriste
  4671. objektno orijentisane metode
  4672. i
  4673. Message-passing
  4674. za implementaciju I/O
  4675. UNIX I/O Struktura Kernela
  4676. Transformisanje I/O Zahteva u Hardverske Operacije
  4677. Abalizirajmo učitavanje datoteke sa diska:
  4678. Određivanje uređaja koji čuva datoteku
  4679.  
  4680. Prevođenje imena koje se prikazuje uređaju
  4681.  
  4682. Fizičko učitavanje podataka sa diska u bafer
  4683.  
  4684. Priprema podataka dostupnih za proces
  4685.  
  4686. Vraćanje kontrole procesu
  4687. Životni Ciklus I/O Zahteva
  4688. STREAMS
  4689. stream:
  4690. full-duplex komunikacioni kanal
  4691. Između:
  4692. procesa na korisničkom nivou
  4693. i
  4694. uređaja
  4695.  
  4696. (stream) se sastoji od:
  4697. glave (stream head) koja komunicira sa korisničkim procesom
  4698. drajvera i interfejsa sa uređaja
  4699. proizvoljnog broja STREAM modula između njih
  4700.  
  4701. Svaki modul sadrži
  4702. red za čitanje
  4703. red za pisanje
  4704.  
  4705. Prosleđivanje poruka
  4706. se koristi
  4707. za komunikaciju
  4708. između redova
  4709. Struktura STREAM-ova
  4710. Performanse
  4711. I/O performanse jako utiču na opšte performanse sistema:
  4712. Zahtev od CPU da izvrši drajverski i kernelski I/O kod
  4713.  
  4714. prebacivanja konteksta i rukovanja prekidima
  4715.  
  4716. kopiranje podataka
  4717.  
  4718. Mrežni saobraćaj takođe izaziva veliki broj prekida
  4719. Komunikacija Unutar Računara
  4720. Poboljšanje Performansi
  4721. Smanjenje broja prebacivanja sadržaja
  4722.  
  4723. Smanjenje kopiranja podataka
  4724.  
  4725. Smanjenje prekida
  4726. korišćenjem
  4727. velikih transfera
  4728. pametnih kontrolera,
  4729. tehnikom pozivanja polling
  4730.  
  4731. Korišćenjem direktnog pristupa memoriji (DMA)
  4732.  
  4733. Balansirano korišćenje:
  4734. CPU, memorije, magistrale, I/O performansi
  4735. za najveću propusnu moć
  4736. Način Postizanja Najbolje Funkcionalnosti Uređaja
  4737.  
  4738.  
  4739.  
  4740.  
  4741.  
  4742. Mass Storage Sistemi (Za Masovno Skladištenje)
  4743. Struktura Diska
  4744.  
  4745. Raspoređivanje Disk Zahteva (Disk Scheduling)
  4746.  
  4747. Upravljanje Diskovima
  4748.  
  4749. Upravljanje Swap Prostorom
  4750.  
  4751. RAID Strukture
  4752.  
  4753. Priključivanje Diskova
  4754.  
  4755. Realizacija Stabilnih Sistema
  4756.  
  4757. Tercijalna Memorija
  4758.  
  4759. Zadaci Operativnog Sistema
  4760.  
  4761. Zadaci Performansi
  4762. Struktura Diska
  4763. Diskovi se adresiraju
  4764. kao široko jednodimenziono polje logičkih blokova ,
  4765. gde je
  4766. logički blok najmanja jedinica transfera
  4767.  
  4768. Jednodimeziono polje logičkih blokova
  4769. se mapira
  4770. u sektore na disku sekvencijalno .
  4771. logički blok 0
  4772. se mapira u prvi sektor,
  4773. prve staze,
  4774. spoljašnjeg cilindra .
  4775. Proces mapiranja se nastavlja na drugu stazu,
  4776. pa se pređe na sledeću stazu tog cilindra,
  4777. pa na sledeći cilindar
  4778. od krajnjeg unutrašnjeg
  4779.  
  4780. Raspoređivanje Disk Zahteva (Disk Scheduling)
  4781. operativni sistem je odgovoran
  4782. za efikasno korišćenje hardvera
  4783.  
  4784. Za diskove, ovo znači:
  4785.  
  4786. 1. brzo vreme pristupa (seek)
  4787.  
  4788.  
  4789.  
  4790. 2. brze disk transfere (disk media bandwidth)
  4791.  
  4792. Vreme Pristupa
  4793.  
  4794. Vreme pristupa se sastoji iz dve osnovne komponente:
  4795. Vreme pozicioniranja (seek time)
  4796. je vreme za koje disk
  4797. pomera glavu do cilindra
  4798. koji sadrži željeni sektor
  4799.  
  4800. Rotaciono kašnjenje (Rotational latency)
  4801. je naknadno vreme
  4802. čekanja da glava diska
  4803. rotira na željeni sektor
  4804.  
  4805. Smanjenje vremena pozicioniranja
  4806.  
  4807. Vreme pozicioniranja  udanjenost pozicije
  4808.  
  4809.  
  4810. Brzina Disk Transfera
  4811.  
  4812.  
  4813. Brzina disk transfera je:
  4814. ukipan broj prebačenih bajtova
  4815. u jedinici vremena
  4816.  
  4817. ukupno vreme između
  4818. prvog zahteva za servis
  4819. završetka poslednjeg transfera
  4820. Raspoređivanje Disk Zahteva
  4821. Postoji nekoliko algoritama
  4822. za raspoređivanje servisiranje disk I/O zahteva
  4823.  
  4824. Ilustrovaćemo ih preko reda zahteva (disk 0-199)
  4825. 98, 183, 37, 122, 14, 124, 65, 67
  4826.  
  4827. Pokazivač na glavu (head pointer) 53
  4828. FCFS
  4829. SSTF
  4830. Kriterijum: Biranje zahteva
  4831. sa minimalnim vremenom pozicioniranja
  4832. od trenutne pozicije glave
  4833.  
  4834. SSTF raspoređivanje
  4835. je forma SJF raspoređivanja;
  4836. može da izazove zakucavanje nekih zahteva
  4837.  
  4838. SSTF (Nastavak)
  4839. SCAN
  4840. Kriterijum:
  4841. glava diska počinje sa jednog kraja diska,
  4842. I kreće se prema drugom kraju diska,
  4843. opslužuje zahteve
  4844. dok ne dođe do drugog kraja diska,
  4845. gde se kretanje glave obrće
  4846. i opsluživanje se nastavlja
  4847.  
  4848. Često se naziva i lift algoritam.
  4849.  
  4850.  
  4851. SCAN (Nastavak)
  4852. C-SCAN
  4853. Obezbeđuje ravnomernije vreme čekanja od SCAN.
  4854.  
  4855. Kriterijum:
  4856. glava se kreće od jednog kraja diska do drugog.
  4857. opslužuje zahteve po redu.
  4858. kada dođe do kraja,
  4859. međutim,
  4860. on se odmah vraća na početak diska,
  4861. bez ikakvog opsluživanja zahteva pri povratku.
  4862.  
  4863. Opsluživanje cilindara
  4864. kao kružne liste
  4865. koja se vrti okolo
  4866. od zadnjeg cilindra
  4867. do prvog
  4868. C-SCAN (Nastavak)
  4869. C-LOOK
  4870. Verzija C-SCAN:
  4871. glava ide samo do poslednjeg zahteva u svakom pravcu,
  4872. zatim odmah obrće pravac,
  4873. i vraća na najbliži zahtev na početku diska
  4874. i tako stalno do kraja diska
  4875. C-LOOK (Nastavak)
  4876. Izbor Algoritma za Disk Raspoređivanje
  4877. SSTF je najbolji na prvi pogled
  4878. SCAN i C-SCAN su bolji
  4879. za sisteme
  4880. koji smeštaju velike količine podataka na disk.
  4881.  
  4882. Performanse zavise od broja i tipa zahteva
  4883.  
  4884. Na zahteve za opsluživanje diska se može uticati preko metoda alokacije datoteka (allocation method).
  4885.  
  4886. Algoritmi za raspoređivanje po disku
  4887. trebaju biti napisani kao odvojeni moduli operativnog sistema,
  4888. dozvoljavaju da budu zamenjeni sa drugim algoritmima ako je to neophodno.
  4889.  
  4890. SSTF i LOOK su dobar izbor
  4891. za default algoritam
  4892. Upravljanje Diskovima
  4893. Formatiranje niskog nivoa (low-level formatting) , ili fizičko formatiranje (physical formatting)
  4894. Deljenje diska u sektore
  4895. da bi disk kontroler
  4896. mogao da čita i upisuje
  4897.  
  4898. Korišćenje diska za čuvanje datoteka:
  4899. Operativni sistem mora da snimi
  4900. sopstvene strukture podataka na disk
  4901. 1. Deljenje diska na jednu ili više grupa cilindara
  4902. 2. logičko formatiranje ili pravljenje sistemskih datoteka
  4903.  
  4904. Boot block podiže sistem (start a booting)
  4905. Bootstrap program je smešten u ROM memoriji
  4906. Bootstrap loader program
  4907.  
  4908. Metode kao što je sector sparing
  4909. se koriste
  4910. da bi se otklonili loši blokovi (bad blocks).
  4911. MS-DOS Disk Šema (FAT)
  4912. Upravljanje Swap Prostorom
  4913. Swap-prostor, Virtuelna memorija
  4914. koristi prostor diska
  4915. kao nastavak glavne memorije
  4916. Swap-prostor može biti
  4917. izdvojen od normalnog fajl sistema,
  4918. može biti u zasebnoj particiji diska
  4919.  
  4920. Upravljanje swap-prostorom
  4921. 4.3BSD dodeljuje swap prostor
  4922. kada se započne proces;
  4923. zadržava segmente teksta (program) i segmente podataka
  4924. Kernel koristi swap mape to da bi vodio evidenciju o korišćenju
  4925. swap prostora
  4926. Solaris 2 dodeljuje swap prostor
  4927. samo kada se strana izbaci iz fizičke memorije,
  4928. a ne kada je strana prvi put kreirana u virtuelnoj memoriji
  4929. 4.3 BSD Text-Segment Swap Mapa
  4930. 4.3 BSD Data-Segment Swap Mapa
  4931. RAID
  4932. Na početku
  4933. N diskova = kao jedan veliki disk
  4934.  
  4935.  
  4936.  
  4937.  
  4938.  
  4939.  
  4940.  
  4941.  
  4942.  
  4943. Ali…Bez velikih, previše skupih diskova
  4944. ogroman kapacitet
  4945. veoma visoke performanse
  4946. veoma visoka pouzdanost
  4947. RAID Struktura
  4948. RAID
  4949. 1. Povećanje performansi
  4950. paralelizam operacija diska za velike zahteve
  4951. više diskova radi paralelno za jedan zahtev
  4952. konkurentni rad istovremeno za manje zahteve
  4953. više zahteva na različitim diskovima
  4954.  
  4955. 2. Povećanje pouzdanosti
  4956. RAID obezbeđuju pouzdanost preko redundanse
  4957. Dve osnovne šeme su:
  4958. tehnika ogledala (mirroring)
  4959. Informacije o parnosti (parity information)
  4960.  
  4961. 3. RAID je realizovan u 7 različitih nivoa
  4962. RAID (Nastavak)
  4963. Nekoliko poboljšanja
  4964. obuhvata korišćenje više diskova
  4965. koji rade kooperativno
  4966. Disk striping koristi grupu diskova kao jednu jedinicu
  4967. RAID šeme
  4968. poboljšavaju performanse
  4969. poboljšavaju pouzdanost sistema za smeštanje
  4970. čuvanjem redundantnih podataka
  4971.  
  4972. Ogledala (mirroring) ili senčenje(shadowing) čuvaju duplikate svakog diska
  4973.  
  4974. Parnost mnogo manje troši redundanse
  4975. Konvencialno Postavljanje Podataka naspram Stripinga
  4976. Mirroring vs Parity
  4977. Mirroring
  4978.  
  4979.  
  4980.  
  4981. Parity
  4982.  
  4983. Bez Redundanse (RAID Nivo 0)
  4984. niska cena svake RAID organizacije
  4985.  
  4986. uopšte ne koristi redundansu
  4987.  
  4988. Najbolje write preformanse
  4989. pošto uopšte ne mora da obnavlja(update) informacije o redundansi.
  4990.  
  4991. Neočekivano, nema najbolje read performanse.
  4992. Šeme redudansi koje dupliciraju podatke, kao što su mirroring, mogu bolje da izvode učitavanja(reads) preko
  4993. selektivnog raspoređivanja zahteva na disku sa najkraćim očekivanim vremenom pozicioniranja i rotacionih kašnjenja
  4994.  
  4995. Bez redundanse, svaki pojedini disk failure će rezultovati gubitkom podataka.
  4996.  
  4997. RAID-0 se koriste:
  4998. kod superkompjutera
  4999. koji su više nego pouzdani
  5000. gde su performanse i kapacitet
  5001. osnovni zahtev
  5002. Optimal Stripe Unit- RAID-0
  5003. RAID-0
  5004. Stripe unit- minimalna jedinica podataka=
  5005.  
  5006.  
  5007.  
  5008.  
  5009.  
  5010. Gde je:
  5011. P prosečno vreme pozicioniranja
  5012. X prosečna brzina transfera
  5013. L (concurrency)
  5014. Z veličina zahteva
  5015. N veličina reda na disku
  5016.  
  5017. MTTF(RAID-0) = MTTF(disk) / N
  5018. Mirrored - Ogledalo (RAID Level 1)
  5019. Koristi duplo
  5020. više diskova nego
  5021. disk redovi bez redundanse
  5022.  
  5023. svaki upis povlači 2 upisa
  5024.  
  5025. najsporiji za upis (duplo =100%), ali ne uvek
  5026.  
  5027. Kada se podatak čita,
  5028. može biti pročitan sa diska
  5029. sa kraćim pravljenjem redovima, vremenom pozicioniranja i rotacionim kašnjenjem
  5030.  
  5031. Ako disk otkaže, druga kopija se koristi za opsluženje zahteva
  5032.  
  5033. Mirroring se često koristi za baze podataka
  5034. gde su raspoloživost i stopa transakcije
  5035. mnogo važnije od efikasnosti skladištenja
  5036. Stil Memorije ECC (RAID Level 2)
  5037. Memorijski sistemi imaju predviđen oporavak
  5038. izgubljenih komponenti
  5039. sa mnogo manje štete od mirroring-a korišćenjem Hamming kodova.
  5040.  
  5041. Hamming kodovi
  5042. sadrže parnost
  5043. za različita prekoračenja sadržaja komponenti.
  5044.  
  5045. U jednoj verziji ove šeme,
  5046. 4 diska podataka zahtevaju 3 pridodata diska,
  5047. jedan manje od mirroring-a.
  5048.  
  5049. Pošto je broj pridodatih diskova
  5050. proporcionalan logaritmu ukupnog broja diskova u sistemu,
  5051. efikasnost smeštanja se uvećava kada se uveća broj diskova podataka.
  5052.  
  5053. Stil Memorije ECC (RAID Level 2)
  5054. Ako se jedna komponenta otkaže,
  5055. nekoliko komponenata parnosti će imati netačne vrednosti,
  5056. i
  5057. izgubljena komponenta
  5058. važi kao zajednička za svaki netačan sadržaj.
  5059.  
  5060. Izgubljen informacija se vraća
  5061. Čitanjem drugih komponenti iz sadržaja,
  5062. uključujući i komponentu parnosti,
  5063. i setovanje bita koji nedostaje na 0 ili 1
  5064. da bi se dobila odgovarajuća parnost za taj sadržaj.
  5065.  
  5066. Prema tome,
  5067. višestruki pridodati diskovi su za identifikaciju greške,
  5068. ali
  5069. samo jedan potreban za povratak izgubljene informacije.
  5070. Bit-Isprepletana Parnost (RAID Level 3) Bit-Interleaved Parity
  5071. Može da poboljša memory-style ECC raspored diskova
  5072. zato što,
  5073. za razliku od otkaza memorijskih komponenti,
  5074. disk kontroleri mogu lako da otkriju
  5075. koji disk je otkazao
  5076.  
  5077. Prema tome,
  5078. može da koristi samo jedan disk parnosti
  5079. pre nego set diskova parnosti
  5080. da bi povratio izgubljenu informaciju
  5081.  
  5082. Stripe unit(minimalna jedinica podataka) < 512 bajtova (1bajt ili 1 bit)
  5083. Svako čitanje zahteva pristup svim diskovima podataka
  5084. svaki zahtev za upis pristupa svim diskovima podataka i diskovima parnosti.
  5085.  
  5086. Prema tome samo jedan zahtev može biti opslužen u datom trenutku
  5087. Bit-Isprepletana Parnost (RAID Level 3) Bit-Interleaved Parity
  5088. Zato što disk parnosti sadrži samo parnost bez podataka,
  5089. disk parnosti ne može učestvovati u čitanju,
  5090. što dovodi do nešto slabijih performansi čitanja
  5091. od
  5092. redudansnih šema
  5093. koje distribuiraju parnost i podatke preko celog diska (RAID5).
  5094.  
  5095. RAID-3
  5096. se često koristi kod aplikacija
  5097. koje zahtevaju
  5098. veliku brzinu disk transfera (bandwidth)
  5099. a ne velike I/O brzine
  5100.  
  5101. Block-Isprepletana Parnost (RAID Level 4) Block-Interleaved Parity
  5102. N diskova podataka + 1 disk parnosti
  5103. Sličan RAID3, ali striping unit = N disk blokova.
  5104. Zahtevi za čitanje
  5105. su manji od minimalne jedinice podataka (striping unit)
  5106. pristupaju
  5107. samo jednom disku podataka
  5108.  
  5109. Zahtevi za upis
  5110. mora da ažurira blokove podataka za zahteve
  5111. takođe mora da proračuna i ažurira blokove parnosti
  5112.  
  5113. Zato što RAID4, ima samo jedan disk parnosti,
  5114. koji mora da se ažurira na svakoj upisnoj operaciji,
  5115. disk parnosti može lako da postane usko grlo.
  5116.  
  5117. Zbog ovog ograničenja,
  5118. RAID-5, block-interleaved distributed-parity
  5119. je u opštem slučaju bolji od RAID-4, block-interleaved parity
  5120.  
  5121. Block-Interleaved Parity (RAID Level 4)
  5122.  
  5123. Za velike upise
  5124. koji dodiruju blokove na celom disku,
  5125. parnost se lako proračunava
  5126. preko ekskluzivne OR ili funkcije novog podatka za svaki disk.
  5127.  
  5128. Za male zahteve upisa
  5129. koji ažuriraju samo jedan disk podataka
  5130. parnost se izračunava
  5131. beleženjem
  5132. kako se novi podatak razlikuje od starog i
  5133. stavlja ove razlike u blok parnosti
  5134.  
  5135. Mali upisni zahtevi zahtevaju 4 disk I/O-a:
  5136. jedan za upis novog podatka
  5137. dva za čitanje starog podatka i stare parnosti da bi proračunao novu parnost
  5138. jedan za upis nove parnosti
  5139. Ovo upućuje ka čitaj-promeni-upiši (read-modify-write) proceduri.
  5140. Block-Interleaved Distributed-Parity (RAID Level 5)
  5141.  
  5142. Distribuirani disk parnosti eliminiše usko grlo parnosti
  5143. Podaci su na svim diskovima
  5144. Bitovi parnosti na svim diskovima
  5145.  
  5146. svi diskovi su jednako opterećeni pri operacijama čitanja
  5147. RAID 5 je najbolji za:
  5148. mala čitanja
  5149. velika čitanja
  5150. performanse velikih upisa bilo kog pridodatog reda diska
  5151.  
  5152. Mali zahtevi upisa su i dalje neefikasni
  5153. u poređenju sa šemama kao što je mirroring,
  5154. zbog potrebe za izvođenjem read-modify-write operacija
  5155. za ažuriranje parnosti
  5156.  
  5157. Ova slabost u performansama
  5158. RAID level 5 disk redova
  5159. je bila tema intenzivnih ispitivanja.
  5160.  
  5161. RAID-5
  5162. stripe jedinica=
  5163. 0.5K+1/4 * prosečno vreme pozicioniranja * brzine prenosa podataka * (konkurentnost-1))
  5164. stripe jedinica=
  5165. 0.5 * prosečno vreme pozicioniranja * brzina prenosa podataka
  5166.  
  5167. MTTF(RAID-5) = MMTF2(disk) / MTTR(disk)xNx(G-1)
  5168. N - ukupan broj diskova
  5169. G – grupa parnosti
  5170. MTTF(RAID-1) = MMTF2(disk) / 2xMMTR(disk)
  5171. N = 2
  5172. G = 2
  5173. RAID5 Problem Performansi Malih Upisa
  5174.  
  5175. Logovanje parnosti (Parity Log)
  5176.  
  5177.  
  5178. RAID keširanje
  5179. P+Q Redundansa (RAID Level 6)
  5180. Parnost
  5181. je kod redudanse
  5182. sposoban za ispravku bilo koje greške
  5183.  
  5184. Kod velikih RAID sistema se uzimaju u obzir,
  5185. mogućnost višestrukih grešaka
  5186. tu su potrebni jači kodovi
  5187.  
  5188. Prema tome, aplikacije sa strožijim zahtevima
  5189. zahtevaju
  5190. jače kodove za ispravljanje grešaka.
  5191.  
  5192. Jedna takva šema, nazvana P+Q redudansa
  5193. koristi Reed-Solomon kodove
  5194. za zaštitu
  5195. od dva otkaza diska
  5196. korišćenjem
  5197. neophodan minimum od dva pridodata diska
  5198. P+Q Redundancy (RAID Level 6)
  5199. P+Q RAID su
  5200. po strukturi veoma slični
  5201. RAID sa block-interleaved distributedparnosti
  5202. rade na sličan način
  5203.  
  5204. U suštini, P+Q RAID takođe
  5205. izvode male operacije upisa
  5206. koristeći read-modify-write proceduru,
  5207. očekivano je da umesto 4 pristupa disku za upis,
  5208. P+Q RAID zahtevaju 6 pristupa disku
  5209. usled
  5210. potrebe za ažuriranjem obe ‘P’ i ‘Q’ informacije
  5211.  
  5212. RAID (0 + 1) and (1 + 0)
  5213. Priključivanje Diskova
  5214. Disk može da se priključi na dva načina:
  5215.  
  5216. Host attached (server) preko I/O porta
  5217.  
  5218. Network attached (mrežni) preko mrežne konekcije
  5219. Mrežni Način Priključivanja
  5220. Storage-Area Network
  5221. Realizavija Stabilnih Sistema
  5222. Upis-ispred logaritamske šeme zahteva stabilni sistem
  5223. Da bi se realizovao stabilni sistem potrebna je:
  5224. kopija informacije
  5225. o više nepromenljivih mediuma
  5226. sa nezavisnim modovima otkaza
  5227.  
  5228. Informacija o ažuriranju
  5229. da bi se kontrolisano obezbedilo
  5230. da možemo da povratimo
  5231. stabilni podatak
  5232. posle bilo kog otkaza za vreme transfera podataka
  5233. Tercijalna memorija
  5234. Osnovne karakteristike tercijalne memorije je niska cena
  5235.  
  5236. Generalno, tercijalna memorija je napravljena
  5237. korišćenjem
  5238. izmenljivih mediuma
  5239. Opšti primeri izmenljivih mediuma su
  5240. floppy diskovi
  5241. CD-ROM-ovi; DVD-ovi
  5242. i neki drugi tipovi
  5243. Izmenljivi Diskovi
  5244. Floppy disk —
  5245.  
  5246. tanak fleksibilan disk obložen sa magnetnim materijalom,
  5247. upakovan u plastični omot.
  5248. Većina je kapaciteta oko 1 MB
  5249.  
  5250. slična tehnologija se koristi kod izmenjivih diskova
  5251. čiji je kapacitet veći od 1 GB.
  5252. Izmenljivi magnetni diskovi mogu biti
  5253. približne brzine kao hard diskovi,
  5254. ali se lakše oštećuju
  5255. Izmenljivi Diskovi (Nastavak)
  5256. Magnetno-optički diskovi
  5257. upisuju podatke
  5258. na čvrst disk
  5259. obložen magnetnim materialom.
  5260.  
  5261. Korišćenjem toplote lasera na disk se
  5262. upisuju podaci
  5263. Laser se takođe koristi za čitanje podataka.
  5264.  
  5265. Magneto-optička glava
  5266. datoteke su mnogo udaljenije
  5267. od površine diska
  5268. nego kod glave magnetnog diska, i
  5269. magnetni materijal je prekriven zaštitnim (plastičnim ili staklenim) slojem.
  5270.  
  5271. Optički diskovi ne koriste magnetizam;
  5272. oni koriste specijalne materijale
  5273. koji se menjaju laserskim svetlom.
  5274. WORM Diskovi
  5275. Podaci na R/W diskovima
  5276. mogu da se menjaju iznova i iznova.
  5277.  
  5278. WORM (“Upiši jednom čitaj mnogo puta”) diskovi
  5279. Podaci mogu samo jednom da se upišu.
  5280.  
  5281. Tanki aluminijumski film smešten
  5282. između dva staklena
  5283. ili plastična diska.
  5284.  
  5285. Za upis bita,
  5286. uređaj koristi lasersku svetlost
  5287. za utiskivanje male rupe u aluminumu;
  5288. Informacije mogu biti uništene ako se neprepravljaju
  5289.  
  5290. Veoma su izdržljivi i pouzdani.
  5291.  
  5292. Read Only diskovi, kao što su CD-ROM i DVD,
  5293. Dolaze iz fabrike
  5294. sa podacima koji su već upisani.
  5295. Trake
  5296. U poređenju sa diskom,
  5297. trake su jeftinije i
  5298. čuvaju više podataka,
  5299. ali nasumičan pristup je mnogo sporiji.
  5300. Traka je ekonomičan medium
  5301. pod pretpostavkom da se ne zahteva brz nasumičan pristup,
  5302. npr., backup disk podataka,
  5303. smešta velike količine podataka.
  5304. Instalacija velikih traka
  5305. obično koristi robotiske menjače traka
  5306. koji pomeraju trake izmežu uređaja i
  5307. smeštaju slotove u biblioteku.
  5308. stacker – biblioteka koja čuva nekoliko traka
  5309. silo – Biblioteka koja čuva na hiljade traka
  5310. datoteka koja se nalazi na disku može biti arhivirana na traci po niskoj ceni smeštanja; kompjuter može ponovo da ih vrati na disk za aktivnu upotrebu
  5311. Proglemi Operativnog Sistema
  5312. Osnovni zadaci Operativnog Sistema
  5313. su da upravlja fizičkim uređajima i
  5314. da predstavi abstrakciju virtuelne mašine
  5315. Aplikacijama
  5316.  
  5317. Za hard disk, OS sprovodi dve apstrakcije:
  5318.  
  5319. Sirov uređaj –
  5320. niz blokova podataka.
  5321.  
  5322. Sistem fajlovi –
  5323. Redovi čekanja OS i uređenja
  5324. ispreplitanje zahteva nekoliko aplikacija.
  5325. Aplikacioni Inteffejs
  5326. Većina OS-a rukovodi izmenljivim diskovima skoro isto kao sa fiksnim diskovima
  5327. novi kertridž je formatiran
  5328. i prazan fajl sistem generisan na disku
  5329.  
  5330. Trake se predstavljaju kao sirov medium
  5331. aplikacija ne otvara fajl na traci
  5332. već otvara ceo uređaj kao sirov uređaj
  5333.  
  5334. Obično je uređaj za traku rezervisan samo za tu aplikaciju.
  5335. Pošto OS ne sprovodi file sistem servis,
  5336. aplikacija mora da odluči kako da koristi niz blokova.
  5337. Pošto svaka aplikacija
  5338. stvara sopstvena pravila
  5339. kako da organizuje traku,
  5340. traka puna podataka
  5341. generalno može biti korišćena samo
  5342. od strane programa koji je napravio te podatke
  5343. Tape Drives
  5344. Osnovne operacije uređaja za traku
  5345. se razlikuju od
  5346. onih na disk uređaju.
  5347.  
  5348. lociranje
  5349. pozicionira traku određen logički blok,
  5350. (odgovara pozicionranju kod diska).
  5351. operacija čitanja pozicije
  5352. vraća broj logičkog bloka gde se nalazi glava
  5353.  
  5354. space operacija
  5355. omogućuje relativno kretanje
  5356.  
  5357. Uređaji za trake su “append-only” uređaji;
  5358. ažuriranje blokova u sredini
  5359. briše sve iza tog bloka
  5360.  
  5361. EOT znak se postavlja nakon bloka koji je upisan
  5362. Imenovanje Fajlova
  5363. Imenovanje fajlova na izmenljivim diskovima
  5364. je naročito teško
  5365. kada želimo da upišemo podatak na promenljivi kertridž
  5366. na jednom kompjuteru,
  5367. i
  5368. kasnije koristimo taj kertridž na drugom kompjuteru
  5369.  
  5370. Savremeni OS-i generalno
  5371. ostavljaju problem imenovanja nerešen za izmenljive mediume,
  5372. i
  5373. u zavisnosti od aplikacije i korisnika
  5374. shvata kako da pristupi i interpretira podatke
  5375.  
  5376. Neke vrste izmenljivih mediuma (npr. CD-ovi)
  5377. su tako dobro standardizovani
  5378. tako da ih svi kompjuteri
  5379. koriste na isti način
  5380. Upravljanje Hierarhijom Skladištenja(HSM)
  5381. Hierarhijski sistem memorije
  5382. nastavlja
  5383. memorijsku hijerarhiju
  5384. iza primarne i sekundarne memorije
  5385. za objedinjavanje tercijalne memorije —
  5386. obično je implementirana kao jukebox traka ili izmenljivih diskova.
  5387.  
  5388. obično objedinjuje tercijalnu memoriju proširivanjem sistema fajlova sa
  5389. Malim i često korišćenim fajlovima koji su ostali na disku.
  5390. Velikim, starim, ne aktivnim fajlovima koji su arhivirani u jukebox-u.
  5391.  
  5392. HSM se obično nalazi
  5393. u centrima sa superkompjuterima i
  5394. drugim velikim ustanovama
  5395. koje poseduju ogromnu količinu podataka.
  5396. Brzina
  5397. Dva aspekta brzine tercijalne memorije su
  5398. Brzina disk transfera (bandwidth)
  5399. and
  5400. latentnost.
  5401. Brzina disk transfera je izražena brojem bajtova po sekundi.
  5402. Podržana brzina disk transfera –
  5403. Prosečna brzina protoka podataka za vreme velikog transfera;
  5404. # bajtovi/vreme transfera.
  5405. To je brzina podataka kada tok podataka bukvalno protiče.
  5406.  
  5407. Efektivna brzina disk transfera –
  5408. Prosečna za ukupno I/O vreme,
  5409. uključuje pozicioniranje ili lociranje, i menjanje kertridža.
  5410. To je stvarna brzina protoka podataka.
  5411. Brzina (Nastavak)
  5412. Latentnost pristupa –predstavlja vreme potrebno da se locira podatak.
  5413. Pristupno vreme za disk –
  5414. Pomera ruku do izabranog cilindra
  5415. i čeka za rotaciono kašnjenje; < 35 milisekundi
  5416.  
  5417. Pristup traci zahteva
  5418. namotavanje kotura trake
  5419. dok izabrani blok ne dođe do glave;
  5420. desetine ili stotine sekundi.
  5421.  
  5422. Brzina (Nastavak)
  5423. Generalno važi da je
  5424. nasumičan pristup kod trake
  5425. oko hiljadu puta sporiji od
  5426. nasumičnog pristupa kod diska.
  5427.  
  5428. Niska cena tercijalne memorije
  5429. daje za rezultat mnogo jeftinih kertridža
  5430. koje dele
  5431. nekoliko skupih uređaja.
  5432.  
  5433. Prenosiva biblioteka je najzahvalnija za
  5434. smeštanje podataka koji se ne koriste često,
  5435. zato što biblikoteka može da zadovolji
  5436. relativno male brojeve I/O zahteva po satu.
  5437. Pouzdanost
  5438. Fiksni disk uređaj je
  5439. pouzdaniji
  5440. od izmenljivog disk uređaja ili trake.
  5441. Optički disk je
  5442. pouzdaniji
  5443. od magnetnog diska ili trake.
  5444. Kvar glave
  5445. kod fiksnih hard diskova uništava sve podatke,
  5446. dok kod trake ili optičkog uređaja
  5447. najčešće
  5448. neoštećuje podatke unutar kertridža.
  5449. Cena
  5450. Gavna memorija
  5451. je mnogo skuplja
  5452. od sekundarne (disk memorije)
  5453. cena po megabajtu kod hard diska
  5454. može da se poredi sa
  5455. magnetnom trakom
  5456. samo kada se koristi jedna traka po uređaju
  5457. Najjeftiniji uređaji za trake i
  5458. najjeftiniji disk uređaji
  5459. godinama imaju iste kapacitete.
  5460. Tercijalna memorija pruža
  5461. smanjenje troškova
  5462. samo kad je broj broj kertridža srazmerno veći
  5463. od broja uređaja
  5464. Cena po Megabajtu DRAM, od 1981 do 2000
  5465. Cena po Megabajtu Magnetnog Hard Diska, od 1981 do 2000
  5466. Cena po Megabajtu Uređaja za Traku, od 1984 do 2000
  5467.  
  5468.  
  5469.  
  5470.  
  5471. Mrežne Strukture
  5472. Pozadina
  5473.  
  5474. Topologija
  5475.  
  5476. Tipovi mreže
  5477.  
  5478. Komunikacija
  5479.  
  5480. Komunikacioni protokoli
  5481.  
  5482. Robusnost
  5483.  
  5484. Strategija dizajniranja
  5485. Distribuirani Sistem
  5486. Motivacija (4 beneficije)
  5487. 1. Deljenje resursa
  5488. deljenje i štampanje datoteka
  5489. procesiranje informacija u distribuiranoj bazi
  5490. korišćenje udaljenog specijalizovanog hardvera
  5491.  
  5492. 2. Ubrzavanje Izračunavanja (computation speedup)
  5493.  
  5494. 3. Pouzdanost:
  5495. detektovanje i oporavak neispravnog sajta
  5496. oporavak neispravnog sajta
  5497.  
  5498. 3. Komunikacije: prenošenje poruka
  5499. Mrežni Operativni Sistemi
  5500. Korisnici su upoznati sa različitim računarima na mreži
  5501.  
  5502. Pristup resursima različitih mašina se radi preko:
  5503. Daljinskog logovanja na odgovarajuću daljinsku mašinu
  5504.  
  5505. FTP: Prenošenje podataka sa daljinskih na lokalne mašine, preko File Transfer Protocol (FTP) mehanizma
  5506. Distribuirani Operativni sistemi
  5507. Korisnici nisu upoznati sa različitim računarima, sve se vidi kao jedan. Pristup daljinskim resursima sličan je pristupu lokalnim resursima
  5508.  
  5509. 1. Migracija podataka (data migration):
  5510. prenos podataka kao prenos cele datoteke (AFS),
  5511. ili
  5512. prenos samo onih delova podataka neophodnih za sledeći zadatak (NFS)
  5513.  
  5514. 2. Migracija Izračunavanja (compute migration):
  5515. transfer izračunavanja, umesto prenos podataka, kroz sistem
  5516.  
  5517. 3. Migracija procesa (process migration)
  5518. Distribuirani Operativni Sistemi (Nastavak)
  5519. Migracija procesa: izvršava ceo proces, ili samo deo, na različitim sajtovima
  5520. Beneficije:
  5521. Load balancing: distribuira procese preko mreže
  5522.  
  5523. Computation speedup: podprocesi se mogu izvršavati konkurentno na različitim sajtovima
  5524.  
  5525. Hardware preference: izvršavanje procesa može da zahteva specijalizovani sajt
  5526.  
  5527. Sotfware preference: zahtevani softver može biti samo na posebnim sajtovima
  5528.  
  5529. Data access: pokreće proces daljinski, umesto prebacivanja svih podataka lokalno
  5530. Topologija
  5531. Računari u sistemu mogu biti fizički povezana na različite načine; ona se porede poštovanjem sledećih kriterijuma:
  5532. Osnovna cena. Kolika je cena povezivanja različitih mesta u sistemu?
  5533. Cena komunikacije. Koliko vremena treba da se prenese poruka od mesta A do mesta B?
  5534. Pouzdanost. Ako je veza ili mesto u sistemu otkazalo, da li ostatak može da komunicira međusobno?
  5535.  
  5536. Različite topologije su prikazane kao grafovi čiji čvorovi odgovaraju mestima gde su. Ivica čvora A do čvora B odgovara direktnoj konekciji između dva mesta.
  5537.  
  5538. Sledećih 6 slika prikazuju različite topologije mreža.
  5539. Topologija Mreže
  5540. Tipovi Mreže
  5541. Local-Area Network (LAN): dizajnirana da pokrije malo geografsko područje.
  5542. Višepristupna magistrala, prsten ili zvezda.
  5543. Brzina  10 megabita/sekudi, ili više
  5544. Broadcast: brzo i jeftino
  5545. Čvorovi:
  5546. Obično stanice i/ili personalni računari
  5547. Nekoliko(obično jedan ili dva) glavna računara-mainfrafes
  5548. Tipovi Mreže (nastavak)
  5549. Prikaz tipične LAN mreže:
  5550. Tipovi Mreže (nastavak)
  5551. Wide-Area Network (WAN): povezuje geografski šire područje.
  5552. Veza tačka do tačke preko dugačkih linija (često iznajmljena iz telefonske kompanije)
  5553. Brzina  100 kilobita/sekundi
  5554. Broadcast obično zahteva više poruka
  5555. Čvorovi:
  5556. Obično veliki procenat glavnih računara
  5557. Komunikacioni Procesori u Wide-Area Network-u
  5558. Komunikacija
  5559. Naming and name resolution : Kako procesi nalaze jedan drugog da bi komunicirali?
  5560.  
  5561. Routing strategies. Kako se poruke šalju kroz mrežu?
  5562.  
  5563. Connection strategies. Kako dva procesa šalju više poruka?
  5564.  
  5565. Contention. Mreža je izvor koji se deli, pa kako rešiti konfliktne zahteve za njenu upotrebu?
  5566. Odlučivanje o Imenima
  5567. Sistemi za imenovanje u mreži
  5568.  
  5569. Adresne poruke sa ID-om procesa
  5570.  
  5571. Identifikacija procesa na daljinskom sistemu preko:
  5572. <host-name, identifier> pair
  5573. Domain name service (DNS):
  5574. određuje strukturu imenovanja host-a,
  5575. kao i način adresne rezolucije (Internet)
  5576. Strategije Rutiranja
  5577. Fixed routing: Ruta od A do B je određena unapred; putanja se menja samo ako je hardverski otkaz obustavi
  5578. Pošto se obično bira najkraća staza, cene komunikacija su svedene na minimum
  5579. Fiksne rute se ne mogu prilagoditi promenama
  5580. Osiguravaju da poruke budu dostavljene u redu po kome su slate
  5581.  
  5582. Virtual circuit: Putanja od A do B je određena u trajanju od jedne sesije. Različite sesije koje uključuju poruke od A do B mogu imati različite rute.
  5583. prilagođenje mrežnim opterćenjima
  5584. osiguravaju da poruke budu dostavljene u redu po kome su slate.
  5585. Strategije rutiranja (nastavak)
  5586. Dinamično rutiranje. Ruta koja se koristi za prenošenje poruke od sajta A do sajta B se bira samo kada se poruka pošalje
  5587.  
  5588. Obično site šalje poruku na drugo mesto na bazi prethodne rute
  5589.  
  5590. Prilagođava se opterećenjima, izbegavajući rute koje su opterećene
  5591.  
  5592. Poruke mogu stići bez reda. Ovaj problem može biti ispravljen dodeljivanjem određenog broja svakoj poruci
  5593. Strategije Konekcije
  5594. Circuit switching: Stalni fizički link se uspostavlja u trajanju komunikacije (npr.telefonski sistem).
  5595.  
  5596. Message switching: Privremeni link se uspostavlja za vreme transfera jedne poruke (npr.poštanski sistem).
  5597.  
  5598. Packet switching: Poruke različitih dužina su podeljene u pakete fiksne dužine koji se šalju na određenu destinaciju. Svaki paket može imati različitu putanju kroz mrežu. Paketi moraju biti ponovo sastavljeni u poruke kada stignu.
  5599.  
  5600. Circuit switching requires setup time, but incurs less overhead for shipping each message, and may waste network bandwidth.
  5601. Message and packet switching require less setup time, but incur more overhead per message.
  5602. Sudari
  5603. Neka mesta mogu zahtevati istovremeni prenos informacija preko linka:
  5604.  
  5605. 1. CSMA/CD
  5606. Carrier sense with multiple access (CSMA);
  5607. collision detection (CD)
  5608.  
  5609. 2. Token passing
  5610.  
  5611. 3. Message slots
  5612. Sudari-CSMA/CD
  5613. CSMA/CD. Carrier sense with multiple access (CSMA); collision detection (CD)
  5614. Sajt određuje da li se još neka poruka trenutno prenosi preko linka.
  5615. Ako dva ili više mesta počnu prenos u istom trenutku, oni će detektovati sudar i prekinuti prenos
  5616. Kada je mreža optrećena, mogu se pojaviti mnogi sudari i zbog toga opadaju preformanse
  5617.  
  5618. SCMA/CD
  5619. se uspešno koristi u Ethernet sistemu,
  5620. najčešćem mrežnom sistemu
  5621. Sudari (Nastavak)
  5622. Token passing. A unique message type, known as a token, continuously circulates in the system (usually a ring structure)
  5623. A site that wants to transmit information must wait until the token arrives
  5624. When the site completes its round of message passing, it retransmits the token
  5625. A token-passing scheme is used by the IBM and Apollo systems
  5626.  
  5627. Message slots. A number of fixed-length message slots continuously circulate in the system (usually a ring structure).
  5628. Since a slot can contain only fixed-sized messages, a single logical message may have to be broken down into a number of smaller packets, each of which is sent in a separate slot.
  5629. This scheme has been adopted in the experimental Cambridge Digital Communication Ring
  5630. Komunikacioni Protokoli
  5631. Fizički sloj: rukuje mehaničkim i električnim detaljima prenosa bitova
  5632.  
  5633. Data-link sloj: rukuje okvirima ili delovima paketa fiksne dužine, koji uključuje svaku detekciju greške i oporavlja svaku koja se dogodila u tom sloju
  5634.  
  5635. Mrežni sloj: Omogućava vezu i rutiranje paketa u mrežnim komunikacijama, uključujući rukovanje adresama odlazećih paketa, dekodiranje adresa dolazećih paketa, i održavanje puteva informacija i odgovor na promene opterećenja
  5636. Komunikacioni Protokoli (Nastavak)
  5637. Transportni sloj: odgovoran za low-level mrežni pristup i za transfer poruka između klijenata, uključuje deljenje poruka u pakete, održavanje redosleda paketa, kontrolu protoka i generisanje fizičkih adresa
  5638.  
  5639. Sesioni sloj: implementira sesiju, ili process-to-process komunikacioni protokol
  5640.  
  5641. Prezentacioni sloj: Rešava razlike u formatima između raznih mesta u mreži uključujući promenu karaktera i half duplex/full duplex (echoing)
  5642.  
  5643. Aplikacioni sloj: u direktnom je dodiru sa korisnikom, radi sa prenosom datoteka, remote-login protokoli i elektronska pošta, kao i šeme za distribuirane baze podataka
  5644. Komunikacija Preko ISO Mrežnog Modela
  5645. ISO Sloj Protokola
  5646. ISO Mrežne Poruke
  5647. TCP/IP Skup Protokola
  5648. Robustnost
  5649. Detektovanje greške
  5650. Rekonfiguracija
  5651. Detekcija Greške
  5652. Detektovanje hardverske greške je teško
  5653.  
  5654. Detektovati prekid veze, handshaking protokol se koristi
  5655. Predpostavimo da su mesto A i B uspostavili vezu
  5656. u fiksnim intervalima,
  5657. svako mesto će razmeniti <I-am-up> poruku
  5658. to upućuje da su i dalje povezani
  5659.  
  5660. Ako mesto A ne primi poruku fiksnom intervalu predpostavlja da :
  5661. (a) drugo mesto nije u funkciji
  5662. ili
  5663. (b) je poruka izgubljena
  5664.  
  5665. Mesto A može da pošalje <Are-you-up>? poruku za mesto B.
  5666. Ako mesto A ne primi odgovor,
  5667. može ponoviti poruku
  5668. ili pokušati preko druge rute do mesta B
  5669. Detekcija Greške (Nastavak)
  5670. Ako mesto A ne primi odgovor od mesta B, ono zaključuje da je došlo do greške
  5671. Tipovi greške:
  5672. mesto B je u otkazu
  5673. direktna veza od A do B je prekinuta
  5674. alternativna veza od A do B je prekinuta
  5675. poruka je izgubljena
  5676. Mesto A ne može da odredi zašto je došlo do greške
  5677. Rekonfiguracija
  5678. Kada mesto A utvrdi da je došlo do kvara sistem se mora rekonfigurisati:
  5679. 1. Ako je pao link-ruta od A do B, mora biti objavljeno (broadcast) za svako mesto u sistemu.
  5680.  
  5681. 2. Ako je lokacija B pala, svako mesto mora biti obavešteno da usluge servisa više nisu dostupne
  5682. Kada se veza ponovo uspostavi, informacija ponovo mora biti poslata svim lokacijama
  5683. Problemi Dizajna
  5684. Transparentnost: distribuirani sistemi treba da izgledaju kao centralizovani sistemi za korisnika.
  5685. Tolerancija greške: distribuirani sistem treba da nastavi da funkcioniše posle pada bilo kog dela sistema
  5686. Skalabilnost: Kako se zahtevi povećavaju, sistem bi trebalo lako da prihvati dodavanje novih resursa da bi zadovoljili povećanu tražnju
  5687. Clusters:
  5688. Kolekcija polu-autonomnih mašina
  5689. koje se ponašaju kao jedinstven sistem.
  5690. Primer Mreže
  5691. Prenos mrežnog paketa između hostova u Ethernet mreži
  5692.  
  5693. Svaki host ima jedinstvenu IP adresu i a odgovarajuću Ethernet (MAC) adresu.
  5694.  
  5695. Komunikacija zahteva obe adrese.
  5696.  
  5697. Domain Name Service (DNS) može biti upotrebljen da bi dobili sve IP adrese.
  5698.  
  5699. Address Resolution Protocol (ARP) se koristi da mapira MAC adrese u IP adrese.
  5700.  
  5701. Ako su hostovi na istoj mreži, ARP može biti upotrebljen.
  5702. Ako su hostovi na različitim mrežama, izvorišni host će poslati paket ruteru koji rutira paket do odredišne mreže.
  5703. Ethernet paket
  5704.  
  5705.  
  5706.  
  5707.  
  5708.  
  5709.  
  5710. Distribuirani FS (Sistemi Datoteka)
  5711. Pozadina
  5712.  
  5713. Imenovanje i Transparentnost
  5714.  
  5715. Udaljni Pristup datotekema
  5716.  
  5717. Statefull v Stateless Services
  5718.  
  5719. File Replikacije
  5720.  
  5721. Primeri Sistema
  5722. Pozadina
  5723. Distribuirani FS (DFS):
  5724. distribuirana implementacija
  5725. klasičnog time-sharing modela FS (file system),
  5726. gde više korisnika dele datoteke i memorijske resurse
  5727. DFS upravlja skupom udaljenih memorijskih uređaja (diskova)
  5728.  
  5729. Ukupan memorijski-disk prostor sa kojim upravlja DFS
  5730. je sastavljen od različitih
  5731. udaljenih
  5732. manjih memorijskih prostora (diskova i mašina)
  5733.  
  5734. Obično postoji korespodencija između:
  5735. konzistetnog disk-memorijskog prostora i
  5736. skupa datoteka.
  5737. Struktura DFS-a
  5738. Servis:
  5739. softverska celina tj softver
  5740. Koji se koristi na jednoj ili više mašina
  5741. obavlja određene funkcije
  5742. da obezbedi uslugu nepoznatim klijentima
  5743. Server:
  5744. softver koji se koristi za servis se nalazi na jednoj mašini.
  5745. Client:
  5746. proces koji može da pozove servis
  5747. korišćenjem skupa operacija
  5748. koje formulišu njegov klijentski interfejs.
  5749. Klijentski interfejs za FS
  5750. je formiran od
  5751. seta primitivnih FS operacija (create, delete, read, write).
  5752. Klijentski interfejs DFS-a
  5753. treba da bude transparentan,
  5754. ne sme da bude različit između lokalnih i udaljenih datoteka
  5755. Imenovanje i Transparentnost
  5756. Imenovanje: mapiranje između logičkih i fizičkih objekata
  5757.  
  5758. Multilevel mapping:
  5759. apstrakcija datoteke
  5760. koja krije detalje o tome kako i i gde su
  5761. na disku datoteke smeštene
  5762.  
  5763.  
  5764.  
  5765.  
  5766. Transparentni DFS
  5767. krije lokaciju
  5768. gde unutar mreže je datoteka smeštena.
  5769. Za datoteke koji su iskopirane na više sajtova,
  5770. mapiranje vraća set lokacija kopija te datoteke;
  5771. kopije i njihove lokacije
  5772. su sakrivene.
  5773. Imenovanje Struktura
  5774. Transparentnost lokacija:
  5775. ime datoteke ne pokazuje
  5776. fizičku lokaciju te datoteke
  5777. Karakteristike
  5778. Ime datoteke i dalje označava specifičan, mada skriven,
  5779. set fizičkih disk blokova
  5780. Pogodan način za deljenje podataka
  5781. Može da otkrije korespodentnost između
  5782. komponenti i mašina.
  5783. Nezavisnost lokacija:
  5784. ime datoteke ne treba da se menja
  5785. kada se promeni njena fizička lokacija.
  5786. Karakteristike
  5787. Bolje izdavajanje datoteka
  5788. Unapređuje deljenje memorijskog prostora.
  5789. Odvaja hierarhiju imenovanja
  5790. od memorijske hijerarhije
  5791. Šeme Imenovanja — Tri Osnovne Metode
  5792. I Jedinstven system-wide name
  5793. datoteke dobijaju imena
  5794. kombinacijom njihovog host imena i lokalnog imena;
  5795. Garantuje jedinstveno ime unutar sistema.
  5796. II Dodaje udaljene direktorijume lokalnim direktorijumima
  5797. daje izgled jedinstvenog stabla ditektorijuma;
  5798. samo prethodno mount-ovanim udaljenim direktorijumima
  5799. može transparentno da se pristupi
  5800. III Sveobuhvatna integracija komponenti FS (sistema datoteka)
  5801. Jedinstveno globalno ime strukture obuhvata sve datoteke u sistemu.
  5802. ako server nije dostupan,
  5803. neki proizvoljan set direktorijuma na različitim mašinama
  5804. takođe postaje nedostupan
  5805. Pristup udaljenim datotekema
  5806. 1. remote access
  5807. 2. using cache
  5808. Pristup Udaljenim datotekema
  5809. 1. Remote Service
  5810. koristi rpc pozive
  5811. za upis ili čitanje
  5812. dela datoteke koji je klijent dobio preko mreže
  5813.  
  5814. 2. Keširanje za globalno poboljšanje performansi (ali…)
  5815. ako potrebni podatak već nije keširan
  5816. kopija podatka se dobija od servera do korisnika
  5817. uvek se pristupa keširanoj kopiji
  5818.  
  5819. datoteke se indentifikuju sa jednom master kopijom
  5820. MC je smeštena na jednom serveru,
  5821. ali
  5822. kopije(delovi) su rasuti po različitim mestima.
  5823.  
  5824. Cache-consistency problem
  5825. čuvanje keširanih kopija je koizistentno master datoteci.
  5826. Lokacija Keša – Disk vs. Glavne Memorije
  5827.  
  5828.  
  5829. Prednosti disk keša (DCD)
  5830. Mnogo pouzdaniji
  5831. Keširani podaci se čuvaju na disku
  5832. su i dalje tu za vreme oporavka
  5833. nije potrebno da se ponovo dovlače (fecth)
  5834. Prednosti memorijskog keša:
  5835. Dozvoljava da radne stanice budu bez diska
  5836. Brži pristup podacima
  5837. Veća memorija i može da se izvodi ubrzanje.
  5838. Serverski keš (koji se koriste da ubrzaju disk I/O) je u glavnoj memoriji
  5839. bez obzira gde je korisnički keš lociran;
  5840. korišćenjem memorijskog keša na korisničkoj mašini se omogućava
  5841. jedinstven keš mehanizam za servere i korisnike
  5842. Cache Update Policy
  5843. Write-through: upis kroz
  5844. Upisivanje podataka kroz disk
  5845. umesto u bilo koji keš.
  5846. Pouzdano, ali slabijih performansi
  5847. Delayed-write – odloženi upis
  5848. modifikacije se upisuju u keš
  5849. a zatim na server.
  5850. Brži pristup za upis;
  5851. neki podaci mogu biti prekucani pre nego što se upišu ponovo
  5852. tako da oni uopšte ne treba da se upisuju.
  5853. nepouzdan;
  5854. neupisani podatak će se izgubiti kad god se mašina blokira.
  5855.  
  5856. Variation – flushing
  5857. keš se skenira u regularnim intervalima
  5858. prazni blokove koji su bili modifikovani nakon poslednjeg skeniranja
  5859. Variation – write-on-close,
  5860. upisuje blokove podataka na server
  5861. kada se datoteka zatvara.
  5862. najbolje za podatke koji su otvoreni na duže vreme i često se menjaju
  5863. Konzistencija
  5864. Konzistencija
  5865. Da li je lokalno keširana kopija
  5866. podatka konzistentna master kopiji?
  5867. Pristup iniciran od strane klijenta (Client-initiated approach)
  5868. Klijent započinje proveru vrednosti
  5869. Server proverava da li
  5870. su lokalni podaci konzistentni
  5871. master kopiji
  5872. Pristup iniciran od strane servera (Server-initiated approach)
  5873. Server vodi zapis,
  5874. o svakom klijentu,
  5875. o (delovima datoteka) datotekema koje dobije
  5876. Kada server detektuje potencijalnu nekonzistenciju, mora da reaguje
  5877. Poređenje Keširanja i Udaljenog Servisa
  5878. Kod keširanja,
  5879. lokalni keš efikasno rukovodi većinom udaljenih pristupa;
  5880. većina udaljenih pristupa se opsluđuje istom brzinom kao i lokalni.
  5881. Kod keširanja serverima se pristupa samo s vremena na vreme
  5882. (pre nego za svaki upis).
  5883. Smanjuju serverski i mrezni saobraćaj
  5884. Povećava potencijal za scalability
  5885.  
  5886. Metod udaljenog servera
  5887. rukovodi svim udaljenim pristupima preko mreže;
  5888. o obara performanse zbog mrežnog saobraćaju, čitanje/upis sa servera
  5889.  
  5890. Total network overhead
  5891. in transmitting big chunks of data (caching)
  5892. is lower than
  5893. a series of responses to specific requests (remote-service)
  5894. Keširanje i Udaljeni Servisi (Nastavak)
  5895. Keširanje je najbolje
  5896. kod pristupa delovima sa ređim upisima (read dominant).
  5897. kod čestih upisa,
  5898. su bitni opšti troškovi
  5899. da bi se prevazišao problem konzistencije keša.
  5900.  
  5901. Keširanje je dobro za mašine sa:
  5902. lokalnim diskovima
  5903. velikim RAM memorijama.
  5904.  
  5905. Udaljeni pristup je dobar za:
  5906. mašine bez diska,
  5907. sa malim memorijskim RAM kapacitetom
  5908. Stateful File Services
  5909. Mehanizam:
  5910. Klijent otvara datoteku.
  5911. Server fečuje informaciju o datoteci sa svog diska,
  5912. smešta je na svoju memoriju
  5913. daje klijentu identifikator konekcije
  5914. jedinstven za klijenta i otvara datoteku.
  5915.  
  5916. Identifikator se koristi za sledeće pristupe dok se ne sesija ne završi .
  5917.  
  5918. Server mora da podesi informaciju u glavnoj memoriji
  5919. koju je koristio klijent
  5920. koji više nije aktivan
  5921. Povećane performanse:
  5922. Smanjeni pristup disku
  5923. Stateful server zna:
  5924. da li je datoteka bila otvorena za sekvencijalni pristup
  5925. pa može da čita unapred sledeće blokove.
  5926. Stateless File-Server
  5927. Izbegava informacije o stanju
  5928. pravljenjem
  5929. nezavisnih zahteva
  5930. Svaki zahtev
  5931. identifikuje datoteku
  5932. i
  5933. poziciju u datoteci
  5934. Nema potrebe za uspostavljanje i raskidanje veze
  5935. operacijama open i close
  5936. Razlika Između Stateful & Stateless Servisa
  5937. Oporavak od otkaza:
  5938. Stateful server gubi sve svoje memorijske informacije usled pada
  5939. obnavlja stanje
  5940. preko recovery protokola, zasnovanog na dialogu sa klijentom,
  5941. i prekinute operacije
  5942. koje su bile u toku kada se dogodio pad
  5943.  
  5944. Server treba da bude svestan otkaza od strane klijenta
  5945. zbog zahteva za popravljanje prostora
  5946. dodeljenog za upis mesta oktazalih klijent procesa
  5947. (detekcija i eliminacija siročića).
  5948.  
  5949. Kod stateless servera,
  5950. oporavak je skoro neprimetan.
  5951. Oporavljeni server
  5952. može da odgovori
  5953. nezavisnim zahtevima bez ikakvih poteškoća
  5954. Razlike (Nastavak)
  5955. Nedostaci korišćenje snažnih stateless servisa:
  5956. duže request poruke
  5957. sporije procesiranje zahteva
  5958. dodatna ograničenja nametnuta na dizajn DFS
  5959. Neki okruženja zahtevaju stateful servise:
  5960. Server koji koristi server-initiated cache validation
  5961. Ne može da sprovodi stateless servis,
  5962. pošto sadrži zapis
  5963. koji datoteke su keširani od strane kog klijenta
  5964.  
  5965. UNIX koristi fajl deskriptore i implicitne ofsete
  5966. i to je stateful servis;
  5967. serveri moraju da sadrže tabele
  5968. za mapiranje fajl deskriptora za inode,
  5969. i
  5970. smeštanje konkretnog ofseta unutar datoteke
  5971. Replikacija datoteka
  5972. Replikacije iste datoteke
  5973. smeštene na failure-independent mašinama
  5974.  
  5975. Povećava korisnost i može da skrati vreme servisiranja.
  5976.  
  5977. Šeme za imenovanje mapiraju replicirano ime datoteke za određenu repliku
  5978. Postojenje replika bi trebalo da bude nevidljivo za više nivoe.
  5979. Replikacije moraju da se odlikuju
  5980. različitim imenima nižih nivoa
  5981.  
  5982. Ažuriranje:
  5983. replike datoteke označavaju isti logički smisao,
  5984. i zbog toga
  5985. ažuriranje bilo koje replike
  5986. mora da se reflektuje na sve ostale replike.
  5987.  
  5988. Demand replication:
  5989. ažuriranje samo unutar primarne replike,
  5990. onda obaveštavanje drugih replikcija o invalidaciji
  5991.  
  5992.  
  5993.  
  5994.  
  5995.  
  5996.  
  5997. Distribuirana Sinhronizacija
  5998. Distribuirana sinhronizacija procesa
  5999.  
  6000. Međusobno Isključenje
  6001.  
  6002. Atomatske Transakcije
  6003.  
  6004. Konkurentne Atomske Transakcije
  6005.  
  6006. Upravljanje Zastojima
  6007.  
  6008. Election Algoritmi
  6009. Distribuirana Sinhronizacija Procesa
  6010. Happened-before relacija ( označena kao )
  6011. Ako su A i B
  6012. događaji istog procesa,
  6013. i
  6014. A je izvršen pre B,
  6015. onda A  B
  6016.  
  6017. Ako je A:događaj slanje poruke jednog procesa
  6018. B je događaj primanja poruke od strane drugog procesa,
  6019. onda A  B
  6020.  
  6021. Ako A  B i B  C onda A  C
  6022. Povezano Vreme za Tri Konkurentna Procesa
  6023. Imlpementacija 
  6024. Dodeljivanje vremenske oznake (timestamp) svakom sistemskom događaju
  6025.  
  6026. Zahteva da svaki par događaja A i B,
  6027. ako A  B,
  6028. onda
  6029. vremenska oznaka za A je manja od vremenske oznake za B.
  6030.  
  6031. Unutar svakog procesa Pi
  6032. se dodeljuje logički časovnik, LC
  6033.  
  6034. Logički časovnik može biti implementiran:
  6035. kao jednostavan brojač
  6036. koji se inkrementira
  6037. između
  6038. bilo koja dva uspela događaja
  6039. izvršena unutar procesa
  6040. (na završetak prvog)
  6041. Implementacija 
  6042. Proces pokreće svoj logički sat
  6043. kada primi poruku
  6044. čija vremenska oznaka TS je veća
  6045. od trenutne vrednosti njegovog logičkog sata
  6046.  
  6047. Ako su vremenske oznake dva događaja A i B iste,
  6048. onda su događaji konkurentni
  6049.  
  6050. Možemo da koristimo identifikacione brojeve procesa
  6051. da prekinemo veze
  6052. i
  6053. da stvorimo totalno uređenje (total ordering)
  6054. Distributed Mutual Exclusion (DME)
  6055. Pretpostavke:
  6056. Sistem se sastoji od n procesa;
  6057. svaki proces Pi se izvršava
  6058. na različitom procesoru
  6059. Svaki proces ima kritičnu sekciju
  6060. koji zahteva međusobno isključenje
  6061.  
  6062. Uslov
  6063. Ako Pi , izvršava svoj kritičnu sekciju
  6064. onda
  6065. ni jedan proces Pj nemože da izvršava svoju kritičnu sekciju
  6066.  
  6067. dva algoritma za DME
  6068. Centralizovano rešenje (centralized approach)
  6069. Distribuirano rešenje (distributed approach)
  6070. DME: Centralizovano rešenje
  6071. Jedan od procesa unutar sistema
  6072. je izabran
  6073. da koordinira pristup kritičnim sekcijama
  6074. 1. Proces
  6075. koji želi da uđe u svoj kritični deo
  6076. šalje request poruku koordinatoru.
  6077.  
  6078. 2. Koordinator odlučuje
  6079. koji proces može da uđe u kritičnu sekciju,
  6080. šalje poruku tom procesu reply poruku.
  6081.  
  6082. 3. Kada proces primi
  6083. reply poruku od koordinatora,
  6084. on ulazi u svouj kritičnu sekciju.
  6085.  
  6086. 4. Nakon izlaska iz kritičnog dela,
  6087. proces šalje
  6088. release poruku koordinatoru
  6089. nastavlja sa izvršavanjm
  6090.  
  6091. Ova šema zahteva tri poruke po ulasku u kritičan deo:
  6092. request
  6093. reply
  6094. release
  6095. DME: Centralizovano rešenje
  6096. DME: Puno Distribuirano Rešenje
  6097. Kada proces Pi želi da uđe u svoju kritičnu sekciju,
  6098. on stvara new vremensku oznaku, TS
  6099. šalje poruku request (Pi, TS)
  6100. svim drugim procesima u sistemu.
  6101.  
  6102. Kada proces Pj primi request poruku,
  6103. može odmah da odgovori
  6104. ili
  6105. može da odloži slanje odgovora.
  6106.  
  6107. Kada proces Pi primi reply poruku
  6108. od svih ostalih procesa u sistemu,
  6109. može da uđe u svoju kritičnu sekciju
  6110.  
  6111. Nakon izlaska iz kritične sekcije,
  6112. proces šalje reply poruku
  6113. DME: Puno Distribuirano Rešenje
  6114. DME: Puno Distribuirano Rešenje(Odluka)
  6115. Odluka da li proces Pj
  6116. odgovara istog trenutka na request(Pi, TS) poruku
  6117. ili
  6118. da odloži svoj odgovor se zasniva na tri faktora:
  6119.  
  6120. 1. Out of CS, do not want-in
  6121. Ako Pj ne želi da uđe u svoju kritičnu sekciju,
  6122. on šalje odgovor odmah ka Pi
  6123.  
  6124. 2. In-CS
  6125. Ako se Pj nalazi u svojoj kritičnoj sekciji,
  6126. onda on odlaže odgovor ka Pi.
  6127.  
  6128. 3. Out of CS, want-in
  6129. Ako Pj želi da uđe u svoju kritičnu sekciju
  6130. ali još nije ušao,
  6131. onda poredi svoju vremensku oznaku sa vremenskom oznakom TS.
  6132. ako je njegova vremenska oznaka veća od TS,
  6133. onda šalje odgovor istog trenutka ka Pi (Pi je prvi tražio)
  6134. U suprotnom, odgovor se odlaže
  6135. Poželjno Ponašanje Punog Distribuiranog Rešenja
  6136. Oslobođeno od zastoja (Deadlock)
  6137.  
  6138. Oslobođeno od zakucavanja (starvation)
  6139. nakon ulaska u kritičnu sekciju
  6140. se raspoređuje
  6141. prema rasporedu vremenskih oznaka
  6142.  
  6143. Raspored vremenskih oznaka osigurava
  6144. ti procesi se opslužuju FIFO način:
  6145. prvi ušao, prvi opslužen (FIFO)
  6146.  
  6147. broj poruka po ulasku u kritičnu sekciju je 2 x (n – 1). Ovo je minimalan broj
  6148. zahtevanih poruka za ulazak u kritičnu sekciju
  6149. kad se proces ponaša nezavisno i konkurentno
  6150. Tri Neželjene Posledice
  6151. 1. Proces mora da zna
  6152. identitet svih ostalih procesa u sistemu,
  6153. što čini
  6154. dinamičko dodavanje i uklanjanje procesa
  6155. još komplikovanijim
  6156. 2. Ako jedan proces otkaže,
  6157. onda cela šema propada.
  6158. Ovo može da bude prevaziđeno
  6159. konstantnim monitoring-om
  6160. stanja svih procesa u sistemu.
  6161. 3. Procesi koji nisu ušli u svoje kritične delove
  6162. moraju se često pauzirati (zbog slanja poruka)
  6163. da bi osigurali ostale procese
  6164. one koji nameravaju da uđu u kritičan deo.
  6165.  
  6166. Ovaj protokol je dakle zadovoljavajući
  6167. za male,
  6168. stabilne setove kooperativnih procesa.
  6169. Atomske Transakcije
  6170. Transakcija =
  6171. Kolekcija instrukcija
  6172. koja čini jednu logičku funkciju
  6173.  
  6174. U sistemima baza podataka
  6175. beleže čitanje
  6176. beleže upisivanje
  6177.  
  6178. Kraj transakcije = status
  6179. izvršeno - commit (uspešna transakcija)
  6180. prekinuto - abort
  6181. Atomska transakcija
  6182. u slučaju greške =>T treba da se vrati na početak (roll-back)
  6183.  
  6184. log implementacija
  6185. log zapis za T sadrži:
  6186. ime T
  6187. ime zapisa za upis (R)
  6188. stare vrednosti R (pre upisivanja)
  6189. nove vrednosti R (nakon upisivanja)
  6190. Atomske Transakcije-Log
  6191.  
  6192.  
  6193.  
  6194.  
  6195.  
  6196.  
  6197.  
  6198.  
  6199.  
  6200.  
  6201. Nakon pada sistema => Atomska transakcija
  6202. undo(T) if not exist <commit T>
  6203. vraća na stanje R pre Ti (roll-back)
  6204.  
  6205. redo (T) if exist <commit T>
  6206. upisuje poslednje vrednosti R preko T da bi zapisao R
  6207. Atomske Transakcije - Checkpoint
  6208.  
  6209.  
  6210.  
  6211.  
  6212.  
  6213.  
  6214.  
  6215.  
  6216.  
  6217.  
  6218. Checkpoint = sve uspele transakcije
  6219. nakon pada -> traži checkpoint
  6220. za sve Tk sa <Tcommit>
  6221. radi redo(Tk)
  6222. za sve Tk bez <Tcommit>
  6223. radi undo(Tk)
  6224.  
  6225. Konkurentne Atomske Transakcije
  6226. Conflict mode transakcija
  6227. minimum dve transakcije Ti, Tj
  6228. za isto R,
  6229. bar jedna od njih = upis T
  6230.  
  6231.  
  6232.  
  6233.  
  6234.  
  6235.  
  6236. Dve šeme:
  6237. lock - protocoli za zaključavanje
  6238.  
  6239. TS redosled izvršavanja
  6240.  
  6241. Lock Protokol
  6242. T će da zaključa (lock) R pre korišćenja
  6243. zahtev za lock
  6244. koristi R
  6245. nakon što je odobren lock
  6246. Otključavanje R (release a lock)
  6247.  
  6248. Shared lock (samo za čitanje)
  6249. posle odobrenog zaključavanja,
  6250. Ti će da koristi R, samo za čitanje
  6251. nekoliko deljenih zaključavanja istovremeno
  6252.  
  6253. Exclusive lock (za upisivanje)
  6254. posle odobrenog zakljčavanja,
  6255. Ti može da upisuje u R
  6256. samo jedno ekskluzivno zaključavanje istovremeno
  6257.  
  6258. TS ordering
  6259. log based + TS
  6260. TS (timestamp protokol obezbeđuje)
  6261. da konfliktno čitanje i upis obave u TS poretku,
  6262. koja isključuje preklapanje konflikta
  6263.  
  6264. TS funkcioniše na sledeći način:
  6265.  
  6266. Svakoj transakciji dodeljujemo vremensku oznaku TS,
  6267. a to je vreme kada počinje se izvršava.
  6268.  
  6269. Takođe svakom zapisu dodeljujemo dva vremenska parametra:
  6270. W-timestamp(Q)
  6271. predstavlja vreme poslednje transakcije
  6272. koja je uspešno obavila upis u Q
  6273.  
  6274. R-timestamp(Q)
  6275. prestavlja vreme poslednje transakcije
  6276. koja je uspešno obavila čitanje iz Q
  6277.  
  6278. Ova dva parametra se stalno ažuziraju
  6279.  
  6280. TS protocol-reading case
  6281. transakcija Ti pošalje zahtev read(Q).
  6282.  
  6283. Moguće su dve situacije:
  6284.  
  6285. 1. TS(Ti) >= W-TS(Q)
  6286. tada je zahtev korektan
  6287. čitanje se obavlja iz Q
  6288. a posle toga se ažurira R-timestamp(Q)
  6289.  
  6290. 2. TS(Ti)< W-TS(Q),
  6291. T traži vrednost Q iz nekog prošlog vremena,
  6292. a vrednost je prepisana
  6293. čitanje iz Q odbaci
  6294. cita se iz log zapisa
  6295. Ili roll-back za sve koje su pogresne
  6296. TS protocol-writing case
  6297. transakcija Ti pošalje zahtev write(Q).
  6298. Moguće su 3 situacije:
  6299.  
  6300. 1. TS(Ti) < R-TS(Q)
  6301. pokušava da se upiše nešto
  6302. što je već trebalo da bude pročitano.
  6303. rool-back za onu Tk koja je procitala pogresno, restart za Tk
  6304.  
  6305. 2. TS(Ti)< W-TS(Q),
  6306. tada transakcija pokušava da upiše
  6307. staru vrednost za Q
  6308. upis ide u log
  6309. ili roll-back za pogresne, restart
  6310.  
  6311. 3. U svim ostalim slučajevima
  6312. TS(Ti) > R-TS(Q) i TS(Ti) > W-TS(Q)
  6313. upis u Q se obavlja
  6314. Timestamping
  6315. Stvara jedinstvenu vremensku oznaku u distribuiranoj šemi:
  6316. Svaki sajt generiše
  6317. jedinstvenu lokalnu vremensku oznaku.
  6318. globalna jedinstvena vremenska oznaka se koristi
  6319. vezivanjem
  6320. the unique local timestamp
  6321. with the unique site identifier
  6322.  
  6323. Use a logical clock defined within each site
  6324. to ensure
  6325. the fair generation of timestamps.
  6326. Generation of Unique Timestamps
  6327. Vremanska Oznaka – Šema Rasporeda
  6328.  
  6329. Ova šema kombinuje
  6330. centralizovanu timestamp metodu
  6331. sa 2PC protokolom
  6332. da obezbedi poredak
  6333. bez velikog broja kaskadnih roll-back operacije.
  6334.  
  6335. Baferuju (log) se različiti zahtevi za čitanje i upis
  6336. a onda se izvršavaju preko timestamp poretka, koji glasi:
  6337.  
  6338. reading:
  6339. record x Ti {read(x)}
  6340. tada read(x) mora biti odloženo
  6341. ako postoji transakcija Tj {write(x)} i ako je TS(Tj) < TS(Ti)
  6342.  
  6343. writing:
  6344. record x Ti {write(x)}
  6345. tada write(x) mora biti odloženo
  6346. ako postoji transakcija Tj {read(x)} i ako je TS(Tj) < TS(Ti)
  6347. Atomičnost Distribuiranih Sistema
  6348.  
  6349. Osiguravanje atomičnosti u distribuiranim sistemima
  6350.  
  6351. zahteva koordinatora transakcije
  6352.  
  6353. koji je odgovoran za sledeće:
  6354.  
  6355. startovanje izvršenja transakcije
  6356.  
  6357. deljenje transakcije na više podtransakcija
  6358.  
  6359. distribucija tih podtransakcija
  6360. na odgovarajuća mesta za izvršenje
  6361.  
  6362. Koordiniranje završetkom transakcije
  6363. čiji rezultat može da bude:
  6364. transakcija izvršena na svim mestima
  6365. ili
  6366. prekinuta na svim mestima
  6367. Two-Phase Commit Protocol (2PC)
  6368. Preuzima fail-stop model
  6369.  
  6370. Izvršenje protokola se inicijalizuje
  6371. od strane koordinatora
  6372.  
  6373. Kada je protokol inicijalizovan,
  6374. transakcija može da se izvršava
  6375. na nekim lokalnim mestima
  6376. Protokol obuhvata
  6377. sva lokalna mesta
  6378. na kojima se izvršava transakcija
  6379. Primer:
  6380. Neka T bude transakcija
  6381. inicijalizovana na mestu Si i
  6382. neka koordinator transakcije na Si bude Ci
  6383. Two-Phase Commit Protocol (2PC)
  6384. Faza 1: Dodavanje Odluka
  6385. Ci dodaje <prepare T> zapis
  6386. za log
  6387.  
  6388. Ci šalje <prepare T> poruku
  6389. Svim mestima.
  6390.  
  6391. Mesto K:
  6392. Kada sajt primi <prepare T> poruku,
  6393. upravljač(menager) transakcije odlučuje
  6394. da li može da izvrši transakciju.
  6395.  
  6396. Ako ne može (neće da radi):
  6397. dodaje <no T> zapis u log
  6398. odgovara Ci sa <abort T> porukom.
  6399.  
  6400. Ako može (hoće da radi):
  6401. dodaje <ready T> zapis u log.
  6402. izbacuje sve log zapise za T u stabilnu memoriju-log
  6403. šalje <ready T>poruku do Ci
  6404. Faza 1 (Nastavak)
  6405. Koordinator sakuplja odgovore
  6406.  
  6407. 1. Ako su svi odgovori “ready”, => odluka je commit (izvrši)
  6408.  
  6409. 2. Bar jedan odgovor “abort”, => odluka je prekini
  6410.  
  6411. 3. Bar jedan učesnik neuspe da odgovori
  6412.  
  6413. unutar time out perioda, => odluka je prekini
  6414. Faza 2: Zapisivanje Odluke u Bazu
  6415. Koordinator dodaje zapis o odluci
  6416. <abort T>
  6417. ili
  6418. <commit T>
  6419. u svoj log
  6420. izbacuje zapis u stabilnu memoriju-log
  6421.  
  6422. Kada zapis stigne do stabilne memorije
  6423. on je neopoziv
  6424. (čak i ako se desi neuspeh prilikom upisa)
  6425.  
  6426. Koordinator šalje poruku
  6427. svakom učesniku
  6428. obaveštavajući ga
  6429. o odluci (commit ili abort).
  6430.  
  6431. Učesnici izvode određenu radnju, lokalno.
  6432. Faza 2: Zapisivanje Odluke u Bazu
  6433. abort T
  6434. koordinator šalje poruku
  6435. svakom učesniku
  6436. obaveštavajući ga o odluci (abort)
  6437. commit T
  6438. koordinator šalje poruku
  6439. svakom učesniku
  6440. obaveštavajući ga o odluci (commit)
  6441.  
  6442. Učesnici izvode određenu radnju lokalno
  6443. nakon završetka,
  6444. učesnik šalje poruku
  6445. <acknowledge T> koordinatoru Ci
  6446.  
  6447. Nakon svega, Ci dodaje zapis <complete T>
  6448. Manipulisanje Neuspesima u 2PC – Site Failure
  6449. Site failed and recover, look at the log
  6450. Log sadrži <commit T> zapis.
  6451. U ovom slučaju, sajt izvršava redo(T).
  6452.  
  6453. Log sadrži <abort T> zapis.
  6454. U ovom slučaju, sajte izvršava undo(T).
  6455.  
  6456. Log sadrži <ready T> zapis; konsultuje Ci
  6457. Ako je Ci pao-otkazao,
  6458. sajt šalje <query-status T> poruku drugim sajtovima
  6459.  
  6460. Log ne sadrži kontrolne zapise koji se tiču T
  6461. U ovom slučaju,
  6462. sajt izvršava undo(T)
  6463. Manipulisanje Neuspesima u 2PC – Koordinator failed Ci
  6464. Koordinator failed Ci
  6465.  
  6466. Čekanje na oporavak Ci
  6467.  
  6468. Ako aktivno mesto (sajt)
  6469. sadrži <commit T> zapis u svom logu
  6470. T mora da se izvrši
  6471.  
  6472. Svi aktivni sajtovi
  6473. imaju <ready T> zapis u svojim logovima,
  6474. ali bez dodatnih kontrolnih zapisa.
  6475. u ovom slučaju moramo da sačekamo koordinatora da se oporavi.
  6476. Blocking problem:
  6477. T je blokiran do oporavka sajta Si
  6478.  
  6479. Ako nema oporavka Ci
  6480. sve transakcije izvršavaju undo()
  6481. Locking Protokoli
  6482. mogu da koriste
  6483. 2PC locking protokol
  6484. u distribuiranom okruženju
  6485. menjanjem načina na koji je lock menadžer implementiran
  6486. Šema bez replikacije
  6487. samo jedna replika
  6488. svaki sajt održava lokalni lock menadžer
  6489.  
  6490. LM upravlja lock i unlock zahtevima
  6491. za one stavke podataka
  6492. koje su smeštene na tom sajtu
  6493. Jednostavna implementacija obuhvata
  6494. dva transfera poruka za manipulisanje lock zahtevima,
  6495. lock request, lock acknowledge
  6496. jedan transfer poruka za manipulisanje unlock zahtevima.
  6497.  
  6498. Manipulisanje zastojima je još komplikovanije.
  6499. Locking Protokoli - Šeme sa Replikacijama
  6500. Metod sa jednim koordinatorom
  6501.  
  6502. Metod sa više koordinatora
  6503. Metod sa Jednim Koordinatorom
  6504. Centralizovani lock menadžer
  6505.  
  6506. Jedan lock menadžer je smešten na jedan izabrani sajt,
  6507. svi lock i unlock zahtevi
  6508. čine taj sajt.
  6509. Jednostavna implementacija
  6510. Jednostavna manipulacija zastojima
  6511. mogućnost uskog grla
  6512. Podložan gubitku sinhronizacije procesa
  6513. ako jedan sajt otkaže
  6514.  
  6515. Moguć pad sistema
  6516. Metod sa Više Koordinatora
  6517. distribuira lock meadžer funkciju
  6518. preko
  6519. više sajtova.
  6520.  
  6521. Majority protocol – Protokol većine
  6522.  
  6523. Biased protocol – Pristrasni protokol
  6524.  
  6525. Primary copy – Primarna kopija
  6526. Majority Protocol
  6527. LM na svakom sajtu
  6528. koji kontroliše svoje lokalne podatke i njihove replike
  6529.  
  6530. kada transakcija trazi lock(Q)
  6531. koji repliciran na n različitih sajtova
  6532. transakcija mora da pošaje lock zahtev
  6533. za više od n/2 sajtova
  6534.  
  6535. Svaki sajt odlučuje
  6536. hoće li da ispuni lock zahtev
  6537. a transakcija je dobiti dozvolu
  6538. ako većina dozvoljava
  6539.  
  6540. Dobra osobina ove šeme je
  6541. što se poštuje većina
  6542. izbegava centralizovanu kontrola
  6543.  
  6544. Međutim postoje 2 loše osobine:
  6545. komplikovanija je za realizaciju
  6546. zastoji se mnogo teže kontorlišu
  6547. Biased Protocol
  6548. .
  6549. Ovaj metod je sličan većinskom protokolu
  6550. ovde postoji LM za svaki sajt,
  6551. ali deljivi i eksluzivni lock se opslužiju drugačije
  6552. lock zahtevi za deljivi lock, favorizuju
  6553. u odnosu na zahteve za ekskluzivni lock.
  6554.  
  6555. Deljivi lock zahtevi (svaki zahtev za čitanje) su takvi
  6556. da kada transakcija traži lock Q zapisa,
  6557. on se upućuje samo jednom sajtu koji sadrži repliku od Q
  6558.  
  6559. Ekskluzivni lock zahtevi (svaki zahtev za upis) su takvi
  6560. da kada transakcija traži lock Q zapisa,
  6561. on se upućuje svim sajtovima koji sadrži repliku od Q
  6562.  
  6563. Šema ima prednosti u odnosu na većinski protokol
  6564. ima manje kašnjenje (overhead) na operacije čitanja
  6565. u odnosu na većinski protokol, jer su lock zathevi deljivi
  6566. ali za ciklus upisa je lošiji
  6567. jer mora da se obrati svakom sajtu koji sadrži repliku
  6568. Primarna Kopija
  6569. U slučaju replika,
  6570. jedan od sajtova koji sadrzi repliku datoteke
  6571. ce se proglasiti za njegovu primarnu repliku (primary site).
  6572.  
  6573. Uvek se lock zahtev prosleđuje
  6574. samo za primarnu repliku (tom sajtu),
  6575. čiji će sajt obezbediti konkurentnu lock kontrolu
  6576.  
  6577. Slično jednoj LM metodi
  6578.  
  6579. Ali ako primarni sajt otkaže,
  6580. tada će Q zapis da budu neraspoloživ,
  6581. bez obzira što postoji ostale replike na različitim računarima.
  6582. Sprečavanje Zastoja
  6583. Raspoređivanje resursa - sprečavanje zastoja:
  6584. definisanje globalnog raspoređivanja resursa sistema
  6585. Zadavanje jedinstvenog broja svim resursima sistema
  6586. Proces može da zahteva resurs sa jedinstvenim brojem
  6587. samo ako već ne poseduje resurs sa jedinstvenim brojem većim od trazenog
  6588. Jednostavno za implementaciju; zahteva male troškove
  6589. Banker’s algoritam:
  6590. označava jedan proces u sistemu
  6591. kao proces koji sadrži informaciju
  6592. neophodnu za sprovođenje Banker’s algoritma
  6593. takođe se lako implementira
  6594. ali može da zahteva mnogo više troškova
  6595. Timestamped Deadlock-Šema Prevencije
  6596. Svaki proces Pi je označen
  6597. jedinstvenim brojem prioriteta
  6598. Brojevi prioriteta se koriste za odlučivanje da li
  6599. proces Pi treba da sačeka proces Pj;
  6600. inače za Pi se obavi roll-back
  6601. Šema sprečava deadlock ako:
  6602. Za svaku ivicu Pi  Pj
  6603. u wait for grafiku,
  6604. Pi ima veći prioritet od Pj.
  6605.  
  6606. U tom slučaju krug je nemoguć
  6607. Wait-Die Šema
  6608. Zasnovana na non-preemptive tehnici
  6609.  
  6610. Ako Pi zahteva resurs
  6611. koji trenutno drži Pj,
  6612. Pi je dozvoljeno da čeka samo
  6613. ako ima manju vremensku oznaku nego Pj
  6614. (Pi je stariji od Pj)
  6615. Inače, za Pi se obavi roll-back (umire)
  6616. Primer: Pretpostavimo da procesi P1, P2, i P3
  6617. imaju vremenske oznake 5, 10, i 15 redom.
  6618. ako P1 zahteva resurs koji drži P2, onda će P1 da čeka.
  6619. akoP3 zahteva resurs koji drži P2, onda će P3 biti roll-backed
  6620. Would-Wait Šema
  6621. Zasnovana na preemptive tehnici; kopija wait-die sistema
  6622. Ako Pi zahteva resurs
  6623. koji drži Pj,
  6624. Pi je dozvoljeno da čeka samo
  6625. ako ima veću vremensku oznaku nego Pj
  6626. (Pi je mlađi od Pj)
  6627. Inače za Pj se obavlja roll-back (Pj je preempt od strane Pi).
  6628. Primer: Pretpostavimo da procesi P1, P2, i P3
  6629. imaju vremenske oznake 5, 10, i 15 redom.
  6630. ako P1 zahteva resurs koji drži P2,
  6631. onda će resurs biti oduzet od P2
  6632. P2 će biti roll-back
  6633. ako P3 zahteva resurs koji drži P2, onda će P3 čekati
  6634. Detekcija zastoja
  6635. wait for graf
  6636.  
  6637. Centralizovano rešenje
  6638.  
  6639. Puno distribuirano rešenje
  6640.  
  6641. Dva Lokalna Wait-For Grafika
  6642. Globalni Wait-For Grafik
  6643. Detekcija Zakočenja – Centralizovano Rešenje
  6644. Svaki sajt čuva lokalni wait-for graf
  6645.  
  6646. čvorovi grafa odgovaraju
  6647. svim procesima
  6648. od kojih bilo ko može da drži ili zahteva
  6649. bilo koji resurs koji je lociran na tom sajtu
  6650.  
  6651.  
  6652. Globalni wait-for graf je onaj koji se kreira
  6653. u jednom procesu koordinacije;
  6654. ovaj grafik je unija svih lokalnih wait-for grafika
  6655.  
  6656. Detekcija zastoja – Centralizovano Rešenje
  6657.  
  6658. Postoje tri različite opcije (tačke u vremenu)
  6659. kada wait-for graf može stvori:
  6660.  
  6661. Kad god se ubaci ili izbaci nova ivica
  6662. u neki od lokalnih wait-for grafa
  6663. Periodično, kada se neki broj promena dogodio u wait-for graph
  6664. Kad god koordinator treba da pozove cycle-detection algoritam..
  6665.  
  6666. Mogu da se dogode nepotrebni rollback-ovi
  6667. kao rezultat false cycles
  6668. Lokalni i Globalni Wait-For Grafici
  6669. Potpuno Distribuirano Rešenje
  6670. Svi kontroleri dele podjednako
  6671. odgovornost detektovanje zakočenja
  6672.  
  6673. Svaki sajt obrazuje wait-for graph
  6674. koji predstavlja deo ukupnog grafika.
  6675.  
  6676. Uvodimo dodatni čvor Pex
  6677. za svaki lokalni wait-for graf
  6678.  
  6679. Ako lokalni wait-for grafik sadrži krug
  6680. koji ne sadrži čvor Pex,
  6681. onda je sistem u stanju zakočenja
  6682.  
  6683. Ako ciklus sadrži cvor Pex to podrazmeva
  6684. mogućnost zakočenja
  6685.  
  6686. Da bi se saznalo da li postoji zakočenje,
  6687. distributed deadlock-detection algoritam
  6688. mora da se pozove
  6689. Uvećani Lokalni Wait-For Grafovi
  6690. Election Algoritmi
  6691. Determine
  6692. Gde nova kopija koordinatora
  6693. treba da bude restart
  6694. Preuzma jedinstveni broj prioriteta
  6695. koji je vezan za svaki aktivni proces u sistemu,
  6696. broj prioriteta od procesa Pi , je i.
  6697. Preuzima jedan-na-jedan korespodenciju
  6698. između procesa i sajtova.
  6699. Koordinator je uvek proces
  6700. sa najvećim brojem prioriteta.
  6701. Kada koordinator neuspe,
  6702. algoritam mora da izabere
  6703. onaj aktivni proces sa najvećim brojem prioriteta.
  6704. Dva algoritma,
  6705. bully algorithm i ring algorithm,
  6706. mogu da se koriste pri izboru novog koordinatora u slučaju neuspeha.
  6707. Bully Algoritam
  6708. Primenljiv kod sistema
  6709. gde svaki proces može da pošalje poruku
  6710. svakom drugom procesu u sistemu.
  6711. Ako proces Pi šalje zahtev
  6712. na koji koordinator nije odgovorio
  6713. unutar vremenskog intervala T,
  6714. pretpostavlja da je koordinator pao;
  6715. Pi pokušava da izabere samog sebe
  6716. kao novog koordinatora.
  6717. Pi šalje election (biranje) poruku
  6718. svakom procesu sa većim brojem prioriteta,
  6719. Pi zatim čeka sa bilo koji od ovih procesa
  6720. odgovori unutar intervala T.
  6721. Bully Algoritam (Nastavak)
  6722. Ako nema odgovora unutar T,
  6723. pretpostavlja da su svi procesi
  6724. sa brojevima većim od i pali;
  6725. Pi postavlja sebe kao novog koordinatora.
  6726. Ako primi odgovor,
  6727. Pi započine vremenski interval T´,
  6728. čeka da primi poruku
  6729. da je proces
  6730. sa većim brojem prioritata izabran.
  6731. Ako nije poslata poruka unutar T´,
  6732. pretpostavlja da proces
  6733. sa višim brojem nije uspeo;
  6734. Pi će da restartuje algoritam
  6735. Bully Algoritam (Nastavak)
  6736. Ako Pi nije koordinator,
  6737. onda, bilo kad za vreme izvršenja,
  6738. Pi može da primi jednu od sledeće dve poruke
  6739. od procesa Pj.
  6740. 1. Pj je novi koordinator (j > i).
  6741. 2. Pj započeo biranje (j > i).
  6742. Pi, sends a response to Pj and
  6743. započinje sopstveni election algoritam,
  6744. ako taj Pi nije već inicijalizovao takav izbor.
  6745. Nakon što se neuspeli proces povrati,
  6746. odmah počinje izvršenje istog algoritma.
  6747. ako nema aktivnog procesa sa većim brojevima,
  6748. povraćeni proces izbacuje sve procese
  6749. sa manjim brojebvima
  6750. da bi postao koordinator procesa,
  6751. čak i ako već postoji koordinator sa manjim brojem.
  6752. Ring Algoritam
  6753. Primenjiv na sistemima koji su organizovani
  6754. kao prsten (ring)
  6755. (logički ili fizički).
  6756. Pretpostavlja da su linkovi sjedinjeni,
  6757. i
  6758. da procesi šalju svoje poruke
  6759. svom desnom susedu.
  6760. Svaki proces sadrži aktivnu listu,
  6761. u kojoj se nalaze svi brojevi prioriteta
  6762. svih aktivnih procesa u sistemu
  6763. kada se algoritam završi.
  6764. Ako proces Pi detektuje neuspeh koordinatora,
  6765. Stvara novu aktivnu listu koja je na početku prazna.
  6766. zatim šalje poruku elect(i) svom desnom susedu,
  6767. i
  6768. dodaje broj i svojoj aktivnoj listi.
  6769. Ring Algoritam (Nastavak)
  6770. Ako Pi primi poruku elect(j)
  6771. od procesa sa leve strane,
  6772. mora da odgovori na jedan od tri načina:
  6773. Ako je ovo prva elect koja je viđena ili poslata,
  6774. Pi stvara novu aktivnu listu sa brojevima i i j.
  6775. zatim šalje poruku elect(i),
  6776. a posle nje poruku elect(j).
  6777.  
  6778. 2. Ako i  j,
  6779. onda aktivna lista za Pi sada sadrži brojeve
  6780. svih aktivnih procesa u sistemu.
  6781. Pi može sada da determinira najveći broj
  6782. u aktivnu listu
  6783. da bi identifikovao novi koordinator proces.
  6784.  
  6785. 3. Ako i = j,
  6786. onda Pi proma poruku elect(i).
  6787. Aktivna lista za Pi sadrži sve aktivne procese u sistemu.
  6788. Pi može sada da determinira novi koordinator proces.
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!