Adarsh B Shankar COMPSCI 143A SS2
UCI ID: 11972805
CS 143A : EXCERCISES
Exercise 2.3.1: Creation hierarchy without linked lists.
Processes 0-4 are related as follows: 1, 2, 3 are children of 0, and 4 is a child
of 2. PCBs are implemented as an array indexed by the process number.
Each PCB has the links: parent (p), first child (c), younger sibling (ys), and
older sibling (os).
(a)
Complete the PCB array to show the values of the 4 links (p, c, ys, os) for all
processes, to reflect the parent-child hierarchy.
Solution
The parent of process 0 is unknown (?).
A dash means no index. Ex: Process 1 has no child (c) and no older siblings
(os).
,Adarsh B Shankar COMPSCI 143A SS2
UCI ID: 11972805
(b)
Modify the array to reflect the creation of a new child, 5, of process 2.
Solution
The new child is created at index 5.
Note that the parent process (2) is not modified in any way.
Exercise 2.3.2: RL without linked lists.
The RL can be implemented without dynamically managed linked lists by
creating a new field, next, in each PCB, which points to the next PCB on the
same list. Each entry of the RL then points to the first PCB on the list.
(a)
Assume that RL contains 3 processes at level 5 and 1 process at level 0.
Draw a diagram showing the RL and the modified PCBs.
, Adarsh B Shankar COMPSCI 143A SS2
UCI ID: 11972805
Exercise 2.3.3: A modified implementation of PCBs.
Implementing the PCBs as an array is more efficient than using dynamic
memory allocation. The drawback is that the array size must be kept relatively
small. To overcome this drawback, the PCBs are implemented as fixed size
array, PCB[n], where n is large enough most of the time. In the case where
more processes need to be created, the array size n is temporarily extended
to accommodate the spike. The extension is removed when the number of
elements falls again below n. To compare the effectiveness of this scheme
with a dynamic linked list implementation, assume the following values:
s is the time to perform one insert or remove operation in a linked list
r is the time to perform one insert or remove operation in the array
o is the overhead time to temporarily extend the array
p is the probability that any given insert operation will overrun the
normal array size n
(a)
Derive a formula for computing the value of p, below which the proposed
scheme will outperform the linked list implementation.
Solution
With the linked list implementation, each insert or remove takes s
ms.
With the array implementation, a remove takes r ms and each
insert takes r + o*p ms since the overhead of extending the array
occurs with probability p.
Since half of all operations are inserts and half are removes, the
time for one operation is (r + r + o*p)/2.
The break-even point is when the time for the implementations is
equal: s = (r + r + o*p)/2.
Solving for p yields the probability p = (2s - 2r)/o
(b)
Compute the value of p when s = 10r and o = 100r.
Solution
p = (2*10r - 2r)100r = 18/100 = 0.18
UCI ID: 11972805
CS 143A : EXCERCISES
Exercise 2.3.1: Creation hierarchy without linked lists.
Processes 0-4 are related as follows: 1, 2, 3 are children of 0, and 4 is a child
of 2. PCBs are implemented as an array indexed by the process number.
Each PCB has the links: parent (p), first child (c), younger sibling (ys), and
older sibling (os).
(a)
Complete the PCB array to show the values of the 4 links (p, c, ys, os) for all
processes, to reflect the parent-child hierarchy.
Solution
The parent of process 0 is unknown (?).
A dash means no index. Ex: Process 1 has no child (c) and no older siblings
(os).
,Adarsh B Shankar COMPSCI 143A SS2
UCI ID: 11972805
(b)
Modify the array to reflect the creation of a new child, 5, of process 2.
Solution
The new child is created at index 5.
Note that the parent process (2) is not modified in any way.
Exercise 2.3.2: RL without linked lists.
The RL can be implemented without dynamically managed linked lists by
creating a new field, next, in each PCB, which points to the next PCB on the
same list. Each entry of the RL then points to the first PCB on the list.
(a)
Assume that RL contains 3 processes at level 5 and 1 process at level 0.
Draw a diagram showing the RL and the modified PCBs.
, Adarsh B Shankar COMPSCI 143A SS2
UCI ID: 11972805
Exercise 2.3.3: A modified implementation of PCBs.
Implementing the PCBs as an array is more efficient than using dynamic
memory allocation. The drawback is that the array size must be kept relatively
small. To overcome this drawback, the PCBs are implemented as fixed size
array, PCB[n], where n is large enough most of the time. In the case where
more processes need to be created, the array size n is temporarily extended
to accommodate the spike. The extension is removed when the number of
elements falls again below n. To compare the effectiveness of this scheme
with a dynamic linked list implementation, assume the following values:
s is the time to perform one insert or remove operation in a linked list
r is the time to perform one insert or remove operation in the array
o is the overhead time to temporarily extend the array
p is the probability that any given insert operation will overrun the
normal array size n
(a)
Derive a formula for computing the value of p, below which the proposed
scheme will outperform the linked list implementation.
Solution
With the linked list implementation, each insert or remove takes s
ms.
With the array implementation, a remove takes r ms and each
insert takes r + o*p ms since the overhead of extending the array
occurs with probability p.
Since half of all operations are inserts and half are removes, the
time for one operation is (r + r + o*p)/2.
The break-even point is when the time for the implementations is
equal: s = (r + r + o*p)/2.
Solving for p yields the probability p = (2s - 2r)/o
(b)
Compute the value of p when s = 10r and o = 100r.
Solution
p = (2*10r - 2r)100r = 18/100 = 0.18
