Processes 2

Overview

• Introduction to process scheduling
• Types of process schedulers
• Evaluation criteria for scheduling algorithms
• Typical process scheduling algorithms

Process Scheduling

Context

• The OS is responsible for managing and scheduling processes
  • Decide when to admit processes to the system (new → ready)
  • Decide which process to run next (ready → run)
  • Decide when and which processes to interrupt (running → ready)
• It relies on the scheduler (dispatcher) to decide which process to run next, which uses a scheduling algorithm to do so
• The type of algorithm used by the scheduler is influenced by the type of operating system (e.g., real time vs. batch)

Classification by Time Horizon

• Long term: applies to new processes and controls the degree of multiprogramming by deciding which processes to admit to the system
  • A good mix of CPU and I/O bound processes is favourable to keep all resources as busy as possible
  • Usually absent in popular modern OS
• Medium term: controls swapping and the degree of multi-programming
• Short term: decide which process to run next
  • Usually called in response to clock interrupts, I/O interrupts, or blocking system calls
  • Invoked[调用] very frequently, hence must be fast
  • Manages the ready queue

Classification by Approach

• Non-preemptive: processes are only interrupted voluntarily[自愿的] (e.g., I/O operation or “nice” system call – yield())
• Preemptive[优先的]: processes can be interrupted forcefully or voluntarily
  • This requires context switches which generate overhead, too many of them should be avoided
    Prevents processes from monopolising[垄断的] the CPU
  • Most popular modern operating systems are preemptive

Performance Assessment[性能评估]

User oriented[导向]criteria:

• Response time: minimise the time between creating the job and its first execution
• Turnaround time: minimise the time between creating the job and finishing it
• Predictability[可调度性]: minimise the variance[差异，方差] in processing times

System oriented criteria:

• Throughput[吞吐量]: maximise the number of jobs processed per hour
• Fairness[公平性]:
  • Are processing power/waiting time equally distributed?
  • Are some processes kept waiting excessively long (starvation)

Evaluation criteria can be conflicting, i.e., reducing the response time may increase context switches and may worsen the throughput and increase the turn around time

Scheduling Algorithms

Algorithms considered:

1. First Come First Served (FCFS)/ First In First Out (FIFO)
2. Shortest job first
3. Round Robin
4. Priority queues

Performance measures used:

• Average response time
• Average turnaround time

First Come First Served

• Concept: a non-preemtive algorithm that operates as a strict[严格的] queueing mechanism[机制] and schedules the processes in the same order that they were added to the queue
• Advantages: positional fairness and easy to implement
• Disadvantages:
  • good for long processes over short ones
  • Could compromise[危害] resource utilisation, i.e., CPU vs. I/O devices
    

Shortest Job First

• Concept: A non-preemtive algorithm that starts processes in order of ascending[递增] processing time using a provided/known estimate of the processing
• Advantages: always result in the good turn around time
• Disadvantages:
  • Starvation[饿死] might occur
  • Fairness and predictability are compromised
  • Processing times have to be known beforehand
    

Round Robin

• Concept: a preemptive version of FCFS that forces context switches at periodic[周期性] intervals[间隔] or time slices
• Processes run in the order that they were added to the queue
• Processes are forcefully interrupted by the timer
  Advantages:
• Improved response time
• Effective for general purpose time sharing systems
  Disadvantages:
• Increased context switching and thus overhead
• Favours CPU bound processes (which usually run long) over I/O processes (which do not run long)
• Can reduce to FCFS

The length of the time slice must be carefully considered!

• a low response time is achieved with a small time slice (e.g. 1ms) ⇒ low throughput
• a high throughput is achieved with a large time slice (e.g. 1000ms) ⇒ high response time

If a time slice is only used partially, the next process starts immediately

Priority Queues

• Concept: A preemptive algorithm that schedules processes by priority (high → low)
  • The process priority is saved in the process control block
• Advantages: can prioritise[优先] I/O bound jobs
• Disadvantages: low priority processes may suffer from starvation (with static priorities)
• 

##Summary

• Types of schedulers: preemptive/non-preemptive, long/medium/short term)
• Performance evaluation criteria
• Scheduling algorithms: FCFS, SJF, Round Robin, Priority Queues

赏

谢谢投喂 (～o￣3￣)～

支付宝