QMCS 360 Class Notes # 16	Dr. Rick Smith Quantitative Methods and Computer Science
Dr. Smith Home | Research | Classes | Blackboard | Cryptosmith | QMCS Home | UST A-Z | UST Home last update: Thursday, November 10, 2005

Rest of Semester

Scheduling

Long term scheduling

Medium term scheduling

Short term scheduling

I/O scheduling

Differences - think in terms of the 5+ state process model

Long term scheduling

Deciding whether to create/start a job or not

Is system already too busy?

DOes it need resources that it just won't get for a while yet?

How much multiprogramming do you want in the system?

Interactive long term scheduling: is my desktop too busy and cluttered with activity already?

Medium term scheduling

To swap or not to swap: that is the question

Deciding whether to let the guy's working set migrate onto the paging file

Also a question of how much multiprogramming you want/need for full system utilization

Short term scheduling

Keep the processor busy and give each process their fair share of processing

I/O scheduling and queueing theory

The ugly duckling of this chapter - doesn't quite fit

The only reason -all- scheduling is in one chapter is so they can talk about queueing theory

I'm not a subscriber to queueing theory - I did it in grad school for a year, and I don't hold with it

I'll talk about it later on - the chapter really ignores it anyway.

So if the whole thing is about process scheduling after all, fergoshsakes why didn't we talk about it while spun up to deal with processes and process states???

The Policy Question - How do we choose the next process to run?

From the Book:

User-oriented performance criteria

Turnaround time - how long to finish a job

Response time - for interactive tasks: minimize the time between a user command and a system response. The response might not be completion.

Deadlines - specific completion time for a job

Other user-oriented criteria

Predictability - a given job should always take about the same amount of time

System-oriented performance criteria

Throughput - maximize the number of processes completed per unit time

Processor utilization - maximize the amount of time the processor is busy

Other system-oriented criteria

Fairness - Processes should be treated the same, absent other system- or user-level guidance to the contrary

Fairness II: Avoid Starvation - no process should starve

Enforce Priorities - higher priority processes should get more resources than lower priority processes

"Rightful Share" - a system-oriented criterion (NOT in the book)

Customers may "buy" a certain percentage of the processor time

If their processes are falling below their percentage, their priority goes up

Implementation is called a "Pie Slice" scheduler

Technical parameters in scheduling

w = time a job spends in the system, waiting or running - OR - just the time waiting (depends on page in the text!!)

e = time spent actually executing

s = total service time that the job will require (may be an estimate provided by the user)

TAT - Turnaround Time = total time a job spends in the system from start to finish

q = time quantum used for execution

Alternative Scheduling Disciplines

First Come First Served - duh

Round Robin

Shortest Process Next

Shortest Remaining Time

Highest Response Ratio Next - prefers processes that are shorter or ignored

I/O scheduling

Tailored to the weirdness of the device

Disks spin and have heads: sort the I/O into the proper physical order for the device

Printers can't be preempted, so it's either FIFO or prioritized FIFO.

Homework Problem/Project

Software simulation of Problems 9.1 and 9.2

Break the task into 6 parts: 1 "simulation driver" and 5 "schedulers"