University of California, Irvine

• 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 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 over