Process Scheduling

1. Scheduling queue

• Job queue – set of all processes in the system.
• Ready queue – set of all processes residing in main memory, ready and waiting to execute.
• Device queues – set of processes waiting for an I/O device.
• Process migration between the various queues.

2. Schedulers
Goal – mimic functionality of kernel threads
gain performance of user space threads . Avoids unnecessary user/kernel transitions. Kernel assigns virtual processors to each process lets runtime system allocate threads to processors.
Problem: Fundamental reliance on kernel (lower layer)
calling procedures in user space (higher layer)

3. Context Switch -To give each process on a multiprogrammed machine a fair share of the CPU, a hardware clock generates interrupts periodically. This allows the operating system to schedule all processes in main memory (using scheduling algorithm) to run on the CPU at equal intervals. Each time a clock interrupt occurs, the interrupt handler checks how much time the current running process has used. If it has used up its entire time slice, then the CPU scheduling algorithm (in kernel) picks a different process to run. Each switch of the CPU from one process to another is called a context switch.

Major Steps of Context Switching :

• The values of the CPU registers are saved in the process table of the process that was running just before the clock interrupt occurred.
• The registers are loaded from the process picked by the CPU scheduler to run next.

In a multiprogrammed uniprocessor computing system, context switches occur frequently enough that all processes appear to be running concurrently. If a process has more than one thread, the Operating System can use the context switching technique to schedule the threads so they appear to execute in parallel. This is the case if threads are implemented at the kernel level. Threads can also be implemented entirely at the user level in run-time libraries. Since in this case no thread scheduling is provided by the Operating System, it is the responsibility of the programmer to yield the CPU frequently enough in each thread so all threads in the process can make progress.

Action of Kernel to Context Switch Among Threads
The threads share a lot of resources with other peer threads belonging to the same process. So a context switch among threads for the same process is easy. It involves switch of register set, the program counter and the stack. It is relatively easy for the kernel to accomplished this task.

Action of kernel to Context Switch Among Processes
Context switches among processes are expensive. Before a process can be switched its process control block (PCB) must be saved by the operating system. The PCB consists of the following information:

• The process state.
• The program counter, PC.
• The values of the different registers.
• The CPU scheduling information for the process.
• Memory management information regarding the process.
• Possible accounting information for this process.
• I/O status information of the process.
• When the PCB of the currently executing process is saved the operating system loads the
• PCB of the next process that has to be run on CPU. This is a heavy task and it takes a lot of time.