Page 260 - DCAP403_Operating System

Unit 13: Case Study: Linux

getting from user mode into system mode and back again. User mode has far less privileges than Notes
system mode. Each time a process makes a system call it swaps from user mode to system mode
and continues executing. At this point the kernel is executing on behalf of the process. In Linux,
processes do not preempt the current, running process, they cannot stop it from running so that
they can run. Each process decides to relinquish the CPU that it is running on when it has to wait
for some system event. For example, a process may have to wait for a character to be read from

a file. This waiting happens within the system call, in system mode; the process used a library

function to open and read the file and it, in turn made system calls to read bytes from the open

file. In this case the waiting process will be suspended and another, more deserving process will
be chosen to run.
Processes are always making system calls and so may often need to wait. Even so, if a process
executes until it waits then it still might use a disproportionate amount of CPU time and so
Linux uses pre-emptive scheduling. In this scheme, each process is allowed to run for a small
amount of time, 200ms, and, when this time has expired another process is selected to run and
the original process is made to wait for a little while until it can run again. This small amount of
time is known as a time-slice.
It is the scheduler that must select the most deserving process to run out of all of the runnable
processes in the system.
A runnable process is one which is waiting only for a CPU to run on. Linux uses a reasonably
simple priority based scheduling algorithm to choose between the current processes in the system.
When it has chosen a new process to run it saves the state of the current process, the processor
specific registers and other context being saved in the processes task_struct data structure. It then

restores the state of the new process (again this is processor specific) to run and gives control of

the system to that process. For the scheduler to fairly allocate CPU time between the runnable
processes in the system it keeps information in the task_struct for each process:
Policy: This is the scheduling policy that will be applied to this process. There are two types
of Linux process, normal and real time. Real time processes have a higher priority than all of
the other processes. If there is a real time process ready to run, it will always run fi rst. Real
time processes may have two types of policy, round robin and fi rst in first out. In round robin

scheduling, each runnable real time process is run in turn and in fi rst in, first out scheduling
each runnable process is run in the order that it is in on the run queue and that order is never
changed.
Priority: This is the priority that the scheduler will give to this process. It is also the amount of

time (in jiffies) that this process will run for when it is allowed to run. You can alter the priority
of a process by means of system calls and the renice command.
rt_priority: Linux supports real time processes and these are scheduled to have a higher priority
than all of the other non-real time processes in system. This field allows the scheduler to give

each real time process a relative priority. The priority of a real time processes can be altered using
system calls.

Counter: This is the amount of time (in jiffi es) that this process is allowed to run for. It is set to

priority when the process is first run and is decremented each clock tick.
The scheduler is run from several places within the kernel. It is run after putting the current
process onto a wait queue and it may also be run at the end of a system call, just before a process
is returned to process mode from system mode. One reason that it might need to run is because
the system timer has just set the current processes counter to zero. Each time the scheduler is run
it does the following:
Kernel work: The scheduler runs the bottom half handlers and processes the scheduler task
queue.

LOVELY PROFESSIONAL UNIVERSITY 253