mar6-18.md

March 6 2018

---

Uniprocessor handling

Goals of processor scheduling

• Assign processes to be executed by processors
• Must meet
  1. Response time
  2. Throughput
  3. Processor Efficiency
  4. Temperature
  5. Power

Types of Scheduling

1. ** Long term scheduling **: Decision to add to the pool of processes to be executed

• Controls level of multi programming
• Decides whether it can take another process, and which process
• More processes, less time per process is executed

2. ** Medium term scheduling**: Decision to add to the number of processes that are partially or fully in main memory

• Part of the swapping function
• Depends on the availability of virtual memory, and the need to manage the degree of multi programming

3. ** Short term scheduling**: The decision to which available process will be executed by the processor

• The dispatcher
• Invoked when an event occurs, i.e. Clock interrupts, I/O interrupts
• Can be user oriented vs system-oriented

4. I/O scheduling: The decision to which process' pending I/O request shall be handled by an available I/O device


User Oriented Criteria

• Turnaround time - interval of time between process submission and completion
• Response time - Time from submission of a request until response begins to be received
• **Deadlines ** - Maximizing the percentage of deadlines met
• Predictability - Job should run in the same amount of time and cost regardless of system load.

System Oriented Criteria

• Throughput
• Processor utilization
• Fairness
• Enforcing priorities - prioritizes higher-priority processes
• Balancing resources - scheduling policy should keep system resources busy

Classifications

• Loosely coupled or distributed multiprocessor, or cluster
  • Each processor has its own memory and I/O channels
  • Classical distributed system
• Functionally specialized processors
  • I/O processor
  • FPGA card
• Tightly coupled multi-processing

Priorities

• Scheduler always chooses higher priority over lower priority
• Use multiple ready queues to represent priority levels
• Lower-priority may suffer starvation
  • Allow processes to change its priority based on age

** Priority based scheduling is non-preemptive **

Decision Modes

1. **Non-preemptive **

   • Once a process is in a running state, it will run until terminated or blocks itself with I/O

2. ** Preemptive **

   • Currently running process may be interrupted and moved to the ready state
   • Allows for better service as one process cannot eat up processor for long.

3. ** Cooperative **

First-Come-First-Served


• Oldest process in ready queue is served
• Non-preemptive
• Pros:
  • Good for computation-intensive processes
  • Favours CPU-bound processes
• ** Cons: **
  • Short process will wait a very long time before execution

Round Robin


• Use preemption based on a clock, clock creates interrupts
• When interrupt occurs, currently running process is placed in ready queue
  • Next ready job is selected
• Need to pick a good quantum for effective time slicing
• Pros:
  • Good overall strategy
• Cons:
  • processor-bound processes receive an unfair share

Shortest Process Next


• Nonpreemptive policy
• Process with shorted expected processing time is selected next
• Pros:
  • Good for minimizing waiting time
• Cons:
  • Predictability of longer processes is reduced
  • Possibility of starvation for longer processes or they can be aborted if estimated incorrectly
• Fix: Shortest Remaining Time

Shortest Remaining Time


• Preemptive version of SPN
• Estimate processessing time
• Starvation of longer processes
• Pros:
  • Better general turn-around time than SPN
  • No bias for long processes like in FCFS
• Cons:
  • Elapsed service time must be recorded

Highest Response Ratio Next


• Choose next process with the greatest ratio
• Accounts for age and short processes (better ratio)
• Still needs to know the service time

Feedback-based Scheduling


• Select the first job of the lowest queue (highest priority queue) that is not empty
• Penalize jobs that have been running longer
• Uses: If you have one application that creates a number of processes that block the CPU
• Pros:
  • Reduces turnaround time
• Cons:
  • Complex
  • Starves tasks that drop to the last queue (if first queue is filled with multiple short tasks)

Summary

	FCFS	Round Robin	SPN	SRRT	HRRN	Feedback
Decision Mode	Non-preemptive	Preemptive	Non-preemptive	Preemptive	Non-preemptive	Preemptive
Throughput	Not emphasized	May be low with a low quantum	High	High	High	Not emphasized
Response time	May be high if large varience in process execution time	Good response time for short processes	Good response time for short processes	Good response time	Good response time	Not emphasized
Overhead	Minimum	Minimum	Can be high	Can be high	Can be high	Can be high
Effect on process	Penalizes short or I/O bound processes	Fair treatment	Penalizes long processes	Penalizes Long processes	Good Balance	Favors i?o bound processes
Starvation	No	No	Possible	No	No	Possible

Fair-Share Scheduler

• Users application runs as a collection of processes (threads)
• CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes.

UNIX Scheduling

• Multilevel feedback with round robin with multiple priority queues
• Preempts processes that are not finished or blocked within 1 second
• Recompute priorities every second