home *** CD-ROM | disk | FTP | other *** search
/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___4.edu < prev    next >
Encoding:
Text File  |  1992-03-19  |  18.8 KB  |  708 lines
  1. 30
  2. BS___4      
  3.               Diplomprüfung Informatik (Teil 4 von 7)               
  4.                    Teilprüfung  Betriebssysteme                     
  5.                          Thema: Deadlocks                           
  6.                 zusammengestellt von Andreas Smoor                  
  7.                                                                     
  8.    Dieses Programm ist eine Shareware-Version des                   
  9.                                                                     
  10.    educard Tutoren-Systems. Das Erstellen neuer Lernprogramme       
  11.                                                                     
  12.    oder das Verändern des bestehenden ist nur mit dem               
  13.                                                                     
  14.    educard Autoren-System möglich (siehe "Educard - Information").  
  15.                                                                     
  16.    März     
  17. 1992
  18. Geben Sie Beispiele sowohl   
  19. Hardware-Betriebsmittel:     
  20.                              
  21.   Drucker, Bandgeräte, CPU,  
  22. für Hardware- als auch für   
  23.   Terminal, Speicher, ...    
  24.                              
  25.                              
  26. Software-Betriebsmittel.     
  27. Software-Betriebsmittel:     
  28.                              
  29.   Programme, Dateien, Daten, 
  30.                              
  31.   Prozesse, Routinen, ...    
  32. 2
  33.                                
  34.                                
  35. Betriebsmittel II      
  36. 1
  37. 1
  38. Betriebsmittel - 1             
  39.                                
  40. 41100246
  41. Betriebsmittel werden        
  42. a) reusable:                 
  43. unterschieden in             
  44.    CPU, Speicher, Dateien    
  45.                              
  46.                              
  47. a) wiederverwendbare und     
  48. b) consumable:               
  49. b) nicht wiederverwendbare.  
  50.    Nachrichten, Rechenzeit   
  51.                              
  52.                              
  53. Geben Sie Beispiele !        
  54.                              
  55. 2
  56.                                
  57.                                
  58. Betriebsmittel II      
  59. 1
  60. 1
  61. Betriebsmittel - 2             
  62.                                
  63. 41200247
  64. Die Zuteilung von Betriebs-  
  65. Betriebsmittel               
  66. mitteln wird unterschieden in
  67.                              
  68.                              
  69. a) preemptibel:              
  70. a) entziehbare und           
  71.    CPU, Arbeitsspeicher      
  72. b) nicht-entziehbare         
  73.                              
  74.                              
  75. b) non preemptibel:          
  76. Geben Sie Beispiele !        
  77.    Drucker, Bandgeräte       
  78. 2
  79.                                
  80.                                
  81. Betriebsmittel II      
  82. 1
  83. 1
  84. Betriebsmittel - 3             
  85.                                
  86. 41300248
  87. Der Zugriff auf Betriebs-    
  88. a) exclusive controllable:   
  89. mittel wird unterschieden in 
  90.    Drucker, Bandgeräte,      
  91.                              
  92.    Schreibzugriff auf Datei  
  93. a) exklusiv benutzbar        
  94. b) common controllable:      
  95. b) gemeinsam benutzbar.      
  96.    Lesezugriff auf Dateien,  
  97.                              
  98.    Programmcode, Compiler in 
  99. Geben Sie Beispiele !        
  100.    reentrant geschrieben     
  101. 2
  102.                                
  103.                                
  104. Betriebsmittel II      
  105. 1
  106. 1
  107. Betriebsmittel - 4             
  108.                                
  109. 41400249
  110. Ein Prozeßsystem paralleler  
  111. ...unendlich lange blockiert 
  112. Prozesse ist im              
  113. ist, weil Prozesse sich      
  114.                              
  115. gegenseitig blockieren, indem
  116.           Deadlock,          
  117. sie selbst exklusive, nicht- 
  118.                              
  119. entziehbare Betriebsmittel   
  120. wenn der Prozeßfortschritt...
  121. belegen, die ein anderer     
  122. Ergänzen Sie die Definition !
  123. Prozeß benötigt.             
  124. 2
  125.                                
  126.                                
  127. Deadlock II            
  128. 1
  129. 1
  130. Deadlock, Definition           
  131.                                
  132. 42100250
  133. Nennen Sie die vier          
  134. Bedingungen für Deadlock:    
  135.                              
  136.                              
  137. Bedingungen, die für das     
  138. 1. Gegenseitiger Ausschluß   
  139.                              
  140. 2. Nicht-Unterbrechbarkeit   
  141. Entstehen eines Deadlocks    
  142. 3. Warten auf weitere        
  143.                              
  144.    Betriebsmittel            
  145. notwendig sind.              
  146. 4. Geschlossene Kette        
  147. 2
  148.                                
  149.                                
  150. Deadlock II            
  151. 1
  152. 1
  153. Deadlock, Bedingungen          
  154.                                
  155. 42200251
  156. Eine notwendige Bedingung    
  157. Gegenseitiger Ausschluß:     
  158. für einen Deadlock besteht   
  159.                              
  160. im gegenseitigen Ausschluß   
  161. Die angeforderten und        
  162. (mutual exclusion).          
  163. vergebenen Betriebsmittel    
  164.                              
  165. sind nur exklusiv verwendbar.
  166. Was ist damit gemeint ?      
  167.                              
  168.                              
  169.                              
  170. 2
  171.                                
  172.                                
  173. Deadlock II            
  174. 1
  175. 1
  176. gegenseitiger Ausschluß        
  177.                                
  178. 42200252
  179. Eine notwendige Bedingung    
  180. Nicht-Unterbrechbarkeit:     
  181. für einen Deadlock besteht in
  182.                              
  183. der Nicht-Unterbrechbarkeit  
  184. Die Betriebsmittel können    
  185. (non preemption).            
  186. einem Prozeß nicht entzogen  
  187.                              
  188. werden. Der Prozeß muß sie   
  189. Was ist damit gemeint ?      
  190. von sich aus freigeben.      
  191.                              
  192.                              
  193. 2
  194.                                
  195.                                
  196. Deadlock II            
  197. 1
  198. 1
  199. Nicht-Unterbrechbarkeit        
  200.                                
  201. 42200253
  202. Eine notwendige Bedingung    
  203. Die Prozesse belegen die     
  204. für einen Deadlock besteht im
  205. bereits erhaltenen           
  206. Warten auf weitere Betriebs- 
  207. exklusiven Betriebsmittel,   
  208. mittel (resource waiting).   
  209. während sie auf die Zuteilung
  210.                              
  211. noch weiterer Betriebsmittel 
  212. Sagen Sie etwas dazu.        
  213. warten.                      
  214.                              
  215.                              
  216. 2
  217.                                
  218.                                
  219. Deadlock II            
  220. 1
  221. 1
  222. resource waiting               
  223.                                
  224. 42200254
  225. Eine notwendige Bedingung    
  226. Die Prozesse warten aufein-  
  227. für einen Deadlock besteht   
  228. ander, das heißt jeder Prozeß
  229. in einer geschlossenen Kette 
  230. der Kette belegt bereits     
  231. (chains of tasks).           
  232. Betriebsmittel, die von einem
  233.                              
  234. anderen Prozeß der Kette     
  235. Was besagt diese Bedingung ? 
  236. benötigt werden.             
  237.                              
  238.                              
  239. 2
  240.                                
  241.                                
  242. Deadlock II            
  243. 1
  244. 1
  245. chains of tasks                
  246.                                
  247. 42200255
  248. Nennen Sie drei Verfahren    
  249. Umgang mit Deadlocks:        
  250.                              
  251. - Verhindern (prevention),   
  252. zur Behandlung des           
  253. - Vermeiden (avoidance) oder 
  254.                              
  255. - Erkennen und Beheben       
  256. Deadlock-Problems !          
  257.   (detection and recovery)   
  258.                              
  259.                              
  260.                              
  261. Merkwort : "dead PADRe"      
  262. 2
  263.                                
  264.                                
  265. Deadlock II            
  266. 1
  267. 1
  268. Deadlock-Behandlung            
  269.                                
  270. 42200256
  271. Das Verhindern von Deadlocks 
  272. Deadlockverhinderung durch:  
  273. (prevention) kann durch      
  274. - streng sequentieller Ablauf
  275. verschiedene Methoden        
  276. - alle benötigten Betriebs-  
  277. erreicht werden.             
  278.   mittel zugleich anfordern  
  279.                              
  280. - nachfordernde Prozesse     
  281. Nennen Sie vier Methoden um  
  282.   müssen BM freigeben        
  283. Deadlocks zu verhindern.     
  284. - BM hierarchisch anordnen   
  285. 2
  286.                                
  287.                                
  288. Deadlock II            
  289. 1
  290. 1
  291. prevention                     
  292.                                
  293. 42200257
  294. Es gibt drei Forderungen     
  295. 1. MAXi ≤ m                  
  296. im Zusammenhang mit Deadlocks
  297. 2. DEVi ≤ MAXi               
  298. damit ein Zustand            
  299. 3. REQ  ≤ FREE               
  300.                              
  301.                              
  302.        realisierbar          
  303. Eine genauere Erläuterung    
  304.                              
  305. durch Drücken der Taste 'i'. 
  306. ist. Welche ?                
  307.                              
  308. 2
  309.                                
  310.                                
  311. Deadlock-Vermeidung    
  312. 1
  313. 1
  314. Deadlock, Vermeidung - 1       
  315.                                
  316. 42200258
  317. Geben Sie ein Beispiel für   
  318. m   = (4)                    
  319. den Fall, daß ein Zustand    
  320. MAX = (4, 4, 2)              
  321. zwar realisierbar ist, aber  
  322. DEV = (1, 1, 1) -> (2, 1, 1) 
  323. nicht sicher, also Deadlock- 
  324.                              
  325. gefahr besteht.              
  326. Falls die Prozesse nun ihre  
  327.                              
  328. Maximalanforderungen stellen,
  329.                              
  330. tritt der Deadlock ein.      
  331. 2
  332.                                
  333.                                
  334. Deadlock-Vermeidung    
  335. 1
  336. 1
  337. Deadlock, Vermeidung - 2       
  338.                                
  339. 42200259
  340. Ein Prozeßsystem P ist in    
  341. a) |P| ≤ 1                   
  342. einem sicheren Zustand Z,    
  343. b) Zu jedem Zeitpunkt gibt es
  344. wenn eine von zwei           
  345.    einen Prozeß, der seine   
  346. Bedingungen erfüllt ist.     
  347.    Maximalforderungen erfüllt
  348.                              
  349.    bekommen kann, also       
  350. Um welche Bedingungen handelt
  351.    beendet werden kann.      
  352. es sich ?                    
  353.                              
  354. 2
  355.                                
  356.                                
  357. Deadlock-Vermeidung    
  358. 1
  359. 1
  360. sicherer Zustand               
  361.                                
  362. 42200260
  363. Um Deadlockfreiheit zu       
  364. Zu jeder Zeit muß es         
  365. gewährleisten muß sich ein   
  366. mindestens einen Prozeß geben
  367. System jederzeit in einem    
  368. der beendet werden kann und  
  369. sicheren Zustand befinden.   
  370. seine Betriebsmittel frei-   
  371. Wie lautet in diesem Zusam-  
  372. gibt. Danach muß es dann     
  373. menhang die                  
  374. wieder einen Prozeß geben,   
  375. "Habermann'sche Forderung" ? 
  376. der beendet werden kann, usw.
  377. 2
  378.                                
  379.                                
  380. Deadlock-Algorithmen   
  381. 1
  382. 1
  383. Habermann'sche Forderung - 1   
  384.                                
  385. 42200261
  386. Drücken Sie die              
  387. NEEDk1 ≤ FREE                
  388.                              
  389. NEEDk2 ≤ FREE + DEVk1        
  390. Habermann'sche Forderung mit 
  391.   :                          
  392.                              
  393.   :                          
  394. Hilfe von NEED, FREE und DEV 
  395. NEEDkj ≤ FREE + S (k-1)      
  396.                              
  397. mit S (k-1) =                
  398. aus !                        
  399.     DEVk1 + ... + DEVk(j-1)  
  400. 2
  401.                                
  402.                                
  403. Deadlock-Algorithmen   
  404. 1
  405. 1
  406. Habermann'sche Forderung - 2   
  407.                                
  408. 42200262
  409. Gegeben seien m Betriebs-    
  410. 1 ≤ MAXi ≤ m drückt aus,     
  411. mittel des gleichen Typs.    
  412. daß kein Prozeß mehr         
  413. Eine Bedingung für die       
  414. Betriebsmittel anfordern     
  415. Realisierbarkeit eines       
  416. kann, als im System über-    
  417. Zustandes ist dann           
  418. haupt zur Verfügung stehen.  
  419.        1 ≤ MAXi ≤ m          
  420.                              
  421. Was heißt das ?              
  422.                              
  423. 2
  424.                                
  425.                                
  426. Deadlock-Algorithmen   
  427. 1
  428. 1
  429. Realisierbarkeit - 1           
  430.                                
  431. 42200263
  432. Eine Voraussetzung für die   
  433. 0 ≤ DEVi ≤ MAXi drückt aus,  
  434. Realisierbarkeit eines       
  435. daß keinem Prozeß mehr       
  436. Zustandes ist                
  437. Betriebsmittel zugewiesen    
  438.                              
  439. werden dürfen, als er zu     
  440.       0 ≤ DEVi ≤ MAXi        
  441. Beginn als Maximalanforderung
  442.                              
  443. angegeben hatte.             
  444. Was bedeutet das ?           
  445.                              
  446. 2
  447.                                
  448.                                
  449. Deadlock-Algorithmen   
  450. 1
  451. 1
  452. Realisierbarkeit - 2           
  453.                                
  454. 42200264
  455. Eine Voraussetzung für die   
  456. Das System kann nicht mehr   
  457. Realisierbarkeit eines       
  458.                              
  459. Zustandes ist:               
  460. Betriebsmittel vergeben, als 
  461.                   n          
  462.                              
  463.           S (n) = Σ DEVi ≤ m 
  464. ihm überhaupt zur Verfügung  
  465.                  i=1         
  466.                              
  467. Was heißt das ?              
  468. stehen.                      
  469. 2
  470.                                
  471.                                
  472. Deadlock-Algorithmen   
  473. 1
  474. 1
  475. Realisierbarkeit - 3           
  476.                                
  477. 42200265
  478. Sei G der größte zulässige   
  479. Deadlockgefährdeter Bereich: 
  480. Maximalwert für ein MAXi.    
  481.                              
  482. Dann muß die Zahl der BM m im
  483.    [G .. n * (G - 1)]        
  484. Bereich von [G..n*G] liegen. 
  485.                              
  486. Innerhalb dieses Bereichs    
  487. Deadlockfreier Bereich:      
  488. gibt es eine Grenze für      
  489.                              
  490. Deadlockfreiheit. Wo ?       
  491.    [n * (G - 1) + 1 .. n * G]
  492. 2
  493.                                
  494.                                
  495. Deadlock-Algorithmen   
  496. 1
  497. 1
  498. Betriebsmittel, Anzahl         
  499.                                
  500. 42200266
  501. Wie lautet das Habermann'sche
  502. Ein Zustand ist dann und nur 
  503.                              
  504. dann deadlockfrei, wenn für  
  505. Theorem für die Deadlock-    
  506. alle k aus [0..m] gilt:      
  507.                              
  508.                              
  509. freiheit eines Systems ?     
  510.    Uk ≤ m - k                
  511.                              
  512.                              
  513.                              
  514. Genaueres mit Taste 'i'.     
  515. 2
  516.                                
  517.                                
  518. Deadlock-Algorithmen   
  519. 1
  520. 1
  521. Habermann'sches Theorem - 1    
  522.                                
  523. 42200267
  524. Leiten Sie das               
  525. Uk + Lk = m - FREE        ==>
  526.                              
  527.                              
  528. Habermann'sche Theorem       
  529.      Uk = m - FREE - Lk      
  530.                              
  531.                              
  532.    für alle k:  Uk ≤ m - k   
  533.      Lk ≥ k - FREE        ==>
  534.                              
  535.                              
  536. ab.                          
  537.      Uk ≤ m - k              
  538. 2
  539.                                
  540.                                
  541. Deadlock-Algorithmen   
  542. 1
  543. 1
  544. Habermann'sches Theorem - 2    
  545.                                
  546. 42200268
  547. Wie läßt sich ein System-    
  548. Tabelle führen mit Vektor U  
  549. zustand im Prinzip auf       
  550. für jeden Prozeß Pi.         
  551. Deadlock-Freiheit untersuchen
  552. U enthält die aktuellen Uk's 
  553. falls die Zahl der Betriebs- 
  554. der Pi's. Zu jedem Zeitpunkt 
  555. mitteltypen T auf 1          
  556. muß gelten:                  
  557. beschränkt ist.              
  558. für alle k:  Uk ≤ m - k      
  559.                              
  560. Aufwand: O (max (MAXi))      
  561. 2
  562.                                
  563.                                
  564. Deadlock-Algorithmen   
  565. 1
  566. 1
  567. Deadlockuntersuchung - 1       
  568.                                
  569. 42200269
  570. Wie überprüft man einen      
  571. Immer wieder alle Prozesse   
  572. Systemzustand auf Deadlock-  
  573. durchgehen. Wenn einer       
  574. Freiheit, wenn die Zahl der  
  575. beendet werden kann, seine BM
  576. Betriebsmittel-Typen T       
  577. freigeben und ihn streichen. 
  578. größer als 1 ist ?           
  579. Am Ende darf kein Prozeß mehr
  580.                              
  581. übrigbleiben.                
  582.                              
  583.                              
  584. 2
  585.                                
  586.                                
  587. Deadlock-Algorithmen   
  588. 1
  589. 1
  590. Deadlockuntersuchung - 3       
  591.                                
  592. 42200271
  593. Wie groß ist der Aufwand für 
  594. Aufwand im günstigsten Fall: 
  595. die Untersuchung eines       
  596.                              
  597. Systemzustandes auf Deadlock-
  598.   O (n * T)                  
  599. freiheit im günstigsten und  
  600.                              
  601. im ungünstigsten Fall ?      
  602. Ungünstigster Fall:          
  603. Zahl der Betriebsmitteltypen 
  604.                              
  605. T sei > 1.                   
  606.   O (T * n²)                 
  607. 2
  608.                                
  609.                                
  610. Deadlock-Algorithmen   
  611. 1
  612. 1
  613. Deadlockuntersuchung - 4       
  614.                                
  615. 42200272
  616. Wie kann man den Algorithmus 
  617. Einführen von k_min.         
  618. zur Untersuchung auf         
  619. k_min ist der kleinste Wert  
  620. Deadlockfreiheit bei T = 1   
  621. von k mit Uk = m - k.        
  622. noch verbessern ?            
  623. Untersucht werden brauchen   
  624.                              
  625. nun nur die Werte > k_min.   
  626.                              
  627.                              
  628.                              
  629.                              
  630. 2
  631.                                
  632.                                
  633. Deadlock-Algorithmen   
  634. 1
  635. 1
  636. Deadlockuntersuchung - 2       
  637.                                
  638. 42200270
  639. Wodurch unterscheidet sich   
  640. Das Erkennen von Deadlocks   
  641. das Erkennen von Deadlocks   
  642. unterscheidet sich:          
  643. bei den zwei prinzipiellen   
  644. a) durch den Zeitpunkt der   
  645. Vorgehensweisen "Erkennen und
  646.    Untersuchung und          
  647. Beseitigen" und "Vermeiden"  
  648. b) beim Vermeiden muß man die
  649. von Deadlocks ?              
  650.    Maximalanforderungen der  
  651.                              
  652.    Prozesse kennen.          
  653. 2
  654.                                
  655.                                
  656. Deadlock-Algorithmen   
  657. 1
  658. 1
  659. Erkennen und Beseitigen - 1    
  660.                                
  661. 42200273
  662. Bei den Algorithmen zum      
  663. NEED wird durch REQ          
  664. Erkennen und Beseitigen von  
  665.                              
  666. Deadlocks wird im Vergleich  
  667. und restliche Anforderungen  
  668. zu denen beim Vermeiden      
  669.                              
  670. "NEED" durch ... und         
  671. wird durch aktuelle          
  672. "restliche Anforderung" durch
  673.                              
  674. ... ersetzt ?                
  675. Anforderungen ersetzt.       
  676. 2
  677.                                
  678.                                
  679. Deadlock-Algorithmen   
  680. 1
  681. 1
  682. Erkennen und Beseitigen - 2    
  683.                                
  684. 42200274
  685. Welches sind die Vor- und    
  686. "Erkennen + Beseitigen" von  
  687. Nachteile des                
  688. Deadlocks ist weniger auf-   
  689. "Erkennen und Beseitigen"    
  690. wendig, aber es wird Schaden 
  691. im Vergleich zum "Vermeiden" 
  692. angerichtet beim Beseitigen  
  693. von Deadlocks ?              
  694. der entstehenden Deadlocks.  
  695.                              
  696.                              
  697.                              
  698.                              
  699. 2
  700.                                
  701.                                
  702. Deadlock-Algorithmen   
  703. 1
  704. 1
  705. Erkennen und Beseitigen - 3    
  706.                                
  707. 42200275
  708.