UNIVERSITY OF YORK 

COM00021 Systems & Devices

1 (20 marks)
(i) [5 marks] A computer system runs six programs in its main memory. Each program is idle waiting for I/O one-fourth of the time. What fraction of the CPU time is wasted?

Answer: A program idle waiting for I/O is 1/4. The probability all six programs are idle at the same time is (1/4)6=1/4096; this is the fraction (1/4096) when there is no program available for CPU execution, and the CPU stays idle. This CPU time is wasted.

Marking criteria: 2 marks for mentioning idle waiting for one process and 4 marks for calculating probability of idle time for all processes and full marks for the correct answer.

(ii) [8 marks] When an interrupt or a system call transfers control from a user program (process) to the operating system, a kernel stack (which is separate from the stack of the interrupted process) is used. Explain why a kernel stack is used, not the user stack.

Answer: When an interrupt or a system call transfers control from a user program (process) to the operating system, a kernel stack is used to save the process context data for the privilege instruction execution during the system call trap. This stack is used by the scheduler and dispatcher (kernel programs). The user stack can’t be used because, as it is in the user space, it might be corrupted either by the malicious user process or inadvertently by the user process. The kernel stack is modified by kernel code only, so it is safe and prevents accidental or intentional malicious changes.

Marking criteria: 4 marks for mentioning use of the kernel stack and 4 marks for unsuitability of the user stack.

(iii) How many times printf statement - i is <number> is printed on the screen and what are the values of printed i? Explain your answer by providing a tree structure of processes along with i values.

Answer: The main process has created two child processes. One of the child processes created its child process. Therefore, there are four processes (including the main process). Therefore, there are four printf statements. The main parent process (P0) has i = = 3 initially and then increments it by three, so finally, it prints 6. The first child process (P1) gets i = = 3 value when forked and increments it by three, so it finally prints 6; the second child process (P2) gets i == 6 when forked and finally prints 6. The child process (P3) of (P1) gets i == 6 when forked and finally prints 6.

The values of i are 6, 6, 6, 6.

2 (20 marks)

(i) [6 marks] You are given the problem of designing a CPU scheduling algorithm that prioritises processes that have used the least processor time in the recent past. How do you develop this algorithm to favour I/O-bound programs without permanently starving CPU-bound programs? Explain your algorithm clearly by providing all assumptions, e.g., data structures, tables, or variables used by the algorithm.

Answer: The algorithm maintains a table with all processes’ recent CPU burst times and assigns high to low priority to processes from the least CPU burst time to high burst time. Every process execution time is divided into CPU burst time and I/O burst time. So if a process has a short CPU burst time, it most likely has a longer I/O burst time (I/O bound processes). Thus, this algorithm inherently favours (priority) I/O bound processes. To prevent permanently starving CPU-bound programs, the algorithm should allow all processes (which are already ready in the scheduling queue) to execute in the priority order before assigning a high priority to a new incoming I/O bound process (which has a recent low CPU burst time). Another solution is to attach an ageing timer, which keeps decrementing (assuming a lower priority number corresponds to high priority) the priority number of the processes (which are waiting for a longer time in the scheduling queue).

Marking criteria: 2 marks for clearly mentioning relationship between process execution time and CPU and I/O burst time (part 1). Four marks for providing one solution to prevent starvation (part2). Full marks for correctly answering both parts of the answer. Partial marking for partial correct answer based on markers judgement.

(ii) [6 marks] Round-robin (RR) scheduling allocates the CPU to each process for a time quantum. If the process does not relinquish the CPU before its time quantum expires, it is preempted, and another process is scheduled to run for a time quantum. Consider there are three processes (P 1, P 2, P 3) coming in the system in the given order, each with a burst time of 12 ms and arrival time = 0. RR time quantum is 2 ms, with context switching time 1 ms. What are the turnaround and waiting times of each process? Show how you calculated these and fill in your answers in Table 1.

(iii) [8 marks] As a system software developer, you are assigned a task to develop an internet browser application which allows users to open different tabs concurrently. Would you design the browser application to open each new tab in a new process or in a separate thread? What are pros and cons of your approach over other? Explain.

Answer: If security is important, process based approach will be taken. however, creating a new tab in thread is more resource efficient as creating threads has lower system overhead as compared to creating a new process. Threads will use parent process memory and resources, thus require more application level synchronisation where creating process require more resources and explicit Inter-process communication mechanism.

Marking criteria: 4 marks for clearly mentioning one approach over other with explanation. 4 marks for mentioning one or more pros and cons. Partial marks for partial correct answer based on markers judgement.