CS330 · Annotated SlidesChapter 5 — CPU Scheduling
Chapter 5 · Annotated slides

CPU Scheduling

CPU–I/O burst cycle, preemptive vs. nonpreemptive scheduling, the dispatcher, scheduling criteria, FCFS, SJF and SRTF (with exponential averaging), Round Robin, priority, multilevel and multilevel feedback queues, thread and real-time scheduling, and algorithm evaluation.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low

    Outline

    • Basic Concepts
    • Scheduling Criteria
    • Scheduling Algorithms
    • Thread Scheduling
    • Multi-Processor Scheduling
    • Real-Time CPU Scheduling
    • Operating Systems Examples
    • Algorithm Evaluation
    Outline
    2
    Exam weight Low

      Objectives

      • Describe various CPU scheduling algorithms
      • Assess CPU scheduling algorithms based on scheduling criteria
      • Explain the issues related to multiprocessor and multicore scheduling
      • Describe various real-time scheduling algorithms
      • Describe the scheduling algorithms used in the Windows, Linux, and Solaris operating systems
      • Apply modeling and simulations to evaluate CPU scheduling algorithms
      Objectives
      3
      Exam weight Low
        Slide 4: Basic Concepts
        Exam weight Low
        1. Processes alternate CPU bursts and I/O bursts; most CPU bursts are short.
        Slide 5: Histogram of CPU-burst Times
        Exam weight Low

          CPU Scheduler

          • The CPU scheduler selects from among the processes in ready queue, and allocates a CPU core to one of them
            • Queue may be ordered in various ways
          • CPU scheduling decisions may take place when a process:
          1. Switches from running to waiting state
          2. Switches from running to ready state
          3. Switches from waiting to ready
          4. Terminates
          • For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution.
          • For situations 2 and 3, however, there is a choice.
          CPU Scheduler
          6
          Exam weight Low

            Preemptive and Nonpreemptive Scheduling

            • When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is nonpreemptive.
            • Otherwise, it is preemptive.
            • Under Nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.
            • Virtually all modern operating systems including Windows, MacOS, Linux, and UNIX use preemptive scheduling algorithms.
            Preemptive and Nonpreemptive Scheduling
            7
            Exam weight High
            1. Scheduling decisions when a process: 1) running → waiting, 2) running → ready, 3) waiting → ready, 4) terminates. Only 1 and 4 → nonpreemptive; otherwise preemptive.
            🎯 How this can come up · 1 question
            MCQ

            Under nonpreemptive scheduling, the CPU is taken from a process only when it:

            Preemptive Scheduling and Race Conditions

            • Preemptive scheduling can result in race conditions when data are shared among several processes.
            • Consider the case of two processes that share data. While one process is updating the data, it is preempted so that the second process can run. The second process then tries to read the data, which are in an inconsistent state.
            • This issue will be explored in detail in Chapter 6.
            Preemptive Scheduling and Race Conditions
            8
            Exam weight Low

              Dispatcher

              • Dispatcher module gives control of the CPU to the process selected by the CPU scheduler; this involves:
                • Switching context
                • Switching to user mode
                • Jumping to the proper location in the user program to restart that program
              • Dispatch latency
                • time it takes for the dispatcher to stop one process and start another running
              Dispatcher
              9
              Exam weight Low
              1. Dispatcher gives the CPU to the chosen process: context switch, switch to user mode, jump to the right instruction. Dispatch latency = time to do this.

              Scheduling Criteria

              • CPU utilization – keep the CPU as busy as possible
              • Throughput – # of processes that complete their execution per time unit
              • Turnaround time – amount of time to execute a particular process
              • Waiting time – amount of time a process has been waiting in the ready queue
              • Response time
                • amount of time it takes from when a request was submitted until the first response is produced.
              Scheduling Criteria
              10
              Exam weight High
              1. Maximize CPU utilization and throughput; minimize turnaround, waiting and response time.
              TipWaiting time = turnaround − burst. Turnaround = completion − arrival. Response = first run − arrival. Draw the Gantt chart first.
              🎯 How this can come up · 1 question
              MCQ

              Which criterion should be MINIMIZED?

              Scheduling Algorithm Optimization Criteria

              • Max CPU utilization
              • Max throughput
              • Min turnaround time
              • Min waiting time
              • Min response time
              Scheduling Algorithm Optimization Criteria
              11
              Exam weight Low
                Slide 12: First- Come, First-Served (FCFS) Scheduling
                Exam weight High
                1. FCFS: run in arrival order; nonpreemptive. Convoy effect: short processes wait behind a long one.
                🎯 How this can come up · 1 question
                MCQ

                P1 = 24, P2 = 3, P3 = 3 arrive in that order at time 0. FCFS average waiting time:

                Slide 13: FCFS Scheduling (Cont.)
                Exam weight Low
                1. Order P2, P3, P1 gives average wait (6 + 0 + 3) / 3 = 3: order matters a lot.

                Shortest-Job-First (SJF) Scheduling

                • Associate with each process the length of its next CPU burst
                  • Use these lengths to schedule the process with the shortest time
                • SJF is optimal – gives minimum average waiting time for a given set of processes
                • Preemptive version called shortest-remaining-time-first
                • How do we determine the length of the next CPU burst?
                  • Could ask the user
                  • Estimate
                Shortest-Job-First (SJF) Scheduling
                14
                Exam weight High
                1. SJF: run the shortest next CPU burst. Optimal: minimum average waiting time for a given set. Problem: you can’t know the next burst length.
                🎯 How this can come up · 1 question
                True / False

                SJF gives the minimum average waiting time for a given set of processes.

                Slide 15: Example of SJF
                Exam weight Low
                  Slide 16: Determining Length of Next CPU Burst
                  Exam weight High
                  1. Predict the next burst: τₙ₊₁ = α·tₙ + (1 − α)·τₙ (exponential averaging), usually α = ½.
                  🎯 How this can come up · 1 question
                  MCQ

                  τ₀ = 10, α = 0.5, the actual burst t₀ = 6. τ₁ =

                  Slide 17: Prediction of the Length of the Next CPU Burst
                  Exam weight Low

                    Examples of Exponential Averaging

                    •  =0
                      •  =  n+1 n
                      • Recent history does not count
                    •  =1
                      •  = t n+1 n
                      • Only the actual last CPU burst counts
                    • If we expand the formula, we get:  =  t +(1 -  )  t + ... n +1 n n -1 +(1 -  ) j  t + ... n - j +(1 -  ) n +1  0
                    • Since both  and (1 -  ) are less than or equal to 1, each successor predecessor term has less weight than its predecessor
                    Examples of Exponential Averaging
                    18
                    Exam weight Low

                      Shortest Remaining Time First Scheduling

                      • Preemptive version of SJN
                      • Whenever a new process arrives in the ready queue, the decision on which process to schedule next is redone using the SJN algorithm.
                      • Is SRT more “optimal” than SJN in terms of the minimum average waiting time for a given set of processes?
                      Shortest Remaining Time First Scheduling
                      19
                      Exam weight High
                      1. SRTF = preemptive SJF: a new arrival with a shorter burst than the remaining time preempts the running process.
                      Exam trapIn SRTF compare the newcomer with the REMAINING time of the running process, not its original burst.
                      Slide 20: Example of Shortest-remaining-time-first
                      Exam weight Low

                        Round Robin (RR)

                        • Each process gets a small unit of CPU time (time quantum q ), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
                        • If there are n processes in the ready queue and the time quantum is q, then each process gets 1/ n of the CPU time in chunks of at most q time units at once. No process waits more than (n -1) q time units.
                        • Timer interrupts every quantum to schedule next process
                        • Performance
                          • q large  FIFO (FCFS)
                          • q small  RR
                        • Note that q must be large with respect to context switch, otherwise overhead is too high
                        Round Robin (RR)
                        21
                        Exam weight High
                        1. Round Robin: each process gets a time quantum q, then goes to the back of the ready queue. No process waits more than (n − 1)q.
                        🎯 How this can come up · 1 question
                        MCQ

                        P1 = 24, P2 = 3, P3 = 3, RR with q = 4. P1 completes at time:

                        Slide 22: Example of RR with Time Quantum = 4
                        Exam weight Low
                          Slide 23: Time Quantum and Context Switch Time
                          Exam weight High
                          1. Large q → behaves like FCFS. Small q → too many context switches. q should be large compared with the context-switch time (80% of bursts < q).
                          🎯 How this can come up · 1 question
                          MCQ

                          If the RR time quantum is very large, RR behaves like:

                          Slide 24: Turnaround Time Varies With The Time Quantum
                          Exam weight Low

                            Priority Scheduling

                            • A priority number (integer) is associated with each process
                            • The CPU is allocated to the process with the highest priority (smallest integer  highest priority)
                              • Preemptive
                              • Nonpreemptive
                            • SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
                            • Problem  Starvation – low priority processes may never execute
                            • Solution  Aging – as time progresses increase the priority of the process
                            Priority Scheduling
                            25
                            Exam weight High
                            1. Priority scheduling (smaller number = higher priority here). Problem: starvation. Solution: aging (raise priority over time).
                            🎯 How this can come up · 1 question
                            MCQ

                            The solution to starvation in priority scheduling is:

                            Slide 26: Example of Priority Scheduling
                            Exam weight Low
                              Slide 27: Priority Scheduling w/ Round-Robin
                              Exam weight Low

                                Multilevel Queue

                                • The ready queue consists of multiple queues
                                • Multilevel queue scheduler defined by the following parameters:
                                  • Number of queues
                                  • Scheduling algorithms for each queue
                                  • Method used to determine which queue a process will enter when that process needs service
                                  • Scheduling among the queues
                                Multilevel Queue
                                28
                                Exam weight Low
                                1. Multilevel queue: separate queues (e.g. foreground RR, background FCFS), each with its own algorithm; scheduling between queues by fixed priority or time slices.
                                Slide 29: Multilevel Queue
                                Exam weight Low
                                  Slide 30: Multilevel Queue
                                  Exam weight Low

                                    Multilevel Feedback Queue

                                    • A process can move between the various queues.
                                    • Multilevel-feedback-queue scheduler defined by the following parameters:
                                      • Number of queues
                                      • Scheduling algorithms for each queue
                                      • Method used to determine when to upgrade a process
                                      • Method used to determine when to demote a process
                                      • Method used to determine which queue a process will enter when that process needs service
                                    • Aging can be implemented using multilevel feedback queue
                                    Multilevel Feedback Queue
                                    31
                                    Exam weight High
                                    1. Multilevel feedback queue: processes MOVE between queues (demote CPU-hogs, age old ones up).
                                    🎯 How this can come up · 1 question
                                    MCQ

                                    What distinguishes a multilevel FEEDBACK queue from a multilevel queue?

                                    Slide 32: Example of Multilevel Feedback Queue
                                    Exam weight Low

                                      Thread Scheduling

                                      • Distinction between user-level and kernel-level threads
                                      • When threads supported, threads scheduled, not processes
                                      • Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP
                                        • Known as process-contention scope (PCS) since scheduling competition is within the process
                                        • Typically done via priority set by programmer
                                      • Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system
                                      Thread Scheduling
                                      33
                                      Exam weight Low
                                      1. Process-contention scope (user threads on LWPs) vs. system-contention scope (kernel threads competing system-wide).
                                      Slide 34: Dispatch Latency
                                      Exam weight Low
                                        Slide 35: Priority-based Scheduling
                                        Exam weight Low
                                          Slide 36: Rate Monotonic Scheduling
                                          Exam weight Low
                                          1. Rate-monotonic: static priority = shorter period gets higher priority.

                                          Operating System Examples

                                          • Linux scheduling
                                          • Windows scheduling
                                          • Solaris scheduling
                                          Operating System Examples
                                          37
                                          Exam weight Low
                                            Slide 38: Windows Priorities
                                            Exam weight Low

                                              Solaris

                                              • Priority-based scheduling
                                              • Six classes available
                                                • Time sharing (default) (TS)
                                                • Interactive (IA)
                                                • Real time (RT)
                                                • System (SYS)
                                                • Fair Share (FSS)
                                                • Fixed priority (FP)
                                              • Given thread can be in one class at a time
                                              • Each class has its own scheduling algorithm
                                              • Time sharing is multi-level feedback queue
                                                • Loadable table configurable by sysadmin
                                              Solaris
                                              39
                                              Exam weight Low
                                                Slide 40: Solaris Scheduling
                                                Exam weight Low

                                                  Solaris Scheduling (Cont.)

                                                  • Scheduler converts class-specific priorities into a per-thread global priority
                                                    • Thread with highest priority runs next
                                                    • Runs until (1) blocks, (2) uses time slice, (3) preempted by higher-priority thread
                                                    • Multiple threads at same priority selected via RR
                                                  Solaris Scheduling (Cont.)
                                                  41
                                                  Exam weight Low
                                                    Slide 42: Algorithm Evaluation
                                                    Exam weight Low
                                                      Slide 43: Deterministic Evaluation
                                                      Exam weight Low
                                                      1. Deterministic modelling: compute each algorithm’s numbers for a given workload.

                                                      Queueing Models

                                                      • Describes the arrival of processes, and CPU and I/O bursts probabilistically
                                                        • Commonly exponential, and described by mean
                                                        • Computes average throughput, utilization, waiting time, etc.
                                                      • Computer system described as network of servers, each with queue of waiting processes
                                                        • Knowing arrival rates and service rates
                                                        • Computes utilization, average queue length, average wait time, etc.
                                                      Queueing Models
                                                      44
                                                      Exam weight Low
                                                        Slide 45: Slide 45
                                                        Exam weight Low