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.