Q152: CPU Idle time in SRTF scheduling

Question 152: Consider 3 processes, all arriving at time zero with total execution time of 10, 20, and 30 units respective each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation and last 10% of time doing I/O again. OS uses SRTF scheduling algorithm. Assuming I/O of processes can be overlapped, what percentage of CPU time will remain idle?

Options:

1. 0%
2. 30%
3. 6%
4. 4%

Solution: The correct answer is the third one. Processes will run as follows:

0-2: Idle

2-9: P1

9-23: P2

23-44: P3

44-47: Idle

Idle time = 5 / 47 * 100 = 10.6%

Q150: Priority Scheduling

Question #150: Priority Scheduling is an algorithm where scheduler assigns priority to the processes, and the highest priority process is the next one to get CPU attention. Priority scheduling can be preemptive (such that if a higher priority process enters the queue while a lower priority process is running, the lower priority process gets preempted) or it can be non-preemptive.

Which of the following is true?

Options:

1. Starvation of a low priority process may occur if preemption is used but will not happen when processes are non-preemptive.
2. Starvation of a low priority process may occur if non preemption is used but will not happen when processes are preemptive.
3. If static priorities are assigned (meaning, once assigned, priority of a process will not be changed) then starvation can happen with or without preemption. Starvation can be avoided if priorities are dynamically adjusted.
4. Priority scheduling will always suffer from starvation.

Solution: 3rd option is the correct one. Priority scheduling can prevent starvation by using aging which dynamically changes process’s priority.

Q141: Contiguous block allocation for the files

Question 141: What will be the disadvantage when the files will be allocated only on contiguous blocks on the disk?

1. Head of the disk will require too much movement to traverse the file.
2. Head of the disk will require minimal movement as the file is contiguous.
3. It will be difficult to calculate the block location of block I of a file.
4. It will be difficult to find the contiguous space for a large file in the disk and file size growth would be a heavy operation.

Solution: The correct answer is option 4. Head of the disk movement will be minimal as the file is contiguous, hence this is advantage. Also, calculating the block “i” would be easy as they are sequential. The problem is that dynamic growth as we are not sure that there will be enough blocks available after the allocated blocks. In the worst case we will need to move the whole file.

Q73: Shared pages between two processes

Question 73: Consider the following situation where process X and Y’s page table is shown. VPFN refers to virtual page frame number in virtual memory address space and PFN refers to page frame number in physical memory.

\

Which of the following statement is true?

1. Physical page frame number 4 is shared between virtual PFN 1 of Process Y and virtual PFN 3 of Process X.
2. Physical page frame number 0 is shared between virtual PFN 2 of Process Y and virtual PFN 3 of Process X.
3. Physical page frame number 4 is shared between virtual PFN 1 of Process X and virtual PFN 3 of Process Y.
4. No physical page is shared.

Solution: Page table of Process X maps its VPFN 3 to PFN 4, and page table of Process Y maps its VPFN 1 of Process Y to PFN 4. The correct answer is option 1.

Q59: Least average waiting time

Question #59: If there are 4 processes in the system namely P1, P2, P3, P4 with the CPU burst time of 1ms, 2ms, 3ms, and 4ms respectively. They arrive at the same time in order of P3, P2, P4, P1. Which of the following scheduling policy will yield the least average waiting time?

 

Options:

1. Shortest Job First
2. First come first serve
3. All scheduling policies yield the same average waiting time.
4. None of the above

 

Solution:

SJF yields the least waiting time when all of the processes arrive at the same time. For SJF, waiting time is (0 + 1 + 3 + 6) / 4 = 2.5ms. For FCFS, it is (9 + 3 + 0 + 5 ) / 4 = 4.25ms. Hence, the correct answer is option 1.

Q11: Access pattern in memory

Question #11: Consider the hypothetical scenario where there are 4 pages in physical memory and 3 processes are running simultaneously on 3 different processors. Following is the access pattern which repeats over and over again.
Access pattern of P1: {a, b, b, c, b}, {a, b, b, c, b}, …
Access pattern of P2: {p, q, q, q, p}, {p, q, q, q, p}, …
Access pattern of P3: {x, x, x, y, z}, {x, x, x, y, z}, …
Which of the following is a sensible choice of 3 pages which could always remain in memory?

 

Options:

1. b, q, x

2. a, b, x

3. b, p, x

4. Can’t say

 

Solution:

Process P1 accesses ‘b’ the most, P2 accesses ‘q’ the most, and P3 accesses ‘x’ the maximum times. So if these 3 pages are present always and the remaining pages in memory can be used for other accesses. Hence, the correct answer is option 1.