先週デスペ受けてて更新を休んでいました。手応えとしては午後ⅠはOK、午後Ⅱは悪く見積もって64点くらいです。さて恐竜本7章練習問題です。問題はこちらです。
7.1 List three examples of deadlocks that are not related to a computersystem environment.
自身の回答：4本の道が交差している交差点で渋滞が起きており、他の車両が動かないとどの車線も動けない状態
解答：1車線の橋を反対方向から2つの車が通りかかっている状況
一人がはしごを降ろうとし、もう一人が登ろうとしている状況
同じ線路の上を2つの列車が向かい合って通ろうとしている状況
7.2
Suppose that a system is in an unsafe state. Show that it is possible for
the processes to complete their execution without entering a deadlock
state.
自身の回答：unsafe stateを忘れた
解答：P0,P1,P2がいる状況で、それぞれ最大10,4,9個のリソースを必要とし、現在5,2,3保持しているとする。このときsafe sequenceは存在しないのでunsafeだが、すべてのプロセスが同時にリソースを全部要求するのではなく、一時的に解放したりすることがありうる。その場合プロセスが終了することができ、デッドロックは起こらない。
7.3
Consider the following snapshot of a system:
Allocation Max Available
ABCD ABCD ABCD
P0 0012 0012 1520
P1 1000 1750
P2 1354 2356
P3 0632 0652
P4 0014 0656
Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need?
b. Is the system in a safe state?
c. If a request from process P1 arrives for (0,4,2,0), can the request be
granted immediately?
自身の回答：a
A B C D
0 0 0 0
0 7 5 0
1 0 0 2
0 0 2 0
0 6 4 2
b
Work=1 5 2 0
Finish=0 0 0 0 0
Work=1 11 5 2
Finish=0 0 0 1 0
Work=1 11 6 4
Finish=1 0 0 1 0
Work=2 11 6 4
Finish=1 1 0 1 0
Work=2 11 7 8
Finish=1 1 0 1 1
Work=3 14 12 12
Finish=1 1 1 1 1
safe stateである
c 可能
解答：a (0,0, 0, 0), (0, 7, 5, 0), (1, 0, 0, 2), (0, 0, 2, 0), and (0, 6, 4, 2).
b safe stateである。まずP0かP3を動かせる。P3が終わったらリソースを開放するが、それにより存在する他のプロセスが動作できる。
c リクエストにすぐ答えるとAvailableが(1,1,0,0)となる。P0,P2,P3,P1,P4の順序で実行すれば終了できる。
7.4
A possible method for preventing deadlocks is to have a single, higherorder resource that must be requested before any other resource. For
example, if multiple threads attempt to access the synchronization
objects A··· E, deadlock is possible. (Such synchronization objects may
include mutexes, semaphores, condition variables, and the like.) We can
prevent the deadlock by adding a sixth object F. Whenever a thread
wants to acquire the synchronization lock for any object A··· E, it must
first acquire the lock for object F. This solution is known as containment:
the locks for objects A ··· E are contained within the lock for object F.
Compare this scheme with the circular-wait scheme of Section 7.4.4.
自身の回答：circular-waitスキームではリソース獲得順序を保証することでデッドロックを防止しているが、containmentではあるリソースを取らないと他のすべてのリソースを取れない。containmentはデッドロックを防止できるがリソースを取れるプロセスが1つとなり、システムの効率が落ちる。
解答：それは大きすぎるスコープを生むのでこれはおそらく良い解法ではない。できる限りスコープが小さいロッキングポリシーを定義するほうが良い。
7.5
Prove that the safety algorithm presented in Section 7.5.3 requires an
order of m × n2 operations.
自身の回答：step2で選択するインデックスが毎回1個とは限らない。ループを重ねると複数個のインデックスがstep2のaとbの条件を満たすことが考えられる。また、どのインデックスを選択するかによって、正解のsafe sequenceにたどり着けないことも考えられる。そのため、step2の選択インデックス候補は最悪全部試し、正解のsafe sequenceを見つけ出さなければならない。インデックス候補数は1からnまでの値をとるので、最悪nパターンを全部試す必要がある。一方、全体のループは全プロセスがfinishになるまで行うので、最悪n回行われる。また、各ループでworkにallocationを加算するオペレーションが入っているのでmに比例した計算量となる。よって、ループ回数と各ループでの計算量から全体の計算量はm×n^2となる。
解答：インデックス探索がnプロセス分探索するので計算量O(n)、ループがn回、Available加算がO(m)、合計O(m×n^2)
7.6
Consider a computer system that runs 5,000 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 (like 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 5,000 jobs per
month could still be run, although turnaround time would increase by
about 20 percent on average.
a. What are the arguments for installing the deadlock-avoidance
algorithm?
b. What are the arguments against installing the deadlock-avoidance algorithm?
自身の回答：
a プロセスを再起動させるオペレータの人件費を削減することができる。
b 月に20ジョブを再起動している。同じジョブを2回回すので、デッドロックで起こる損失は$40となる。これを防止できればそれがそのまま利益となる。一方、防止するのにかかるコストとして、実装コスト、デッドロック検知のオーバーヘッドによって今後ジョブが増えた場合に対応できる余力が減る、ターンアラウンドタイムが伸び、緊急のジョブがすぐ終わらないなどがかさみ、デッドロックの損失を上回っている。
解答：デッドロック防止システムを入れるのに賛成する議論としては、デッドロックを決して起こらなくできるし、ターンアラウンド時間は伸びるが5000ジョブはなお動かせる。反対する議論としては、デッドロックは稀にしか起こらず、起きてもコストがほとんどかからない。
7.7 Can a system detect that some of its processes are starving? If you answer “yes,” explain how it can. If you answer “no,” explain how the system can deal with the starvation problem.
自身の回答：yes. プロセスaがリソース解放待ち状態に入ったとき、その時刻を記録する。それよりも後にリソースを獲得したプロセスのリソース解放待ち開始時刻をチェックし、プロセスaのリソース解放街開始時刻より後だった場合、starvationが起きている。
解答：最も長く待っているプロセスにリソースを与えるというのが一つの方法である。もう一つのあまり厳格ではない方法は、待ち時間が短いプロセスにリソースを与えることを許容し、その代わりあるプロセスが飢餓状態であると考えられるときにそのプロセスにまずリソースを与えるようにするというものである。
7.8
Consider the following resource-allocation policy. Requests for and
releases of resources are allowed at any time. If a request for resources cannot be satisfied because the resources are not available, then we check any processes that are blocked waiting for resources. If a blocked process has the desired resources, then these resources are taken away from it and are given to the requesting process. The vector of resources for which the blocked process is waiting is increased to include the resources that were taken away. For example, consider a system with three resource types and the vector Available initialized to (4,2,2). If process P0 asks for (2,2,1), it gets them. If P1 asks for (1,0,1), it gets them. Then, if P0 asks for (0,0,1), it is blocked (resource not available). If P2 now asks for (2,0,0), it gets the available one (1,0,0) and one that was allocated to P0 (since P0 is blocked). P0’s Allocation vector goes down to (1,2,1), and its Need vector goes up to (1,0,1).
a. Can deadlock occur? If you answer “yes,” give an example. If you answer “no,” specify which necessary condition cannot occur.
b. Can indefinite blocking occur? Explain your answer
自身の回答：
a yes preemptが可能になっているので、デッドロックの必要条件が満たされない。
b 自分が待っているとき他のプロセスが毎回リソースを引き剥がしてくる場合無限ブロックは起こりうる。
解答：a デッドロックはpreemptionが存在するとき起こり得ない。
b yes.プロセスCからなどの連続したリクエストによって連続的にリソースがpreemptされればプロセスは決してすべてのリソースを得ることはない。
7.9 Suppose that you have coded the deadlock-avoidance safety algorithm and now have been asked to implement the deadlock-detection algorithm. Can you do so by simply using the safety algorithm code and redefining Max[i] = Waiting[i] + Allocation[i], where Waiting[i] is a vector specifying the resources for which process i is waiting and Allocation[i] is as defined in Section 7.5? Explain your answer.
自身の回答：可能。
解答：yes.
7.10 Is it possible to have a deadlock involving only one single-threaded process? Explain your answer
自身の回答：デッドロックは起こりうる。自分で獲得したリソースをもう一度獲得しようとする場合。
解答：hold-and-waitの条件からno。
コメント