Page 424 - DCAP103_Principle of operating system

Unit 14: Case Study of Linux Operating System

The Linux thread model raises another difficulty. UNIX systems associate a single PID with a Notes
process, independent of whether it is single- or multi-threaded. In order to be compatible with
other UNIX systems, Linux distinguishes between a process identifier (PID) and a task identifier
(TID). Both fields are stored in the task structure. When clone is used to create a new process
which shares nothing with its creator, PID is set to a new value, otherwise, the task receives a
new TID, but inherits the PID. In this manner all threads in a process will receive the same PID
as the first thread in the process.
14.2.5 Scheduling in Linux

We will now look at the Linux scheduling algorithm. To start with, Linux threads are kernel
threads, so scheduling is based on threads, not processes. Linux distinguishes three classes of
threads for scheduling purposes:
1. Real-time FIFO.

2. Real-time round robin.
3. Timesharing.
Real-time FIFO threads are the highest priority and are not preemptable except by a newly-
readied real-time FIFO thread with higher priority. Real-time round-robin threads are the same
as real-time FIFO threads except that they have time quanta associated with them, and are
preemptable by the clock. If multiple real-time round-robin threads are ready, each one is run
for its quantum, after which it goes to the end of the list of real-time round-robin threads. None
of these classes is actually real time in any sense. Deadlines cannot be specified and guarantees
are not given. These classes are simply higher priority than threads in the standard timesharing
class. The reason Linux calls them real time is that Linux is conformant to the P1003.4 standard
(‘’real-time’’ extensions to UNIX) which uses those names. The real time threads are internally
represented with priority levels from 0 to 99, 0 being the highest and 99 the lowest real-time
priority level. The conventional, non-real-time threads are scheduled according to the following
algorithm. Internally, the non-real-time threads are associated with priority levels from 100 to
139, i.e., Linux internally distinguishes among 140 priority levels (for real-time and non-real-
time tasks). Like for the real-time round-robin threads, Linux associates time quantum values
for each of the non-real time priority levels. The quantum is a number of clock ticks the thread
may continue to run for. In the current Linux version, the clock runs at 1000Hz and each tick
is 1ms, which is called a jiffy. Like most UNIX systems, Linux associates a nice value with
each thread. The default is 0 but this can be changed using the nice (value) system call, where
value ranges from –20 to +19. This value determines the static priority of each thread. A user
computing ?to a billion places in the background might put this call in his program to be nice to
the other users. Only the system administrator may ask for better than normal service (meaning
values from ?20 to ?1). Deducing the reason for this rule is left as an exercise for the reader.
A key data structure used by the Linux scheduler is a runqueue. A runqueue is associated
with each CPU in the system, and among other information, it maintains two arrays, active and
expired. As shown in Figure 14.10, each of these fields is a pointer to an array of 140 list heads,
each corresponding to a different priority.
The list head points to a doubly-linked list of processes at a given priority. The basic
operation of the scheduler can be described as follows. The scheduler selects a task from
the highest priority active array. If that task’s timeslice (quantum) expires, it is moved to
an expired list (potentially at a different priority level). If the task blocks, for instance to
wait for an I/O event, before its timeslice expires, once the event occurs and its execution
can resume, it is placed back on the original active array, and its timeslice is decremented
to reflect the CPU time it already consumed. Once its timeslice is fully exhausted, it will
also be placed on an expired array. When there are no more tasks in any of the active

LOVELY PROFESSIONAL UNIVERSITY 417