Operating Systems Day 05

Multiprogramming: a technique that allows a single processor to process several programs residing simultaneously in main memory and interleaving their execution by overlapping I/O requests with CPU requests.

Nonpreemptive scheduling policy: a job scheduling strategy that functions without external interrupts so that once a job captures the processor and begins execution, it remains in the running state uninterrupted until it issues an I/O request or it’s finished.

Preemptive scheduling policy: any process scheduling strategy that, based on predetermined policies, interrupts the processing of a job and transfers the CPU to another job. It is widely used in time-sharing environments.

Nonpreemptive scheduling policy includes the following process scheduling schemes:

1. First Come First Serve (FCFS)
2. Shortest Job Next (SJN)
3. Priority scheduling

Preemptive scheduling policy includes the following process scheduling schemes:

1. Shortest Remaining Time (SRT)
2. Round Robin
3. Round Robin with Priority

The Operating System tracks jobs by means of Process Control Blocks (PCB’s). Each process has its own PCB.

Process Control Block (PCB) components

• Process identification (PID)
• Unique 
• Process status
• Status (HOLD, READY, RUNNING, WAITING)
• Process state
• Process status word register contents, main memory info (segment table, page table), resources (files), process priority
• Accounting
• Billing and performance measurements
• CPU time, total time, memory occupancy, I/O operations, number of input records read, etc.

Multiple-level queues are used for both Nonpreemptive and Preemptive policies.

Interrupts usually temporarily suspend execution of a process

The following figure shows the queuing paths from HOLD to FINISHED process states.

Good process scheduling policy criteria are

1. Maximise throughput: Run as many jobs as possible
2. Minimise response time: Quickly handle interactive requests
3. Minimise turnaround time: Move job through system quickly
4. Minimise waiting time: Move job out of READY queue quickly
5. Maximise CPU efficiency: Keep CPU busy 100 percent of time
6. Ensure fairness for all jobs: Give every job equal CPU and I/O time

References

1. McHoes, A., & Flynn, I.M. (2008). Understanding operating systems (5th ed.). CENGAGE Learning.
2. Melbourne Institute of Technology (Semester 1, 2012). BN104 Operating Systems Lecture Notes.