Operating Systems and System Programming
Meti Dejene
tiimeekoo@gmail.com
Haramaya University
Chapter 2 - Processes and Threads
Overview
Early computers allowed only one program to be executed at a time.
This program had complete control of the system and had access to all the system’s
resources.
In contrast, contemporary computer systems allow multiple programs to be loaded into
memory and executed concurrently.
This evolution required firmer control and more compartmentalization of the various
programs.
That is why it is stated that, one of the services provided by an operating system is process
management.
Process
But what is process in the context of operating system?
A process is basically (a) a program in execution, (b) an instance of an executing
program, (c) an abstraction of a running program. (d) the unit of work in a modern
computing system.
For example,
In a given computer a user may have started (1) a video editing program and
instructed it to convert a one-hour video to a certain format (something that can take
hours) and (2) then gone off to surf the Web. (3) Meanwhile, a background process that
wakes up periodically to check for incoming email may have started running.
Thus we have (at least) three active processes.
Cont.
It is known that modern computers often do several things or execute multiple programs at
the same time. (AKA the concept of Multiprogramming)
Multiprogramming: The concurrent residency of more than one program in the main
memory to increase the CPU utilization and improves the throughput by reducing the CPU
idle time
But the question is how can this be achieved?
The answer is through process management.
Process management is one of the most important abstractions that operating systems
provide to manage all process related activities.
With process abstraction the OS supports the ability to have (pseudo) concurrent
operation even when there is only one CPU available.
Cont.
So, in any multiprogramming system, the CPU switches from process to process
quickly back and forth, running each for tens or hundreds of milliseconds.
While, strictly speaking, at any one instant the CPU is running only one process, in the
course of 1 second it may work on several of them, giving the illusion of parallelism.
This is known as pseudo-parallelism.
Overall, the OS is responsible for the following activities in connection with process
management:
creation and deletion of both user and system processes;
scheduling of processes;
provision of mechanisms for synchronization, communication, and deadlock handling
for processes.
Process Model
Associated with each process is its address space, a list of memory locations from
0 to some maximum, which the process can read and write.
The address space contains the executable program, the program’s data, and its
stack (which contains temporary data such as function parameters, return
addresses, and local variables).
Also associated with each process is a set of resources, commonly including
registers (including the program counter and stack pointer), a list of open files, lists
of related processes, and all the other information needed to run the program.
The program counter (PC) is a register that manages the memory address of
the instruction to be executed next.
Cont.
The memory layout of a process is typically
divided into multiple sections.
Text section - the executable code
Data section - global variables
Heap section - memory that is dynamically
allocated during program run time
Stack section - temporary data storage when
invoking functions (such as function parameters,
return addresses, and local variables)
Process Creation
Four principal events cause processes to be created:
1. System initialization.
When an operating system is booted, typically numerous processes are created.
Some of these are foreground processes, that is, processes that interact with (human)
users and perform work for them.
Others run in the background and are not associated with particular users, but
instead have some specific function.
Processes that stay in the background to handle some activity such as email, Web
pages, news, printing, and so on are called daemons.
In UNIX, the ps program can be used to list the running processes and in Windows, the
task manager can be used.
Cont.
2. Execution of a process-creation system call by a running process.
This is often when a running process issue system calls to create one or
more new processes to help it do its job.
3. A user request to create a new process.
In interactive systems, users can start a program by typing a command or (double)
clicking on an icon.
Taking either of these actions starts a new process and runs the selected program in it.
Cont.
4. Initiation of a batch job.
The last situation in which processes are created applies only to the batch systems
found on large mainframes.
Here users can submit batch jobs to the system and when the operating system decides
that it has the resources to run another job, it creates a new process and runs the next
job from the input queue in it.
In UNIX, there is only one system call to create a new process: fork.
In Windows, in contrast, a single Win32 function call, CreateProcess, handles both
process creation and loading the correct program into the new process.
Process Termination
After a process has been created, it starts running and does whatever its job is.
However, nothing lasts forever, not even processes. Sooner or later the new process will
terminate, usually due to one of the following conditions:
1. Normal exit (voluntary).
Most processes terminate because they have done their work.
This call is exit in UNIX and ExitProcess in Windows.
Screen-oriented programs also support voluntary termination.
Word processors, Internet browsers, and similar programs always have an icon or menu
item that the user can click to tell the process to remove any temporary files it has
open and then terminate .
Cont.
2. Error exit
The other reason for termination is when fatal is error caused by the process, often due to
a program bug.
Examples include
executing an illegal instruction, referencing nonexistent memory, or dividing by zero.
a user types a command tries to compile a program and no such file exists, the
compiler simply announces this fact and exits.
Cont.
3. Killed by another process (involuntary).
The fourth reason is when a process executes a system call telling the operating system to
kill some other process.
In UNIX this call is kill and the Win32 function is TerminateProcess.
Usually, such a system call can be invoked only by the parent of the process that is to be
terminated. (the killer must have the necessary authorization to do the kill)
A parent may terminate the execution of one of its children for a variety of reasons, such
as these:
The child has exceeded its usage of some of the resources that it has been allocated.
The task assigned to the child is no longer required.
The parent is exiting, and the OS does not allow a child to continue if its parent
terminates (cascading termination).
Process Hierarchies
When a process can create one or more other processes, the creating process is called
a parent process, and the new processes are called the children of that process (referred
to as child processes).
Each of these new processes may in turn create other processes.
This creates a tree of processes forming a process hierarchy.
Process State
As a process executes, it changes state.
Thus, a process may be in one of the following states:
New: The process is being created.
Running: Instructions are being executed.
Waiting/Blocked: The process is waiting for some event to occur (such as an I/O
completion or reception of a signal).
Ready: The process is waiting to be assigned to a processor.
Terminated: The process has finished execution.
Cont.
Implementation of Processes
The OS must know specific information about processes in order to manage, control
them and also to implement the process model.
For this purpose, the OS maintains a table, called the process table aka process
control blocks (PCB), with one entry per process.
So, each process is represented in the operating system by a PCB.
This entry contains each and every important information about the process
This is because, the information must be saved when the process is switched from
running to ready or blocked state so that it can be restarted later as if it had never
been stopped.
Cont.
Some of these important information include:
Process state: may be new, ready, running, waiting, halted, and so on.
Program counter: the address of the next instruction to be executed for this process.
CPU registers: These vary in number and type, depending on the computer architecture.
Along with the program counter, these are useful when an interrupt occurs, to allow the
process to be continued correctly afterward when it is rescheduled to run.
Accounting information: includes the amount of CPU and real time used, time limits,
account numbers, job or process numbers, and so on.
I/O status information: includes the list of I/O devices allocated to the process, a list of
open files, and so on.
Memory-management information: include such as the value of the base and limit
registers and the page tables, or the segment tables, and others.
Cont.
Context Switch
For multitasking, different circumstances may cause the operating system to
change a CPU from its current task and to run another task.
Switching the CPU to another process requires performing a state save of the
current process and a state restore of a different process.
This task is known as a context switch.
In short, it is to save the current context of the process running on the CPU so
that it can restore that context later, essentially suspending the process and
then resuming it.
THREADS
Threads are mini-processes running with in a process (also called Lightweight
processes).
They are lightweight than processes, as they are easier (i.e., faster) to create and
destroy than processes.
Threads in a process use the address space and resource of the process in which
they are running in.
Thus, different threads in a process are not as independent as different
processes and all threads in a process have exactly the same address space,
which means that they also share the same global variables.
Cont.
The term multithreading is also used to describe the situation of allowing multiple threads
in the same process.
When a multithreaded process is run on a single-CPU system, the threads take turns
running providing the illusion that the threads are running in parallel,
What threads add to the process model is to allow multiple executions to take place in
the same process environment.
Multiple threads of execution share a set of resources so that they can work together
closely to perform some task.
Another concept in threads is the pop-up thread system.
In pop-up thread system, the arrival of message causes the system to create a new
thread just to handle the message. Such a thread is called a pop-up thread.
Processes usually start with a single thread present and they can create new
threads by calling a library procedure such as thread create.
When a thread has finished its work, it can exit by calling a library procedure
thread exit.
In some thread systems, one thread can wait for a (specific) thread to exit by
calling a procedure, for example, thread join.
Another common thread call is thread yield, which allows a thread to voluntarily
give up the CPU to let another thread run.
There are several reasons (advantages) for having threads.
In applications where multiple activities are going on at once, by
decomposing the application into multiple sequential threads that run in quasi-
parallel, the programming model becomes simpler.
Since they are lighter weight than processes, they are easier (i.e., faster) to
create and destroy than processes.
Having threads allows multiple activities to overlap, thus speeding up the
application.
Thread Implementation
There are two main places to implement threads: in user space and the kernel.
1. Implementing Threads in User Space
The first method is to put the threads package entirely in user space. The kernel knows
nothing about them.
As far as the kernel is concerned, it is managing ordinary, single-threaded processes.
When threads are managed in user space, each process needs its own private
thread table to keep track of the threads in that process.
2. Implementing Threads in the Kernel
In here, the kernel know about and manage the threads.
There is no thread table in each process. Instead, the kernel has a thread table that keeps
track of all the threads in the system.
Cont.
InterProcess Communication
Processes frequently need to communicate with other processes and synchronize
their activities.
This may be because the output of the first process must be passed to the
second process, and so on down the line or related processes are cooperating
to get some job done .
This communication is called InterProcess Communication or IPC.
In other words, InterProcess communication (IPC) refers specifically to the
mechanisms an operating system provides to allow the processes to
communicate with each other.
Cont.
In IPC there are three issues to be considered in particular.
The first is how one process can pass information to another.
The second is making sure two or more processes do not get in each other’s
way.
The third concerns proper sequencing when dependencies are present:
If process A produces data and process B prints them, B has to wait until A
has produced some data before starting to print.
Cont.
There are two fundamental models of InterProcess communication: shared memory and
message passing.
1. The Message-Passing Model
In this model, communication takes place by means of messages exchanged between
the cooperating processes.
Message passing is useful for exchanging smaller amounts of data.
Since message-passing systems are typically implemented using system calls and thus
require the more time-consuming task of kernel intervention.
Message passing is also easier to implement in a distributed system than shared memory.
Cont.
1. The Shared-memory Model
In this model, a region of memory that is shared by the cooperating processes is
established.
Processes can then exchange information by reading and writing data to the shared
region.
Shared memory can be faster than message passing.
System calls are required only to establish shared memory regions.
Once shared memory is established, all accesses are treated as routine memory accesses.
Race Conditions
Processes that are working together may share some common resource(may be
main memory or it may be a shared file) that each one can read and write.
In such cases, if multiple processes happen to use some shared resource
concurrently at the same time it leads to undesirable situation.
Situations like this, where two or more processes are “racing” each other to
access/change the resource/data are called race conditions.
In such conditions, the final result depends on who runs precisely when.
Critical Regions
How do we avoid race conditions?
The key to preventing trouble in situations involving shared memory, shared files,
and shared everything else is to find some way to prohibit more than one
process from reading and writing the shared data at the same time.
Part of the time, a process is busy doing internal computations and other things that
do not lead to race conditions.
However, sometimes a process has to access shared memory or files, or do other
critical things that can lead to races.
In a process, that segment of the program where the shared memory is accessed is
called the critical region or critical section.
Mutual Exclusion
If we could arrange matters such that no two processes were ever in their
critical regions at the same time, we could avoid races.
This technique of concurrency control and process synchronization which states
that “no two processes can exist in the critical section at any given point of
time” is known as mutual exclusion.
Thus, while one process is busy updating shared memory in its critical region, no
other process will enter its critical region and cause trouble.
Cont.
So, overall there are four conditions to hold to avoid race conditions and have a good
solution:
1. No two processes may be simultaneously inside their critical regions.
2. No assumptions may be made about speeds or the number of CPUs.
3. No process running outside its critical region may block any process.
4. No process should have to wait forever to enter its critical region.
Cont.
Process Scheduling
Back in the old days of batch systems with input in the form of card images on a
magnetic tape, executing a task (the scheduling algorithm) was simple: just run the
next job on the tape.
When a computer is multi-programmed, it frequently has multiple processes or
threads competing for the CPU at the same time.
So, if only one CPU is available, a choice has to be made which process to run next
i.e., the process of removing an active task from the processor and replacing it with
a new one.
Cont.
The activity of the OS (particularly the process manager) that handles the removal of
the running process from the CPU and the selection of another process on the basis of
a particular strategy is known as process scheduling.
The part of the operating system that makes the choice is called the scheduler, and
the particular strategy or algorithm it uses for scheduling is called the scheduling
algorithm.
Process Behavior
Processes have different behavior and nearly all processes alternate bursts of
computing with (disk or network) I/O requests.
Some processes, such as the one in Fig. 2-39(a), spend most of their time computing,
while other processes, such as the one shown in Fig. 2-39(b), spend most of their time in
I/O operation.
The former are called compute-bound or CPU-bound; the latter are called I/O
bound.
Compute-bound processes typically have long CPU bursts and thus infrequent I/O
waits, whereas I/O-bound processes have short CPU bursts and thus frequent I/O waits.
CPU burst is the amount of time the process uses the processor.
Cont.
When to Schedule
Situations in which scheduling is needed are:
First, when a new process is created, a decision needs to be made whether to
run the parent process or the child process.
Second, a scheduling decision must be made when a process exits.
That process can no longer run (since it no longer exists), so some other
process must be chosen from the set of ready processes.
Third, when a process blocks on I/O or for some other reason another process
has to be selected to run.
Cont.
Fourth, when an I/O interrupt occurs, a scheduling decision may be made.
If the interrupt came from an I/O device that has now completed its work,
some process that was blocked waiting for the I/O may now be ready to
run.
It is up to the scheduler to decide whether to run the newly ready process,
the process that was running at the time of the interrupt, or some third
process.
Categories of Scheduling Algorithms
Scheduling algorithms can be divided into two major categories with respect to
how they deal with clock interrupts.
I. A non-preemptive scheduling algorithm picks a process to run and then just lets it
run until it blocks (either on I/O or waiting for another process) or voluntarily
releases the CPU.
Even if it runs for many hours, it will not be forcibly suspended.
II. A preemptive scheduling algorithm, in contrast, picks a process and lets it run for a
maximum of some fixed time.
If it is still running at the end of the time interval, it is suspended and the
scheduler picks another process to run (if one is available).
Cont.
In different environments different scheduling algorithms are needed. Why?
Because different application areas (and different kinds of operating
systems) have different goals and thus what the scheduler should optimize
for is not the same in all systems.
In batch systems, there are no users impatiently waiting at their terminals for a
quick response to a short request.
Consequently, non-preemptive algorithms, or preemptive algorithms with
long time periods for each process, are often acceptable.
Cont.
In an environment with interactive users, preemption is essential to keep one
process from hogging the CPU and denying service to the others.
In systems with real-time constraints, preemptive scheduling is most commonly
used to accommodate high priority and time-critical tasks.
But preemption is sometimes not needed because the processes know that
they may not run for long periods of time and usually do their work and block
quickly.
So, it can also be designed by combining both preemptive and non-
preemptive scheduling.
Scheduling Algorithm Goals
Cont.
Throughput is the number of jobs per hour that the system completes.
Turnaround time is the statistically average time from the moment that a batch
job is submitted until the moment it is completed.
It measures how long the average user has to wait for the output.
The rule is: Small is Beautiful.
Response time, that is, the time between issuing a command and getting the
result.
Commonly Known Scheduling Algorithms
1. First-Come, First-Served (FSFS)
This is the simplest of all non-preemptive scheduling algorithms.
With this algorithm, processes are assigned the CPU in the order they request it.
Basically, there is a single queue of ready processes.
When the first job enters the system from the outside, it is started immediately and
allowed to run as long as it wants to.
It is not interrupted because it has run too long.
As other jobs come in, they are put onto the end of the queue.
When the running process blocks, the first process on the queue is run next.
When a blocked process becomes ready, like a newly arrived job, it is put on the end of
the queue, behind all waiting processes.
The pros of this algorithm is that it is easy to understand and to program; However it lacks
efficiency.
2. Shortest Job First
This is another non-preemptive batch algorithm that assumes the run times are
known in advance.
When several equally important jobs are sitting in the input queue waiting to be
started, the scheduler picks the shortest job first.
It is worth pointing out that shortest job first is optimal only when all the jobs are
available simultaneously.
3. Shortest Remaining Time Next
This is a preemptive version of shortest job first.
With this algorithm, the scheduler always chooses the process whose remaining run
time is the shortest.
Again here, the run time has to be known in advance.
When a new job arrives, its total time is compared to the current process’
remaining time.
If the new job needs less time to finish than the current process, the current
process is suspended and the new job started.
This scheme allows new short jobs to get good service.
The problem is, it may lead to starvation of long jobs.
4. Round-Robin Scheduling
Round robin is one of the oldest, simplest, fairest, and most widely used algorithms.
Each process is assigned a time interval, called its quantum, during which it is
allowed to run.
The implicit assumption that all processes are equally important.
If the process is still running at the end of the quantum, the CPU is preempted and
given to another process.
The only really interesting issue with round robin is the length of the quantum.
Setting the quantum too short causes too many process switches and lowers the
CPU efficiency, but setting it too long may cause poor response to short
interactive requests.
5. Priority Scheduling
This is for cases where there may be multiple processes and some of them more important
than others based on some factor.
This need to take external factors into account leads to priority scheduling.
The basic idea behind priority scheduling is:
Each process is assigned a priority, and the runnable process with the highest priority is
allowed to run.
To prevent high-priority processes from running indefinitely, alternatively, each process
may be assigned a maximum time quantum that it is allowed to run.
When this quantum is used up, the next-highest-priority process is given a chance to run.
It is often convenient to group processes into priority classes and use priority scheduling
among the classes but round-robin scheduling within each class.
6. Multi-level Queues
This is a different variation of priority scheduling.
Unlike in priority scheduling which puts all processes in the same queue, this
algorithm uses multiple priority queues separately for processes with common
characteristics.
Each queue will be assigned a quantum and can have its own scheduling
algorithms.
Then processes in the highest priority class were run for one quantum, processes in
the next-highest class were run for two quanta, processes in the next one were run
for four quanta, etc.
Whenever a process used up all the quanta allocated to it, it was moved down
one class.
7. Guaranteed Scheduling
This is a proportionate scheduling which aims to ensure a fair allocation of
CPU time among processes.
Guaranteed scheduling attempts to evenly split CPU time among processes
to maximize fairness.
So, if we have n processes, then we shouldn’t ever allow any process to
exceed 1/n fraction of the total runtime.
8. Lottery Scheduling
The basic idea here is to give processes lottery tickets for various system
resources, such as CPU time.
Whenever a scheduling decision has to be made, a lottery ticket is chosen at
random, and the process holding that ticket gets the resource.
9. Fair-Share Scheduling
So far we have assumed that each process is scheduled without regard to who
its owner is.
Fair share scheduling takes into account which user owns a process before
scheduling it.
In this model, each user is allocated some fraction of the CPU and the
scheduler picks processes in such a way as to enforce it.
Thus, if two users have each been promised 50% of the CPU, they will each get
that, no matter how many processes they have in existence.
Scheduling Real-time Systems
Real-time scheduling algorithms are grouped into two primary categories: Static
and Dynamic.
With static scheduling,
decisions about what to run next are not made in real time instead scheduling
decisions are made before the system starts running.
This works only when there is perfect information available in advance about
the work to be done and the deadlines that have to be met.
It can be achieved by feeding the system a pre-made list of processes and
the order in which they should run or by building scheduling decisions into our
code by means of various control mechanisms.
Cont.
With dynamic real-time scheduling, decisions about what to run next are made
in real time.
Scheduling decisions are made depending on task deadline and task
priority.
Earliest Deadline First scheduling (EDF) is one of dynamic real-time scheduling.
