Thursday, January 10, 2008

Guide to Operation System Part 6

Scheduling
- Scheduling is the task of managing CPU sharing among a pool of ready processes or threads and it is only possible if context switching facility exist.

- A Scheduler chooses a ready thread to allocate to the CPU when available.

- A Schedule Policy determines when it is time for a thread to be removed from the CPU and allocate it to another thread.

- The Scheduling Mechanism determines how process manager can determine it is time to interrupt the CPU and how thread can be allocated to and removed from CPU.

Scheduling Mechanism
Consist of 3 Logical Parts:
- Enqueuer: help to lineup process (in ready list)
- Dispatcher: try to bring the process to CPU so that the process can start executing
- Context Switcher: save state of old process and switch to a new process

Invoking the Scheduler (A mechanism to call the scheduler)
- Voluntary Call: Process blocks itself and calls the scheduler
- Involuntary Call: External force(interrupt) blocks the process and calls the scheduler

Sharing of CPU
- Voluntary CPU Sharing: also known as non-preemptive (not forced) scheduling
o Process voluntarily release the CPU to be reallocated to other process, usually happens after the process s ends or process executes a system call to release CPU (e.g. yield machine instruction).

- Involuntary CPU Sharing: also known as preemptive (forced) scheduling
o Uses interrupt system to periodically force an interruption of any process’s execution. Interrupt is generated by an internal timer, which the timer is usually programmable by software so that the Interval (Time Slice) can be adjusted by the OS.

Scheduling Performance
If a process continually gets ignored by the scheduler, even though it is ready, this phenomenon is called Starvation.

Non-preemptive Scheduler
- First-Come-First-Served (FCFS): Scheduler picks up first job to arrive in the ready list.
- Shortest Job First (SJF): Scheduler picks up shortest job to arrive in the ready list.
- Priority (PR): Scheduler picks up the job with highest priority in the ready list.

Preemptive Scheduler
- Shortest Job First (SJF): Scheduler picks up shortest job to arrive in the ready list.
- Priority (PR): Scheduler picks up the job with highest priority in the ready list.
- Round Robin (RR): Scheduler gives a short Interval (Time Slice) to each job.
- Multi-Level Queues: Implement multiple queues with different scheduling policies.

Posted by Zack at 10:29 PM