Scribd Logo
Upload

Welcome to Scribd!

  • 14 views

    MSCIT 4th COMP2115 7,8

    Uploaded by

    countsohaib.as
    This document provides an overview of CPU scheduling techniques including FCFS, SJF, priority scheduling, round robin scheduling, and multilevel queue scheduling. It also discusses dispatcher functionality and criteria for evaluating scheduling algorithms such as CPU utilization, throughput, turnaround time, and waiting time. Finally, it covers challenges and techniques for scheduling on multiprocessor systems including load balancing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MSCIT 4th COMP2115 7,8

    Uploaded by

    countsohaib.as
    14 views22 pages
    This document provides an overview of CPU scheduling techniques including FCFS, SJF, priority scheduling, round robin scheduling, and multilevel queue scheduling. It also discusses dispatcher functionality and criteria for evaluating scheduling algorithms such as CPU utilization, throughput, turnaround time, and waiting time. Finally, it covers challenges and techniques for scheduling on multiprocessor systems including load balancing.

    Original Description:

    OPERATING SYSTEMS LECTURE

    Original Title

    MSCIT-4th-COMP2115-7,8

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of CPU scheduling techniques including FCFS, SJF, priority scheduling, round robin scheduling, and multilevel queue scheduling. It also discusses dispatcher functionality and criteria for evaluating scheduling algorithms such as CPU utilization, throughput, turnaround time, and waiting time. Finally, it covers challenges and techniques for scheduling on multiprocessor systems including load balancing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    14 views22 pages

    MSCIT 4th COMP2115 7,8

    Uploaded by

    countsohaib.as
    This document provides an overview of CPU scheduling techniques including FCFS, SJF, priority scheduling, round robin scheduling, and multilevel queue scheduling. It also discusses dispatcher functionality and criteria for evaluating scheduling algorithms such as CPU utilization, throughput, turnaround time, and waiting time. Finally, it covers challenges and techniques for scheduling on multiprocessor systems including load balancing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 22

    Operating Systems (COMP2115)

    Lecture # 7
    Lecture Contents

    ➢ CPU Schedulers
    ➢ Dispatcher
    ➢ Scheduling Criteria
    ➢ Scheduling Techniques(FCFS, SJF, Priority)

    Course Instructor: Mr. Sabih Jamal


    Chapter 4: CPU Scheduling
    Reference Book: Operating Systems Concepts 9th Edition by Abraham Silber Schatz
    Basic Concepts

    Maximum CPU utilization


    obtained with multiprogramming
    CPU–I/O Burst Cycle – Process
    execution consists of a cycle of
    CPU execution and I/O wait
    CPU burst followed by I/O burst
    CPU burst distribution is of main
    concern
    CPU Scheduler
    Short-term scheduler selects from among the processes in
    ready queue, and allocates the CPU 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
    Scheduling under 1 and 4 is non-preemptive
    All other scheduling is preemptive
    Dispatcher

    Dispatcher module gives control of the CPU to the process


    selected by the short-term scheduler; :
    Dispatch latency – time it takes for the dispatcher to stop
    one process and start another running
    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, not output (for
    time-sharing environment)
    Scheduling Algorithm Optimization Criteria

    Max CPU utilization


    Max throughput
    Min turnaround time
    Min waiting time
    Min response time
    First- Come, First-Served (FCFS) Scheduling

    Process Burst Time


    P1 24
    P2 3
    P3 3
    Suppose that the processes arrive in the order: P1 , P2 , P3
    The Gantt Chart for the schedule is:

    P1 P2 P3
    0 24 27 30

    Waiting time for P1 = 0; P2 = 24; P3 = 27


    Average waiting time: (0 + 24 + 27)/3 = 17
    FCFS Scheduling (Cont.)
    Suppose that the processes arrive in the order:
    P2 , P3 , P1
    The Gantt chart for the schedule is:

    P2 P3 P1
    0 3 6 30

    Waiting time for P1 = 6; P2 = 0; P3 = 3


    Average waiting time: (6 + 0 + 3)/3 = 3
    Much better than previous case
    Convoy effect - short process behind long process
    Consider one CPU-bound and many I/O-bound processes
    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
    The difficulty is knowing the length of the next CPU request
    Could ask the user
    Example of SJF

    ProcessArrival Time Burst Time


    P1 0.0 6
    P2 2.0 8
    P3 4.0 7
    P4 5.0 3

    SJF scheduling chart

    P4 P1 P3 P2
    0 3 9 16 24

    Average waiting time = (3 + 16 + 9 + 0) / 4 = 7


    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
    Non-preemptive

    Problem  Starvation – low priority processes may never execute

    Solution  Aging – as time progresses increase the priority of the


    process
    Example of Priority Scheduling

    ProcessA arri Burst TimeT Priority


    P1 10 3
    P2 1 1
    P3 2 4
    P4 1 5
    P5 5 2

    Priority scheduling Gantt Chart

    P1 P5 P1 P3 P4
    2 2

    0 1 6 16 18 19

    Average waiting time = 8.2 msec


    Operating Systems (COMP2115)
    Lecture # 8
    Lecture Contents

    ➢ Scheduling Techniques(Round Robin, Multi level


    Queue)
    ➢ Multi-processors Scheduling
    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
    Timer interrupts every quantum to schedule next process
    Performance
    q large  FIFO
    q small  q must be large with respect to context switch,
    otherwise overhead is too high
    Example of RR with Time Quantum = 4
    Process Burst Time
    P1 24
    P2 3
    P3 3
    The Gantt chart is:

    P1 P2 P3 P1 P1 P1 P1 P1
    0 4 7 10 14 18 22 26 30

    Typically, higher average turnaround than SJF, but better


    response
    q should be large compared to context switch time
    q usually 10ms to 100ms, context switch < 10 usec
    Time Quantum and Context Switch Time
    Multilevel Queue
    Ready queue is partitioned into separate queues, e.g:
    foreground (interactive)
    background (batch)
    Each queue has its own scheduling algorithm:
    foreground – RR
    background – FCFS
    Scheduling must be done between the queues:
    Fixed priority scheduling; (i.e., serve all from foreground then
    from background). Possibility of starvation.
    Time slice – each queue gets a certain amount of CPU time
    which it can schedule amongst its processes; i.e., 80% to
    foreground in RR
    20% to background in FCFS
    Multilevel Queue Scheduling
    Multiple-Processor Scheduling
    CPU scheduling more complex when multiple CPUs are
    available
    Asymmetric multiprocessing – only one processor accesses
    the system data structures, alleviating the need for data sharing
    Symmetric multiprocessing (SMP) – each processor is self-
    scheduling, all processes in common ready queue, or each has
    its own private queue of ready processes
    Currently, most common
    Processor affinity – process has affinity for processor on which
    it is currently running
    NUMA and CPU Scheduling

    Note that memory-placement algorithms can also consider affinity


    Multiple-Processor Scheduling – Load Balancing

    If SMP, need to keep all CPUs loaded for efficiency


    Load balancing attempts to keep workload evenly distributed
    Push migration – periodic task checks load on each processor,
    and if found pushes task from overloaded CPU to other CPUs
    Pull migration – idle processors pulls waiting task from busy
    processor

    You might also like