Chapter 5 - CPU Scheduling Flashcards
What is CPU scheduling?
CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the CPU to it. The CPU is allocated to the selected process by the dispatcher.
What are the two types of scheduling algorithms?
Scheduling algorithms may be either preemptive (where the CPU can be taken away from a process) or nonpreemptive (where a process must voluntarily relinquish control of the CPU). Almost all modern operating systems are preemptive.
What are the five criteria of evaluating scheduling algorithms?
- CPU utilization
- throughput
- turnaround time
- waiting time
- response time
What is first-come, first-served (FCFS)?
First-come, first-served (FCFS) scheduling is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes.
What is shortest-job-first (SJF)?
Shortest-job-first (SJF) scheduling is provably optimal, providing the shortest average waiting time. Implementing SJF scheduling is difficult, however, because predicting the length of the next CPU burst is difficult.
What is round-robin (RR)?
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, the process is preempted, and another process is scheduled to run for a time quantum.
What does priority scheduling do?
Priority scheduling assigns each process a priority, and the CPU is allocated to the process with the highest priority. Processes with the same priority can be scheduled in FCFS order or using RR scheduling.
What does multilevel queue scheduling do?
Multilevel queue scheduling partitions processes into several separate queues arranged by priority, and the scheduler executes the processes in the highest-priority queue. Different scheduling algorithms may be used in each queue.
What are multilevel feedback queues?
Multilevel feedback queues are similar to multilevel queues, except that a process may migrate between different queues.
What does load balancing on multicore systems do?
Load balancing on multicore systems equalized loads between CPU cores, although migrating threads between cores to balance loads may invalidate cache contents and therefore may increase memory access times.
What is rate-monotonic real-time scheduling?
Rate-monotonic real-time scheduling schedules periodic tasks using a static priority police with preemption.
What is earliest-deadline-first (EDF)?
Earliest-deadline-first (EDF) scheduling assigns priorities according to deadline. The earlier the deadline, the higher the priority; the later the deadline, the lower the priority.
What is proportional share scheduling?
Proportional share scheduling allocates T shares among all applications. If an application is allocated N shares of time, it is ensured of having N/T of the total processor time.
What does Linux use as a scheduler?
Linux uses the completely fair scheduler (CFS), which assigns a proportion of CPU processing time to each task. The proportion is based on the virtual runtime (vruntime) value associated with eachtask.
What does windows use to determine the order of thread scheduling?
Windows scheduling uses a preemptive, 32-level priority scheme to determine the order of thread scheduling.
