CSci 430: Programming Project

Uniprocessor Scheduling

Csci 430, Spring 2018

Texas A&M University – Commerce

Derek Harter

Introduction to Operating System Concepts

Types of Processor Scheduling

Objective: Be able to explain the differences between long-, medium- and short-term scheduling policies.

Processor Scheduling

 Aim is to assign processes to be executed by the processor in a way that meets system objectives, such as response time, throughput, and processor efficiency

 Broken down into three separate functions: – Long-term – Medium-term – Short-term

Table 9.1 Types of Scheduling

Scheduling and Process State Transitions

Figure 9.2

Nesting of

Scheduling

Functions

(Referencing figure 3.9b)

Queuing Diagram

Long-Term Scheduler

 Determines which programs are admitted to the system for processing

 Controls the degree of multiprogramming  the more processes that are created, the smaller the

percentage of time that each process can be executed  may limit to provide satisfactory service to the current set

of processes

Medium-Term Scheduling

 Part of the swapping function

 Swapping-in decisions are based on the need to manage the degree of multiprogramming

 considers the memory requirements of the swapped-out processes

Short-Term Scheduling  Known as the dispatcher

 Executes most frequently

 Makes the fine-grained decision of which process to execute next

 Invoked when an event occurs that may lead to the blocking of the current process or that may provide an opportunity to preempt a currently running process in favor of another

Scheduling Algorithms

Objective: Be able to assess the performance of different scheduling policies (for the short term scheduler or dispatcher).

Short Term Scheduling Criteria

 Main objective is to allocate processor time to optimize certain aspects of system behavior

 A set of criteria is needed to evaluate the scheduling policy

– User vs. system oriented criteria

Short-Term Scheduling Criteria: Performance

- Performance related criteria are quantative (can be measured) - Examples: response time and throughput

- Not performance related are qualitative or not readily measured - Predictability

Table 9.2 Scheduling

Criteria

Priority Queuing

Alternative Scheduling Policies

Selection Function  Determines which process, among ready processes, is selected

next for execution

 May be based on priority, resource requirements, or the execution characteristics of the process

 If based on execution characteristics then important quantities are:  w = time spent in system so far, waiting  e = time spent in execution so far  s = total service time required by the process, including e;

generally, this quantity must be estimated or supplied by the user

Decision Mode

 Specifies the instants in time at which the selection function is exercised

 Two categories:

 Nonpreemptive  Preemptive

Nonpreemptive vs Preemptive

Nonpreemptive

 once a process is in the running state, it will continue until it terminates or blocks itself for I/O

Preemptive

 currently running process may be interrupted and moved to ready state by the OS

 preemption may occur when new process arrives, on an interrupt, or periodically

Alternative Scheduling Policies

Process Scheduling Example

Comparison of Scheduling

Policies

Table 9.5

Comparison of Scheduling

Policies

First-Come-First- Served (FCFS)

 Simplest scheduling policy

 Also known as first-in-first- out (FIFO) or a strict queuing scheme

 When the current process ceases to execute, the longest process in the Ready queue is selected

 Performs much better for long processes than short ones

 Tends to favor processor- bound processes over I/O- bound processes

FCFS: Penalizes Short Jobs

● FCFS performs much better for long processes than short ones.

Round Robin  Uses preemption based on a

clock

 Also known as time slicing because each process is given a slice of time before being preempted

 Principal design issue is the length of the time quantum, or slice, to be used

 Particularly effective in a general-purpose time- sharing system or transaction processing system

 One drawback is its relative treatment of processor- bound and I/O-bound processes

Round Robin

Effect of Size of Preemption Time Quantum

Figure 9.6a

Figure 9.6b Effect of Size of Preemption Time

Quantum

Virtual Round Robin (VRR)

Shortest Process Next (SPN)

 Nonpreemptive policy in which the process with the shortest expected processing time is selected next

 A short process will jump to the head of the queue

 Possibility of starvation for longer processes

 One difficulty is the need to know, or at least estimate, the required processing time of each process

 If the programmer’s estimate is substantially under the actual running time, the system may abort the job

Calculating Service Time Interactively

● One difficulty with SPN is need to know or estimate required processing time (service time)

● For batch job, can be supplied by programmer.

● For interactive jobs, OS can keep average of each “burst”

Rewrite summation:

Exponential averaging:

Exponential Smoothing Coefficients

Use Of Exponential Averaging

Use Of Exponential Averaging

Shortest Remaining Time (SRT)

 Preemptive version of SPN

 Scheduler always chooses the process that has the shortest expected remaining processing time

 Risk of starvation of longer processes

 Should give superior turnaround time performance to SPN because a short job is given immediate preference to a running longer job

Highest Response Ratio Next (HRRN)

 Chooses next process with the greatest ratio

 Attractive because it accounts for the age of the process

 While shorter jobs are favored, aging without service increases the ratio so that a longer process will eventually get past competing shorter jobs

Feedback Scheduling  If we have no indication of length (service time) of processes, we

can’t use SPN, SRT or HRRN.

 But we can establish preference for shorter jobs by penalizing jobs that run longer.

 If we can’t focus on time remaining, let us focus on time spent so far.

 Use a preemptive (at time quantum) scheduling with a dynamic priority mechanism.

 Process enters at highest priority, every preemption reduces priority. Thus longer running processes “age” and become low priority, and new short processes don’t age enough before they finish execution.

Feedback Scheduling

Feedback Performance

Performance Comparison

Objective: Introduction to queuing theory and modeling to comparative analysis of scheduling (and other) algorithms.

Performance Comparison

 Any scheduling discipline that chooses the next item to be served independent of service time obeys the relationship:

Normalized Turnaround Time as a Function of Processor Utilization

Table 9.6

Formulas for Single-Server Queues with Two Priority Categories

Overall Normalized Response Time

Normalized Response Time for Shorter Processes

Normalized Response Time for Longer Processes

Results

Simulation

Alternative Scheduling Policies

Fair-Share Scheduling

Objective: Look at scheduling pools (processes organized as threads).

Fair-Share Scheduling  Scheduling decisions based on the process

sets

 Each user is assigned a share of the processor

 Objective is to monitor usage to give fewer resources to users who have had more than their fair share and more to those who have had less than their fair share

Fair-Share Scheduling

Fair-Share Scheduler

Traditional UNIX Scheduling

Objective: Understand the scheduling technique used in traditional UNIX systems.

Traditional UNIX Scheduling  Used in both SVR3 and 4.3 BSD UNIX

 these systems are primarily targeted at the time-sharing interactive environment

 Designed to provide good response time for interactive users while ensuring that low-priority background jobs do not starve

 Employs multilevel feedback using round robin within each of the priority queues

 Makes use of one-second preemption

 Priority is based on process type and execution history

Scheduling Formula

Bands  Used to optimize

access to block devices and to allow the operating system to respond quickly to system calls

 In decreasing order of priority, the bands are:

Example of Traditional UNIX Process Scheduling

Summary  The operating system must make three types of scheduling

decisions with respect to the execution of processes:  Long-term – determines when new processes are admitted to

the system  Medium-term – part of the swapping function and determines

when a program is brought into main memory so that it may be executed

 Short-term – determines which ready process will be executed next by the processor

 From a user’s point of view, response time is generally the most important characteristic of a system; from a system point of view, throughput or processor utilization is important

 Algorithms:

 FCFS, Round Robin, SPN, SRT, HRRN, Feedback