INTRODUCTION TO OPERTATING SYSTEMS

1.0 What is an Operating System?

The 1960’s definition of an operating system is “the software that controls the hardware”.
However, today, due to microcode we need a better definition. We see an operating
system as the programs that make the hardware useable. In brief, an operating system is
the set of programs that controls a computer. Some examples of operating systems are
UNIX, MS-DOS, MS-Windows, Windows/NT, Chicago, OS/2, MacOS, VMS, MVS,
and VM, DOS, Symbian OS, Windows 95 / 98 / Me / , DOS, IBM , Linux OS, Windows

Server 2003, Virtualization, Macintosh, Windows Server 2008, Windows 2000,

Professional , Windows Vista, Palm OS, Windows 2000 Server, Windows XP, Sun
Solaris and Windows 7.

Controlling the computer involves software at several levels. We will differentiate kernel
services, library services, and application-level services, all of which are part of the
operating system. Processes run Applications, which are linked together with libraries
that perform standard services. The kernel supports the processes by providing a path to
the peripheral devices. The kernel responds to service calls from the processes and
interrupts from the devices. The core of the operating system is the kernel, a control
program that functions in privileged state (an execution context that allows all hardware
instructions to be executed), reacting to interrupts from external devices and to service
requests and traps from processes. Generally, the kernel is a permanent resident of the
computer. It creates and terminates processes and responds to their request for service.

Operating Systems are resource managers. The main resource is computer hardware in
the form of processors, storage, input/output devices, communication devices, and data.
Some of the operating system functions are: implementing the user interface, sharing
hardware among users, allowing users to share data among themselves, preventing users
from interfering with one another, scheduling resources among users, facilitating
input/output, recovering from errors, accounting for resource usage, facilitating parallel
operations, organizing data for secure and rapid access, and handling network
communications.

Objectives of Operating Systems

Modern Operating systems generally have following three major goals. Operating
systems generally accomplish these goals by running processes in low privilege and
providing service calls that invoke the operating system kernel in high-privilege state.

 To hide details of hardware by creating abstraction

an abstraction is software that hides lower level details and provides a set of
higher-level functions. An operating system transforms the physical world of
devices, instructions, memory, and time into virtual world that is the result of

1
 abstractions built by the operating system. There are several reasons for
abstraction.
First, the code needed to control peripheral devices is not standardized. Operating
systems provide subroutines called device drivers that perform operations on
behalf of programs for example, input/output operations.
Second, the operating system introduces new functions as it abstracts the
hardware. For instance, operating system introduces the file abstraction so that
programs do not have to deal with disks.
Third, the operating system transforms the computer hardware into multiple
virtual computers, each belonging to a different program. Each program that is
running is called a process. Each process views the hardware through the lens of
abstraction.
Fourth, the operating system can enforce security through abstraction.

 To allocate resources to processes (Manage resources)

An operating system controls how processes (the active agents) may access
resources (passive entities).

 Provide a pleasant and effective user interface

The user interacts with the operating systems through the user interface and
usually interested in the “look and feel” of the operating system. The most
important components of the user interface are the command interpreter, the file
system, on-line help, and application integration. The recent trend has been
toward increasingly integrated graphical user interfaces that encompass the
activities of multiple processes on networks of computers.

One can view Operating Systems from two points of views: Resource manager and
Extended machines. Form Resource manager point of view Operating Systems manage
the different parts of the system efficiently and from extended machines point of view
Operating Systems provide a virtual machine to users that is more convenient to use. The
structurally Operating Systems can be design as a monolithic system, a hierarchy of
layers, a virtual machine system, an exokernel, or using the client-server model. The
basic concepts of Operating Systems are processes, memory management, I/O
management, the file systems, and security.

1.1 History of Operating Systems

Historically operating systems have been tightly related to the computer architecture, it is
good idea to study the history of operating systems from the architecture of the computers
on which they run.

2
Operating systems have evolved through a number of distinct phases or generations
which corresponds roughly to the decades.

The 1940's - First Generations

The earliest electronic digital computers had no operating systems. Machines of the time
were so primitive that programs were often entered one bit at time on rows of mechanical
switches (plug boards). Programming languages were unknown (not even assembly
languages). Operating systems were unheard of.

The 1950's - Second Generation

By the early 1950's, the routine had improved somewhat with the introduction of punch
cards. The General Motors Research Laboratories implemented the first operating
systems in early 1950's for their IBM 701. The system of the 50's generally ran one job at
a time. These were called single-stream batch processing systems because programs and
data were submitted in groups or batches.

The 1960's - Third Generation

The systems of the 1960's were also batch processing systems, but they were able to take
better advantage of the computer's resources by running several jobs at once. So
operating systems designers developed the concept of multiprogramming in which
several jobs are in main memory at once; a processor is switched from job to job as
needed to keep several jobs advancing while keeping the peripheral devices in use.

For example, on the system with no multiprogramming, when the current job paused to
wait for other I/O operation to complete, the CPU simply sat idle until the I/O finished.
The solution for this problem that evolved was to partition memory into several pieces,
with a different job in each partition. While one job was waiting for I/O to complete,
another job could be using the CPU.

Another major feature in third-generation operating system was the technique called
spooling (simultaneous peripheral operations on line). In spooling, a high-speed device
like a disk interposed between a running program and a low-speed device involved with
the program in input/output. Instead of writing directly to a printer, for example, outputs
are written to the disk. Programs can run to completion faster, and other programs can be
initiated sooner when the printer becomes available, the outputs may be printed.

Note that spooling technique is much like thread being spun to a spool so that it may be
later be unwound as needed.

Another feature present in this generation was time-sharing technique, a variant of

multiprogramming technique, in which each user has an on-line (i.e., directly connected)
terminal. Because the user is present and interacting with the computer, the computer
system must respond quickly to user requests, otherwise user productivity could suffer.

3
Timesharing systems were developed to multiprogram large number of simultaneous
interactive users.

Fourth Generation

With the development of LSI (Large Scale Integration) circuits, chips, operating system
entered in the personal computer and the workstation age. Microprocessor technology
evolved to the point that it becomes possible to build desktop computers as powerful as
the mainframes of the 1970s. Two operating systems have dominated the personal
computer scene: MS-DOS, written by Microsoft, Inc. for the IBM PC and other machines
using the Intel 8088 CPU and its successors, and UNIX, which is dominant on the large
personal computers using the Motorola 6899 CPU family.

TYPES OF OPERATING SYSTEMS

Most simple, single-function computers (such as in microwave ovens with digital
keypads) do not require an operating system. In fact, trying to implement an operating
system in these computers would be overkill. On the other hand, all personal desktop and
laptop computers and servers do require an operating system. While there are hundreds of
operating systems available, the most popular by far are the Microsoft Windows family
of operating systems, the Macintosh operating system, and the Unix family of operating
systems.

There are four general types of operating systems. Their use depends on the type of
computer and the type of applications that will be run on those computers.

1. Real-time operating systems (RTOS) are used to control machinery, scientific

instruments, and industrial systems. In general, the user does not have much control
over the functions performed by RTOS.
2. Single-user, single-task operating systems allow one user to do one thing at a
time. An example of a single-user, single-task operating system is the operating
system used by personal digital assistants (PDAs), also known as handheld
computers.
3. Single-user, multi-tasking operating systems allow a single user to simultaneously
run multiple applications on their computer. This is the type of operating system

4
 found on most personal desktop and laptop computers. Microsoft Windows, Mac OS,
and Linux are three well-known examples of this type of system.
4. Multi-user operating systems allow multiple users to simultaneously use the
resources on a single computer. Unix is an example of a multi-user operating system.

AVAILABLE OPERATING SYSTEMS

The most popular and widely-known operating system is Windows, a family of operating
systems introduced by the Microsoft Corporation in 1985. Windows employs a graphical
user interface (GUI), which eliminates the need for the user to learn complex commands.
With a GUI, the user instructs the operating system by using a mouse to point and click
icons that are displayed on the screen. The first version of Windows, released in
November 1985, was designed as a GUI add-on for MS-DOS (short for Microsoft Disk
Operating System), Microsoft's original command-line operating system. In order to
communicate with the computer, DOS users had to type commands or instructions at a
command prompt, and then the command-line interpreter executed those commands.
DOS has limited use with modern computer systems and applications because it does not
support multiple users or multitasking. It is also not as“user friendly” as a GUI operating
system. By the late-1990s, most command-line operating systems had been replaced by
user-friendly systems using a GUI.

By the time Windows 3.1 was released in 1991, Windows had gained significantly in
market share, and from the mid-1990s on, Microsoft dominated the operating-system
market. Microsoft released Windows 95 in August 1995. It was so well marketed and in
such high demand that people bought the operating system even if they did not own a
home computer. With each new release, from Windows 98 to Windows 2000 to
Windows XP to Windows Vista, Microsoft gained popularity. By 2004, Microsoft
commanded around 90 percent of the operating-system market. The latest Windows
release, Windows Vista, was introduced worldwide in January 2007, five years after the
introduction of its predecessor, Windows XP—the longest time between releases of
Windows. Vista is only slowly gaining in popularity, while Windows XP remains the
world's dominant operating system, commanding 79 percent market share in September
2007 (compared to only 7 percent for Vista).

5
The second-most popular family of operating systems is the Mac OS. Macintosh is often
credited with introducing the GUI-style operating system; Mac OS was not the first
graphical user interface, but it was the

first successful one, largely because competitors were so expensive—the Xerox Alto, the
first true GUI system, cost $32,000 to build while the Macintosh retailed for $2,500.
Because of its relative affordability, it immediately became much more popular than
other GUI computers. The first Mac OS, unnamed at the time but now known as “System
1,” was introduced in 1984. It had a desktop, windows, icons, a mouse, menus, and
scrollbars.

Early versions of the Mac OS could only be used on Apple computers. In 1991, Apple
introduced computers with PowerPC hardware; these computers could run either
Windows or Mac OS. The latest version of the Mac OS, OS X, was first introduced in
2000. It can be used in computers with both PowerPC and Intel processors, giving it
wider applicability and use. However, the Mac OS lags far behind Microsoft Windows.
In 2007, it was the world's third-most popular operating system—after Windows XP and
Windows Vista—but it commanded only slightly over 3 percent of the operating-system
market.

UNIX is a multi-user, multitasking operating system, and was designed to be a small,

flexible system used by computer programmers. UNIX is not considered to be very user-
friendly for the average person due to its design. However, graphical user interfaces have
been developed for UNIX to help alleviate the ease-of-use issue.

Linux is a UNIX variant that runs on several different hardware platforms. Linus
Torvalds, a student at the University of Helsinki in Finland, initially created it as a hobby.
The kernel, at the heart of all Linux systems, is developed and released under the General
Public License (GNU), and its source code is freely available to everyone. There are now
hundreds of companies, organizations, and individuals that have released their own
versions of operating systems based on the Linux kernel.

Because of its functionality, adaptability, and robustness, Linux is able to compete

against the Unix and Microsoft operating systems. IBM, Hewlett-Packard, and other
computer giants have embraced Linux and support its ongoing development. More than a

6
decade after its initial release, Linux is being adopted worldwide mainly as a server
platform. More and more people are starting to use Linux as a home and office desktop
operating system. The operating system can also be incorporated directly into microchips
in a process called “embedding.” Many appliances and devices are now starting to use
operating systems in this way.

2.0 Operating Systems Structure

- System Components

Even though, not all systems have the same structure many modern operating systems
share the same goal of supporting the following types of system components.

Process Management

The operating system manages many kinds of activities ranging from user programs to
system programs like printer spooler, name servers, file server etc. Each of these
activities is encapsulated in a process. A process includes the complete execution context
(code, data, PC, registers, OS resources in use etc.).

It is important to note that a process is not a program. A process is only ONE instant of a
program in execution. Many processes can be running the same program. The five major
activities of an operating system in regard to process management are

 Creation and deletion of user and system processes.

 Suspension and resumption of processes.
 A mechanism for process synchronization.
 A mechanism for process communication.
 A mechanism for deadlock handling.

Main-Memory Management

Primary-Memory or Main-Memory is a large array of words or bytes. Each word or byte

has its own address. Main-memory provides storage that can be accessed directly by the
CPU. That is to say for a program to be executed, it must be in the main memory.

The major activities of an operating system in regard to memory-management are:

 Keep track of the part of memory that is currently being used and by whom.

7
  Decide which process is loaded into memory when memory space becomes
available.
 Allocate and deallocate memory space as needed.

File Management

A file is a collection of related information defined by its creator. Computer can store
files on the disk (secondary storage), which provide long term storage. Some examples of
storage media are magnetic tape, magnetic disk and optical disk. Each of these media has
its own properties like speed, capacity, and data transfer rate and access methods.

File systems is normally organized into directories to ease their use. These directories
may contain files and other directions.

The five main activities of an operating system in regard to file management are

1. The creation and deletion of files.

2. The creation and deletion of directions.
3. The support of primitives for manipulating files and directions.
4. The mapping of files onto secondary storage.
5. The back up of files on stable storage media.

I/O System Management

I/O subsystem hides the peculiarities of specific hardware devices from the user. Only the
device driver knows the peculiarities of the specific device to which it is assigned.

Secondary-Storage Management

Generally speaking, systems have several levels of storage, including primary storage,
secondary storage and cache storage. Instructions and data must be placed in primary
storage or cache to be referenced by a running program. Because main memory is too
small to accommodate all data and programs, and its data is lost when power is lost, the
computer system must provide secondary storage to back up main memory. Secondary
storage consists of tapes, disks, and other media designed to hold information that will
eventually be accessed in primary storage (primary, secondary, cache) is ordinarily
divided into bytes or words consisting of a fixed number of bytes. Each location in
storage has an address; the set of all addresses available to a program is called an address
space.

The three major activities of an operating system in regard to secondary storage

management are:

1. Managing the free space available on the secondary-storage device.

2. Allocation of storage space when new files have to be written.
3. Scheduling the requests for memory access.

8
Networking

A distributed system is a collection of processors that do share memory, peripheral

devices, or a clock. The processors communicate with one another through
communication lines called network. The communication-network design must consider
routing and connection strategies, and the problems of connection and security.

Protection of Systems

If computer systems have multiple users and allows the concurrent execution of multiple
processes, then the various processes must be protected from one another's activities.
Protection refers to mechanism for controlling the access of programs, processes, or users
to the resources defined by computer systems.

Command Interpreter System

A command interpreter is an interface of the operating system with the user. The user
gives commands which are executed by operating system (usually by turning them into
system calls). The main function of a command interpreter is to get and execute the next
user specified command. Command-Interpreter is usually not part of the kernel, since
multiple command interpreters (shell, in UNIX terminology) may be supported by an
operating system, and they do not really need to run in kernel mode. There are two main
advantages of separating the command interpreter from the kernel.

1. If we want to change the way the command interpreter looks, i.e., I want to
change the interface of command interpreter, I am able to do that if the command
interpreter is separated from the kernel.
2. If the command interpreter is a part of the kernel it is possible for a malicious
process to gain access to certain part of the kernel. It is advantageous to have the
command interpreter separated from kernel.

- Operating Systems Services

Following are the five services provided by operating systems to the convenience of the
users.

Program Execution

The purpose of computer system is to allow the user to execute programs. So the
operating systems provide an environment where the user can conveniently run programs.
The user does not have to worry about the memory allocation or multitasking. These
things are taken care of by the operating systems.

9
Running a program involves the allocating and deallocating memory, CPU scheduling in
case of multiprocessing. These functions cannot be given to the user-level programs
because user-level programs cannot help the user to run programs independently without
the help from operating systems.

I/O Operations

Each program requires an input and produces output. This involves the use of I/O. The
operating systems hide from the user, the details of underlying hardware from I/O. All the
user sees is that the I/O has been performed without any details. The operating system
makes it convenient for the users to run programs.

File System Manipulation

The output of a program may need to be written into new files or input taken from some
files. The operating systems provide these services. The user does not have to worry
about secondary storage management. User gives a command for reading or writing to a
file and sees his task accomplished. Thus, operating systems make it easier for user
programs to accomplish their task.

This service involves secondary storage management. The speed of I/O that depends on
secondary storage management is critical to the speed of many programs and hence, it is
best relegated to the operating systems to manage it than giving individual users to
control it.

Communications

There are instances where processes need to communicate with each other to exchange
information. It may be between processes running on the same computer or running on
the different computers. By providing this service the operating system relieves the user
of the worry of passing messages between processes. If a case arises that the messages
need to be passed to processes on the other computers through a network it can be done
by the user programs. The user program may be customized to specific hardware through
which the message transits and provides the service interface to the operating system.

Error Detection

An error is one part of the system may cause malfunctioning of the complete system. To
avoid such a situation the operating system constantly monitors the system for detecting
the errors. This relieves the user of the worry of errors propagating to various part of the
system and causing malfunctioning.

This service cannot be allowed to be handled by user programs because it involves

monitoring and in cases of altering area of memory or deal location of memory for a

10
faulty process. Or may be relinquishing the CPU of a process that goes into an infinite
loop. These tasks are too critical to be handed over to the user programs. A user program
if given these privileges can interfere with the correct (normal) operation of the operating
systems.

- System Calls and System Programs

System calls provide an interface between the process and the operating system. System
calls allow user-level processes to request for some services from the operating system
which the process itself is not allowed to do. In handling the trap, the operating system
will enter in the kernel mode, where it has access to privileged instructions, and can
perform the desired service on the behalf of user-level process. It is because of the critical
nature of operations that the operating system itself does them every time they are
needed. For example, for I/O a process involves a system call telling the operating system
to read or write particular area and this request is satisfied by the operating system.

System programs provide basic functioning to users so that they do not need to write their
own environment for program development (editors, compilers) and program execution
(shells). In some sense, they are bundles of useful system calls.

- Layered Approach Design

In this case the system is easier to debug and modify, because changes affect only
limited portions of the code, and programmer does not have to know the details of the
other layers. Information is also kept only where it is needed and is accessible only in
certain ways, so bugs affecting that data are limited to a specific module or layer.

- Mechanisms and Policies

The policies define what is to be done while the mechanism specifies how it is to be
done. For instance, the timer construct for ensuring CPU protection is mechanism. On the
other hand, the decision of how long the timer is set for a particular user is a policy
decision.

The separation of mechanism and policy is important to provide flexibility to a system. If

the interface between mechanism and policy is well defined, the change of policy may
affect only a few parameters. On the other hand, if interface between these two is vague
or not well defined, it might involve much deeper change to the system.

Once the policy has been decided it gives the programmer the choice of using his/her
own implementation. Also, the underlying implementation may be changed for a more
efficient one without much trouble if the mechanism and policy are well defined.

11
Specifically, separating these two provides flexibility in a variety of ways. First, the same
mechanism can be used to implement a variety of policies, so changing the policy might
not require the development of a new mechanism, but just a change in parameters for that
mechanism. Second, the mechanism can be changed for example, to increase its
efficiency or to move to a new platform, without changing the overall policy.

3.0 PROCESS
Definition of Process

The notion of process is central to the understanding of operating systems. There are
quite a few definitions presented in the literature, but no "perfect" definition has yet
appeared.

Definition

The term "process" was first used by the designers of the MULTICS in 1960's. Since
then, the term process, used somewhat interchangeably with 'task' or 'job'. The process
has been given many definitions for instance

 A program in Execution.
 An asynchronous activity.
 The 'animated sprit' of a procedure in execution.
 The entity to which processors are assigned.
 The 'dispatchable' unit.

Process is not the same as program. A process is more than a program code. A process is
an 'active' entity as oppose to program which consider being a 'passive' entity. A program
is an algorithm expressed in some suitable notation, (e.g., programming language).
Process, on the other hand, includes:

 Current value of Program Counter (PC)

 Contents of the processors registers
 Value of the variables
 The process stack (SP) which typically contains temporary data such as
subroutine parameter, return address, and temporary variables.
 A data section that contains global variables.

A process is the unit of work in a system.

In Process model, all software on the computer is organized into a number of sequential
processes. A process includes PC, registers, and variables. Conceptually, each process
has its own virtual CPU. In reality, the CPU switches back and forth among processes.
(The rapid switching back and forth is called multiprogramming).

12
A multitasking* operating system may just switch between processes to give the
appearance of many processes executing concurrently or simultaneously, though in fact
only one process can be executing at any one time on a single-core CPU (unless using
multi-threading or other similar technology).[3]

It is usual to associate a single process with a main program, and 'daughter' ('child')
processes with any spin-off, parallel processes, which behave like asynchronous
subroutines. A process is said to own resources, of which an image of its program (in
memory) is one such resource. (Note, however, that in multiprocessing systems,
many processes may run off of, or share, the same reentrant program at the same location
in memory— but each process is said to own its own image of the program.)

Processes are often called tasks in embedded operating systems. The sense of 'process' (or
task) is 'something that takes up time', as opposed to 'memory', which is 'something that
takes up space'. (Historically, the terms 'task' and 'process' were used interchangeably, but
the term 'task' seems to be dropping from the computer lexicon.)

The above description applies to both processes managed by an operating system, and
processes as defined by process calculi.

If a process requests something for which it must wait, it will be blocked. When the
process is in the Blocked State, it is eligible for swapping to disk, but this is transparent
in a virtual memory system, where blocks of memory values may be really on disk and
not in main memory at any time. Note that even unused portions of active processes/tasks
(executing programs) are eligible for swapping to disk. All parts of an executing program
and its data do not have to be in physical memory for the associated process to be active.

______________________________

*Tasks and processes refer essentially to the same entity. And, although they have
somewhat different terminological histories, they have come to be used as synonyms.
Today, the term process is generally preferred over task, except when referring to
'multitasking', since the alternative term, 'multiprocessing', is too easy to confuse with
multiprocessor (which is a computer with two or more CPUs).

Process State

13
The process state consist of everything necessary to resume the process execution if it is
somehow put aside temporarily. The process state consists of at least the following:

 Code for the program.

 Program's static data.
 Program's dynamic data.
 Program's procedure call stack.
 Contents of general purpose registers.
 Contents of program counter (PC)
 Contents of program status word (PSW).
 Operating Systems resource in use.

A process goes through a series of discrete process states.

 New State: The process being created.

 Running State: A process is said to be running if it has the CPU, that is, process
actually using the CPU at that particular instant.
 Blocked (or waiting) State: A process is said to be blocked if it is waiting for
some event to happen such as an I/O completion before it can proceed. Note that a
process is unable to run until some external event happens.
 Ready State: A process is said to be ready if it use of CPU is available. A ready
state process is runnable but temporarily stopped running to let another process
run.
 Terminated state: The process has finished execution.

Process Operations

Process Creation

In general-purpose systems, there are procedures needed to create processes during

operation. There are four principal events led to processes creation.

 System initialization.
 Execution of a process Creation System calls by a running process.
 A user request to create a new process.
 Initialization of a batch job.

Foreground processes interact with users. Background processes that stay in background
sleeping but suddenly springing to life to handle activity such as email, webpage,
printing, and so on. Background processes are called daemons. This call creates an exact
clone of the calling process.

A process may create a new process such as ‘fork’. The process that created a new

14
process is called parent process while the created one is called the child process. Only
one parent is needed to create a child process. Note that unlike plants and animals that
use sexual representation, a process has only one parent. This creation of process
(processes) yields a hierarchical structure of processes. Note that each child has only one
parent but each parent may have many children. After the fork, the two processes, the
parent and the child, have the same memory image, the same environment strings and the
same open files. After a process is created, both the parent and child have their own
distinct address space. If either process changes a word in its address space, the change is
not visible to the other process.

<Figure 3.2 pp.55 From Dietel>

Following are some reasons for creation of a process

 User logs on.

 User starts a program.

 Operating systems creates process to provide service, e.g., to manage printer.

 Some program starts another process, e.g., Netscape calls xv to display a picture.

Process Termination

A process terminates when it finishes executing its last statement. Its resources are
returned to the system, and its process control block (PCB) is erased i.e., the PCB's
memory space is returned to a free memory pool. The new process terminates the existing
process in the following ways:

 Normal Exist Most processes terminates because they have done their job. This
call is exist in UNIX.
 Error Exist When process discovers a fatal error. For example, a user trying to
compile a program that does not exist.
 Fatal Error An error caused by processes due to a bug in program for example,
executing an illegal instruction, referring non-existing memory or dividing by
zero.
 Killed by another Process A process executes a system call telling the
Operating Systems to terminate some other process. In UNIX, this call is killing.
In some systems when a process kills all processes, it created ones are killed as
well (UNIX does not work this way).

Process States

A process goes through a series of discrete process states.

 New State The process being created.

 Terminated State The process has finished execution.

15
  Blocked (waiting) State When a process blocks, it does so because logically it
cannot continue, typically because it is waiting for input that is not yet available.
Formally, a process is said to be blocked if it is waiting for some event to happen
(such as an I/O completion) before it can proceed. In this state a process is unable
to run until some external event happens.
 Running State A process is said t be running if it currently has the CPU that is,
actually using the CPU at that particular instant.
 Ready State A process is said to be ready if it use of the CPU is available. It is
runnable but temporarily stopped to let another process run.

Logically, the 'Running' and 'Ready' states are similar. In both cases the process is willing
to run, only in the case of 'Ready' state, there is temporarily no CPU available for it. The
'Blocked' state is different from the 'Running' and 'Ready' states in that the process cannot
run, even if the CPU is available.

Process State Transitions

Following are six (6) possible transitions among above mentioned five (5) states

FIGURE

 Transition 1 occurs when process discovers that it cannot continue. If running

process initiates an I/O operation before its allotted time expires, the running
process voluntarily relinquishes the CPU.

This state transition is:

Block (process-name): Running → Block.

 Transition 2 occurs when the scheduler decides that the running process has run
long enough and it is time to let another process have CPU time.

This state transition is:

Time-Run-Out (process-name): Running → Ready.

 Transition 3 occurs when all other processes have had their share and it is time
for the first process to run again

This state transition is:

Dispatch (process-name): Ready → Running.

 Transition 4 occurs when the external event for which a process was waiting
(such as arrival of input) happens.

16
 This state transition is:

Wakeup (process-name): Blocked → Ready.

 Transition 5 occurs when the process is created.

This state transition is:

Admitted (process-name): New → Ready.

 Transition 6 occurs when the process has finished execution.

This state transition is:

Exit (process-name): Running → Terminated.

FIGURE from Notes

Process Control Block

A process in an operating system is represented by a data structure known as a process

control block (PCB) or process descriptor. The PCB contains important information
about the specific process including

 The current state of the process i.e., whether it is ready, running, waiting, or
whatever.
 Unique identification of the process in order to track "which is which"
information.
 A pointer to parent process.
 Similarly, a pointer to child process (if it exists).
 The priority of process (a part of CPU scheduling information).
 Pointers to locate memory of processes.
 A register save area.
 The processor it is running on.

The PCB is a central store of information that allows the operating systems to locate all
key information about a process. Thus, the PCB is the data structure that defines a
process to the operating systems.

4.0 Threads

17
  Threads
 Processes Vs Threads
 Why Threads?
 User-Level Threads
 Kernel-Level Threads
 Advantages of Threads over Multiple Processes
 Disadvantages of Threads over Multiprocessing
 Application that Benefits from Threads
 Application that cannot benefit from Threads
 Resources used in Thread creation and Process Creation
 Context Switch
 Major Steps of Context Switching
 Action of Kernel to Context switch among threads
 Action of kernel to Context switch among processes

Threads

Despite the fact that a thread must execute in process, the process and its associated
threads are different concept. Processes are used to group resources together and threads
are the entities scheduled for execution on the CPU.
A thread is a single sequence stream within a process. Because threads have some of the
properties of processes, they are sometimes called lightweight processes. In a process,
threads allow multiple executions of streams. In many respect, threads are popular way to
improve application through parallelism. The CPU switches rapidly back and forth
among the threads giving illusion that the threads are running in parallel. Like a
traditional process i.e., process with one thread, a thread can be in any of several states
(Running, Blocked, Ready or Terminated). Each thread has its own stack. Since thread
will generally call different procedures and thus a different execution history. This is why
thread needs its own stack. An operating system that has thread facility, the basic unit of
CPU utilization is a thread. A thread has or consists of a program counter (PC), a register
set, and a stack space. Threads are not independent of another like processes as a result
threads shares with other threads their code section, data section, OS resources also
known as task, such as open files and signals.

Processes Vs Threads

As we mentioned earlier that in many respect threads operate in the same way as that of
processes. Some of the similarities and differences are:

Similarities

 Like processes threads share CPU and only one thread is active (running) at a
time.
 Like processes, threads within processes execute sequentially.
 Like processes, thread can create children.
 And like process, if one thread is blocked, another thread can run.

18
Differences

 Unlike processes, threads are not independent of one another.

 Unlike processes, all threads can access every address in the task.
 Unlike processes, thread are design to assist one other. Note that processes might
or might not assist one another because processes may originate from different
users.

Why Threads?

Following are some reasons why we use threads in designing operating systems.

1. A process with multiple threads make a great server for example printer server.
2. Because threads can share common data, they do not need to use interprocess
communication.
3. Because of the very nature, threads can take advantage of multiprocessors.

Threads are cheap in the sense that

1. They only need a stack and storage for registers therefore, threads are cheap to
create.
2. Threads use very little resources of an operating system in which they are
working. That is, threads do not need new address space, global data, program
code or operating system resources.
3. Context switching are fast when working with threads. The reason is that we only
have to save and/or restore PC, SP and registers.

But this cheapness does not come free - the biggest drawback is that there is no protection
between threads.

User-Level Threads

User-level threads implement in user-level libraries, rather than via systems calls, so
thread switching does not need to call operating system and to cause interrupt to the
kernel. In fact, the kernel knows nothing about user-level threads and manages them as if
they were single-threaded processes.

Advantages:

The most obvious advantage of this technique is that a user-level threads package can be
implemented on an Operating System that does not support threads. Some other
advantages are

 User-level threads does not require modification to operating systems.

19
  Simple Representation:
Each thread is represented simply by a PC, registers, stack and a small control
block, all stored in the user process address space.
 Simple Management:
This simply means that creating a thread, switching between threads and
synchronization between threads can all be done without intervention of the
kernel.
 Fast and Efficient:
Thread switching is not much more expensive than a procedure call.

Disadvantages:

 There is a lack of coordination between threads and operating system kernel.

Therefore, process as whole gets one time slice irrespective of whether process
has one thread or 1000 threads within. It is up to each thread to relinquish control
to other threads.
 User-level threads requires non-blocking systems call i.e., a multithreaded kernel.
Otherwise, entire process will blocked in the kernel, even if there are runnable
threads left in the processes. For example, if one thread causes a page fault, the
process blocks.

Kernel-Level Threads

In this method, the kernel knows about and manages the threads. No runtime system is
needed in this case. Instead of thread table in each process, the kernel has a thread table
that keeps track of all threads in the system. In addition, the kernel also maintains the
traditional process table to keep track of processes. Operating Systems kernel provides
system call to create and manage threads.

Advantages:

 Because kernel has full knowledge of all threads, Scheduler may decide to give
more time to a process having large number of threads than process having small
number of threads.
 Kernel-level threads are especially good for applications that frequently block.

Disadvantages:

 The kernel-level threads are slow and inefficient. For instance, threads operations
are hundreds of times slower than that of user-level threads.
 Since kernel must manage and schedule threads as well as processes. It require a
full thread control block (TCB) for each thread to maintain information about
threads. As a result there is significant overhead and increased in kernel
complexity.

Advantages of Threads over Multiple Processes

20
  Context Switching Threads are very inexpensive to create and destroy, and
they are inexpensive to represent. For example, they require space to store, the
PC, the SP, and the general-purpose registers, but they do not require space to
share memory information, Information about open files of I/O devices in use,
etc. With so little context, it is much faster to switch between threads. In other
words, it is relatively easier for a context switch using threads.
 Sharing Treads allow the sharing of a lot resources that cannot be shared in
process, for example, sharing code section, data section, Operating System
resources like open file etc.

Disadvantages of Threads over Multiprocessing

 Blocking The major disadvantage if the kernel is single threaded, a system call
of one thread will block the whole process and CPU may be idle during the
blocking period.
 Security Since there is, an extensive sharing among threads there is a potential
problem of security. It is quite possible that one thread over writes the stack of
another thread (or damaged shared data) although it is very unlikely since threads
are meant to cooperate on a single task.

Application that benefits from Threads

A proxy server satisfying the requests for a number of computers on a LAN would be
benefited by a multi-threaded process. In general, any program that has to do more than
one task at a time could benefit from multitasking. For example, a program that reads
input, process it, and outputs could have three threads, one for each task.

Application that cannot benefit from Threads

Any sequential process that cannot be divided into parallel task will not benefit from
thread, as they would block until the previous one completes. For example, a program
that displays the time of the day would not benefit from multiple threads.

Resources used in Thread Creation and Process Creation

21
When a new thread is created it shares its code section, data section and operating system
resources like open files with other threads. But it is allocated its own stack, register set
and a program counter.

The creation of a new process differs from that of a thread mainly in the fact that all the
shared resources of a thread are needed explicitly for each process. So though two
processes may be running the same piece of code they need to have their own copy of the
code in the main memory to be able to run. Two processes also do not share other
resources with each other. This makes the creation of a new process very costly
compared to that of a new thread.

Context Switch

To give each process 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 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 accomplish this task.

Action of kernel to Context Switch Among Processes

22
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.

5.0 Deadlock
“Crises and deadlocks when they occur have at least this advantage that they force us
to think.”- Jawaharlal Nehru (1889 - 1964) Indian political leader

A set of process is in a deadlock state if each process in the set is waiting for an event that
can be caused by only another process in the set. In other words, each member of the set
of deadlock processes is waiting for a resource that can be released only by a deadlock
process. None of the processes can run, none of them can release any resources, and none
of them can be awakened. It is important to note that the number of processes and the
number and kind of resources possessed and requested are unimportant.

The resources may be either physical or logical. Examples of physical resources are
Printers, Tape Drivers, Memory Space, and CPU Cycles. Examples of logical resources
are Files, Semaphores, and Monitors.

The simplest example of deadlock is where process 1 has been allocated non-shareable
resources A, say, a tap drive, and process 2 has be allocated non-sharable resource B, say,
a printer. Now, if it turns out that process 1 needs resource B (printer) to proceed and
process 2 needs resource A (the tape drive) to proceed and these are the only two
processes in the system, each is blocked the other and all useful work in the system stops.
This situation ifs termed deadlock. The system is in deadlock state because each process
holds a resource being requested by the other process neither process is willing to release
the resource it holds.

Preemptable and Nonpreemptable Resources

23
Resources come in two flavors: preemptable and nonpreemptable. A preemptable
resource is one that can be taken away from the process with no ill effects. Memory is an
example of a preemptable resource. On the other hand, a nonpreemptable resource is one
that cannot be taken away from process (without causing ill effect). For example, CD
resources are not preemptable at an arbitrary moment.
Reallocating resources can resolve deadlocks that involve preemptable resources.
Deadlocks that involve nonpreemptable resources are difficult to deal with.

Necessary and Sufficient Deadlock Conditions

Coffman (1971) identified four (4) conditions that must hold simultaneously for there to
be a deadlock.

1. Mutual Exclusion Condition

The resources involved are non-shareable.
Explanation: At least one resource (thread) must be held in a non-shareable mode, that
is, only one process at a time claims exclusive control of the resource. If another process
requests that resource, the requesting process must be delayed until the resource has been
released.

2. Hold and Wait Condition

Requesting process hold already, resources while waiting for requested resources.
Explanation: There exist a process that is holding a resource already allocated to it while
waiting for additional resource that are currently being held by other processes.

3. No-Preemptive Condition
Resources already allocated to a process cannot be preempted.
Explanation: Resources that cannot be removed from the processes are used in
completing or released voluntarily by the process holding it.

4. Circular Wait Condition

The processes in the system form a circular list or chain where each process in the
list is waiting for a resource held by the next process in the list.

As an example, consider the traffic deadlock in the following figure

24
Consider each section of the street as a resource.

1. Mutual exclusion condition applies, since only one vehicle can be on a section of
the street at a time.
2. Hold-and-wait condition applies, since each vehicle is occupying a section of the
street, and waiting to move on to the next section of the street.
3. No-preemptive condition applies, since a section of the street that is occupied by a
vehicle cannot be taken away from it.
4. Circular wait condition applies, since each vehicle is waiting on the next vehicle
to move. That is, each vehicle in the traffic is waiting for a section of street held
by the next vehicle in the traffic.

The simple rule to avoid traffic deadlock is that a vehicle should only enter an
intersection if it is assured that it will not have to stop inside the intersection.

It is not possible to have a deadlock involving only one single process. The deadlock
involves a circular “hold-and-wait” condition between two or more processes, so “one”
process cannot hold a resource, yet be waiting for another resource that it is holding. In
addition, deadlock is not possible between two threads in a process, because it is the
process that holds resources, not the thread that is, each thread has access to the resources
held by the process.

Dealing with Deadlock Problem

In general, there are four strategies of dealing with deadlock problem:

25
1. The Ostrich Approach
Just ignore the deadlock problem altogether.
2. Deadlock Detection and Recovery
Detect deadlock and, when it occurs, take steps to recover.
3. Deadlock Avoidance
Avoid deadlock by careful resource scheduling.
4. Deadlock Prevention
Prevent deadlock by resource scheduling so as to negate at least one of the four
conditions.

Deadlock Prevention

Havender in his pioneering work showed that since all four of the conditions are
necessary for deadlock to occur, it follows that deadlock might be prevented by denying
any one of the conditions.

Elimination of “Mutual Exclusion” Condition

The mutual exclusion condition must hold for non-sharable resources. That is, several
processes cannot simultaneously share a single resource. This condition is difficult to
eliminate because some resources, such as the tap drive and printer, are inherently non-
shareable. Note that shareable resources like read-only-file do not require mutually
exclusive access and thus cannot be involved in deadlock.

Elimination of “Hold and Wait” Condition

There are two possibilities for elimination of the second condition. The first alternative is
that a process request be granted all of the resources it needs at once, prior to execution.
The second alternative is to disallow a process from requesting resources whenever it has
previously allocated resources. This strategy requires that all of the resources a process
will need must be requested at once. The system must grant resources on “all or none”
basis. If the complete set of resources needed by a process is not currently available, then
the process must wait until the complete set is available. While the process waits,
however, it may not hold any resources. Thus the “wait for” condition is denied and
deadlocks simply cannot occur. This strategy can lead to serious waste of resources. For
example, a program requiring ten tap drives must request and receive all ten derives
before it begins executing. If the program needs only one tap drive to begin execution and
then does not need the remaining tap drives for several hours. Then substantial computer
resources (9 tape drives) will sit idle for several hours. This strategy can cause indefinite
postponement (starvation). Since not all the required resources may become available at
once.

 Elimination of “No-preemption” Condition

The no preemption condition can be alleviated by forcing a process waiting for a
resource that cannot immediately be allocated to relinquish all of its currently held
resources, so that other processes may use them to finish. Suppose a system does

26
 allow processes to hold resources while requesting additional resources. Consider
what happens when a request cannot be satisfied. A process holds resources a
second process may need in order to proceed while second process may hold the
resources needed by the first process. This is a deadlock. This strategy require that
when a process that is holding some resources is denied a request for additional
resources. The process must release its held resources and, if necessary, request
them again together with additional resources. Implementation of this strategy
denies the “no-preemptive” condition effectively.
High Cost When a process release resources the process may lose all its work to
that point. One serious consequence of this strategy is the possibility of indefinite
postponement (starvation). A process might be held off indefinitely as it
repeatedly requests and releases the same resources.

Elimination of “Circular Wait” Condition

The last condition, the circular wait, can be denied by imposing a total ordering on all of
the resource types and than forcing, all processes to request the resources in order
(increasing or decreasing). This strategy impose a total ordering of all resources types,
and to require that each process requests resources in a numerical order (increasing or
decreasing) of enumeration. With this rule, the resource allocation graph can never have a
cycle.
For example, provide a global numbering of all the resources, as shown

1 ≡ Card reader
2 ≡ Printer
3 ≡ Plotter
4 ≡ Tape drive
5 ≡ Card punch

 Now the rule is this: processes can request resources whenever they want to, but
all requests must be made in numerical order. A process may request first printer
and then a tape drive (order: 2, 4), but it may not request first a plotter and then a
printer (order: 3, 2). The problem with this strategy is that it may be impossible to
find an ordering that satisfies everyone.

Deadlock Avoidance

This approach to the deadlock problem anticipates deadlock before it actually occurs.
This approach employs an algorithm to access the possibility that deadlock could occur
and acting accordingly. This method differs from deadlock prevention, which guarantees
that deadlock cannot occur by denying one of the necessary conditions of deadlock.

If the necessary conditions for a deadlock are in place, it is still possible to avoid
deadlock by being careful when resources are allocated. Perhaps the most famous
deadlock avoidance algorithm, due to Dijkstra [1965], is the Banker’s algorithm. So
named because the process is analogous to that used by a banker in deciding if a loan can
be safely made.

27
Banker’s Algorithm

In this analogy

Customer
≡ Processes
s
resources, say,
Units ≡
tape drive
Operating
Banker ≡
System
Customer
Used Max
s
A 0 6
B 0 5 Available
C 0 4 Units = 10
D 0 7

Fig. 1

In the above figure, we see four customers each of whom has been granted a number of
credit nits. The banker reserved only 10 units rather than 22 units to service them. At
certain moment, the situation becomes

CustomersUsed Max
A 1 6
B 1 5 Available
C 2 4 Units = 2
D 4 7

Fig. 2

Safe State The key to a state being safe is that there is at least one way for all users to
finish. In other analogy, the state of figure 2 is safe because with 2 units left, the banker
can delay any request except C's, thus letting C finish and release all four resources. With
four units in hand, the banker can let either D or B have the necessary units and so on.

Unsafe State Consider what would happen if a request from B for one more unit were
granted in above figure 2.

We would have following situation

CustomersUsed Max
A 1 6
B 2 5 Available
C 2 4 Units = 1
D 4 7

28
 Fig. 3

This is an unsafe state.

If all the customers namely A, B, C, and D asked for their maximum loans, then banker
could not satisfy any of them and we would have a deadlock.

Important Note: It is important to note that an unsafe state does not imply the
existence or even the eventual existence a deadlock. What an unsafe state does imply is
simply that some unfortunate sequence of events might lead to a deadlock.

The Banker's algorithm is thus to consider each request as it occurs, and see if granting it
leads to a safe state. If it does, the request is granted, otherwise, it postponed until later.
Haberman [1969] has shown that executing of the algorithm has complexity proportional
to N2 where N is the number of processes and since the algorithm is executed each time a
resource request occurs, the overhead is significant.

Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and
identifying the processes and resources involved in the deadlock.
The basic idea is to check allocation against resource availability for all possible
allocation sequences to determine if the system is in deadlocked state a. Of course, the
deadlock detection algorithm is only half of this strategy. Once a deadlock is detected,
there needs to be a way to recover several alternatives exists:

 Temporarily prevent resources from deadlocked processes.

 Back off a process to some check point allowing preemption of a needed resource
and restarting the process at the checkpoint later.
 Successively kill processes until the system is deadlock free.

These methods are expensive in the sense that each iteration calls the detection algorithm
until the system proves to be deadlock free. The complexity of algorithm is O(N2) where
N is the number of proceeds. Another potential problem is starvation; same process killed
repeatedly.

6.0 Asynchronous vs Synchronous Communication

There are two general strategies for communicating via the Internet: Asynchronous and
Synchronous. Each has its advantages and disadvantages.

Asynchronous communication and activities take place outside of real time. For
example, a learner sends you an e-mail message. You later read and respond to the
message. There is a time lag between the time the learner sent the message and you
replied, even if the lag time is short. Bulletin board messages can be added at any time

29
and read at your and the learners’ leisure; you do not read someone else’s message as it is
being created, and you can take as much time as you need to respond to the post.
Asynchronous activities take place whenever learners have the time to complete them.
For example, viewing videos linked to the course site, reading a textbook, and writing a
paper are all asynchronous activities.

There are some key advantages to asynchronous collaboration tools. For one thing,
they enable flexibility. Participants can receive the information when it's most convenient
for them. There's less pressure to act on the information or immediately respond in some
way. People have time to digest the information and put it in the proper context and
perspective. Another advantage is that some forms of asynchronous collaboration, such
as email, are ubiquitous. These days, it's hard to find a co-worker, customer, business
partner, consultant, or other party who doesn't have an email account.

The drawbacks of asynchronous collaboration are that they can lack a sense of
immediacy and drama. There's less immediate interaction. Sometimes people have to
wait hours, days, and even weeks to get a response to a message or feedback on a shared
document. The lack of immediacy means that information can be out of date by the time
someone views it. This is especially true in light of the rapid pace of change in today's
business environment [6].

In contrast, synchronous, or real-time, communication takes place like a conversation.

If your class uses only writing-based tools to communicate, the only synchronous
communication possible is a chat session. Everyone gets online in the same chat room
and types questions, comments, and responses in real time. Synchronous activities may
include chat sessions, whiteboard drawings, and other group interactive work. If your
class involves multimedia tools, synchronous communication might involve audio or
video feeds to the computer. Some “online” courses require learners and teachers to get
together at least once (or sometimes several times) in person, by conference call, or
through closed-circuit television links [5].

One of the advantages of synchronous collaboration is its immediacy. You can send
and receive information right away. This more closely resembles a face-to-face or
telephone conversation between two or more people, so can present a more natural way
of communicating. The sense of immediacy is more like to solicit a timely response from
people. Synchronous collaboration, in general, is more interactive than asynchronous. [4]

The downside of synchronous collaboration is that not everyone uses it. Although instant
messaging, chat, and other such tools are becoming more common, they're still not as
ubiquitous as technology such as email. Another drawback is that synchronous
collaboration is not as flexible as asynchronous. All the parties involved must be ready
and willing to collaborate at a given moment-or the session doesn't work as well. Also,
not everyone does well with this kind of collaboration, particularly people who like to
think over what they want to communicate [6].

30
When should you use asynchronous and synchronous collaboration? Much of the
decision-making on this involves common sense. Asynchronous collaboration, such as
email and document sharing, can certainly be used for day-to-day communications when
an urgent response isn't needed. This sort of communication is suitable for sending out
broadcast messages that don't necessarily need to be acted on right away, or for
corresponding with clients, customers. and business partners without putting pressure on
them to respond immediately.

On the other hand, you wouldn't want to use asynchronous collaboration if you need
immediate interaction with people or if you seek to collaborate with a large group at the
same time. Email wouldn't work, for example, as the sole means of conducting a staff
meeting.

Synchronous collaboration is ideal when the collaboration needs to be immediate and

spontaneous, like a conversation between two or more people. Using real-time chat,
instant messaging, electronic white boarding, and other such tools is appropriate for
virtual meetings, where parties in remote locations are expected to participate and ask
questions. In many cases, these types of collaborations might serve as supplements to
telephone conference calls.

Synchronous collaboration wouldn't be suitable for situations that call for less immediate
response or where parties aren't able to respond right away. For example, it might not
work as a way to collaborate with customers on new product design or development.

7.0 Protection and Security

The purpose of a protection system is to prevent accidental or intentional misuse of a
system.

 Accidents: Problems of this kind are easy to solve (can do things to make the
likelihood small).
 Malicious abuse: Problems of this kind are very hard to completely eliminate
(cannot leave any loopholes, cannot play on probabilities).

There are three aspects to a protection mechanism:

 User identification (authentication): make sure we know who is doing what.

 Authorization determination: must figure out what the user is and is not allowed
to do. Need a simple database for this.
 Access enforcement: must make sure there are no loopholes in the system.

Even the slightest flaw in any of these areas may ruin the whole protection mechanism.

Authentication

31
User identification is most often done with passwords. This is a relatively weak form of
protection.
 A password is a secret piece of information used to establish the identity of a user.
 Passwords should not be stored in a readable form. One-way transformations
should be used.
 Passwords should be relatively long and obscure.

Another form of identification: badge or key.

 Does not have to be kept secret.

 Should not be able to be forged or copied.
 Can be stolen, but the owner should know if it is.

Key paradox: key must be cheap to make, hard to duplicate. This means there must be
some trick (i.e. secret) that has to be protected.

Once identification is complete, the system must be sure to protect the identity since
other parts of the system will rely on it.

Authorization Determination

Must indicate who is allowed to do what with what. Draw the general form as an access
matrix with one row per user, one column per file. Each entry indicates the privileges of
that user on that object. There are two general ways of storing this information: access
lists and capabilities.

Access Lists: with each file, indicate which users are allowed to perform which
operations.

 In the most general form, each file has a list of pairs.

 It would be tedious to have a separate listing for every user, so they are usually
grouped into classes. For example, in Unix there are three classes: self, group,
anybody else (nine bits per file).
 Access lists are simple, and are used in almost all file systems.

Capabilities: with each user, indicate which files may be accessed, and in what ways.

 Store a list of pairs with each user. This is called a capability list.
 Typically, capability systems use a different naming arrangement, where the
capabilities are the only names of objects. You cannot even name objects not
referred to in your capability list.
 In access-list systems, the default is usually for everyone to be able to access a
file. In capability-based systems, the default is for no-one to be able to access a
file unless they have been given a capability. There is no way of even naming an
object without a capability.

32
  Capabilities are usually used in systems that need to be very secure. However,
capabilities can make it difficult to share information: nobody can get access to
your stuff unless you explicitly give it to them.

Are the following things access-based or capability-based protection schemes?

 Protection Keys
 Page tables

Access Enforcement

Some part of the system must be responsible for enforcing access controls and protecting
the authorization and identification information.
 Obviously, this portion of the system must run unprotected. Thus it should be as
small and simple as possible. Example: the portion of the system that sets up
memory mapping tables.
 The portion of the system that provides and enforces protection is called the
security kernel. Most systems, like Unix, do not have a security kernel. As a
consequence, the systems are not very secure.

 What is needed is a hierarchy of levels of protection, with each level getting the
minimum privilege necessary to do its job. However, this is likely to be slow
(crossing levels takes time).

Security Abuses

33
In general, protecting a computer system is extremely difficult. There is no completely
secure computer system in existence. Some common problems:

 Abuse of valid privileges.

 Imposter.
 Trojan Horse.
 Listener.
 Spoiler.
 Send weird escape sequences to terminals that cause commands to be echoed back
from the terminal.

Once the system has been penetrated, it may be impossible to secure it again: hooks could
have been left around for the imposter to regain control.

It is not always possible to tell when the system has been penetrated, since the villain can
clean up all traces behind himself.

If we can never be sure that there are no bugs, then we can never be sure that the system
is secure, since bugs could provide loopholes in the protection mechanisms.

How are computers different from humans when it comes to security?

 Computer memory is volatile, humans do not forget.

 We are much more trusting of computers than of people: privileges are given
away freely in huge doses: any program you run could conceivably modify any of
your files.
 Computer programs are very poorly understood.

Security Improvements, Encryption

Security Improvements

Solutions: nothing works perfectly, but here are some possibilities:

 Logging: record all important actions and uses of privilege in an indelible file.
Can be used to catch imposters during their initial attempts and failures. E.g.
record all attempts to specify an incorrect password, all super-user logins. Even
better is to get humans involved at key steps (this is one of the solutions for EFT).
 Principle of minimum privilege ("need-to-know" principle): each piece of the
system has access to the minimum amount of information, for the minimum
possible amount of time. E.g. file system cannot touch memory map, memory
manager cannot touch disk allocation tables. This reduces the chances of
accidental or intentional damage. Note that capabilities are an implementation of
this idea. It is very hard to provide fool-proof information containment: e.g. a
Trojan horse could write characters to a tty, or take page faults, in Morse code, as
a signal to another process.

34
  Correctness proofs. These are very hard to do. Even so, this only proves that the
system works according to spec. It does not mean that the spec. is necessarily
right, and it does not deal with Trojan Horses.

Encryption

Key technology: encryption. Store and transmit information in an encoded form that does
not make any sense.

The basic mechanism:

 Start with text to be protected. Initial readable text is called clear text.
 Encrypt the clear text so that it does not make any sense at all. The nonsense text
is called cipher text. The encryption is controlled by a secret password or number;
this is called the encryption key.

 The encrypted text can be stored in a readable file, or transmitted over

unprotected channels.
 To make sense of the cipher text, it must be decrypted back into clear text. This is
done with some other algorithm that uses another secret password or number,
called the decryption key.

All of this only works under three conditions:

35
  The encryption function cannot easily be inverted (cannot get back to clear text
unless you know the decryption key).
 The encryption and decryption must be done in some safe place so the clear text
cannot be stolen.
 The keys must be protected. In most systems, can compute one key from the other
(sometimes the encryption and decryption keys are identical), so cannot afford to
let either key leak out.

Public key encryption: new mechanism for encryption where knowing the encryption key
does not help you to find decryption key, or vice versa.

 User provides a single password, system uses it to generate two keys (use a one-
way function, so cannot derive password from either key).
 In these systems, keys are inverses of each other: could just as easily encrypt with
decryption key and then use encryption key to recover clear text.
 Each user keeps one key secret, publicizes the other. Cannot derive private key
from public. Public keys are made available to everyone, in a phone book for
example.

Safe mail:

 Use public key of destination user to encrypt mail.

 Anybody can encrypt mail for this user and be certain that only the user will be
able to decipher it.

It is a nice scheme because the user only has to remember one key, and all senders can
use the same key. However, how does receiver know for sure who it is getting mail from?

Digital Signatures

Positive identification: can also use public keys to certify identity:

 To certify your identity, use your private key to encrypt a text message, e.g. "I
agree to pay Mary Wallace $100 per year for the duration of life."
 You can give the encrypted message to anybody, and they can certify that it came
from you by seeing if it decrypts with your public key. Anything that decrypts
into readable text with your public key must have come from you! This can be
made legally binding as a form of electronic signature.

This is really even better than signatures: harder to forge, and can change if
compromised. Note that this idea was developed by an undergraduate (Loren Kohnfelder)
in 1978 as part of his undergraduate thesis (at MIT).

These two forms of encryption can be combined together. To identify sender in secure
mail, encrypt first with your private key, then with receiver's public key. The
encryption/decryption functions to send from B to A are:

36
Encryption appears to be a great way to thwart listeners. It does not help with Trojan
Horses, though.

Old dederal Data Encryption Standard (DES). Is not public-key based, but as
implemented efficiently and appeared to be relatively safe.

More recently, there is the Advanced Encryption Standard (AES), called Ryndal
(pronounced "rine doll"). ***more on AES here****

General problem: how do we know that an encryption mechanism is safe? It is extremely

hard to prove. This is a hot topic for research: theorists are trying to find provably hard
problems, and use them for proving safety of encryption.

Summary of Protection: very hard, but is increasingly important as things like electronic
funds transfer become more and more prevalent

Scheduling and CPU Scheduling

37
Scheduling

Until now we have talked about processes, from now on we will talk about resources, the
things operated upon by processes. Resources range from cpu time to disk space to
channel I/O time.

Resources fall into two classes:

 Preemptible: processor or I/O channel. Can take resource away, use it for
something else, and then give it back later. Non-preemptible: once given, it
cannot be reused until process gives it back. Examples are file space, terminal,
and maybe memory.

OS makes two related kinds of decisions about resources:

 Allocation: who gets what. Given a set of requests for resources, which processes
should be given which resources in order to make most efficient use of the
resources? Implication is that resources are not easily preemptible.
 Scheduling: how long can they keep it. When more resources are requested than
can be granted immediately, in which order should they be serviced? Examples
are processor scheduling (one processor, many processes), memory scheduling in
virtual memory systems. Implication is that resource is preemptible.

Resource #1: the processor.

CPU Scheduling

Processes may be in any one of three general scheduling states:

 Running. Ready. That is, waiting for CPU time. Scheduler and dispatcher
determine transitions between this and running state.
 Blocked. Waiting for some other event: disk I/O, message, semaphore, etc.
Transitions into and out of this state are caused by various processes.

There are two parts to CPU scheduling:

 The dispatcher provides the basic mechanism for running processes.

 The scheduler is a piece of OS code that decides the priorities of processes and
how long each will run.

This is an example of policy/mechanism separation.

Goals for Scheduling Disciplines

 Efficiency of resource utilization (keep CPU and disks busy).

38
  Minimize overhead (context swaps).
 Minimize response time. (Define response time.)
 Distribute cycles equitably. What does this mean?

FCFS (also called FIFO): run until finished.

 In the simplest case this means uniprogramming.

 Usually, "finished" means "blocked". One process can use CPU while another
waits on a semaphore. Go to back of run queue when ready.
 Problem: one process can monopolize CPU.

Solution: limit maximum amount of time that a process can run without a context switch.
This time is called a time slice.

Round Robin: run process for one time slice, then move to back of queue. Each process
gets equal share of the CPU. Most systems use some variant of this. What happens if the
time slice is not chosen carefully?

39
Originally, Unix had 1 sec. time slices. Too long. Most timesharing systems today use
time slices of 10,000 - 100,000 instructions.

Implementation of priorities: run highest priority processes first, use round-robin among
processes of equal priority. Re-insert process in run queue behind all processes of greater
or equal priority.

Even round-robin can produce bad results occasionally. Go through example of ten
processes each requiring 100 time slices.

What is the best we can do?

STCF: shortest time to completion first with preemption. This minimizes the average
response time.

As an example, show two processes, one doing 1 ms computation followed by 10 ms I/O,

one doing all computation. Suppose we use 100 ms time slice: I/O process only runs at
1/10th speed, effective I/O time is 100 ms. Suppose we use 1 ms time slice: then
compute-bound process gets interrupted 9 times unnecessarily for each valid interrupt.
STCF works quite nicely.

Unfortunately, STCF requires knowledge of the future. Instead, we can use past
performance to predict future performance.

Exponential Queue (also called "multi-level feedback queues"): attacks both efficiency
and response time problems.

40
  Give newly runnable process a high priority and a very short time slice. If process
uses up the time slice without blocking then decrease priority by 1 and double
time slice for next time.
 Go through the above example, where the initial values are 1ms and priority 100.
 Techniques like this one are called adaptive. They are common in interactive
systems.
 The CTSS system (MIT, early 1960's) was the first to use exponential queues.

Linux's new scheduler (version 2.6) makes this all very complex:

 Two queues: one with active (eligible to run) processes and with expired (not
eligible to run) processes.
 140 priority levels, but the top 100 are reserved for "real time" processes.
 Always choose a process from the highest non-empty priority level.
 Priority level is the sum of its static priority and its dynamic priority bonus, which
the scheduler assigns as an estimate of its interactivity. Niceness, the value that
 Static priorities range from 0-39 (number of queues) and dynamic priority
bonuses range from -5 to +5.
 Time slices assigned based on static priority, giving higher-priority tasks larger
time slices and lower-priority tasks shorter time slices.

41
  A task might not use all of its time slice at once, since it could block or be
preempted before it finishes, but eventually it consumes the entire amount. When
that happens, the task is usually placed on the expired array with a new time slice
and a recalculated priority.
 An interactive task receives the same time slice as others at the same static
priority, but the slice is divided into smaller pieces. When it finishes a piece, the
task will round robin with other tasks at the same priority level. Execution rotates
more frequently among interactive tasks of the same priority, but higher-priority
tasks will run for longer before expiring

Summary:

 In principle, scheduling algorithms can be arbitrary, since the system should

behave the same in any event.
 However, the algorithms have crucial effects on the behavior of the system:
o Overhead: number of context swaps.
o Efficiency: utilization of CPU and devices.
o Response time: how long it takes to do something.
 The best schemes are adaptive. To do absolutely best, we would have to be able to
predict the future.

Priority Inversion Problem

There are some curious interactions between scheduling and synchronization. A classic
problem caused by this interaction was first observed in 1979 but Butler Lampson and
David Redell at Xerox.

Suppose that you have three processes:

P1: Highest priority

P2: Medium priority
P3: Lowest priority

And suppose that you have the following critical section, S:

S: mutex.P()
...
...
mutex.V()

The three processes execute as follows:

42
 1. P3 enters S, locking the critical section.
2. P3 is preempted by the scheduler and P2 starts running.
3. P2 is preempted by the scheduler and P1 starts running.
4. P1 tries to enter S and is blocked at the P operation.
5. P2 starts running again, preventing P1 from running.

So, what's going wrong here?

To really understand this situation, you should try to work out the example for yourself,
before continuing to read.

 As long as process P2 is running, process P3 cannot run.

 If P3 cannot run, then it cannot leave the critical section S.
 If P3 does not leave the critical section, then P1 cannot enter.

As a result, P2 running (at medium priority) is blocking P 1 (at highest priority) from
running. This example is not an academic one. Many designers of real-time systems,
where priority can be crucial, have stumbled over issue. You can read the original paper
by Lampson and Redell to see their suggestion for handling the situation. Also, do a Web
search for priority inversion.

Review idea of atomic operations. Example:

Synchronization:
counting contest.
static int i;
Process A Process B
i = 0; i = 0;
while (i < 10) { while (i > -10) {
i++; i--;
} }
cout << "A wins"; cout << "B wins";
 Variable i is shared.
 Reference and assignment are each atomic.
 Will process A or process B win?
 Will they ever finish?
 If one finishes, will the other also finish?
 Does it help A to get a head start?

Synchronization: the use of atomic operations to ensure the correct operation of

cooperating processes.

The "too much milk" problem:

Person A Person B
3:00 Look in fridge. Out of milk.
3:05 Leave for store.

43
3:10 Arrive at store. Look in fridge. Out of milk.
3:15 Leave store. Leave for store.
3:20 Arrive home, put milk away. Arrive at store.
3:25 Leave store.
3:30 Arrive home. OH NO!

What does correct mean? One of the most important things in synchronization is to figure
out what you want to achieve.

Mutual exclusion: Mechanisms that ensure that only one person or process is doing
certain things at one time (others are excluded). E.g. only one person goes shopping at a
time.

Critical section: A section of code, or collection of operations, in which only one process
may be executing at a given time. E.g. shopping. It is a large operation that we want to
make "sort of" atomic.

There are many ways to achieve mutual exclusion, which we will be discussing all of this
week. Most involve some sort of locking mechanism: prevent someone from doing
something. For example, before shopping, leave a note on the refrigerator.

Three elements of locking:

1. Must lock before using. leave note

2. Must unlock when done. remove note
3. Must wait if locked. do not shop if note

1st attempt at computerized milk buying:

Processes A & B
1 if (NoMilk) {
2 if (No Note) {
3 Leave Note;
4 Buy Milk;
5 Remove Note;
6 }
7 }

What happens if we leave the note at the very beginning: does this make everything
work?

2nd attempt: Change meaning of note.

A buys if there is no note, B buys if there is a note. This gets rid of confusion.
Process A Process B
1 if (No Note) { if (Note) {
2 if (NoMilk) { if (NoMilk) {

44
3 Buy Milk; Buy Milk;
4 } }
5 Leave Note; Remove Note;
6 } }
 Does this work?
 How can we tell?
 When dealing with complex parallel programs, we cannot rely on our intuitions or
informal reasoning. We need to prove that the programs behave correctly. What
can we say about the above solution?

Suppose B goes on vacation. A will buy milk once and will not buy any more until B
returns. Thus this really does not really do what we want; it is unfair, and leads to
starvation.

3rd attempt: Use 2 notes:

Process A
1 Leave NoteA;
2 if (NoNoteB) {
3 if (NoMilk) {
4 Buy Milk;
5 }
6 }
7 Remove NoteA;

Process B is the same except interchange NoteA and NoteB.

What can we say about this solution?

Solution is almost correct. We just need a way to decide who will buy milk when both
leave notes (somebody has to hang around to make sure that the job gets done).

4th attempt: In case of tie, A will buy milk:

Process B stays the same as before.

Process A
1 Leave NoteA;
2 if (NoNoteB) {
3 if (NoMilk) {
4 Buy Milk;
5 }
6 } else {
7 while (NoteB) {
8 DoNothing;
9 }
10 if (NoMilk) {
11 Buy Milk;

45
12 }
13 }
14 Remove NoteA;

How do we know this is correct?

This solution works. But it still has two disadvantages:

 A may have to wait while B is at the store.

 While A is waiting it is consuming resources (busy-waiting).

ASYNCHRONOUS CONCURRENT EXECUTION

Introduction
Concurrent execution occurs when more than one thread exists in system at once and
these threads can execute independently or in cooperation. In Asynchronous execution,
threads generally operate independently of one another, but must occasionally
communicate and synchronize to perform cooperative tasks. This communication or
synchronization is usually complex and difficult to manage.

Mutual Exclusion
When one thread reads data that another thread is writing, or when one thread writes data
that another thread is also writing, indeterminate results can occur. We can solve this
problem by granting each thread exclusive access to the shared variable i.e. while one
thread increments the shared variable, all other threads desiring to do so will be made to
wait. When the executing thread finishes accessing the shared variable, the system will
allow one of the waiting processes to proceed. This is called serializing access to the
shared variable. Mutual Exclusion refers to the requirement of ensuring that no two
concurrent processes are in their critical section at the same time. In this manner,
threads will not be able to access shared data simultaneously.

Mutual exclusion needs to be enforced only when threads access shared modifiable data
—when threads are performing operations that do not conflict with one another (i.e.,

46
reading data), the system should allow the threads to proceed concurrently. When a
thread is accessing shared modifiable data, the thread is said to be in its critical section
(or critical region). To prevent the kinds of errors we encountered earlier, the system
should ensure that only one thread can execute the instructions in its critical section at a
time. If one thread attempts to enter its critical section while another thread executes its
critical section, the first thread should wait until the executing thread exits its critical
section. Once a thread has exited its critical section, a waiting thread (or one of the
waiting threads, if there are several), may enter and execute its critical section. If a thread
in its critical section terminates, either voluntarily or involuntarily, then the operating
system, in performing its termination housekeeping, must release mutual exclusion so
that other threads may enter their critical sections.

Critical Sections
A critical section is a piece of code that accesses a shared resource (data structure or
device) that must not be concurrently accessed by more than one thread of execution. A
critical section will usually terminate in fixed time, and a thread, task, or process will
have to wait for a fixed time to enter it (bounded waiting). Only one thread can be in its
critical section at once. We must be careful to avoid infinite loops and blocking inside a
critical section.

Mutual Exclusion Primitives

These indicate when critical data is about to be accessed.
• enterMutualExclusion - Delimits beginning of critical section
• exitMutualExclusion – Denotes end of critical section

The enterMutualExclusion() and exitMutualExclusion() primitives, invoke the most

fundamental operations inherent to mutual exclusion. These primitives exhibit the
following properties:
 Each machine-language instruction is executed indivisibly
 No assumption is made about the relative speeds of asynchronous
concurrent threads;

47
  A thread that is executing instructions outside its critical section cannot
prevent other threads from entering their critical sections;
 A thread cannot be indefinitely postponed from entering its critical
section.

Implementing Mutual Exclusion Primitives

Mutual exclusion primitives can be implemented using software
approach, hardware approach and semaphores.

Software Solution to Mutual Exclusion Problem

Besides hardware-supported solutions, some software solutions exist
that use busy waiting to achieve mutual exclusion. Examples of these
include the following:
 Dekker's algorithm
 Peterson's algorithm
 Lamport's Bakery algorithm

These algorithms do not work if out-of-order execution is used on the

platform that executes them. Programmers have to specify strict
ordering on the memory operations within a thread.

Dekker’s Algorithm

Dekker's algorithm is the first known correct solution to the mutual exclusion problem
in concurrent programming. The solution is attributed to Dutch Mathematician Th. J.
Dekker. It allows two threads to share a single-use resource without conflict, using only
shared memory for communication.

It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first
mutual exclusion algorithms to be invented.

Dekker’s Algorithm had the following attributes:

48
  It uses the notion of favored threads to determine entry into critical sections.
 It resolves the conflict over which thread should execute first.
 Each thread temporarily unsets critical section request flag
 It also favored status alternates between threads.
 It guarantees mutual exclusion.
 It also avoids previous problems of deadlock, indefinite postponement

It had four prior versions.

1. First version of Dekker’s algorithm
- Succeeded in enforcing mutual exclusion
- Used variable to control which thread can execute
- Constantly tests whether critical section is available
• Busy waiting
• Wastes significant processor time
- Problem known as lockstep synchronization
• Each thread can execute only in strict alternation
2. Second version of Dekker’s algorithm
- Removes lockstep synchronization
- Violates mutual exclusion
• Thread could be preempted while updating flag variable
- Not an appropriate solution
3. Third version of Dekker’s algorithm
- Set critical section flag before entering critical section test
- Once again guarantees mutual exclusion
- Introduces possibility of deadlock
• Both threads could set flag simultaneously
• Neither would ever be able to break out of loop
- Not a solution to the mutual exclusion problem
4. Fourth version
- Sets flag to false for small periods of time to yield control
- Solves previous problems, introduces indefinite postponement

49
 •Both threads could set flags to same values at same time
• Would require both threads to execute in tandem (unlikely but possible)
- Unacceptable in mission- or business-critical systems

Pseudocode
//flag[] is boolean array; and turn is an integer
flag[0] = false
flag[1] = false
turn = 0 // or 1
P0:
flag[0] = true;
while (flag[1] == true) {
if (turn ≠ 0) {
flag[0] = false;
while (turn ≠ 0) { // busy wait
}
flag[0] = true;
}
}
// critical section
...
turn = 1;
flag[0] = false;
// remainder section
P1:
flag[1] = true;
while (flag[0] == true) {
if (turn ≠ 1) {
flag[1] = false;
while (turn ≠ 1) {
// busy wait
}
flag[1] = true;
}
}
// critical section
...
turn = 0;
flag[1] = false; // remainder section

Peterson’s Algorithm

50
Peterson's algorithm was published in 1981, after more than a decade of experience and
hindsight about Dekker's algorithm. Peterson wanted a much simpler algorithm than
Dekker so that the proof of correctness is much easier.
Peterson’s Algorithm had the following characteristics:
– It still uses busy waiting, favored threads
– It requires fewer steps to perform mutual exclusion primitives
– It is easier to demonstrate its correctness
– It does not exhibit indefinite postponement or deadlock

Pseudocode
bool flag[0] = false;
bool flag[1] = false;
int turn;
P0: flag[0] = true;
P0_gate: turn = 1;
while (flag[1] && turn == 1)
{
// busy wait
}
// critical section
...
// end of critical section
flag[0] = false;
P1: flag[1] = true;
P1_gate: turn = 0;
while (flag[0] && turn == 0)
{
// busy wait
}
// critical section
...
// end of critical section
flag[1] = false;

Lamport’s Bakery Algorithm

The Bakery algorithm is arguably simpler than Dekker's algorithm (and certainly simpler
in the case of more than 2 processors), and is specifically designed to be fault tolerant.
This is because:

51
 - It gives a little bit of history about the definition of the mutual exclusion
problem and attempts to solve it up to 1974.
- The Bakery algorithm demonstrates that no hardware atomicity is
required to solve the mutual exclusion problem. Reads that overlap writes
to the same location can return any value and the algorithm still works.

Lamport’s Bakery Algorithm had the following attributes:

- Creates a queue of waiting threads by distributing numbered “tickets”
- Each thread executes when its ticket’s number is the lowest of all threads
- Unlike Dekker’s and Peterson’s Algorithms, the Bakery algorithm works
in multiprocessor systems and for n-threads relatively simple to
understand due to its real-world analog

JAVA Code for Lamport’s Bakery Algorithm

1. AtomicIntegerArray ticket = new AtomicIntegerArray(threads); //ticket for

threads in line, n - number of threads
2. AtomicIntegerArray entering = new AtomicIntegerArray(threads); //need this for
non-atomic max selection
3. //initialize both arrays
4. for(int i = 0; i < threads; ++i)
5. {
6. [Link](i, 0);
7. [Link](i, 0);
8. }
9. public void lock(int pid) //thread ID
10. {
11. [Link](pid, 1);
12. [Link](pid, max(ticket) + 1); //find max in the array and return it
13. [Link](pid, 0);
14. for(int i = 0; i < [Link](); ++i) {
15. if(i != pid) {
16. while([Link](i) == 1){} //wait while other thread picks a ticket
17. while([Link](i) != 0 &&( [Link](pid) > [Link](i) ||
18. ([Link](pid) == [Link](i) && pid > i)))
19. {}

52
 20. }
21. }
22. }
23. public void unlock(int pid) {
24. [Link](pid, 0);
25.

Hardware Solutions to the Mutual Exclusion Problem

Implementing mutual exclusion in hardware can improve performance and decrease
development time. In implementing mutual exclusion in hardware, there will be no need
to implement complex software mutual exclusion solutions like Lamport’s Algorithm.

Disabling Interrupts
 Works only on uniprocessor systems
 Prevents the currently executing thread from being preempted
 Could result in deadlock
• For example, thread waiting for I/O event in critical section
Test-and-Set Instruction
This uses a machine-language instruction to ensure that mutual exclusion primitives are
performed indivisibly.
– Such instructions are called atomic
– Machine-language instructions do not ensure mutual exclusionalone—the
software must properly use them. For example, programmers must
incorporate favored threads to avoid indefinite postponement
– Used to simplify software algorithms rather than replace them
Example of an atomic read-modify-write (RMW) cycle
testAndSet(a, b)
copies the value of
b
to

53
a
, then sets
b
to
true

Swap Instruction
This is similar in functionality to test-and-set, swap is more commonly implemented on
multiple architectures.
swap(a, b)
exchanges the values of
a
and
b
atomically

Semaphores
These are Software construct that can be used to enforce mutual exclusion.
They contain protected variable which can be accessed only via wait and signal
commands also called P and V operations, respectively.

Mutual Exclusion with Semaphores

Binary semaphore: allow only one thread in its critical section at once.
 Wait operation
 If no threads are waiting, allow thread into its critical section
 Decrement protected variable (to 0 in this case)
 Otherwise place in waiting queue
 Signal operation
 Indicate that thread is outside its critical section
 Increment protected variable (from 0 to 1)
 A waiting thread (if there is one) may now enter

Thread Synchronization with Semaphores

Semaphores can be used to notify other threads that events have occurred.
Taking Producer-consumer relationship as an example, Semaphores offer a clear,

54
easy-to-implement solution to this problem. This is described below:
 Producer enters its critical section to produce value
 Consumer is blocked until producer finishes
 Consumer enters its critical section to read value
 Producer cannot update value until it is consumed
Counting Semaphores
 Initialized with values greater than one
 Can be used to control access toa pool of identical resources
 Decrement the semaphore’s counter when taking resource from pool
 Increment the semaphore’s counter when returning it to pool
 If no resources are available, thread is blocked until a resource becomes
available

Implementing Semaphores
Semaphores can be implemented at application or kernel level.
 Application level: typically implemented by busy waiting inefficient
 Kernel implementations can avoid busy waiting
 Block waiting threads until they are ready

Kernel implementations can disable interrupts

• Guarantee exclusive semaphore access
• Must be careful to avoid poor performance and deadlock
• Implementations for multiprocessor systems must use a more
sophisticated approach

Summary
In Asynchronous execution, threads generally operate independently of one another, but
must occasionally communicate and synchronize to perform cooperative tasks. This
communication or synchronization is usually complex and difficult to manage.

55
Mutual Exclusion refers to the requirement of ensuring that no two concurrent processes
are in their critical section at the same time. A mutual exclusion (mutex) is a program
object that prevents simultaneous access to a shared resource. This means:
 Only one thread allowed access at one time
 Others must wait until resource is unlocked
 Serialized access
 Must be managed such that wait time is not unreasonable

Critical section is a piece of code that accesses a shared resource (data structure or
device) that must not be concurrently accessed by more than one thread of
execution. Mutual exclusion primitives can be implemented using software approach
(Dekker's algorithm, Peterson's algorithm, Lamport's bakery algorithm),
hardware approach(Disabling Interrupts, Test-and Set Instruction, Swap Instructions) and
Semaphores (software construct that can be used to enforce mutual exclusion).

8.0 SCHEDULING

Processor scheduling is the allocation of a computer’s processor power to specific tasks.

The practice uses the word “scheduling” because it assigns specific percentage of time

the processor is running to individual tasks. Processor scheduling is used to prevent a

certain task from monopolizing all of a computer’s processor resources. Processor

scheduling is also used to assign processors to different instances of windows in virtual

machines as well as to share CPU capacity with users connecting to a computer through

remote desktop.

When a system has a choice of processes to execute, it must have a strategy called a

processor scheduling policy (or discipline) for deciding which process to run at a given

time. A scheduling policy should attempt to satisfy certain performance criteria, such as

maximizing the number of processes that complete per unit time (i.e. throughput),

minimizing the time each process waits before executing (i.e. latency), preventing

56
indefinite postponement of processes, ensuring that each process completes before its

stated deadline, or maximizing processor utilization. Some of these goals, such as

maximizing processor utilization and throughput, are complementary; others conflict with

one another a system that ensures that processes will complete before their deadlines may

not achieve the highest throughput.

SCHEDULING LEVELS

There are basically three scheduling levels. Which are:

1. High-level scheduling and

2. Low- level scheduling

3. Intermediate level scheduling.

1. HIGH - LEVEL SCHEDULING: This is also called job scheduling or long-

term scheduling. It determines which jobs the system allows to compete actively

for system resources. This level is sometimes called admission scheduling,

because it determines which jobs gain admission to the system. Once admitted,

jobs are initiated and become processes or groups of processes. The high-level

scheduling policy dictates the degree of multiprogramming, the total number of

processes in a system at a given time. Entry of too many processes into the system

can saturate the system's resources, leading to poor performance. In this case, the

high-level scheduling policy may decide to temporarily prohibit new jobs from

entering until other jobs complete.

2. INTERMEDIATE SHEDULING: After the high-level scheduling policy has

admitted a job (which may contain one or more processes) to the system, the

intermediate-level scheduling policy determines which processes shall be allowed

57
 to compete for processors. This policy responds to short-term fluctuations in

system load. It temporarily suspends and resumes processes to achieve smooth

system operation and to help realize certain system wide performance goals. The

intermediate-level scheduler acts as a buffer between the admission of jobs to the

system and the assignment of processors to the processes representing these jobs.

3. LOW - LEVEL SCHEDULING: A system's low-level scheduling policy

determines which active process the system will assign to a processor when one

next becomes available. In many of today's systems, the low- and intermediate-

level schedulers are the only schedulers.

PREEMPTIVE AND NON - PREEMPTIVE SCHEDULING

Non – preemptive Scheduling disciplines: A scheduling discipline is non-preemptive if,

once the system has assigned a processor to a process; the system cannot remove that

processor from that process. Under a non - preemptive scheduling discipline, each

process, once given a processor, runs to completion or until it voluntarily releases its

processor. In non - preemptive systems, short processes can experience lengthy service

delays while longer processes complete, but turnaround times are more predictable,

because incoming high-priority processes cannot displace waiting processes. Because a

non - preemptive system cannot remove a process from a processor until it completes,

errant programs that never complete (e.g., by entering an infinite loop) may never release

control of the system. Also, in a non - preemptive system, executing unimportant

processes can make important processes wait. Non - preemptive scheduling provides

predictable turnaround times, which is important for batch processing systems that must

provide users with accurate job-completion times.

58
Preemptive Scheduling disciplines: A scheduling discipline is preemptive if the system

can remove the processor from the process it is running. Under a preemptive scheduling

discipline, the processor may execute a portion of a process's code and then perform a

context switch. Preemptive scheduling helps guarantee acceptable user response times.

To make preemption effective, the system must maintain many processes in main

memory, so that the next process is ready when a processor becomes available, a

preemptive system can take the processor away from a process. To prevent users from

monopolizing the system (either maliciously or accidentally), it is important to set an

interrupting clock or interval timer that periodically generates an interrupt, which allows

the operating system to execute. Once a processor is assigned to a process, the process

executes until it voluntarily releases its processor, or until the clock interrupt or some

other interrupt occurs. The operating system may then decide whether the running

process should continue or some other "next" process should execute.

PRIORITIES

Priority Schedulers often use priorities to determine how to schedule and dispatch

processes. Priorities may be statically assigned or may change dynamically. Priorities

quantify the relative importance of processes.

Static priorities: Remain fixed, so static-priority-based mechanisms are relatively easy to

implement and incur relatively low overhead. Such mechanisms are not, however,

responsive to changes in environment, even those that could increase throughput and

reduce latency.

Dynamic priorities: Dynamic priority mechanisms are responsive to change. For

example, the system may want to increase the priority of a process that holds a key

59
resource needed by a higher-priority process. After the first process relinquishes the

resource, the system lowers the priority, so that the higher-priority process may execute.

Dynamic priority schemes are more complex to implement and have greater over- head

than static schemes. Hopefully, the overhead is justified by the increased responsiveness

of the system. In multiuser systems, an operating system must provide reasonable service

to a large community of users but should also provide for situations in which a member

of the user community needs special treatment. A user with an important job may be

willing to pay a premium, i.e., to purchase priority, for a higher level of service. This

extra charge is merited because resources may need to be withdrawn from other paying

customers. If there were no extra charge, then all users would request the higher level of

service.

Scheduling Objectives

A system designer must consider a variety of factors when developing a scheduling

discipline, such as the type of system and the users' needs. For example, the scheduling

discipline for a real-time system should differ from that for an interactive desktop system;

users expect different results from these kinds of systems. Depending on the system, the

user and designer might expect the scheduler to:

1. Maximize throughput: A scheduling discipline should attempt to service the

maximum number of processes per unit time.

2. Maximize the number of interactive processes receiving "acceptable" response

times.

3. Maximize resource utilization: The scheduling mechanisms should keep the

resources of the system busy.

60
4. Avoid indefinite postponement: A process should not experience an unbounded

wait time before or while receiving service.

5. Enforce priorities: If the system assigns priorities to processes, the scheduling

mechanism should favor the higher-priority processes.

6. Minimize overhead: Interestingly, this is not generally considered to be one of

the most important objectives. Overhead often results in wasted resources. But a

certain portion of system resources effectively invested as overhead can greatly

improve overall system performance.

7. Ensure predictability: By minimizing the statistical variance in process response

times, a system can guarantee that processes will receive predictable service

levels. A system can accomplish these goals in several ways. In some cases, the

scheduler can prevent indefinite postponement of processes through aging—

gradually increasing a process's priority as the process waits for service.

Eventually, its priority becomes high enough that the scheduler selects that

process to run. The scheduler can increase throughput by favoring processes

whose requests can be satisfied quickly, or whose completion frees other

processes to run. One such strategy favors processes holding key resources. For

example, a low-priority process may be holding a key resource that is required by

a higher-priority process. If the resource is non pre-emptible, then the scheduler

should give the low-priority process more execution time than it ordinarily would

receive, so that it will release the key resource sooner. This technique is called

priority inversion, because the relative priorities of the two processes are reversed

so that the high-priority one will obtain the resource it requires to continue

61
 execution. Similarly, the scheduler may choose to favor a process that requests

underutilized resources, because the system will be more likely to satisfy this

process's requests in a shorter period of time. Many of these goals conflict with

one another, making scheduling a complex problem. For example, the best way to

minimize response times is to have sufficient resources available whenever they

are needed. The price for this strategy is that overall resource utilization will be

poor. In real-time systems, fast, predictable responses are crucial, and resource

utilization is less important. In other types of systems, the economics often makes

effective resource utilization imperative. Despite the differences in goals among

systems, many scheduling disciplines exhibit similar properties:

8. Fairness: A scheduling discipline is fair if all similar processes are treated the

same, and no process can suffer indefinite postponement due to scheduling issues.

9. Predictability: A given process always should run in about the same amount of

time under similar system loads.

10. Scalability: System performance should degrade gracefully (i.e., it should not

immediately collapse) under heavy loads.

Scheduling Criteria

To realize a system's scheduling objectives, the scheduler should consider process

behavior. A processor-bound process tends to use all the processor time that the system

allocates for it. An I /O-bound process tends to use the processor only briefly before

generating an I/O request and relinquishing it. Processor-bound processes spend most of

their time using the processor; I/O-bound processes spend most of their time waiting for

external resources (e.g., printers, disk drives, network connections, etc.) to service their

62
requests, and only nominal time using processors. A scheduling discipline might also

consider whether a process is batch or interactive. A batch process contains work for the

system to perform without interacting with the user. An interactive process requires

frequent inputs from the user. The system should provide good response times to an

interactive process, whereas a batch process generally can suffer reasonable delays.

Similarly, a scheduling discipline should be sensitive to the urgency (priority) of a

process. In a system that employs priorities, the scheduler should favor processes with

higher priorities. Schedulers can base their decisions on how frequently a higher priority

process has preempted a lower-priority one. Also, a process that has received much

execution time could be near completion and should be favored to help it reach

completion, free its resources for other processes to use and exit the system as soon as

possible. Similarly, a scheduler may maintain an estimate of how much time remains

before a process completes. It is easy to prove that average waiting times can be

minimized by running those processes first that require the minimum runtime until

completion. Unfortunately, a system rarely knows exactly how much more time each

process needs to complete.

SCHEDULING ALGORITHMS

Scheduling algorithms determine at runtime which process runs next. These algorithms

decide when and for how long each process runs; they make choices about preemptibility,

priorities, running time, time-to-completion, fairness and other process characteristics.

63
1. First-In-First-Out (FIFO) Scheduling: Perhaps the simplest scheduling

algorithm is first-in-first-out (FIFO), also called first-come-first-served (FCFS).

Processes are dispatched according to their arrival time at the ready queue. FIFO

is non- preemptive once a process has a processor, the process runs to completion.

FIFO is fair in that it schedules processes according to their arrival times, so all

processes are treated equally, but somewhat unfair because long processes make

short processes wait, and unimportant processes make important processes wait.

2. Round-Robin (RR) Scheduling: In round-robin (RR) scheduling, processes are

dispatched FIFO but are given a limited amount of processor time called a time

slice or a quantum. If a process does not complete before its quantum expires, the

system preempts it and gives the processor to the next waiting process. The

system then places the preempted process at the back of the ready queue. The

system can minimize preemption overhead through efficient context-switching

mechanisms and by keeping waiting processes in main memory.

3. Selfish Round-Robin(SRR): Selfish round-robin uses aging to gradually increase

process priorities over time. In this scheme, as each process enters the system, it

first resides in a holding queue, where it ages until its priority reaches the level of

processes in the active queue. At this point, it is placed in the active queue and

scheduled round-robin with other processes in the queue. The scheduler

dispatches only processes in the active queue, meaning that older processes are

favored over those that have just entered the system. In SRR, a process's priority

increases at a rate a, while in the holding queue, and at a rate b, where b ≤ a, in

the active queue. When b < a, processes in the holding queue age at a higher rate

64
 than those in the active queue, so they will eventually enter the active queue and

contend for the processor.

4. Shortest-process-first (SPF): This is a non- preemptive scheduling discipline or

algorithm in which the scheduler selects the waiting process with the smallest

estimated run-time-to-completion. SPF reduces average waiting time over FIFO.

The waiting times, however, have a larger variance (i.e., are more unpredictable)

than FIFO, especially for large processes. SPF favors short processes at the

expense of longer ones. As a result, SPF can minimize the average waiting time of

processes as they pass through the system. A key problem with SPF is that it

requires precise knowledge of how long a process will run, and this information

usually is not available.

5. Highest-Response-Ratio-Next (HRRN) Scheduling: Brinch Hansen developed

the highest-response-ratio-next (HRRN) policy that corrects some of the

weaknesses in SPF, particularly the excessive bias against longer processes and

the excessive favoritism toward short processes. HRRN is a non- preemptive

scheduling discipline in which each process's priority is a function not only of its

service time but also of its time spent waiting for service. Once a process obtains

it, the process runs to completion. HRRN calculates dynamic priorities according

to the formula:

Because the service time appears in the denominator, shorter processes receive

preference. However, because the waiting time appears in the numerator, longer

processes that have been waiting will also be given favorable treatment. This

65
 technique is similar to aging and prevents the scheduler from indefinitely

postponing processes.

6. Shortest-Remaining-Time (SRT) Scheduling: Shortest-remaining-time (SRT)

scheduling is the preemptive counterpart of SPF that attempts to increase

throughput by servicing small arriving processes. In SRT, the scheduler selects

the process with the smallest estimated run-time-to-completion. In SPF, once a

process begins executing, it runs to completion. In SRT, a newly arriving process

with a shorter estimated run-time preempts a running process with a longer run-

time-to-completion.

7. Multilevel feedback queues: A new process enters the queuing network at the tail

of the highest queue. The process progresses through that queue in FIFO order

until the process obtains a processor. If the process completes its execution, or if it

releases the processor to wait for I/O completion or the completion of some other

event, exits the queuing network. If a process's quantum expires before the

process voluntarily releases the processor, the system places the process at the tail

of the next lower-level queue. As long as the process uses the full quantum

provided at each level, it continues to move to the tail of the next lower queue.

A running process is preempted by one arriving in a higher queue. In this system, a

process in a lower queue can suffer indefinite postponement, if a higher queue always

contains at least one process. This can occur in systems that have a high rate of incoming

processes to be serviced, or in which there are several I/O-bound processes consuming

their quanta.

DEADLINE SCHEDULING

66
In deadline scheduling, certain processes are scheduled to be completed by a specific

time or deadline. These processes may have high value if delivered on time and little or

no value otherwise. Deadline scheduling is complex. First, the user must supply the

precise resource requirements in advance to ensure that the process is completed by its

deadline. Such information is rarely available. Second, the system should execute the

deadline process without severely degrading service to other users. Also, the system must

carefully plan its resource requirements through to the deadline. This may be difficult,

because new processes may arrive, making unpredictable demands. Finally, if many

deadline processes are active at once, scheduling could become extremely complex. The

intensive resource management that deadline scheduling requires may generate

substantial overhead service to other processes.

Real-Time Scheduling: Real time scheduling are a special class of scheduling

algorithms of which it is required that they can guarantee a process will be done before its

deadline. The only way these algorithms can work if they at least know when the

deadline for a process is, and how much the process takes of the system.

CONCLUSION

When a system has a choice of processes to execute, it must have a strategy called a

processor scheduling policy (or discipline) for deciding which process to run at a given

time. High-level scheduling sometimes called job scheduling or long-term scheduling

determines which jobs the system allows to compete actively for system resources. The

high- level scheduling policy dictates the degree of multiprogramming the total number

of processes in a system at a given time. After the high-level scheduling policy has

admitted a job (which may contain one or more processes) to the system, the

67
intermediate-level scheduling policy determines which processes shall be allowed to

compete for a processor. This policy responds to short-term fluctuations in system load.

A system's low-level scheduling policy determines which ready process the system will

assign to a processor when one next becomes available. Low-level scheduling policies

often assign a priority to each process, reflecting its importance—the more important a

process, the more likely the scheduling policy is to select it to execute next.

9.0 Context Switching

Context switching is the procedure of storing the state of an active process for the CPU
when it has to start executing a new one. For example, process A with its address space
and stack is currently being executed by the CPU and there is a system call to jump to a
higher priority process B; the CPU needs to remember the current state of the process A
so that it can suspend its operation, begin executing the new process B and when done,
return to its previously executing process A.
Context switches are resource intensive and most operating system designers try to
reduce the need for a context switch. They can be software or hardware governed
depending upon the CPU architecture.
Context switches can relate to either a process switch, a thread switch within a process or
a register switch. The major need for a context switch arises when CPU has to switch
between user mode and kernel mode but some OS designs may obviate it.
A common approach to context switching is making use of a separate stack per
switchable entity (thread/process), and using the stack to store the context itself. This way
the context itself is merely the stack pointer. For example,
pusha ;push all registers
mov OLD_ESP, SAVED_LOCATION
mov NEW_ESP, esp
popa
here the act of context switching is done by changing the stack pointer to a new location,
and the registers are stored on the stack itself.

68
In computing, a context switch is the process of storing and restoring the state (context)
of a process or thread so that execution can be resumed from the same point at a later
time. This enables multiple processes to share a single CPU and is an essential feature of
a multitasking operating system. What constitutes the context is determined by the
processor and the operating system.

Context switches are usually computationally intensive, and much of the design of
operating systems is to optimize the use of context switches. Switching from one process
to another requires a certain amount of time for doing the administration – saving and
loading registers and memory maps, updating various tables and lists etc.

A context switch can mean a register context switch, a task context switch, a stack
frame switch, a thread context switch, or a process context switch.

When to switch?

There are three potential triggers for a context switch:

Multitasking

Most commonly, within some scheduling scheme, one process needs to be switched out
of the CPU so another process can run. This context switch can be triggered by the
process making itself unrunnable, such as by waiting for
an I/O or synchronization operation to complete. On a pre-emptive multitasking system,
the scheduler may also switch out processes which are still runnable. To prevent other
processes from being starved of CPU time, preemptive schedulers often configure a timer
interrupt to fire when a process exceeds its time slice. This interrupt ensures that the
scheduler will gain control to perform a context switch.
Interrupt handling

Modern architectures are interrupt driven. This means that if the CPU requests data from
a disk, for example, it does not need to busy-wait until the read is over; it can issue the
request and continue with some other execution. When the read is over, the CPU can
be interrupted and presented with the read. For interrupts, a program called an interrupt
handler is installed, and it is the interrupt handler that handles the interrupt from the disk.

When an interrupt occurs, the hardware automatically switches a part of the context (at
least enough to allow the handler to return to the interrupted code). The handler may save
additional context, depending on details of the particular hardware and software designs.
Often only a minimal part of the context is changed in order to minimize the amount of

69
time spent handling the interrupt. The kernel does not spawn or schedule a special
process to handle interrupts, but instead the handler executes in the (often partial) context
established at the beginning of interrupt handling. Once interrupt servicing is complete,
the context in effect before the interrupt occurred is restored so that the interrupted
process can resume execution in its proper state.
User and kernel mode switching
When a transition between user mode and kernel mode is required in an operating
system, a context switch is not necessary; a mode transition is not by itself a context
switch. However, depending on the operating system, a context switch may also take
place at this time.

Steps

In a switch, the state of the first process (assuming that the first process is the process in
execution and is to be switched) must be saved somehow, so that, when the scheduler
gets back to the execution of the first process, it can restore this state and continue.

The state of the process includes all the registers that the process may be using, especially
the program counter, plus any other operating system specific data that may be necessary.
This data is usually stored in a data structure called a process control block (PCB), or
switch frame.

In order to switch processes, the PCB for the first process must be created and saved. The
PCBs are sometimes stored upon a per-process stack in kernel memory (as opposed to the
user-mode call stack), or there may be some specific operating system defined data
structure for this information.

Since the operating system has effectively suspended the execution of the first process, it
can now load the PCB and context of the second process. In doing so, the program
counter from the PCB is loaded, and thus execution can continue in the new process.
New processes are chosen from a queue or queues (often referred as ready queue).
Process and thread priority can influence which process continues execution, with
processes of the highest priority checked first for ready threads to execute.

Performance

Context switching itself has a cost in performance, due to running the task
scheduler, TLB flushes, and indirectly due to sharing the CPU cache between multiple
tasks.[2] Switching between threads of a single process can be faster than between two

70
separate processes, because threads share the same virtual memory maps, so a TLB flush
is not necessary.[3]
Hardware vs. software

Context switching can be performed primarily by software or hardware. Some

processors, like the Intel 80386 and its successors,[4] have hardware support for context
switches, by making use of a special data segment designated the task state segment or
TSS. A task switch can be explicitly triggered with a CALL or JMP instruction targeted
at a TSS descriptor in the global descriptor table. It can occur implicitly when an interrupt
or exception is triggered if there's a task gate in the interrupt descriptor table. When a task
switch occurs the CPU can automatically load the new state from the TSS.

As with other tasks performed in hardware, one would expect this to be rather fast;
however, mainstream operating systems, including Windows and Linux,[5] do not use this
feature. This is mainly due to two reasons:

 Hardware context switching does not save all the registers (only general purpose
registers, not floating point registers — although the TS bit is automatically turned on
in the CR0 control register, resulting in a fault when executing floating point
instructions and giving the OS the opportunity to save and restore the floating point
state as needed).
 Associated performance issues, e.g., software context switching can be selective
and store only those registers that need storing, whereas hardware context switching
stores nearly all registers whether they are required or not.

A context switch is a procedure that a computer's CPU (central processing unit) follows
to change from one task (or process) to another while ensuring that the tasks do not
conflict. Effective context switching is critical if a computer is to provide user-
friendly multitasking.

In a CPU, the term "context" refers to the data in the registers and program counter at a
specific moment in time. A register holds the current CPU instruction. A program
counter, also known as an instruction address register, is a small amount of
fast memory that holds the address of the instruction to be executed immediately after the
current one.

A context switch can be performed entirely in hardware (physical media). Older CPUs,
such as those in the x86 series, do it that way. However, most modern CPUs perform

71
context switches by means of software (programming). A modern CPU can perform
hundreds of context switches per second. Therefore, the user gets the impression that the
computer is performing multiple tasks in a parallel fashion, when the CPU actually
alternates or rotates between or among the tasks at a high rate of speed.

In your average, memory-protected environment, a "context" is a virtual address space,

the executable contained in it, its data etc.
A "context switch" occurs for a variety of reasons - because a kernel function has been
called, the application has been preempted, or because it had yielded its time slice.
A context switch involves storing the old state and retrieving the new state. The actual
information stored and retrieved may include EIP, the general registers, the segment
registers, CR3 (and the paging structures), FPU/MMX registers, SSE registers and other
things. Because a context switch can involve changing a large amount data it can be the
one most costly operation in an operating system.
There are many ways of performing a context switch. The x86 CPU provides a way of
doing it completely in hardware, but for performance and portability reasons most
modern OS's do context switches in software.
Software Context Switching
Software context switching can be used on all CPUs, and can be used to save and reload
only the state that needs to be changed. The basic idea is to provide a function that saves
the current stack pointer (ESP) and reloads a new stack pointer (SS:ESP). When the
function is called EIP would be stored on the old stack and a new EIP would be popped
off the new stack when the function returns. Of course the operating system usually needs
to change much more than just the stack and EIP.
Eflags, the general registers and any data segment registers should also be pushed on the
old stack and popped off the new stack. If the paging structures need to be changed, CR3
will also need to be reloaded.
The FPU/MMX and SSE state could be saved and reloaded, but the CPU can also be
tricked into generating an exception the first time that an FPU/MMX or SSE instruction
is used by copying the hardware context switch mechanism (setting the TS flag in CR0).
Details
When the CPU changes to a higher privilege level (CPL 0 being the highest) it will load
new values for SS and ESP from the Task State Segment (TSS). If the operating system
uses multiple privilege levels it must create and load a TSS. An interrupt generated
while the processor is in ring 3 will switch the stack to the resulting permission level
stack entry in the TSS. During a software context switch the values for SS0:ESP0 (and
possibly SS1:ESP1 or SS2:ESP2) will need to be set in the TSS. If the processor is
operating in Long Mode, the stack selectors are no longer present and the RSP0-2 fields
are used to provide the destination stack address.

72
If a context switch also entails a change in IO port permissions, a different TSS may be
loaded for each Process. When running virtual 8086 tasks, the IO permission map in the
TSS isn't checked to provide I/O port protection. IO protection can be implemented by
setting the IO Permission Level to 0. This will generate a General Protection Fault when
a process in ring 3 attempts to write to or read from an IO port. The GP fault handler can
then check permissions and carry out the port IO on behalf of the user-mode code.
Other Possibilities
During a context switch the operating system can do additional work that isn't strictly
part of the context switch. One common thing is calculating the amount of time the last
thread/task/process used so that software (and the end user) can determine where all the
CPU time is going. Another possibility would be dynamically changing
thread/task/process priorities.
Performance Considerations
Translating a virtual address to a physical address is expensive. The processor must
access the pages table structures, which usually have 3-4 levels. Thus, a single memory
access actually requires 4-5 memory accesses.
To mitigate this issue, most modern processors cache virtual-to-physical translations in a
translation look aside buffer (TLB). The TLB is part of the MMU and is (mostly)
transparent to the system developer and users.
When virtual memory is updated -- for instance, when one process's address space is
replaced with another's during a software context switch -- the TLB suddenly contains
"stale" translations that are no longer valid. These translations must be flushed for correct
behaviour. Writing to CR3 will flush the TLB. However, by writing to CR3, you also
eliminate all translations for the kernel, in addition to the last user process. This is less
than ideal, as the next few operations must wait for the slow virtual-to-physical
translations.
Recent Intel and AMD processors sport a tagged TLB, which allow you to tag a given
translation with a certain address space configuration. In this scheme TLB entries never
get "stale", and thus there is no need to flush the TLB.
Hardware Context Switching

Some CPU's have a special mechanism to perform context switches in hardware. The
following information gives details on 80x86 CPU's only.
The hardware context switching mechanism (called Hardware Task Switching in the
CPU manuals) can be used to change all of the CPU's state except for the FPU/MMX and
SSE state. To use the hardware mechanism you need to tell the CPU where to save the
existing CPU state, and where to load the new CPU state. The CPU state is always stored
in a special data structure called a TSS (Task State Segment).
To trigger a context switch and tell the CPU where to load it's new state from the far
version of CALL and JMP instructions are used. The offset given is ignored, and the

73
segment is used to refer to a "TSS Descriptor" in the GDT. The TSS descriptor is used to
specify the base address and limit of the TSS to be used to load the new CPU state from.
The CPU has a register called the "TR" (or Task Register) which tells which TSS will
receive the old CPU state. When the TR register is loaded with an "LDTR" instruction
the CPU looks at the GDT entry (specified with LDTR) and loads the visible part of TR
with the GDT entry, and the hidden part with the base and limit of the GDT entry. When
the CPU state is saved the hidden part of TR is used.

A step further with Hardware Switches

In addition to the CALL and JMP instructions, a context switch can be triggered by a
using a Task-Gate Descriptor. Unlike TSS Descriptors, task-gate descriptors can be in the
GDT, LDT or IDT. Normally, task-gate descriptors are used in the IDT, so that an
exception (or IRQ) can cause a context switch, which is the only way of handling a
double fault exception with complete reliability.
The design of the basic hardware mechanism is limited by the number of usable entries in
the GDT because TSS descriptors can be in the GDT only (theoretical limit is 8190
tasks). However, it is possible to avoid this restriction by dynamically changing TSS
descriptor/s, by setting the TSS descriptor's base before each context switch. Care must
be taken when using this approach when task-gate descriptors in the IDT are also used
(the TSS descriptors referred to by each task-gate descriptor would have to be constant).
Also context switches can't be initiated with a CALL instruction, because the CPU saves
the GDT entry to use for the return in the TSS's "backlink" field.
If the FPU/MMX and SSE state also needs to be changed during a context switch there
are a few options. The data could be explicitly saved by any code that causes a context
switch, or the CPU can generate an exception the first time an FPU/MMX or SSE
instruction is used. With the second option, the exception handlers would save the old
FPU/MMX/SSE state and reload the new state. This option may prevent this data from
being changed when it's not necessary (for e.g. when no tasks or only one task is using
them), but fails to work correctly in a multiprocessor environment without additional
synchronization which may be more expensive than using the first option.
Performance Considerations
Because the hardware mechanism saves almost all of the CPU state it can be slower than
is necessary. For example, when the CPU loads new segment registers it does all of the
access and permission checks that are involved. As most modern operating systems don't
use segmentation loading the segment registers during context switches may be not be
required, so for performance reasons these operating systems tend not to use the hardware
context switching mechanism, due to it not being used as much CPU manufacturers don't
optimize CPUs for this method anymore (AFAIK). In addition the new 64 bit CPU's do
not support hardware context switches when in 64 bit/long mode.
However, there was an interesting post on OSNews by Aage in July 2004, quantifying the
amount of unavoidable hardware overhead involved in a context switch. It appears that

74
the hardware overhead in a context switch on a modern P4 processor dwarfs the overhead
involved in saving/loading registers (995ns of HW overhead vs 67ns to save/load
registers). From this, it would appear that any performance gains from switching to
software task switching would be minimal, amounting to no more than a few percentage
points. However, Brendan points out in this post that this is horrendously wrong and
explains why.
In your average, memory-protected environment, a "context" is a virtual address space,
the executable contained in it, its data etc.
A "context switch" occurs for a variety of reasons - because a kernel function has been
called, the application has been preempted, or because it had yielded its time slice.
A context switch involves storing the old state and retrieving the new state. The actual
information stored and retrieved may include EIP, the general registers, the segment
registers, CR3 (and the paging structures), FPU/MMX registers, SSE registers and other
things. Because a context switch can involve changing a large amount data it can be the
one most costly operation in an operating system.
There are many ways of performing a context switch. The x86 CPU provides a way of
doing it completely in hardware, but for performance and portability reasons most
modern OS's do context switches in software.

REFERENCES
Harvey M. Deitel, Paul J. Deitel, David R. Choffnes, “Operating Systems,”
Asynchronous Concurrent Execution (3rd Edition), Chapter 5, pp. 185-244.
Leslie Lamport, "A Fast Mutual Exclusion Algorithm," ACM Transactions on Computer
Systems (TOCS), Vol. 5, No. 1, pp.l-11,Feb. 1987.

Atwood, J. W., "Concurrency in Operating Systems," Computer, Vol. 9, No. fO, October
1976, pp. 18-26.

Chandy, K. M., and J. Misra, "Asynchronous Distributed Simulation via a Sequence of

Parallel Computations," Communications o f the ACM, Yo\. 24, No. 4, April 1981.

Peterson, G L., "Myths about the Mutual Exclusion Problem," Information Processing
Letters, Vol. 12, No. 3, June 1981, pp. 115-
116.

[Link]

10.0 General Terms in Operating systems

75
concurrent
The description of a process or thread that exists in a system simultaneously
with other processes and/or threads.
asynchronous
Pertaining to events that are not synchronized in time or do not occur in
regular or predictable time intervals.
synchronous
Occurring with a regular or predictable time relationship.

Mutual exclusion

mutual exclusion
A situation in which at most one process can be engaged in a specified
activity at a time.
race condition
A situation where the (uncontrolled) ordering of events can affect the
outcome of the situation.
serialize
To control access to a variable so that only one thread can access the variable
at a time.
producer
A process or thread that creates data and places it into a shared object.
consumer
A process or thread that removes data from a shared object and processes it.
critical section
A section of code which performs operations on a shared resources.
mutual exclusion primitive
A fundamental operation which is needed to implement mutual exclusion.
indefinite postponement
A situation in which a process or thread is waiting for an event which may
never occur.
deadlock
A situation in which two or more processes are prevented from continuing
while each waits for resources to be freed by the continuation of the other.
busy wait
A situation in which a process, while not blocked, continuously checks for a
condition which will allow it to proceed.
atomic operation
An operation which cannot be interrupted.
Semaphores
Semaphore
semaphore
A synchronization variable accessable only through wait and signal
procedures.
binary semaphore
A semaphore that can only have the values 0 and 1.

76
counting semaphore
A semaphore that maintains a count between zero and some maximum value.

Asynchronism
asynchronism, asynchronous, asynchrony means: 1. Operating at a rate determined by
the system rather than at a regular rate of chronological time; without a fixed time
pattern. 2. Describing the relationship of two or more systems that run at their own rates
and interact at unpredictable time
A remote procedure call (RPC) is an inter-process communication that allows
a computer program to cause a subroutine or procedure to execute in another address
space (commonly on another computer on a shared network) without the programmer
explicitly coding the details for this remote interaction.
Time-sharing is the sharing of a computing resource among many users by means
of multiprogramming and multi-tasking.
Protected variables are variables that are visible only to the class to which they belong,
and any subclasses.
A semaphore is a protected variable or abstract data type that provides a simple but
useful abstraction for controlling access by multiple processes to a common resource in
a parallel programming environment.s

Tutorial Questions
Describe the two general roles of an operating system, and elaborate why these roles are
important.
Multi-programming enables more than a single process to apparently execute
simultaneously. How is this achieved on a uni-processor?
Describe the difference between external and internal fragmentation. Indicate which of
the two are most likely to be issues on (i) a simple memory management machine
using base limit registers and static partitioning, and (ii) a similar machine using
dynamic partitioning.

What are the attributes of a process?

What is the relationship between threads and processes?
Describe how a multi-threaded application can be supported by a user-level threads
package.
Name some advantages and disadvantages of user-level threads.

What happens when a context switch occurs?

Describe the concept of a thread. What differences are there between user level threads
and kernel level threads?
How do these differences affect performance (give an example)?
Discuss the motivation for spooling systems.

77
What are the five major activities of an operating system with regard to process
management?
What are the three major activities of an operating system with regard to memory
management?
What are the three major activities of an operating system with regard to secondary-
storage management?
What are the five major activities of an operating system with regard to file management?

Describe four general strategies for dealing with deadlock.

Assuming the operating system detects the system is deadlocked, what can the operating
system do to recover from deadlock?
How does banker's algorithm prevent deadlock?
Describe the general strategy behind deadlock prevention, and give an example of a
practical deadlock prevention method.

Give four reasons why the study of concurrency is appropriate and important for students
of Operating System?
When does indeterminate result occur in concurrent processes?
What is Mutual Exclusion?
What is CPU scheduling? (ii) State the basic assumptions behind most scheduling
algorithms.

Give four reasons why the study of concurrency is appropriate and important for students
of Operating System?
When does indeterminate result occur in concurrent processes?
How are these problems solved?
Give an example of a semaphore operation.

What are asynchronous processes?

Why is parallelism complex?
What are asynchronism problems?
Discuss the problems of asynchronism with mutual exclusion

What happens when a context switching occurs?

Uses a context switching principle to switch from running one process to running another
process.
How does machine implement context switching?
Discuss the motivation for spooling systems.

78
What are the attributes of a process? (ii) How does the OS implement the process
abstraction?
What is the relationship between threads and processes?
Describe how a multi-threaded application can be supported by a user-level threads
package.
Name some advantages and disadvantages of user-level threads

Describe how a multi-threaded application can be supported by a user-level threads

package.
Name some advantages and disadvantages of user-level threads.
Consider a situation when threads run on a uni-processor, how long will the acquiring
thread spin?
Why do we allow threads to access same memory?

State and explain the conditions for deadlock.

Write any deadlock detection algorithm you know.
What is Mutual Exclusion?
What is CPU scheduling? (ii) State the basic assumptions behind most scheduling
algorithms.
Describe the two general roles of an operating system, and elaborate why these roles are
important.
Using a simple system call as an example (e.g. getpid, or uptime), describe what is
generally involved in providing the result, from the point of calling the function in
the C library to the point where that function returns.
Why must the operating system be more careful when accessing input to a system call (or
producing the result) when the data is in memory instead of registers?
Describe the three state process models, describe what transitions are valid between the
three states, and describe an event that might cause such a transition.
Multi-programming (or multi-tasking) enables more than a single process to apparently
execute simultaneously. How is this achieved on a uniprocoessor?
What is a process? What are attributes of a process?
What is the relationship between threads and processes?
Describe how a multi-threaded application can be supported by a user-level threads
package. It may be helpful to consider (and draw) the components of such a
package, and the function they perform.
Name some advantages and disadvantages of user-level threads.
Why are user-level threads packages generally cooperatively scheduled?
Enumerate the advantages and disadvantages of supporting multi-threaded applications
with kernel-level threads.
Describe a sequence of step that occurs when a timer interrupt occurs that eventually
results in a context switch to another application.
Context switching between two threads of execution within the operating system is
usually performed by a small assembly language function. In general terms, what
does this small function do internally?
What is a critical region? How do they relate to controlling access to shared resources?

79
What are three requirements of any solution to the critical sections problem? Why are the
requirements needed?
Why is turn passing a poor solution to the critical sections problem?
Interrupt disabling and enabling is a common approach to implementing mutual
exclusion, what are its advantages and disadvantages?
What is a test-and-set instruction? How can it be used to implement mutual exclusion?
Consider using a fragment of psuedo-assembly language aid you explanation.
What is the producer consumer problem? Give an example of its occurrence in operating
systems.
A semaphore is a blocking synchronisation primitive. Describe how they work with the
aid of pseudo-code. You can assume the existence of a thread_block() and a
thread_wakeup() function.
Describe how to implement a lock using semaphores.
What is deadlock? What is starvation? How do they differ from each other?
What are the four conditions required for deadlock to occur?
Describe four general strategies for dealing with deadlocks.
For single unit resources, we can model resource allocation and requests as a directed
graph connecting processes and resources. Given such a graph, what is involved
in deadlock detection.
What must the banker's algorithm know a priori in order to prevent deadlock?
Assuming the operating system detects the system is deadlocked, what can the operating
system do to recover from deadlock?
Describe the general strategy behind deadlock prevention, and give an example of a
practical deadlock prevention method.

Give an example of a scenario that might benefit from a file system supporting an
append-only access write.

Give a scenario where choosing a large file system block size might be a benefit; give
an example where it might be a hindrance.

What file access pattern is particularly suited to chained file allocation on disk?

80