cse cpu scheduling review

• Switches from running to waiting state
• Switches from running to ready state
• Switches from waiting to ready
• Terminates

• Consider access to shared data
• Consider preemption while in kernel mode
• Consider interrupts occurring during crucial OS activities

• switching context
• switching to user mode
• jumping to the proper location in the user program to restart that program

• CPU utilization -> max
• Throughput -> max
• Turnaround time -> min
• Waiting time -> min
• Response time -> min

• FCFS
• SJF : minimum average waiting time
• Shortest remaining time first
• Priority scheduling
  • Starvation problem - Aging
• RR
  • no process waits more than (n-1)q time units
  • typically higher average turnaround than SJF, but better response
• Multilevel Queue
  • Ready queue is partitioned into separate queues, eg.
    • foreground (interactive)
    • background (batch)
  • Process permanently in a given queue
  • Each queue has its own scheduling algorithm:
    • foreground RR
    • background FCFS
  • Scheduling must be done between the queues:
    • Fixed priority scheduling; 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 Feedback Queue
  • 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

API allows specifying either PCS or SCS during thread creation

• PTHREAD_SCOPE_PROCESS : PCS
• PTHREAD_SCOPE_SYSTEM : SCS

Can be limited by OS - Linux and Mac OS X only allow PTHREAD_SCOPE_SYSTEM

• More complex when multiple CPUs are avaliable
• Homogeneous processors within a multiprocessor
• 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

• soft affinity
• hard affinity
• variations including processor sets

• Virtualization software schedules multiple guests onto CPUs
• Each guest doing its own scheduling
  • Not knowing it doesn’t own CPU
  • Can result in poor response time
  • Can effect time-of-day clocks in guests
• Can undo good scheduling algorithm efforts of guests

• Priority based scheduling
• 6 classes available
  • Time sharing
  • Interactive
  • Real time
  • System
  • Fair Share
  • Fixed priority
• 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)
• Scheduler converts class-specific priorities into a per thread global priority
  • Thread with highest priority runs next
  • Runs until
    • blocks
    • uses time slice
    • preempted by higher priority thread
    • Multiple threads at same priority selected via RR

• Priority based scheduling
• Dispatcher is scheduler
• Thread runs until
  • blocks
  • uses time slice
  • preempted by higher priority thread
• Real time threads can preempt non-real-time
• 32-level priority scheme
• variable class is 1-15, real time class is 16-31
• priority 0 is memory-management thread
• if no run-able thread, runs idle thread

• constant order O(1) scheduling time
• preemptive, priority based
• two priority ranges: time-sharing and real-time
• Real-time range from 0 to 99 and nice value from 100 to 140