|
Instructors : Dr. Tong Lai Yu
Homework 1
Due April 24, 2008 ( Thu )
1) CSP problems.
a)
Use CSP commands to write a statement that does the following:
If x ≥ y, assign x to m; i f y ≥ x assign y to m; if both x ≥ y and
y ≥ x, either assignment can be executed.
( Keep your statement as simple as possible. )
b) Use CSP commands to write a statement that does the following:
On each iteration, accept either a V() signal from process X and increment val,
or a P() signal from process Y, and decrement val. But the second alternative cannot be
selected unless val is positive.
The repetitive command will terminate when both X and Y are terminated,
or when X is terminated and val ≤ 0.
2) ( Textbook 3.2 )
Construct a general resource graph for the following
scenario and determine if the graph is completely
reducible: R1, R2, and R3 are reusable resources with
a total of two, two, and three units. Process P1 is allocated
one unit each of R2 and R3 and is requesting one unit of R1. Process
P2 is allocated one unit of R1 and is requesting two units of R3.
Process P3 is allocated one unit each of R1 and R2 and is requesting
one unit of R3.
3) ( Textbook 3.4 )
Show that the ordered request policy of Havender prevents deadlock.
4) Consider a computer system that has 4 identical units of resource R.
There are 3 processes each with a maximum claim of 2 units of resource R.
Processes can request these resources in any way, i.e. two in one shot or
one by one. The system alwasy satisfies a request if the enough resources
are available. If the processes don't request any other kind of resource,
is deadlock possible in this system? Why? ( Show your steps clearly. )
5) ( Textbook 3.7 ) Assume a system has P processes and R identical units
of a reusable resource. If each process can claim at most N units of the resource,
show that the system will be deadlock free iff R ≥ P(N - 1) + 1.
|