Ψάχνουμε να βρούμε μία γραμμή της οποίας οι επιπλέον απαιτήσεις σε πόρους είναι μικρότερες ή ίσες από το Availabe. Αν φτιάξουμε τον πίνακα Request από τη σχέση @@Request[i,j] = Max[i,j] – Allocation [i,j]@@, έχουμε.

Για να μην υπάρξει αδιέξοδο πρέπει κάθε διεργασία να έχει δεσμεύσει ένα πόρο R και να υπάρχει ένας ακόμη ελεύθερος ώστε μία από αυτές να μπορέσει να δεσμεύσει το μέγιστο των 2 πόρων. Έτσι, το μέγιστο για το οποίο δεν υπάρχει αδιέξοδο είναι Ρ=R-1. Προφανός για οτιδήποτε μικρότερο δεν υπάρχει αδιέξοδο. Έτσι, έχουμε τη συνθήκη P<=R-1.

Κάθε διεργασία θα έχει δεσμεύσει έναν πόρο. Για να μην υπάρξει αδιέξοδο θα πρέπει να υπάρχουν 2 μονάδες ακόμη του R, έτσι ώστε μία διεργασία να μπορεί να φτάσει το μέγιστό της. Αυτό μας δίνει τη σχέση N<=M-2.

>><<

----

A distributed system using mailboxes has two IPC primitives, send and receive. The latter primitive specifies a process to receive from and blocks if no message from that process is available, even though messages may be waiting from other processes. There are no shared resources, but processes need to communicate frequently about other matters. Is deadlock possible? Discuss.

Yes. Suppose that all the mailboxes are empty. Now A sends to B and waits for a reply, B sends to C and waits for a reply, and C sends to A and waits for a reply. All the conditions for deadlock are now fulfilled.

Two processes, A and B, each need three records, 1, 2. and 3, in a database. If A asks for them in the order 1, 2, 3, and B asks for them in the same order, deadlock is not possible. However, if B asks for them in the order 3, 2, 1, then deadlock is possible. With three resources, there are 3! or 6 possible combinations each process can request the resources. What fraction of all the combinations are guaranteed to be deadlock free?

Suppose that process A requests the records in the order a, b, c. If process B also asks for a first, one of them will get it and the other will block. This situation is always deadlock free since the winner can now run to completion without interference. Of the four other combinations, some may lead to deadlock and some are deadlock free. The six cases are as follows:

* abc: deadlock free
* acb: deadlock free
* bac: possible deadlock
* bca: possible deadlock
* cab: possible deadlock
* cba: possible deadlock

Since four of the six may lead to deadlock, there is a 1/3 chance of avoiding a deadlock and a 2/3 chance of getting one.

----

Now reconsider the above problem, but using two-phase locking. Will that eliminate the potential for deadlock? Does it have any other undesirable characteristics, however? If so, which ones?

>>answer<<

!!! Απάντηση

Two-phase locking eliminates deadlocks, but introduces potential starvation. A process has to keep trying and failing to acquire all of its records. There is no upper bound on how long it may take.

>><<

!!! Ερώτηση

In an electronic funds transfer system, there are hundreds of identical processes that work as follows. Each process reads an input line specifying an amount of money, the account to be credited, and the account to be debited. Then it locks both accounts and transfers the money, releasing the locks when done. With many processes running in parallel, there is a very real danger that having locked account x it will be unable to lock y because y has been locked by a process now waiting for x. Devise a scheme that avoids deadlocks. Do not release an account record until you have completed the transactions. (In other words, solutions that lock one account and then release it immediately if the other is locked are not allowed.)

>>answer<<

!!! Απάντηση

To avoid circular wait, number the resources (the accounts) with their account numbers. After reading an input line, a process locks the lower-numbered account first, then when it gets the lock (which may entail waiting), it locks the other one. Since no process ever waits for an account lower than what it already has, there is never a circular wait, hence never a deadlock.

>><<

!!! Ερώτηση

One way to prevent deadlocks is to eliminate the hold-and-wait condition. In the text it was proposed that before asking for a new resource, a process must first release whatever resources it already holds (assuming that is possible). However, doing so introduces the danger that it may get the new resource but lose some of the existing ones to competing processes. Propose an improvement to this scheme.

>>answer<<

!!! Απάντηση

Change the semantics of requesting a new resource as follows. If a process asks for a new resource and it is available, it gets the resource and keeps what it already has. If the new resource is not available, all existing resources are released. With this scenario, deadlock is impossible and there is no danger that the new resource is acquired but existing ones lost. Of course, the process only works if releasing a resource is possible (you can release a scanner between pages or a CD recorder between CDs).

>><<

!!! Ερώτηση

A computer science student assigned to work on deadlocks thinks of the following brilliant way to eliminate deadlocks. When a process requests a resource, it specifies a time limit. If the process blocks because the resource is not available, a timer is started. If the time limit is exceeded, the process is released and allowed to run again. If you were the professor, what grade would you give this proposal and why.

>>answer<<

!!! Απάντηση

I’d give it an F (failing) grade. What does the process do? Since it clearly needs the resource, it just asks again and blocks again. This is no better than staying blocked. In fact, it may be worse since the system may keep track of how long competing processes have been waiting and assign a newly freed resource to the process that has been waiting longest. By periodically timing out and trying again, a process loses its seniority.

>><<

!!! Ερώτηση

Cinderella and the Prince are getting divorced. To divide their property, they have agreed on the following algorithm. Every morning, each one may send a letter to the other’s lawyer requesting one item of property. Since it takes a day for letters to be delivered, they have agreed that if both discover that they have requested the same item on the same day, the next day they will send a letter canceling the request. Among their property is their dog. Woofer. Woofer’s doghouse, their canary. Tweeter, and Tweeter’s cage. The animals love their houses, so it has been agreed that any division of property separating an animal from its house is invalid, requiring the whole division to start over from scratch. Both Cinderella and the Prince desperately want Woofer. So they can go on (separate) vacations, each spouse has programmed a personal computer to handle the negotiation. When they come back from vacation, the computers are still negotiating. Why? Is deadlock possible? Is starvation possible? Discuss.

If both programs ask for Woofer first, the computers will starve with the endless sequence: request Woofer, cancel request, request Woofer, cancel request, etc. If one of them asks for the doghouse and the other asks for the dog, we have a deadlock, which is detected by both parties and then broken, but it is just repeated on the next cycle. Either way, if both computers have been programmed to go after the dog or the doghouse first, either starvation or deadlock ensues. There is not really much difference between the two here. In most deadlock problems, starvation does not seem serious because introducing random delays will usually make it very unlikely. That approach does not work here.

>><<

! Γράφοι Εκχώρησης Πόρων

||width=60%
||Διεργασία || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess.jpg ||
||Τύπος Πόρου με 4 Στιγμιότυπα || http://users.sch.gr/fergadis/images/OS/Deadlock/resource.jpg ||
||Η διεργασία P'_i_' ζητάει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-request.jpg ||
||Η διεργασία P'_i_' δεσμεύει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-get.jpg ||
||Η διεργασία P'_i_' απελευθερώνει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-release.jpg ||

!!! Ερώτηση

Να σχεδιάσετε ένα γράφο εκχώρησης πόρων για τα παρακάτω:
*Η διεργασία P1 απαιτεί τον πόρο R1
*Η διεργασία P2 απαιτεί τον πόρο R3
*Ο πόρος R1 είναι δεσμευμένος από τη διεργασία P2
*Ο πόρος R2 είναι δεσμευμένος από τη διεργασία P1
*Ο πόρος R3 είναι δεσμευμένος από τη διεργασία P3

Υπάρχει αδιέξοδο; Θεωρείστε ότι κάθε πόρος έχει ένα στιγμιότυπο.

>>answer<<

!!! Απάντηση

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise1.png

Όπως φαίνεται από το γράφο δεν υπάρχει κύκλος, άρα δεν υπάρχει αδιέξοδο.

Ο πόρος R1 θα ελευθερωθεί κάποια στιγμή από την P2 και η Ρ1 θα μπορέσει να ολοκληρώσει. Επίσης, ο πόρος R3 θα ελευθερωθεί όταν ολοκληρώσει η Ρ3 και θα μπορέσει να ολοκληρώσει και η Ρ2.

>><<

!!! Ερώτηση

Ένα σύστημα αποτελείται από 4 διεργασίες, (Ρ1, Ρ2, Ρ3, Ρ4), και 3 τύπους από σειριακά επαναχρησιμοποιούμενους πόρους, (R1, R2, R3). Ο αριθμός των μονάδων των πόρων είναι E=<3,2,2>.
*Η διεργασία P1 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P2 κρατά 2 μονάδες του R2 και απαιτεί 1 μονάδα καθενός από τους R1 και R3.
*Η διεργασία P3 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P4 κρατά 2 μονάδες του R3 και απαιτεί 1 μονάδα του R1

Φτιάξτε το γράφο. Υπάρχει αδιέξοδο;

>>answer<<

!!! Απάντηση

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2.png

Όπως φαίνεται παρακάτω υπάρχουν τρεις κύκλοι.

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2a.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2b.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2c.png

Όλοι οι κύκλοι περνούν υποχρεωτικά από τον πόρο R1 ο οποίος έχει ένα στιγμιότυπο ελεύθερο. Το αν θα υπάρξει αδιέξοδο εξαρτάται σε ποια διεργασία θα δοθεί αυτός ο πόρος. Αν δοθεί στην Ρ2, τότε έχουμε αδιέξοδο διότι τότε όλες οι διεργασίες θα αιτούνται ένα ακόμη στιγμιότυπο άλλου πόρου το οποίο δεν είναι ελεύθερο. Αν δοθεί την Ρ4, τότε αυτή έχει όλους τους πόρους που χρειάζεται και μπορεί να ολοκληρώσει. Έτσι, αφήνει ελεύθερα τα δύο στιγμιότυπα που πόρου R3 και το ένα του R1. Αυτό δίνει τη δυνατότητα στην Ρ2 να δεσμεύσει τους πόρους που χρειάζεται και να ολοκληρώσει. Στη συνέχεια ολοκληρώνουν και οι Ρ1 και Ρ3 που έχουν χρειάζονταν τα στιγμιότυπα του πόρου R2.

>><<

! Δομές Δεδομένων για τον Αλγόριθμο του Τραπεζίτη

* @@'''n'''@@ = το πλήθος των διεργασιών,
* @@'''m'''@@ = το πλήθος τύπων πόρων
* @@'''Existence'''@@: Διάνυσμα μήκους @@m@@. Το @@Existence[j]@@ δίνει το μέγιστο πλήθος στιγμιότυπων του πόρου @@R'_j_'@@.
* @@'''Available'''@@: Διάνυσμα μήκους @@m@@. Αν @@Available[j] = k@@, υπάρχουν @@k@@ στιγμιότυπα του τύπου πόρου @@R'_j_'@@ διαθέσιμα.
* @@'''Max'''@@: @@n x m@@ πίνακας. Αν @@Max[i,j] = k@@, τότε η διεργασία @@P'_i_'@@ μπορεί να απαιτήσει κατά μέγιστο @@k@@ στιγμιότυπα του τύπου πόρου @@R'_j_'@@.
* @@'''Allocation'''@@: @@n x m@@ πίνακας. Αν @@Allocation[i,j] = k@@ τότε στη διεργασία @@P'_i_'@@ εκχωρούνται @@k@@ στιγμιότυπα του πόρου @@R'_j_'@@.
* @@'''Request'''@@: @@n x m@@ πίνακας. Αν @@Request[i,j] = k@@, τότε η διεργασία @@P'_i_'@@ μπορεί να χρειαστεί @@k@@ επιπλέον στιγμιότυπα του πόρου @@R'_j_'@@ για να ολοκληρωθεί.

%center%@@Request[i,j] = Max[i,j] – Allocation [i,j]@@

!!! Ερώτηση

Υπάρχουν 3 τύποι πόρων με πλήθος: R1 = 9, R2 = 3, R3 = 6. Είναι η παρακάτω κατάσταση ασφαλής;

(:table cellpadding=2px align=center:)
(:cell:)
(:table:)
(:caption:)Total
----
(:row align=center:)

(:row align=center :)
(:cell:)9

(:cell:)6

(:cell:)0
(:cell:)1
(:cell:)1

(:cell:)6
(:cell:)1
(:cell:)2

(:tableend:)

>>answer<<

!!! Απάντηση

Ψάχνουμε να βρούμε μία γραμμή της οποίας οι επιπλέον απαιτήσεις σε πόρους είναι μικρότερες ή ίσες από το Availabe. Αν φτιάξουμε τον πίνακα Need από τη σχέση @@Need[i,j] = Max[i,j] – Allocation [i,j]@@, έχουμε.

(:row align=center style='background-color: lightyellow;':)

(:cell:)1

Βλέπουμε ότι η Ρ2 έχει μικρότερες απαιτήσεις από τις διαθέσιμες στο Available. Έτσι, δεσμεύει τους πόρους που χρειάζεται και αφού ολοκληρώσει τους ελευθερώνει. Οι πίνακες τώρα είναι όπως παρακάτω.

Προσέχουμε στον πίνακα Available. Η Ρ2 δεσμεύοντας το ένα στιγμιότυπο του πόρου R3, έχει Allocated: 6 1 3 και ο Availabe: 0 1 0. Ο Availabe μετά την ολοκλήρωση της Ρ2 είναι το άθροισμα των παραπάνω.

(:table cellpadding=2px:)
(:cell:)
(:table:)
(:caption:)Available

(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center :)
(:cell:)6
(:cell:)2
(:cell:)3
(:tableend:)
(:cell:)
(:table:)
(:caption:)Max

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)3
(:cell:)2
(:cell:)2
(:row align=center:)
(:head:)P2
(:cell:)6
(:cell:)1
(:cell:)3
(:row align=center:)
(:head:)P3
(:cell:)3
(:cell:)1
(:cell:)4
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)2
(:cell:)2
(:tableend:)
(:cell:)
(:table:)
(:caption:)Allocated

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)1
(:cell:)0
(:cell:)0
(:row align=center:)
(:head:)P2
(:cell:)0
(:cell:)0
(:cell:)0
(:row align=center:)
(:head:)P3
(:cell:)2
(:cell:)1
(:cell:)1
(:row align=center:)
(:head:)P4
(:cell:)0
(:cell:)0
(:cell:)2
(:tableend:)
(:cell:)
(:table:)
(:caption:)Request

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)2
(:cell:)2
(:cell:)2
(:row align=center:)
(:head:)P2
(:cell:)0
(:cell:)0
(:cell:)0
(:row align=center:)
(:head:)P3
(:cell:)1
(:cell:)0
(:cell:)3
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)2
(:cell:)0
(:tableend:)
(:tableend:)

Απ' αυτό το σημείο οποιαδήποτε από τις διεργασίες που παραμένουν μπορεί να ολοκληρώσει αφού υπάρχουν οι διαθέσιμοι πόροι.

>><<


----

A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:

[@
Process Allocated Maximum Availabe
A 1 0 2 1 1 1 1 2 1 3 0 0 x 1 1
B 2 0 1 1 0 2 2 2 1 0
C 1 1 0 1 0 2 1 3 1 0
D 1 1 1 1 0 1 1 2 2 1
@]


What is the smallest value of x for which this is a safe state?

The request matix is as follows:

[@
0 1 0 0 2
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
@]

If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is @@1 1 3 2 1@@ and C can run. After it finishes and returns its resources the available vector is @@2 2 3 3 1@@, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2.

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----



----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

[@
Process Allocated Maximum Availabe
A 1 0 2 1 1 1 1 2 1 3 0 0 x 1 1
B 2 0 1 1 0 2 2 2 1 0
C 1 1 0 1 0 2 1 3 1 0
D 1 1 1 1 0 1 1 2 2 1
@]

The request matix is as follows:

[@
0 1 0 0 2
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
@]

If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is @@1 1 3 2 1@@ and C can run. After it finishes and returns its resources the available vector is @@2 2 3 3 1@@, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2.

|| B || 2 || 0 || 1 || 1 || 0 || 2 || 2 || 2 || 1 || 0 || || || || || ||
|| C || 1 || 1 || 0 || 1 || 0 || 2 || 1 || 3 || 1 || 0 || || || || || ||
|| D || 1 || 1 || 1 || 1 || 0 || 1 || 1 || 2 || 2 || 1 || || || || || ||

A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:

||class='tabtable'
||! Process ||! Allocated ||||||||||! Maximum ||||||||||! Availabe ||||||||||
|| A || 1 || 0 || 2 || 1 || 1 || 1 || 1 || 2 || 1 || 3 || 0 || 0 || x || 1 || 1 ||
|| B || 2 || 0 || 1 || 1 || 0 || 2 || 2 || 2 || 1 || 0 ||||||||||||
|| C || 1 || 1 || 0 || 1 || 0 || 2 || 1 || 3 || 1 || 0 ||||||||||||
|| D || 1 || 1 || 1 || 1 || 0 || 1 || 1 || 2 || 2 || 1 ||||||||||||


What is the smallest value of x for which this is a safe state?

Μπορούμε να πάρουμε περιπτώσεις και να τις μελετήσουμε.

* Με 3 διεργασίες κάθε μία μπορεί να έχει 2 drives. Δεν έχουμε αδιέξοδο.

* Με 4 διεργασίες η κατανομή των drives είναι (2, 2, 1, 1). Οι δύο διεργασίες έχουν το πλήθος που απαιτούν. Ελευθερώνουν τα στιγμιότυπα και οι άλλες δύο μπορούν να τα δεσμεύσουν. Δεν έχουμε αδιέξοδο.

* Με 5 διεργασίες η κατανομή των drives είναι (2, 1, 1, 1, 1). Η μία διεργασία το πλήθος που απαιτεί. Όταν το ελευθερώσει έχουμε την παραπάνω περίπτωση (4 διεργασίες). Δεν έχουμε αδιέξοδο.

* Με 6 διεργασίες η κατανομή των drives είναι (1, 1, 1, 1, 1, 1). Εδώ κάθε διεργασία περιμένει για ένα ακόμη drive. Σ' αυτήν την περίπτωση έχουμε αδιέξοδο.

* @@'''Existence'''@@: Διάνυσμα μήκους @@m@@. Το @@Existence[j]@@ δίνει το μέγιστο πλήθος στιγμιότυπων του πόρου @@R'_j_'@@.
* @@'''Available'''@@: Διάνυσμα μήκους @@m@@. Αν @@Available[j] = k@@, υπάρχουν @@k@@ στιγμιότυπα του τύπου πόρου @@R'_j_'@@ διαθέσιμα.

* @@'''Request'''@@: @@n x m@@ πίνακας. Αν @@Request[i,j] = k@@, τότε η διεργασία @@P'_i_'@@ μπορεί να χρειαστεί @@k@@ επιπλέον στιγμιότυπα του πόρου @@R'_j_'@@ για να ολοκληρωθεί.

%center%@@Request[i,j] = Max[i,j] – Allocation [i,j]@@

(:caption:)Request

(:caption:)Request

(:row align=center:)

Απ' αυτό το σημείο οποιαδήποτε από τις διεργασίες που παραμένουν μπορεί να ολοκληρώσει αφού υπάρχουν οι διαθέσιμοι πόροι.

Προσέχουμε στον πίνακα Available. Η Ρ2 δεσμεύοντας το ένα στιγμιότυπο του πόρου R3, έχει Allocated: 6 1 3 και ο Availabe: 0 1 0. Ο Availabe μετά την ολοκλήρωση της Ρ2 είναι το άθροισμα των παραπάνω.

(:cell:)3

(:cell:)4

(:cell:)2

Βλέπουμε ότι η Ρ2 έχει μικρότερες απαιτήσεις από τις διαθέσιμες στο Available. Έτσι, δεσμεύει τους πόρους που χρειάζεται και αφού ολοκληρώσει τους ελευθερώνει. Οι πίνακες τώρα είναι όπως παρακάτω.

Σ' αυτό το σημείο μόνο η Ρ1 μπορεί να δεσμεύσει τους πόρους που χρειάζεται. Ολοκληρώνοντας έχουμε.

(:cell:)2

(:cell:)0

(:row align=center:)

(:row align=center style='background-color: lightyellow;':)

(:row align=center:)

(:table cellpadding=2px:)

(:cell:)6
(:cell:)2
(:cell:)3

(:row align=center style='background-color: lightyellow;':)

(:cell:)0
(:cell:)0
(:cell:)0

(:cell:)

(:table cellpadding=2px align=center:)
(:cell:)
(:table:)
(:caption:)Available

(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center :)
(:cell:)0
(:cell:)1
(:cell:)1
(:tableend:)
(:cell:)
(:table:)
(:caption:)Max

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)3
(:cell:)2
(:cell:)2
(:row align=center:)
(:head:)P2
(:cell:)6
(:cell:)1
(:cell:)3
(:row align=center:)
(:head:)P3
(:cell:)3
(:cell:)1
(:cell:)4
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)2
(:cell:)2
(:tableend:)
(:cell:)
(:table:)
(:caption:)Allocated

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)1
(:cell:)0
(:cell:)0
(:row align=center:)
(:head:)P2
(:cell:)6
(:cell:)1
(:cell:)2
(:row align=center:)
(:head:)P3
(:cell:)2
(:cell:)1
(:cell:)1
(:row align=center:)
(:head:)P4
(:cell:)0
(:cell:)0
(:cell:)2
(:tableend:)
(:table:)
(:caption:)Need

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)2
(:cell:)2
(:cell:)2
(:row align=center style='background-color: lightyellow;':)
(:head:)P2
(:cell:)0
(:cell:)0
(:cell:)1
(:row align=center:)
(:head:)P3
(:cell:)1
(:cell:)0
(:cell:)3
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)4
(:cell:)0
(:tableend:)
(:tableend:)

>><<


----

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----



----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

Ψάχνουμε να βρούμε μία γραμμή της οποίας οι επιπλέον απαιτήσεις σε πόρους είναι μικρότερες ή ίσες από το Availabe. Αν φτιάξουμε τον πίνακα Need από τη σχέση @@Need[i,j] = Max[i,j] – Allocation [i,j]@@, έχουμε.

(:table:)
(:caption:)Need

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)2
(:cell:)2
(:cell:)2
(:row align=center style='background-color: lightyellow;':)
(:head:)P2
(:cell:)0
(:cell:)0
(:cell:)1
(:row align=center:)
(:head:)P3
(:cell:)1
(:cell:)0
(:cell:)3
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)4
(:cell:)0
(:tableend:)

>><<


----

(:table cellpadding=2px align=center:)
(:cell:)

----
(:row align=center:)
(:head:)R1

(:row align=center :)

(:cell:)
(:table:)
(:caption:)Available

(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center :)
(:cell:)0
(:cell:)1
(:cell:)1
(:tableend:)
(:cell:)
(:table:)
(:caption:)Max

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)3
(:cell:)2
(:cell:)2
(:row align=center:)
(:head:)P2
(:cell:)6
(:cell:)1
(:cell:)3
(:row align=center:)
(:head:)P3
(:cell:)3
(:cell:)1
(:cell:)4
(:row align=center:)
(:head:)P4
(:cell:)4
(:cell:)2
(:cell:)2
(:tableend:)
(:cell:)
(:table:)
(:caption:)Allocated

(:head:)
(:head:)R1
(:head:)R2
(:head:)R3
(:row align=center:)
(:head:)P1
(:cell:)1
(:cell:)0
(:cell:)0
(:row align=center:)
(:head:)P2
(:cell:)6
(:cell:)1
(:cell:)2
(:row align=center:)
(:head:)P3
(:cell:)2
(:cell:)1
(:cell:)1
(:row align=center:)
(:head:)P4
(:cell:)0
(:cell:)0
(:cell:)2
(:tableend:)
(:tableend:)

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----



----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

-----------------------------------
(:table:)
-----------------------------------
(:caption:)Total
-----------------------------------
(headnr:)R1
(:head:)R2
(:head:)R3
-----------------------------------
(:cell:)9
(:cell:)3
(:cell:)6
-----------------------------------
(:tableend:)
-----------------------------------


||! Available ||||||

||! Allocated ||||||||

||

||

||

||

(:table:)

(:cell:)

(:cell:)
||! Max ||||||||
|| || R1 || R2 || R3 ||
||! P1 || 3 || 2 || 2 ||
||! P2 || 6 || 1 || 3 ||
||! P3 || 3 || 1 || 4 ||
||! P1 || 4 || 2 || 2 ||
(:cell:)
||! Max ||||||||
|| || R1 || R2 || R3 ||
||! P1 || 1 || 0 || 0 ||
||! P2 || 6 || 1 || 2 ||
||! P3 || 2 || 1 || 1 ||
||! P1 || 0 || 0 || 2 ||
(:tableend:)

||! Total ||||||
|| R1 || R2 || R3 ||
|| 9 || 3 || 6 ||

||! Available ||||||
|| R1 || R2 || R3 ||
|| 0 || 1 || 1 ||

! Δομές Δεδομένων για τον Αλγόριθμο του Τραπεζίτη

* @@'''n'''@@ = το πλήθος των διεργασιών,
* @@'''m'''@@ = το πλήθος τύπων πόρων
* @@'''Available'''@@: Διάνυσμα μήκους @@m@@. Αν @@Available[j] = k@@, υπάρχουν @@k@@ στιγμιότυπα του τύπου πόρου @@R'_j_'@@ διαθέσιμα.
* @@'''Max'''@@: @@n x m@@ πίνακας. Αν @@Max[i,j] = k@@, τότε η διεργασία @@P'_i_'@@ μπορεί να απαιτήσει κατά μέγιστο @@k@@ στιγμιότυπα του τύπου πόρου @@R'_j_'@@.
* @@'''Allocation'''@@: @@n x m@@ πίνακας. Αν @@Allocation[i,j] = k@@ τότε στη διεργασία @@P'_i_'@@ εκχωρούνται @@k@@ στιγμιότυπα του πόρου @@R'_j_'@@.
* @@'''Need'''@@: @@n x m@@ πίνακας. Αν @@Need[i,j] = k@@, τότε η διεργασία @@P'_i_'@@ μπορεί να χρειαστεί @@k@@ επιπλέον στιγμιότυπα του πόρου @@R'_j_'@@ για να ολοκληρωθεί.

%center%@@Need[i,j] = Max[i,j] – Allocation [i,j]@@

Υπάρχουν 3 τύποι πόρων με πλήθος: R1 = 9, R2 = 3, R3 = 6. Είναι η παρακάτω κατάσταση ασφαλής;

Ένα σύστημα διαθέτει 6 όμοια tape drives και n σε πλήθος διεργασίες που ανταγωνίζονται για τη χρήση τους. Κάθε διεργασία μπορεί να απαιτήσει 2 tape drives. Για ποια τιμή του n το σύστημα είναι απαλλαγμένο από αδιέξοδα;

Υποθέστε ένα σύστημα με P διεργασίες και R όμοιους επαναχρησιμοποιήσιμους πόρους. Αν κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 2 μονάδες πόρων, να αποδείξετε ότι δεν μπορεί να υπάρξει αδιέξοδο μόνον όταν ισχύει η συνθήκη P<=R-1.

Σε ένα σύστημα υπάρχουν N σε πλήθος ενεργές διεργασίες που διαμοιράζονται Μ μονάδες ενός επαναχρησιμοποιήσιμου πόρου R. Κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 3 μονάδες του πόρου R. Να βρείτε ποια σχέση πρέπει να έχουν οι παράμετροι N και Μ ώστε να μην υπάρχει κίνδυνος αδιεξόδου.

Consider a computer system that runs 5000 jobs per month with no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (such as the banker’s algorithm) could be installed in the system with an increase in the average execution time per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.

#%alpha% What are the arguments for installing the deadlock-avoidance algorithm?
# What are the arguments against installing the deadlock-avoidance algorithm?

#%alpha% In order to effectively determine whether or not a deadlock has occurred in this particular environment it is necessary to install either a deadlock prevention or avoidance scheme. By installing the deadlock avoidance algorithm, the variance in average waiting time would be reduced.

# If there is little priority placed on minimizing waiting time variance, then not installing this scheme would mean a reduction in constant cost.

Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

If the printer starts to print a file before the entire file has been received (this is often allowed to speed response), the disk may fill with other requests that can’t be printed until the first file is done, but which use up disk space needed to receive the file currently being printed. If the spooler does not start to print a file until the entire file has been spooled it can reject a request that is too big. Starting to print a file is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire file can be received, a deadlock of the entire system can be avoided. The user with the file that won’t fit is still deadlocked of course, and must go to another facility that permits printing bigger files.

In the preceding question which resources are preemptable and which are nonpreemptable?

The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete file that is growing too large and have the user send it later, assuming the protocol allows that

List three examples of deadlocks that are not related to a computer-system environment.

# Two cars crossing a single lane bridge from opposite directions.
# A person going down a ladder while another person is climbing up the ladder.
# Two trains traveling toward each other on the same track.

Is it possible to have a deadlock involving only one single process? Explain your answer.

No. This follows directly from the hold-and-wait condition.

People have said that proper spooling would eliminate deadlocks. Certainly, it eliminates from contention card readers, plotters, printers, and so on. It is even possible to spool tapes (called staging them), which would leave the resources of CPU time, memory, and disk space. Is it possible to have a deadlock involving these resources? If it is, how could
such a deadlock occur? If it is not, why not? What deadlock scheme would seem best to eliminate these deadlocks (if any are possible), or what condition is violated (if they are not possible)?

It is possible to still have a deadlock. Process P1 holds memory pages that are required by process P2 , while P2 is holding the CPU that is required by P1.The best way to eliminate these types of deadlock is to use preemption.

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

Consider a computer system that runs 5000 jobs per month with no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (such as the banker’s algorithm) could be installed in the system with an increase in the average execution time per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.

#%alpha% What are the arguments for installing the deadlock-avoidance algorithm?
# What are the arguments against installing the deadlock-avoidance algorithm?

#%alpha% In order to effectively determine whether or not a deadlock has occurred in this particular environment it is necessary to install either a deadlock prevention or avoidance scheme. By installing the deadlock avoidance algorithm, the variance in average waiting time would be reduced.

# If there is little priority placed on minimizing waiting time variance, then not installing this scheme would mean a reduction in constant cost.

Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

If the printer starts to print a file before the entire file has been received (this is often allowed to speed response), the disk may fill with other requests that can’t be printed until the first file is done, but which use up disk space needed to receive the file currently being printed. If the spooler does not start to print a file until the entire file has been spooled it can reject a request that is too big. Starting to print a file is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire file can be received, a deadlock of the entire system can be avoided. The user with the file that won’t fit is still deadlocked of course, and must go to another facility that permits printing bigger files.

In the preceding question which resources are preemptable and which are nonpreemptable?

The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete file that is growing too large and have the user send it later, assuming the protocol allows that

Ένα σύστημα διαθέτει 6 όμοια tape drives και n σε πλήθος διεργασίες που ανταγωνίζονται για τη χρήση τους. Κάθε διεργασία μπορεί να απαιτήσει 2 tape drives. Για ποια τιμή του n το σύστημα είναι απαλλαγμένο από αδιέξοδα;

Υποθέστε ένα σύστημα με P διεργασίες και R όμοιους επαναχρησιμοποιήσιμους πόρους. Αν κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 2 μονάδες πόρων, να αποδείξετε ότι δεν μπορεί να υπάρξει αδιέξοδο μόνον όταν ισχύει η συνθήκη P<=R-1.

Σε ένα σύστημα υπάρχουν N σε πλήθος ενεργές διεργασίες που διαμοιράζονται Μ μονάδες ενός επαναχρησιμοποιήσιμου πόρου R. Κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 3 μονάδες του πόρου R. Να βρείτε ποια σχέση πρέπει να έχουν οι παράμετροι N και Μ ώστε να μην υπάρχει κίνδυνος αδιεξόδου.

! Γράφοι Εκχώρησης Πόρων

||width=60%
||Διεργασία || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess.jpg ||
||Τύπος Πόρου με 4 Στιγμιότυπα || http://users.sch.gr/fergadis/images/OS/Deadlock/resource.jpg ||
||Η διεργασία P'_i_' ζητάει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-request.jpg ||
||Η διεργασία P'_i_' δεσμεύει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-get.jpg ||
||Η διεργασία P'_i_' απελευθερώνει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-release.jpg ||

Να σχεδιάσετε ένα γράφο εκχώρησης πόρων για τα παρακάτω:
*Η διεργασία P1 απαιτεί τον πόρο R1
*Η διεργασία P2 απαιτεί τον πόρο R3
*Ο πόρος R1 είναι δεσμευμένος από τη διεργασία P2
*Ο πόρος R2 είναι δεσμευμένος από τη διεργασία P1
*Ο πόρος R3 είναι δεσμευμένος από τη διεργασία P3

Υπάρχει αδιέξοδο; Θεωρείστε ότι κάθε πόρος έχει ένα στιγμιότυπο.

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise1.png

Όπως φαίνεται από το γράφο δεν υπάρχει κύκλος, άρα δεν υπάρχει αδιέξοδο.

Ο πόρος R1 θα ελευθερωθεί κάποια στιγμή από την P2 και η Ρ1 θα μπορέσει να ολοκληρώσει. Επίσης, ο πόρος R3 θα ελευθερωθεί όταν ολοκληρώσει η Ρ3 και θα μπορέσει να ολοκληρώσει και η Ρ2.

Ένα σύστημα αποτελείται από 4 διεργασίες, (Ρ1, Ρ2, Ρ3, Ρ4), και 3 τύπους από σειριακά επαναχρησιμοποιούμενους πόρους, (R1, R2, R3). Ο αριθμός των μονάδων των πόρων είναι E=<3,2,2>.
*Η διεργασία P1 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P2 κρατά 2 μονάδες του R2 και απαιτεί 1 μονάδα καθενός από τους R1 και R3.
*Η διεργασία P3 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P4 κρατά 2 μονάδες του R3 και απαιτεί 1 μονάδα του R1

Φτιάξτε το γράφο. Υπάρχει αδιέξοδο;

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2.png

Όπως φαίνεται παρακάτω υπάρχουν τρεις κύκλοι.

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2a.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2b.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2c.png

Όλοι οι κύκλοι περνούν υποχρεωτικά από τον πόρο R1 ο οποίος έχει ένα στιγμιότυπο ελεύθερο. Το αν θα υπάρξει αδιέξοδο εξαρτάται σε ποια διεργασία θα δοθεί αυτός ο πόρος. Αν δοθεί στην Ρ2, τότε έχουμε αδιέξοδο διότι τότε όλες οι διεργασίες θα αιτούνται ένα ακόμη στιγμιότυπο άλλου πόρου το οποίο δεν είναι ελεύθερο. Αν δοθεί την Ρ4, τότε αυτή έχει όλους τους πόρους που χρειάζεται και μπορεί να ολοκληρώσει. Έτσι, αφήνει ελεύθερα τα δύο στιγμιότυπα που πόρου R3 και το ένα του R1. Αυτό δίνει τη δυνατότητα στην Ρ2 να δεσμεύσει τους πόρους που χρειάζεται και να ολοκληρώσει. Στη συνέχεια ολοκληρώνουν και οι Ρ1 και Ρ3 που έχουν χρειάζονταν τα στιγμιότυπα του πόρου R2.

----

Όλοι οι κύκλοι περνούν υποχρεωτικά από τον πόρο R1 ο οποίος έχει ένα στιγμιότυπο ελεύθερο. Το αν θα υπάρξει αδιέξοδο εξαρτάται σε ποια διεργασία θα δοθεί αυτός ο πόρος. Αν δοθεί στην Ρ2, τότε έχουμε αδιέξοδο διότι τότε όλες οι διεργασίες θα αιτούνται ένα ακόμη στιγμιότυπο άλλου πόρου το οποίο δεν είναι ελεύθερο. Αν δοθεί την Ρ4, τότε αυτή έχει όλους τους πόρους που χρειάζεται και μπορεί να ολοκληρώσει. Έτσι, αφήνει ελεύθερα τα δύο στιγμιότυπα που πόρου R3 και το ένα του R1. Αυτό δίνει τη δυνατότητα στην Ρ2 να δεσμεύσει τους πόρους που χρειάζεται και να ολοκληρώσει. Στη συνέχεια ολοκληρώνουν και οι Ρ1 και Ρ3 που έχουν χρειάζονταν τα στιγμιότυπα του πόρου R2.

*Η διεργασία P1 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P2 κρατά 2 μονάδες του R2 και απαιτεί 1 μονάδα καθενός από τους R1 και R3.
*Η διεργασία P3 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία P4 κρατά 2 μονάδες του R3 και απαιτεί 1 μονάδα του R1

Φτιάξτε το γράφο. Υπάρχει αδιέξοδο;

Όπως φαίνεται παρακάτω υπάρχουν τρεις κύκλοι.

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2a.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2b.png

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2c.png

Ωστόσο όλοι οι κύκλοι περνούν υποχρεωτικά από τον πόρο R1 ο οποίος έχει ένα στιγμιότυπο ελεύθερο. Συνεπώς δεν υπάρχει αδιέξοδο.

*Η διεργασία p1 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία p2 κρατά 2 μονάδες του R2 και απαιτεί 1 μονάδα καθενός από τους R1 και R3.
*Η διεργασία p3 κρατά 1 μονάδα του R1 και απαιτεί 1 μονάδα του R2
*Η διεργασία p4 κρατά 2 μονάδες του R3 και απαιτεί 1 μονάδα του R1

Ένα σύστημα διαθέτει 6 όμοια tape drives και n σε πλήθος διεργασίες που ανταγωνίζονται για τη χρήση τους. Κάθε διεργασία μπορεί να απαιτήσει 2 tape drives. Για ποια τιμή του n το σύστημα είναι απαλλαγμένο από αδιέξοδα;

Υποθέστε ένα σύστημα με P διεργασίες και R όμοιους επαναχρησιμοποιήσιμους πόρους. Αν κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 2 μονάδες πόρων, να αποδείξετε ότι δεν μπορεί να υπάρξει αδιέξοδο μόνον όταν ισχύει η συνθήκη P<=R-1.

Σε ένα σύστημα υπάρχουν N σε πλήθος ενεργές διεργασίες που διαμοιράζονται Μ μονάδες ενός επαναχρησιμοποιήσιμου πόρου R. Κάθε διεργασία μπορεί να απαιτήσει κατά μέγιστο 3 μονάδες του πόρου R. Να βρείτε ποια σχέση πρέπει να έχουν οι παράμετροι N και Μ ώστε να μην υπάρχει κίνδυνος αδιεξόδου.

List three examples of deadlocks that are not related to a computer-system environment.

# Two cars crossing a single lane bridge from opposite directions.
# A person going down a ladder while another person is climbing up the ladder.
# Two trains traveling toward each other on the same track.

Is it possible to have a deadlock involving only one single process? Explain your answer.

No. This follows directly from the hold-and-wait condition.

----

!!! Ερώτηση

People have said that proper spooling would eliminate deadlocks. Certainly, it eliminates from contention card readers, plotters, printers, and so on. It is even possible to spool tapes (called staging them), which would leave the resources of CPU time, memory, and disk space. Is it possible to have a deadlock involving these resources? If it is, how could
such a deadlock occur? If it is not, why not? What deadlock scheme would seem best to eliminate these deadlocks (if any are possible), or what condition is violated (if they are not possible)?

>>answer<<

!!! Απάντηση

It is possible to still have a deadlock. Process P1 holds memory pages that are required by process P2 , while P2 is holding the CPU that is required by P1.The best way to eliminate these types of deadlock is to use preemption.

>><<

----

!!! Ερώτηση

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

>>answer<<

!!! Απάντηση

Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

>><<

----

!!! Ερώτηση

Consider a computer system that runs 5000 jobs per month with no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (such as the banker’s algorithm) could be installed in the system with an increase in the average execution time per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.

#%alpha% What are the arguments for installing the deadlock-avoidance algorithm?
# What are the arguments against installing the deadlock-avoidance algorithm?

>>answer<<

!!! Απάντηση

#%alpha% In order to effectively determine whether or not a deadlock has occurred in this particular environment it is necessary to install either a deadlock prevention or avoidance scheme. By installing the deadlock avoidance algorithm, the variance in average waiting time would be reduced.

# If there is little priority placed on minimizing waiting time variance, then not installing this scheme would mean a reduction in constant cost.

>><<

----

!!! Ερώτηση

Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

>>answer<<

!!! Απάντηση

If the printer starts to print a file before the entire file has been received (this is often allowed to speed response), the disk may fill with other requests that can’t be printed until the first file is done, but which use up disk space needed to receive the file currently being printed. If the spooler does not start to print a file until the entire file has been spooled it can reject a request that is too big. Starting to print a file is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire file can be received, a deadlock of the entire system can be avoided. The user with the file that won’t fit is still deadlocked of course, and must go to another facility that permits printing bigger files.

>><<

----

!!! Ερώτηση

In the preceding question which resources are preemptable and which are nonpreemptable?

>>answer<<

!!! Απάντηση

The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete file that is growing too large and have the user send it later, assuming the protocol allows that

>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

Ο πόρος R1 θα ελευθερωθεί κάποια στιγμή από την P2 και η Ρ1 θα μπορέσει να ολοκληρώσει. Επίσης, ο πόρος R3 θα ελευθερωθεί όταν ολοκληρώσει η Ρ3 και θα μπορέσει να ολοκληρώσει και η Ρ2.

Ένα σύστημα αποτελείται από 4 διεργασίες, (Ρ1, Ρ2, Ρ3, Ρ4), και 3 τύπους από σειριακά επαναχρησιμοποιούμενους πόρους, (R1, R2, R3). Ο αριθμός των μονάδων των πόρων είναι E=<3,2,2>.

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise2.png

Όπως φαίνεται από το γράφο υπάρχουν δύο κύκλοι.

List three examples of deadlocks that are not related to a computer-system environment.

# Two cars crossing a single lane bridge from opposite directions.
# A person going down a ladder while another person is climbing up the ladder.
# Two trains traveling toward each other on the same track.

Is it possible to have a deadlock involving only one single process? Explain your answer.

No. This follows directly from the hold-and-wait condition.

People have said that proper spooling would eliminate deadlocks. Certainly, it eliminates from contention card readers, plotters, printers, and so on. It is even possible to spool tapes (called staging them), which would leave the resources of CPU time, memory, and disk space. Is it possible to have a deadlock involving these resources? If it is, how could
such a deadlock occur? If it is not, why not? What deadlock scheme would seem best to eliminate these deadlocks (if any are possible), or what condition is violated (if they are not possible)?

It is possible to still have a deadlock. Process P1 holds memory pages that are required by process P2 , while P2 is holding the CPU that is required by P1.The best way to eliminate these types of deadlock is to use preemption.

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

Consider a computer system that runs 5000 jobs per month with no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (such as the banker’s algorithm) could be installed in the system with an increase in the average execution time per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.

#%alpha% What are the arguments for installing the deadlock-avoidance algorithm?
# What are the arguments against installing the deadlock-avoidance algorithm?

#%alpha% In order to effectively determine whether or not a deadlock has occurred in this particular environment it is necessary to install either a deadlock prevention or avoidance scheme. By installing the deadlock avoidance algorithm, the variance in average waiting time would be reduced.

# If there is little priority placed on minimizing waiting time variance, then not installing this scheme would mean a reduction in constant cost.

Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

If the printer starts to print a file before the entire file has been received (this is often allowed to speed response), the disk may fill with other requests that can’t be printed until the first file is done, but which use up disk space needed to receive the file currently being printed. If the spooler does not start to print a file until the entire file has been spooled it can reject a request that is too big. Starting to print a file is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire file can be received, a deadlock of the entire system can be avoided. The user with the file that won’t fit is still deadlocked of course, and must go to another facility that permits printing bigger files.

In the preceding question which resources are preemptable and which are nonpreemptable?

The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete file that is growing too large and have the user send it later, assuming the protocol allows that

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

! Γράφοι Εκχώρησης Πόρων

||width=60%
||Διεργασία || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess.jpg ||
||Τύπος Πόρου με 4 Στιγμιότυπα || http://users.sch.gr/fergadis/images/OS/Deadlock/resource.jpg ||
||Η διεργασία P'_i_' ζητάει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-request.jpg ||
||Η διεργασία P'_i_' δεσμεύει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-get.jpg ||
||Η διεργασία P'_i_' απελευθερώνει ένα στιγμιότυπο του πόρου R'_j_' || http://users.sch.gr/fergadis/images/OS/Deadlock/proccess-resource-release.jpg ||

Να σχεδιάσετε ένα γράφο εκχώρησης πόρων για τα παρακάτω:
*Η διεργασία P1 απαιτεί τον πόρο R1
*Η διεργασία P2 απαιτεί τον πόρο R3
*Ο πόρος R1 είναι δεσμευμένος από τη διεργασία P2
*Ο πόρος R2 είναι δεσμευμένος από τη διεργασία P1
*Ο πόρος R3 είναι δεσμευμένος από τη διεργασία P3

Υπάρχει αδιέξοδο; Θεωρείστε ότι κάθε πόρος έχει ένα στιγμιότυπο.

Ο γράφος είναι ως εξής:

http://users.sch.gr/fergadis/images/OS/Deadlock/exercise1.png

Όπως φαίνεται από το γράφο δεν υπάρχει κύκλος, άρα δεν υπάρχει αδιέξοδο.

Students working at individual PCs in a computer laboratory send their files to be printed by a server which spools the files on its hard disk. Under what conditions may a deadlock occur if the disk space for the print spool is limited? How may the deadlock be avoided?

If the printer starts to print a file before the entire file has been received (this is often allowed to speed response), the disk may fill with other requests that can’t be printed until the first file is done, but which use up disk space needed to receive the file currently being printed. If the spooler does not start to print a file until the entire file has been spooled it can reject a request that is too big. Starting to print a file is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire file can be received, a deadlock of the entire system can be avoided. The user with the file that won’t fit is still deadlocked of course, and must go to another facility that permits printing bigger files.

In the preceding question which resources are preemptable and which are nonpreemptable?

The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete file that is growing too large and have the user send it later, assuming the protocol allows that

Consider a computer system that runs 5000 jobs per month with no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (such as the banker’s algorithm) could be installed in the system with an increase in the average execution time per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.

#%alpha% What are the arguments for installing the deadlock-avoidance algorithm?
# What are the arguments against installing the deadlock-avoidance algorithm?

#%alpha% In order to effectively determine whether or not a deadlock has occurred in this particular environment it is necessary to install either a deadlock prevention or avoidance scheme. By installing the deadlock avoidance algorithm, the variance in average waiting time would be reduced.

# If there is little priority placed on minimizing waiting time variance, then not installing this scheme would mean a reduction in constant cost.

We can obtain the banker’s algorithm for a single resource type from the general banker’s algorithm simply by reducing the dimensionality of the various arrays by 1. Show through an example that the multiple-resource-type banker’s scheme cannot be implemented by individual application of the single-resource-type scheme to each resource type.

Consider a system with resource types A, B, C and 2 processes P0, P1 and the following snapshot of the system.

[@ A B C
Available: 1 1 1@]

||border=1px
|| ||! Allocation ||! Max ||! Need ||
|| || @@A B C@@ || @@A B C@@ || @@A B C@@ ||
||! P0 || @@1 2 2@@ || @@2 3 4@@ || @@1 1 2@@ ||
||! P1 || @@1 1 2@@ || @@2 2 3@@ || @@1 2 1@@ ||

The system is not in a safe state. However, if we apply the single resource type banker’s algorithm to each resource type individually we get the following:
* the sequence < P0,P1 > satisfies the safety requirement for resource A
* the sequence < P0,P1 > satisfies the safety requirement for resource B
* the sequence < P1,P0 > satisfies the safety requirement for resource C
and thus the system should be in a safe state.

%define=answer block bgcolor=#c4d4e7 border='1px dashed #31659c' padding-left='10px' padding-right='10px'%

! Αδιέξοδα

Projects can involve simulation: create a list of jobs consisting of requests and releases of resources (single type or multiple types). Ask the students to allocate the resources to prevent deadlock. This basically involves programming the Banker’s Algorithm.

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

!!! Ερώτηση

List three examples of deadlocks that are not related to a computer-system environment.

>>answer<<

!!! Απάντηση

# Two cars crossing a single lane bridge from opposite directions.
# A person going down a ladder while another person is climbing up the ladder.
# Two trains traveling toward each other on the same track.

>><<

----

!!! Ερώτηση

Is it possible to have a deadlock involving only one single process? Explain your answer.

>>answer<<

!!! Απάντηση

No. This follows directly from the hold-and-wait condition.

>><<

----

!!! Ερώτηση

People have said that proper spooling would eliminate deadlocks. Certainly, it eliminates from contention card readers, plotters, printers, and so on. It is even possible to spool tapes (called staging them), which would leave the resources of CPU time, memory, and disk space. Is it possible to have a deadlock involving these resources? If it is, how could
such a deadlock occur? If it is not, why not? What deadlock scheme would seem best to eliminate these deadlocks (if any are possible), or what condition is violated (if they are not possible)?

>>answer<<

!!! Απάντηση

It is possible to still have a deadlock. Process P1 holds memory pages that are required by process P2 , while P2 is holding the CPU that is required by P1.The best way to eliminate these types of deadlock is to use preemption.

>><<

----

!!! Ερώτηση

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

>>answer<<

!!! Απάντηση

Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

!!! Ερώτηση



>>answer<<

!!! Απάντηση



>><<

----

Deadlock is a problem that can only arise in a system with multiple active asynchronous processes. It is important that the students learn the three basic approaches to deadlock: prevention, avoidance, and detection (although the terms prevention and avoidance are easy to confuse).

It can be useful to pose a deadlock problem in human terms and ask why human systems never deadlock. Can the students transfer this understanding of human systems to computer systems?

Projects can involve simulation: create a list of jobs consisting of requests and releases of resources (single type or multiple types). Ask the students to allocate the resources to prevent deadlock. This basically involves programming the Banker’s Algorithm.