Q171: Solution to Critical Section Problem

Question 171: Does the following solution solve the critical section problem?

while(true) {

while (flag);    // Spin lock

flag = true;

// critical section

flag = false;

// remainder section

}

Options:

1. No, there should be ‘if’ condition instead of ‘while’.
2. Yes, it solves the problem.
3. No, this violates the mutual exclusion requirement as both processes can be in critical region if context switch happens just after ‘while’ loop breaks but before setting flag as true.
4. No, this violates the mutual exclusion requirement as both processes can be in critical region if context switch happens just before ‘while’ loop breaks and before setting flag as true.

Solution: The correct answer is the third one. Mutual exclusion is not ensured here, since both processes can enter simultaneously into the critical section in the following case: Process 1 checks the flag as false initially and before making it true, a context switch happens and Process 2 also checks the flag as false. Now, both set the flag as true and are in the critical section.

Q160: Threads over processes?

Question160: Is there any benefit using threads over processes?

Options:

1. No, processes are better as they provide better isolation.
2. Yes, threads are beneficial as they are light weight to spawn.
3. Yes, threads share code segment thereby saving memory.
4. Both B and C depending on use case.

Solution: The correct answer is the last one. Threads are kind of light weight processes, they also share code segment with each other within the same process. Threads are useful for lightweight tasks whereas processes are useful for heavy weight tasks.

Q158: Hardware support for scheduling

Question #159: In operating systems, scheduler is a piece of code that is used to switch the CPU between the processes or threads. Is there a need of any hardware support for scheduling in Operating systems?

1.  No, there is no need. Everything can be done purely in software.
2.  Yes, only an interrupt controller is needed.
3.  Yes, an interrupt controller and a hardware timer is needed.
4.  None of the above.

 

Solution:

The correct answer is the 3rd one. An interrupt controller and a hardware timer is needed such that the scheduler can be invoked after every timer interrupt. If there is no external interrupt, there is no way by which the scheduler runs other processes or threads in the system.

Q157: About Spinlocks

Spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop while repeatedly checking if the lock is available. This is similar to busy-waiting, since the thread is active but is not doing any useful work.

Question #157: Which of the following makes sense regarding spinlocks?

Options:

1. Spinlock is more useful for uni-processor systems, than multiprocessor systems.

2. Spinlock is more useful for multiprocessor systems, than uni-processor systems.

3. Spinlocks can be useful as they avoid the overhead of context switch and CPU scheduling.

4. Acquiring a lock cannot happen without spinlocks.

Solution: In a uni-processor system, if a thread has nothing better to do than just wait, it makes more sense to release the control of processor and go to sleep, so that some other thread/process can take over the processor and do some useful work. However, in a multiprocessor system, it’s okay for a thread to waste a few CPU cycles in spinlock, since other processes can still run on the other processors during that time. Imagine a scenario where process A is running and it  holds lock L, but a higher priority process B comes along, causes context switch and gets hold of the CPU. Now, process B starts running but needs lock L. If process B goes into spin lock, then all the CPU cycles are wasted as unless process A is allowed to run, it cannot release L. Hence option 2 is right over option 1.

Option 3 is also correct, since if a process has to wait for a short time, and then run again, it makes sense to use spinlocks than to do context switches. Option 4 is false, since it is not necessary to implement spinlock for acquiring locks. A thread can go to sleep if a lock is unavailable and be woken up when a lock becomes available again.

So both options  2 & 3 are correct here.

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.

Q148: Shortest job first without pre-emption

Question 148: If shortest job first policy is used without pre-emption, what would be the average waiting time?

Options:

• 2
• 3
• 4
• 5

Solution: The correct answer is the third one. Average waiting time is (0 + 6 + 3 + 7)/4 = 4

Q135: Critical Section Problem

Question #135: Which of the following is not a requirement for the solution to critical section problem?

Options:

1. No two processes may be simultaneously inside their critical regions.
2. No assumptions may be made about speeds or the number of CPUs.
3. No process running outside its critical region may block other processes.
4. No process has to wait for more than a certain amount of time.

Solution: The correct answer is the fourth one. The correct requirement is that no process has to wait forever.

Q130: Resource allocation graphs and deadlock detection

Question #130: Consider the following resource allocation graphs. Here resources have multiple instances indicated by the circles (R2 has 2 instances, R3 has 1 instance).

Figure 1:

Figure 2:

Which of the following statements is true about the figures above?

Options:

1. Both depict a deadlock.
2. Only figure 1 has a deadlock, figure 2 doesn’t.
3. Only figure 2 has a deadlock, figure 1 doesn’t.
4. Can’t say.

Solution: 2nd option is the correct one. In figure 1, P1 is waiting for P2, P2 is waiting for P3, P3 is waiting on both P1 & P2 (as can be seen by the cycle). In figure 2, P2 is not waiting for any other process & thus will release R1 eventually, which will break the cycle in the graph and thus it is not deadlocked. This is an example of resource allocation graph with cycle but no deadlock.

Q126: Comparing process scheduling algorithms

Question #126: Which of the following is not true?

Options:

1. Long jobs can be starved in SJF (Shortest Job First) algorithm.
2. Prediction of future is required in SRTF (Shortest Remaining Time First) algorithm.
3. High turnaround time for equal length jobs in RR (Round Robin) algorithm.
4. If pre-emption is allowed for SJF, it will be better than SRTF.

Solution: The correct answer is the last one. If pre-emption is allowed for SJF, it will be same as SRTF.