CS 143A - EXERCISES + SOLUTIONS - University of California, Irvine CS 143A
8 views 0 purchase
Course
CS 143A
Institution
CS 143A
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 sibl...
cs 143a excercises exercise 231 creation hierarchy without linked lists processes 0 4 are related as follows 1
2
and 4 is a child of 2 pcbs are implemented as an
Written for
CS 143A
All documents for this subject (1)
Seller
Follow
ExamsConnoisseur
Reviews received
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ExamsConnoisseur. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.49. You're not tied to anything after your purchase.
