Page 261 - DCAP403_Operating System

Operating System

Notes Current process: The current process must be processed before another process can be selected
to run.
1. If the scheduling policy of the current processes is round robin then it is put onto the back
of the run queue.
2. If the task is INTERRUPTIBLE and it has received a signal since the last time it was
scheduled then its state becomes RUNNING.
3. If the current process has timed out, then its state becomes RUNNING.
4. If the current process is RUNNING then it will remain in that state.
Processes that were neither RUNNING nor INTERRUPTIBLE are removed from the run queue.
This means that they will not be considered for running when the scheduler looks for the most
deserving process to run.
Process selection: The scheduler looks through the processes on the run queue looking for
the most deserving process to run. If there are any real time processes (those with a real time
scheduling policy) then those will get a higher weighting than ordinary processes. The weight for
a normal process is its counter but for a real time process it is counter plus 1000. This means that
if there are any runnable real time processes in the system then these will always be run before
any normal runnable processes. The current process, which has consumed some of its time-slice
(its counter has been decremented) is at a disadvantage if there are other processes with equal
priority in the system; that is as it should be. If several processes have the same priority, the one
nearest the front of the run queue is chosen. The current process will get put onto the back of the
run queue. In a balanced system with many processes of the same priority, each one will run in
turn. This is known as Round Robin scheduling. However, as processes wait for resources, their
run order tends to get moved around.
Swap processes: If the most deserving process to run is not the current process, then the current
process must be suspended and the new one made to run. When a process is running it is using
the registers and physical memory of the CPU and of the system. Each time it calls a routine
it passes its arguments in registers and may stack saved values such as the address to return
to in the calling routine. So, when the scheduler is running it is running in the context of the
current process. It will be in a privileged mode, kernel mode, but it is still the current process
that is running. When that process comes to be suspended, all of its machine state, including
the program counter (PC) and all of the processor’s registers, must be saved in the processes
task_struct data structure. Then, all of the machine state for the new process must be loaded. This
is a system dependent operation, no CPUs do this in quite the same way but there is usually some
hardware assistance for this act.
This swapping of process context takes place at the end of the scheduler. The saved context for
the previous process is, therefore, a snapshot of the hardware context of the system as it was for
this process at the end of the scheduler. Equally, when the context of the new process is loaded, it
too will be a snapshot of the way things were at the end of the scheduler, including this processes
program counter and register contents.
If the previous process or the new current process uses virtual memory then the system’s page
table entries may need to be updated. Again, this action is architecture specifi c. Processors like
the Alpha AXP, which use Translation Look-aside Tables or cached Page Table Entries, must

flush those cached table entries that belonged to the previous process.
Scheduling in Multiprocessor Systems

Systems with multiple CPUs are reasonably rare in the Linux world but a lot of work has already
gone into making Linux an SMP (Symmetric Multi-Processing) operating system. That is, one that
is capable of evenly balancing work between the CPUs in the system. Nowhere is this balancing
of work more apparent than in the scheduler.

254 LOVELY PROFESSIONAL UNIVERSITY