Understanding Preemptive Scheduling and CPU Performance Metrics
Week 3: What is Preemptive Scheduling?
Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to ready state. The resources (mainly CPU cycles) are allocated to the process for a limited amount of time and then taken away, and the process is again placed back in the ready queue if that process still has CPU burst time remaining. That process stays in the ready queue till it gets its next chance to execute. Preemptive schedulers are Round robin, shortest remaining time first, priority.
What if you have multiple CPUs? How does that affect performance?
More processor runs at the same time thus it increases the performance.
What metrics should you consider when designing a scheduling algorithm?
Average wait time.
Describe First-Come, First-Served scheduling? Describe pros & cons.
First come first served scheduling works similar to a fifo (first in first out) queue. Therefore, it simply queues processes in the order of its arrival. It is simple and easy to understand. Cons: The process with less execution time suffer i.e. waiting time is often quite long. Favors CPU Bound process then I/O bound process. Here, first process will get the CPU first, other processes can get CPU only after the current process has finished it’s execution. Now, suppose the first process has large burst time, and other processes have less burst time, then the processes will have to wait more unnecessarily, this will result in more average waiting time, i.e., Convey effect. This effect results in lower CPU and device utilization. FCFS algorithm is particularly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals. Shortest Job First Pros: Shortest jobs are favored. It is provably optimal, in that it gives the minimum average waiting time for a given set of processes. Cons: SJF may cause starvation, if shorter processes keep coming. This problem is solved by aging. It cannot be implemented at the level of short term CPU scheduling. Round Robin Pros: Every process gets an equal share of the CPU. RR is cyclic in nature, so there is no starvation. Cons: Setting the quantum too short, increases the overhead and lowers the CPU efficiency, but setting it too long may cause poor response to short processes. Average waiting time under the RR policy is often long. PriorityBased Pros: This provides a good mechanism where the relative importance of each process maybe precisely defined. Cons: If high priority processes use up a lot of CPU time, lower priority processes may starve and be postponed indefinitely. The situation where a process never gets scheduled to run is called starvation. Another problem is deciding which process gets which priority level assigned to it. Multilevel Queue Scheduling Pros: Application of separate scheduling for various kind of processes is possible. System Process – FCFS, Interactive Process – SJF, Batch Process – RR Student Process – PB Cons: The lowest level process faces starvation problem. Multilevel Feedback Queue Scheduling Pros: Low scheduling overhead. Allows aging, thus no starvation. Shortest-Job-First Scheduling? Describe pros & cons. Shortest-remaining-time-first? SJF: Running the process first which has the least CPU burst time. Cons: Need to Know the length of the CPU burst. Algorithms may cause very long turnaround times or starvation. Starvation: long jobs may never get a chance to run. Pros: SJF is optimal – gives minimum average waiting time for a given set of processes. A preemptive version of the SJF is known as SRJF. Round Robin? It’s preemptive algorithm. After reaching upto some extended time it switches to the next process. Preemptive process added to the last of the queue. It’s a hybrid which is clock-driven. Widely used in the current os. Cons: Higher average turnaround than sjf. More switches. Doesn’t give more priority to the special tasks. Lower quantum time cause an higher switches in the result. Pros: No starvation or convey effect issues. Fair allocation of cpu. Deal with all process without any priority. Don’t depend on the burst time thus easy to implement. Priority Scheduling? A priority number is associated with each process. Higher priority jobs run first. SJF is a priority scheduling where priority is the inverse of the predicted CPU burst time. Cons: Starvation of the low priority jobs. Solution: Aging → changing the priority as the time progresses. Earliest Deadline First? Suitable for Hard real time systems where task must be serviced by its Deadline. EDF is the optimal dynamic priority scheduling used in real-time system. It can be used for both dynamic and static real-time scheduling. It uses the priority based scheduling. It gives higher priority to the task which is closer to the deadline. The priorities are assigned and changed in a dynamic fashion. It can make the CPU utilization to about 100% while still guaranteeing the deadlines of all the tasks. Kernel overload – uses less than 100% cup – if EDF is not able to find feasible scheduling in real-time no one else can. All tasks should be given a deadline in order to run in EDF. What changes when multiple CPUs become available? CPU scheduling is more complex when multiple cpus are available. What is load balancing? Load balancing attempts to keep workload evenly distributed between multiple CPUs. What is push and pull migration? What are they trying to achieve? Push migrations: Periodic tasks to check load on each processor, and if found pushes tasks from overloaded cpu to other CPUs. Pull Migration: Idle Processors pull waiting tasks from a busy processor. It is trying to achieve load balancing for efficiency. What does NUMA mean and how does it work? If the operating system is NUMA(non uniform memory access)-aware, it will assign memory closest to the CPU the thread is running on.
Week 4: What is a race condition? Give an example.
Situation when the system behaviour depends on the timing of uncontrollable events (Version ANDREY). When two processes access a shared variable at the same exact time even though it should not. Example: 2 processes requesting a new pid using fork() at the same time receive the exact same pid. What is a critical section of code? Why is it useful to define a critical section of code in the context of synchronization? Having a shared common variable, updating tables, and writing a file is a critical section. When one process is in a critical section no other process may be in its critical section. Each process must ask permission before entering that critical section. What does atomic mean (in the context of synchronization)? An operation is considered atomic if it is guaranteed to be isolated from other operations that are happening concurrently. What is the difference between busy waiting and blocking? Which is preferable and why? Busy waiting is when a process is running on the CPU while waiting for another process to exit the critical section, when the first process exits then the next process gets to enter the critical section. On the other hand blocking is when a process checks if the critical section is locked and if it is then the current process will be placed in a “waiting” queue. Blocking is preferable when you only have a single core available so that other processes that’s running inside a critical section get a chance to run. Although blocking does increase the number of context switches and increase the overhead. What is the difference between blocking and non-blocking in processing? Blocking would mean that there is no execution in that particular thread for the duration of the call. I.e. no return value. (the process will be placed in a waiting queue) Whereas in non-blocking, there is always a return immediately even if there is no data (if it is not available yet). The data will be returned once it is available.