Chapter 4: Processor Management, Flynn and McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Co. (1997)

Lesson A: Job Scheduling Versus Process Scheduling, Process Scheduler, Job and Process Status, Process Control Blocks, PCBs and Queueing, Process Scheduling Policies, Process Scheduling Algorithms, First Come First Served

Problems 1, 2, 3, 4, 5, 6, 11 or 13

Problem 1.  What information about a job needs to be kept in the Process Control Block? 

Answer:  All information needed to restart a suspended process is required to be kept in the Process Control Block (PCB).  Additional information needed for accounting and performance assessment is nice to keep in the PCB.

The PCB includes information from Figure 4.3 on page 80.

Problem 2:  What information about a process needs to be saved, changed, or updated when context switching takes place?

Answer:  All information except the Process Identification block must be updated and saved when a process is moved from the running state.  At each state change, the process Status block must be updated and saved.  When a process is returned to the Running state, at least the register contents, the program counter, and the resources must be restored. 

Problem 3:  Five jobs are in the READY queue waiting to be processed.  Their estimated CPU cycles are as follows:  10, 3, 5, 6, and 2.  Using SJN, in what order should they be processed to minimize average waiting time?

Answer:  2, 3, 5, 6, 10

Problem 4.  A job running in a system, with variable time quantums per queue, needs 30 milliseconds to run to completion.  If the first queue has a time quantum of 5 milliseconds and each queue thereafter has a time quantum that is twice as large as the previous one, how many times will the job be interrupted and on which queue will it finish its execution?

Examine the low order quanta queues:  5 x 2⁰ + 5 x 2¹ + 5 x 2²  = 5 + 10 + 20 = 35

The job will be interrupted twice, and will finish on the 20 millisecond queue.

Problem 5.  The following diagram (adapted from Madnick & Donovan, 1974) is a simplified process model of you, in which there are only two states: sleeping and waking.  You make the transition from waking to sleeping when you are tired, and from sleeping to waking when the alarm clock goes off.

1. Add three more states to the diagram (for example, one might be eating).
2. State all of the possible transitions among the five states.

States are labeled with letters.  Transitions are labeled with numbers.   In the table, a pair of letters denotes a transition from the first state to the second state.  Order is significant. 

What constitutes a possible transition?  If you mean all possible linkages (direction is important), then not ALL possible transitions are shown above.  Each state could possibly link to every other state.  5 states could transition to each of the other 4 states, yielding 20 possible transitions.  These are:

An analyst attempts to discover all possible transitions when observing human processes.  The system architect defines the possible system model transitions when the system is designed.  The transitions in the table correspond to the transitions shown in the state diagram.

Operating systems are modeled as state diagrams in simulations.   Simulation languages exist to make setting up and running a simulation easy.  They include random event generators and statistics software.

Problem 6.  What is the relationship between turn-around time, CPU cycle time, and waiting time?  Write an equation to express this relationship, if possible.

T = Turn-Around Time: The time required to execute a job and return output to the user.

C = CPU Cycle Time (Running Queue Time):  The amount of time the CPU spends in executing a job.  It may also include the overhead required to service a job, such as saving the process control block during context switching.

H = Hold Queue Time:  The amount of time waiting for initial allocation of resources necessary to run the job.

R_init = Initial Ready Queue Time:

R = Ready Queue Time.  This includes R_init.  

W = Waiting Queue Time

Z = Waiting Time:  The amount of time a process spends waiting for resources, primarily I/O devices.  A job in the "Hold" queue is waiting for system resources to become available.  A job in the "Ready" queue is waiting for the CPU to become available.  A job in the "Waiting" queue is waiting for response from devices that must be obtained before the job can productively use the CPU again.

F = Finished Queue Time:  Time between job completion and customer retrieval of job results.

Which actions and states you include in these times depends on your analysis goals.  The customer has a different interest than the system administrator or the computer engineer.

The customer is interested in:  T  =  C + Z = H + R + C + W + F

The system administrator concerned with CPU utilization an job throughput is interested in:

T = R + C + W

The text's answer book says that T = C + W for a simple system.

Problem 11.  In a single-user dedicated system, such as a personal computer, it's easy for the user to determine when a job is caught in an infinite loop.  The typical solution to this problem is for the user to manually intervene and terminate the job.  What mechanism would you implement in the Process Scheduler to automate the termination of a job that's in an infinite loop?  Take into account jobs that legitimately use large amounts of CPU time; for example, one "finding the first 10,000 prime numbers."

Require the programmer to assign a time and resource classification to the job being submitted.  Each classification screens to ensure that maximum resources for that class are not exceeded, and does not permit the job to run longer than the maximum time allowed for that class.  In addition, require a time estimate when the job is submitted.  Terminate the job when the job estimated time or job class time is exceeded.  Programmers developing new code usually like the class system.  It gives the programmer simple protection from the consequences of a bug. 

Keep statistics on the CPU time used per account.  When a job exceeds 2 standard deviations from the average time used by that account, place the job on hold until the customer is contacted, or follow directions provided by the customer in advance.

For the interactive customer that is using lots of CPU time, check the customer profile.  Check on system security issues, such as file accesses (including accounting files), use of privileged instructions, etc.  Long jobs submitted remotely are usually submitted as batch jobs, not interactive.  Exceptions: interactive simulations.

Problem 13.  Using the process state diagrams of Figure 4.2, explain why there's no transition:

1. From the READY state to the WAITING state.

A job in the WAITING state is waiting for peripheral device response which must be received before the CPU can effectively be used again.  A process in the READY queue is ready in all aspects to make effective use of the CPU.  If a job in the READY state cannot proceed because a required device fails, it should be sent back to the HOLD state, not the WAITING state.

2. From the WAITING state to the RUNNING state.

The Process Scheduler selects processes from the READY state for the CPU.  Bypassing the READY queue would make process management impossible.