28/Feb/Mon

Basic concept

• 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 Scheduler and Dispacher

• CPU scheduler
  • selects the processes in ready queue, and allocates the CPU to one of them
• Dispacher module
  • gives control of the CPU to the process selected by the short-term scheduler
  • switching context
  • switching to user mode
  • jumping to the proper location in the user program to restart that program

Scheduling Criteria

• Max CPU utilization - keep the CPU as busy as posAsible
• Max Throughput - of processes that complete their execution per time unit
• Min Turnaround time - amount of time to execute a particular process
• Min Waiting time - amount of time a process has been waiting in the ready queue
• Min 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)

Scheduler algorithm

First-come, First-Served(FCFS) Scheduling

FCFS Scheduling(Cont.)

Shotrest-Jon-First (SJF) Scheduling

Determining Length of Next CPU Burst

Shortest-remaining-time-first

Priority Scheduling

Round Robin(RR)

Multilevel Queue

Multilevel Feedback Queue

• A process can move between the various queues; aging can be implemented this way

  Tread Scheduling

• Thread library schedules user-level threads to run on LWP
  • process-contention scope(PCS)
  • priority set by programer
  • PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling
• Kernel thread scheduled on CPU
  • System contention scop (SCS)
  • PTHREAD_SCOPE_SYSTEM schedules threads using SCS scheduling

    Pthread Scheduling API

    

    Multipli-Processor Scheduling

• Asymmetric multiprocessing
• Symmetric multprocessing (SMP)
• Processor affinity
• Load Balancing
  • Push migration
  • Pull migration

    Multicore Processors

• Multiple processor cores on same physical chip
• Multiple threads per core also growing

essing

• Symmetric multprocessing (SMP)
• Processor affinity
• Load Balancing
  • Push migration
  • Pull migration pic

    Multicore Processors

• Multiple processor cores on same physical chip
• Multiple threads per core also growing pic

  Real-Time CPU Scheduling

• Soft real-time systems/ Hard real-time systems
• Interrupt latency pic
• Dispatch latency pic

  Priority-based Scheduling

• For real-time scheduling, scheduler must support preemptive, priority-based scheduling
• But only guarantees soft real-time
• Processes have new characteristics: periodic ones require CPU at constant intervals
  • pic pic

    Rate Montonic Scheduling

• A priority is assigned based on the inverse of its period
  • Shorter periods = higher pority;
  • Longer periods = lower priority
• P1 is assigned a higer priority than P2. pic

  Missed Deadlines with Rate Monotonic Scheduling

  Earliest Deadline First Scheduling (EDF)

• Priorities are assigned according to deadlines:
  • the earlier the deadline, the higher the priority;
  • the later the deadline, the lower the priorty pic

    Proportional Share Scheduling

• T shares are allocated among all processes in the system
• An application receives N shares where N < T
• This ensures each application will receive N/T of the to the total processor time

Algorithm Evaluation

• Deterministic modeling
• Consider 5 processes arriving at time 0; pics

Queueing Models

• Describes the arrival of processed, and CPU and I/O bursts probalilistically
• n = average queue length
• W = average waiting time in queue
• λ = average arrival rate into queue
• Little's law - in steady state, processed leaving queue must equal processes arriving, thus: n = λ x W
• For example, if on average 7 processes arrive per second, and normally 14 processes in queue, the average wait time per process = 2 ceconds

  Simulations

  pic

  Implementatioin

• Just implement new scheduler and test in real systems
  • High cost, high risk
  • Environments vary
• Most flexible schedulers can be modified per-site or per-system or APIs to modify priorities
  • But again environments vary

    Real-Time CPU Scheduling

• Soft real-time systems/ Hard real-time systems
• Interrupt latency
• Dispatch latency

  Priority-based Scheduling

• For real-time scheduling, scheduler must support preemptive, priority-based scheduling
• But only guarantees soft real-time
• Processes have new characteristics: periodic ones require CPU at constant intervals

  Rate Montonic Scheduling

• A priority is assigned based on the inverse of its period
  • Shorter periods = higher pority;
  • Longer periods = lower priority
• P1 is assigned a higer priority than P2.

  Missed Deadlines with Rate Monotonic Scheduling

  

  Earliest Deadline First Scheduling (EDF)

• Priorities are assigned according to deadlines:
  • the earlier the deadline, the higher the priority;
  • the later the deadline, the lower the priorty

    Proportional Share Scheduling

• T shares are allocated among all processes in the system
• An application receives N shares where N < T
• This ensures each application will receive N/T of the to the total processor time

Algorithm Evaluation

• Deterministic modeling
• Consider 5 processes arriving at time 0;

Queueing Models

• Describes the arrival of processed, and CPU and I/O bursts probalilistically
• n = average queue length
• W = average waiting time in queue
• λ = average arrival rate into queue
• Little's law - in steady state, processed leaving queue must equal processes arriving, thus: n = λ x W
• For example, if on average 7 processes arrive per second, and normally 14 processes in queue, the average wait time per process = 2 ceconds

  Simulations

  

  Implementatioin

• Just implement new scheduler and test in real systems
  • High cost, high risk
  • Environments vary
• Most flexible schedulers can be modified per-site or per-system or APIs to modify priorities
  • But again environments vary