Answer the following, without exceeding 150 words per subquestion. a) What is the difference between user mode and kernel mode and why is it necessary to have these two modes of execution? b) What are the three most common events that lead to a process switch? Describe them briefly. c) How is a thread different from a process? List three main differences. d) What operations can be performed on a semaphore? Do these depend on whether the semaphore is general or binary?  e) What are the differences between deadlock, livelock and starvation?  f) What is the main benefit of dynamic partitioning? What is its main drawback and how is it addressed?  g) What is the purpose of introducing multi-level and inverted page tables? How does an inverted table differ from a standard one?  h) How can the use of priorities in scheduling lead to starvation? How can this be avoided?  i) What is Direct Memory Access (DMA) and why is it useful? j) Why does it take less, on average, to find a record in an indexed sequential file than in a sequential file?

Question 2 [4 + 3 = 7%]  A system has four processes and five allocatable resource types. Consider the following state:    R1 R2 R3 R4 R5 9 5 5 5 5 2 2 3 3 0 4 3 3 2 0 4 4 4 4 4 P1 P2 P3 P4      Claim Matrix   R1 R2 R3 R4 R5 2 0 2 1 2 0 1 1 1 0 4 1 0 2 0 1 1 0 0 1 P1 P2 P3 P4      Allocation Matrix   R1 R2 R3 R4 R5 15 6 9 10 5      Resource Vector   R1 R2 R3 R4 R5 8 3 6 6 2      Available Vector   a) Is this a safe state? Justify your answer by applying the Banker’s Algorithm. If your answer is yes, show a sequence of process executions and how the available vector changes after each execution. If your answer is no, is this state deadlocked, or is there a way to arrive at a safe state?

b) Repeat (a), for the following state:    R1 R2 R3 R4 R5 9 5 5 5 5 2 4 3 3 0 4 3 3 2 0 4 4 4 4 4 P1 P2 P3 P4      Claim Matrix   R1 R2 R3 R4 R5 2 0 2 1 2 0 1 1 1 0 4 1 0 2 0 1 1 0 0 1 P1 P2 P3 P4      Allocation Matrix   R1 R2 R3 R4 R5 9 5 5 6 6      Resource Vector   R1 R2 R3 R4 R5 2 2 2 2 3      Available Vector    Question 3 [2 x 3 = 6%]  To which physical address (in binary format) does the logical address 0011011010101010 correspond, under the following hypothetical memory management schemes? Justify your answers. a) A paging system with a page table containing 512 entries and in which the frame number happens to be two times smaller than the page number. b) A segmentation system with a maximum segment size of 2,048 bytes, using a segment table in which bases happen to be regularly placed at real addresses equal to 22 + 4,096 + segment number.     Question 4 [4 x 3 = 12%]  Suppose that a system has 32-bit physical addresses and 48-bit virtual addresses. Answer the following: a) If page size is 8KB, how many entries are in the page table (assume that it has only a single level)? Justify your answer. b) If accessing a page directly from main memory takes 100ns, while having to retrieve the page from the disk takes 2ms, what is the average access time when the page fault rate is 0.005%?  c) What is the maximum required page fault rate in order to ensure average memory access time does not increase more than 25% of the direct memory access time?

d) A Translation Lookaside Buffer (TLB) is added to the system. In case of a TLB hit, memory access is reduced to 30ns. The TLB hit rate is 95%. What is the average access time if we assume a page fault rate of 0.005%, as in (a)?     Question 5 [3 x 3 = 9%]  The table below gives a list of processes along with their burst times and priorities. We assume that the processes have arrived in the order P1, P2, P3, P4, P5, all at time 0.   Process Burst Time Priority P1 3 3 P2 3 1 P3 4 3 P4 2 4 P5 7 2  Assuming only one single-core CPU, answer the following: a) Show the schedule using a time scale diagram (as in Lecture/Tutorial 8) if we use the First Come First Served (FCFS) scheduling policy. What is the average turnaround and waiting time?  b) Repeat (a), this time using Round-Robin (RR) with a time quantum equal to 2.  c) Repeat (a), this time using Shortest Job First (SJF).      Question 6 [3 x 3 = 9%]  Consider the following sequence of disk track requests: 120, 50, 11, 22, 27, 76, 166, 52 and 140. Assume that the disk head is initially positioned over track 50 and is moving in the direction of increasing track number. a) How many tracks will have to be traversed (total seek length) and what is the average number of tracks to be traversed (average seek length) if we use the SSTF scheduling policy? b) Repeat (a), this time using the SCAN scheduling policy. c) Repeat (a), this time using the C-SCAN scheduling policy.

To assist in answering the questions, you may fill in the table that follows:  SSTF SCAN C-SCAN Next track accessed Number of tracks traversed Next track accessed Number of tracks traversed Next track accessed Number of tracks traversed                            Question 7 [3 x 3 = 9%]  Consider a file consisting of 2000 records of size 250B stored on a disk with a block size of 512B using fixed blocking. a) How many blocks are required to store the file and how much space is wasted due to internal fragmentation?  b) Repeat (a), for a block size of 8KB. c) Repeat (b), this time assuming that spanned blocking is used: a record can span two blocks.    Question 8 [8 + 10 = 18%]  In the Serengeti National Park in Tanzania, Africa, there is a deep canyon that can only be crossed by the baboons living in the park using a rope that has been fastened on both sides by the park administration. Several baboons can cross at the same time, provided they are all going in the same direction. If eastward-moving and westward-moving baboons ever get onto the rope at the same time, the baboons will get stuck in a deadlock because it is impossible for one baboon to climb over another one while suspended over the canyon. a) Using Java semaphores or Java synchronisation (or any other language you prefer), design an algorithm that prevents deadlock. Implement and test your algorithm by designing two threads, one representing an eastward-moving baboon and the other representing a westward-moving baboon. Once both are on the bridge, each will sleep for a random period of time to simulate traveling across the bridge. Initially, do not be concerned about starvation (the situation in which eastward-moving baboons hold up westward-moving baboons indefinitely, or vice-versa). b) Modify your algorithm in (a) so that it is starvation-free, implement and test it.