Tanta University

Faculty of science

Mathematics Dept.

Division of computer science

Introduction to Operating

systems
Prepared by

Dr. Mousaad Wageh Hassan

Lecturer in computer science,

Faculty of science

Tanta University

2024
 Computer science vision ‫رؤية برنامج علوم الحاسب اﻵلي‬
Leadership at the local and regional ٕ ‫وا‬ ‫ي ا‬ ‫ا‬ ‫ا دة‬
levels in the field of computer science
to prepare a distinguished graduate ‫در‬ ‫اد‬ ٕ ‫ما‬ ‫ل‬
capable of competing in the labor
market and conducting integrated ‫و ا ٕ اء‬ ‫ق ا‬ ‫ا‬
scientific research aimed at
community service. . ‫ا‬ ٕ‫ف ا‬
***********************

Computer science mission ‫رسالة برنامج علوم الحاسب اﻵلي‬

ً ‫ً و‬ ‫ء‬ ‫ٕ اد‬ ‫م ا‬
The program is committed to
preparing a qualified graduate who is
able to conduct meaningful and ‫ در‬، ‫و ا‬ ‫م ا‬
constructive scientific research to
develop the educational process and ‫دف و ء‬ ‫ا ٕ اء‬
compute in the local and international
labor market to meet the requirements ‫ق ا‬ ‫ وا‬، ‫ا‬ ‫ا‬
of societal and environmental
problems. ‫ت‬ ‫ت ا‬ ، ‫وا و‬ ‫ا‬

. ‫وا‬ ‫ا‬
***********************
‫أهداف برنامج علوم الحاسب اﻵلي‬
Computer science aims to: ‫يهدف برنامج علوم الحاسب اﻵلي‬
 Providing students with ‫ا‬ ‫ و ا ب‬
theoretical knowledge in the
various branches of computer ٕ‫ت ا‬ ٔ ‫ا‬ ‫ ًءا‬، ‫وع م ا‬
sciences, ranging from the basics
‫رة‬ ‫ا‬ ‫ود ا ث ا‬
to the limits of free research in
selected topics with . ‫ا‬ ‫ودور‬ ‫ما‬
understanding of computer
science and its role in ً ‫ب‬ ‫ا‬ ‫ا رات ا‬ 
community development.
‫ا و ت‬ ‫ا ر ا‬ ٕ‫ا‬
 Developing the appropriate

2
 scientific skills for students . ‫ا‬ ‫ا‬
along with continuous training
in different programs and ‫رات‬ ‫ا‬ ‫ب‬ ‫ب ا‬ ‫ ا‬
programming languages.
‫ا‬ ‫وا‬ ‫ا‬
 Provide students with a set of
personal and transferable skills : ‫ذ‬ ‫؛‬ ‫ا‬ ‫ا‬
that increase their chances of
working in the future including ، ‫ا‬ ‫ي وا‬ ‫وا ض ا‬ ‫ا‬
writing, oral presentation,
.‫ت‬ ‫ا‬ ‫رات‬ ‫و‬
teamwork, as well as
information technology skills. ‫رة‬ ‫و‬ ‫ا ا‬ ‫ا‬ 
 Promote self-learning of
knowledge and develop students' ‫ت‬ ‫ت وا‬ ‫ا‬ ‫ر‬ ‫ا‬ ‫ب‬ ‫ا‬
ability to find, understand, and
. ‫و‬ ‫و‬ ‫ا‬
analyze information and
computer data. ‫ر‬ ‫ب‬ ‫رة ا‬ 
 Develop students' ability to
apply their knowledge and skills ‫وا‬ ‫ت ا‬ ‫ا‬ ‫و را‬
to solve theoretical and practical
‫ا‬ ‫ا‬ ‫ًء‬ ‫ت ا‬ ‫ا‬
problems in different fields
based on ethical, economic, and . ‫د وا‬ ‫وا‬ ٔ ‫ا‬
environmental aspects.
 Prepare students for a ‫أو‬ ‫ر‬ ‫ب‬ ‫ ا ٕ اد ا‬
specialized career path or degree . ‫ما‬ ‫در‬
in computer science.
***************************

3
Preface

An operating system acts as an intermediary between the user of a

computer and the computer hardware. The purpose of an operating system is
to provide an environment in which a user can execute programs in a
convenient and efficient manner. An operating system is software that
manages the computer hardware. The hardware must provide appropriate
mechanisms to ensure the correct operation of the computer system and to
prevent user programs from interfering with the proper operation of the
system. Operating systems are an essential part of any computer system.
Similarly, a course on operating systems is an essential part of any computer-
science education. We wrote this book as a text for an introductory course in
operating systems at the junior or senior undergraduate level. The topics of
this book are taken from “Operating system concepts 8th edition- 2009”. We
hope that students will find it useful. It provides a clear description of some
concepts that underlie operating systems.

This book is organized in seven chapters:

 Chapter 1: Explains what operating systems are, what they do, how they
are designed and constructed. It discusses what the common features of
an operating system are, what an operating system does for the user,
and what it does for the computer-system operator.
 Chapter 2: Describes the process concept and concurrency as the heart
of modern operating systems. It covers the methods for inter-process
communication.
 Chapter 3: Discusses the methods of CPU scheduling.
 Chapter 4: Explains process synchronization.
 Chapter 5: discusses the concept of deadlock and methods of handling.
4
  Chapter 6: Deals with the management of main memory during the
execution of a process. It explains different management algorithms.
 Chapter 7: Discusses the secondary storage devices such as magnetic
disks.

Course objectives:

 To describe the major components of operating system.

 To describe the services an operating system provides to users,
processes, and other systems.
 To discuss the different ways of structuring an operating system.
 To introduce the notion of a process, which forms the basis of all
computation.
 To describe the different features of processes, including scheduling,
creation and termination, and communication.
 To introduce CPU scheduling, which is the basis for multi-programmed
operating systems, and various CPU-scheduling algorithms.
 To introduce the critical-section problem, whose solutions can be used
to ensure the consistency of shared data.
 To develop a description of deadlocks, which prevent sets of concurrent
processes from completing their tasks.
 To present several different methods for preventing or avoiding
deadlocks in a computer system.
 To discuss various memory-management techniques, such as paging.
 To describe the physical structure of secondary and tertiary storage
devices and its effects on the uses of the devices.

5
 Chapter 1

Introduction

1.1 What is operating system?

An operating system (OS) is a program that controls the execution of

application programs and acts as an interface between applications and the
computer hardware. OS have main three objectives:

1. Convenience: An OS makes a computer more convenient to use.

2. Efficiency: An OS allows the computer system resources to be used in an
efficient manner.
3. Ability to evolve: An OS should be constructed in such a way as to
permit the effective development, testing, and introduction of new
system functions without interfering with service.

Different OSs are varied in accomplishing these objectives. Some OSs are
designed to be convenient, others to be efficient, and others some
combination of the two. For example:
 Mainframe: OS is designed primarily to optimize utilization of hardware.
Utilization means how various hardware and software resources are
shared.
 Personal computer: OS support complex games, business applications,
and everything in between.
 Handheld computers: OS is designed to provide an environment in
which a user can easily interface with the computer to execute
programs.

6
1.2 What operating systems do?

As we saw in previous section, OS acts as an interface between

applications and the computer hardware. So, we can show its role from two
viewpoints: user view and system view.

1. User view: user's view of the computer varies according to the interface
being used.
 PC consists of monitor, keyboard, mouse, and system unit. Users of
PCs want OS to maximize their works. So, OS is designed mostly for
ease of use, with some attention paid to performance and none paid
to resource utilization. Performance is important to the user, but
such systems are optimized for single-user not multiple users.
 Users sits at a terminal connected to a mainframe or a minicomputer
are shared with other users the same computer through other
terminals. These users share resources and may exchange
information. OS in this case is designed to maximize resource
utilization (to assure that all available CPU time, memory, and I/0 are
used efficiently, and that no individual user takes more than his fair
share).
 Users sit at workstation connected to networks of other workstations
and servers have dedicated resources at their disposal, but they also
share resources such as networking and servers-file, compute, and
print servers. Therefore, their OS is designed to compromise between
individual usability and resource utilization.
 Handheld computers may be standalone units for individual users or
connected to networks. Their OSs are designed mostly for individual
usability, but performance per unit of battery life is important as well.

7
  Embedded computers in home devices and automobiles have little or
no user view. They may have numeric keypads and may turn
indicator lights on or off to show status, but they and their OSs are
designed primarily to run without user intervention.
2. System view: From this point of view, we can view OS as:
 Resource allocator: A computer system has many resources that may
be required to solve a problem: CPU time, memory space, file-storage
space, I/0 devices, and so on. OS must decide how to allocate these
resources (when there are conflicting requests for them) to specific
users so that it can operate the computer system efficiently and
fairly.
 Control program: A control program manages the execution of user
programs to prevent errors and improper use of the computer. It is
especially concerned with the operation and control of I/O devices.

1-3 Operating system services

OS provides environments in which programs run, and services for the

users of the system. Figure 1.1 illustrates how an operating system interacts
with users, provides services, and allocates resources. We can see that the
system addresses several functions that involve:

 User Interfaces: Means by which users can issue commands to the

system. Depending on the system these interfaces may be:
o Command-line interface.
o Graphical user interface (GUI): Windows, etc.,
o Batch command systems are generally older systems using
punch cards of job-control language but may still be used today
for specialty systems designed for a single purpose.
8
 Program Execution: OS must be able to load a program into RAM,
run the program, and terminate the program, either normally or
abnormally.

Figure 1.1: Operating system services.

 Error Detection: Both hardware and software errors must be

detected and handled with a minimum of harmful effects.
 Accounting: Keeping track of system activity and resource usage,
either for billing purposes or for statistical record keeping that can be
used to optimize future performance.
 Enforced sharing. Resources should be made available to users as
appropriate. Sharing brings about the need to guarantee integrity
and consistency.
 Inter-process communication and synchronization. Executing
processes sometimes need to communicate with other processes or
to synchronize their accesses to shared resources. OS provide these
services by acting as a bridge between processes, responding to
process requests for asynchronous communication with other
9
 processes or synchronization. Inter-process communication may be
implemented as either shared memory or message passing. Inter-
process communications between processes running on:
o The same processor,
o Separate processors,
o Separate machines.
 Protection of critical operating system data. OS Prevents harm to
the system and to resources, either through wayward internal
processes or malicious outsiders. OS must maintain data by which it
can enforce security. Various techniques (including encryption,
hardware control, and isolation) support protection of operating
system security data.
 Guaranteed fair service. All users expect CPU usage and other service
to be provided so that no user is indefinitely starved from receiving
service. So, OS provides:
o Fairness through scheduling, and
o Control through hardware facilities and data tables.
 Interface to hardware. All users access hardware functionality. Fair
access and controlled sharing are hallmarks of multitask operating
systems (those running more than one task concurrently). Hardware
interface used to be more tightly bound into an operating system’s
design. However, now operating systems are designed to run on a
range of hardware platforms, both to maximize the size of the
potential market and to position the operating system for hardware
design enhancements.

10
  User authentication. OS must identify each user who requests access
and must discover that the user is who has the access right. The most
common authentication mechanism is password comparison.
 Memory protection. Each user’s program must run in a portion of
memory protected against unauthorized accesses. The protection will
certainly prevent outsiders’ accesses, and it may also control a user’s
own access to restricted parts of the program space. Differential
security, such as read, write, and execute, may be applied to parts of
a user’s memory space. Memory protection is usually performed by
hardware mechanisms, such as paging or segmentation.
 File and I/O device access control. OS is responsible for maintaining
directory and subdirectory structures, mapping file names to specific
blocks of data storage, and providing tools for navigating and utilizing
the file system. OS must protect user and system files from access by
unauthorized users. Similarly, OS is responsible for transferring data
to and from I/O devices, including keyboards, terminals, printers, and
storage devices. I/O device using must be protected.
 Allocation and access control to general objects. Users need general
objects, such as constructs to permit concurrency and allow
synchronization. However, access to these objects must be controlled
so that one user does not have a negative effect on other users.

1.4 Operating system structure

Operating systems are not just for conventional computers. Some form
of operating system can be found on any of the following objects:

 A dedicated device such as a home thermostat or a heart pacemaker.

11
  An automobile (especially the engine performance sensors and the
automated control functions such as antilock brakes); similarly, the
avionics components of an airplane or the control system of a
streetcar or mass transit system.
 A smartphone, tablet, or other web appliance.
 A network appliance, such as a firewall or intrusion detection and
prevention system.
 A controller for a bank of web servers.
 A computer network traffic management device.

In addition to this list, of course, computers (from microcomputers to

laptops to huge mainframes) have operating systems. The nature of an
operating system varies according to the complexity of the device on which it is
installed, the degree of control it exercises, and the amount of interaction it
supports, both with humans and other devices. Thus, there is no one simple
model of an operating system.

1.4.1 Simple Structure

A common example of OS that have a simple structure is MS-DOS. It was

written to provide the most functionality in the least space, so it was not
divided into modules carefully. Figure 1.2 shows its structure.

In MS-DOS, the interfaces and levels of functionality are not well

separated. For instance, application programs can access the basic I/O routines
to write directly to the display and disk drives. Such freedom leaves MS-DOS
vulnerable to errant (or malicious) programs, causing entire system crashes
when user programs fail.

12
 Application program

Resident system program

MS-DOS device drivers

ROM BIOS device drivers

Figure 1.2: MS-DOS structure.

1.4.2 Layered approach

One way to achieve modularity in the OS is the layered (top-down)

approach. In this, the bottom layer (layer 0) is the hardware, and the topmost
layer (layer N) is the user interface. Each upper layer is built on the bottom
layer. Under a layered approach, the overall functionality and features are
determined and are separated into components. All the layers hide some
structures and operations from their upper layers. Figure 1.3 shows the basic
structure of layered approach.
Layer N (user interface)

Layer N-1

Layer 1

Layer 0
(Hardware)

Figure 1.3: A layered OS structure.

13
 Figure 1.4 shows functions arranged from the most critical layer (at the
bottom) to least critical one (at the top). The functions of OS in layered
approach are grouped in three categories:
 Security kernel. To enforce security.
 Operating system kernel. To allocate primitive resources such as time or
access to hardware devices.
 Other operating system functions. To implement the user’s interface to
hardware.
Above the operating system come some system utility functions and
then the user’s applications. The critical functions of controlling hardware and
enforcing security are said to be in lower or inner layers, and the less critical
functions in the upper or outer layers.

Figure 1.4: Layered OS functions

 The main advantage of layered structure is the simplicity of construction

and debugging.

14
  The main difficulty with the layered structure is that each layer needs to
be carefully defined. That is, deciding what order in which to place the
layers, since each layer can use only the services of lower layers and
cannot use the functionalities of any higher layers. This leads to many
chicken-and-egg situations.
 The main disadvantage is that the OS tends to be less efficient, as a
request for service from a higher layer must filter through all lower
layers before it reaches the hardware, possibly with significant
processing at each step.

Figure 1.5: A microkernel OS structure.

1.4.3 Microkernels

The basic idea behind micro kernels is to remove all non-essential

services from the kernel, and implement them as system applications instead,
thereby making the kernel as small and efficient as possible. Most microkernels
provide basic process and memory management, and message passing
between other services, and not much more. Security and protection can be
enhanced, as most services are performed in user mode, not kernel mode.
Figure 1.5 shows this structure.

15
 System expansion can also be easier, because it only involves adding
more system applications, not rebuilding a new kernel.

Figure 1.6: OS modules.

1.4.4 Modules

Modern OS development is object-oriented, with a relatively small core

kernel and a set of modules which can be linked in dynamically. Figure 1.6
shows the modules structure. Not all codes come from one source. Hardware
device drivers may come from the device manufacturer or a third party, and
users can install add-ons to implement a different file system or user interface,
for example. As we can guess, replacing the file system or user interface
requires integration with several levels of the operating system. System tools,
such as antivirus code, are said to “hook” or be incorporated into the operating
system; those tools are loaded along with the operating system to be active by
the time user programs execute. Even though they come from different
sources, all these modules, drivers, and add-ons may be collectively thought of
as the operating system because they perform critical functions and run with
enhanced privileges.

16
 Modules are like layers in that each subsystem has clearly defined tasks
and interfaces. But they unlike layers in that any module is free to contact any
other module, eliminating the problems of going through multiple
intermediary layers, as well as the chicken-and-egg problems.

Modules are like microkernels in that the kernel is relatively small. But
they are unlike microkernels in that the kernel does not have to implement
message passing since modules are free to contact each other directly.

1.5 Operating system types

In this section we explore some types of operating systems.

1.5.1 Simple Batch System

 There is no direct interaction between user and computer.

 The user must submit a job (written on cards or tape) to a computer
operator.
 Then computer operator places a batch of several jobs on an input
device.
 Jobs are batched together by type of languages and requirement.
 Then a special program, the monitor, manages the execution of each
program in the batch.
 The monitor is always in the main memory and available for execution.

Disadvantages of Simple Batch Systems

 No interaction between user and computer.

 CPU is often idle because the speeds of the I/O devices are much slower
than the speed of the CPU.
 Waiting time is more for a user/program.
17
  No mechanism to prioritize the processes.

1.5.2 Multiprogramming Batch System

 Operating system picks up and begins to execute one of the jobs from
memory.
 Once this job needs an I/O operation OS switch to another job (CPU and
OS always busy).
 Jobs in the memory are always less than the number of jobs on disk (Job
Pool).
 If several jobs are ready to run at the same time, then OS chooses which
one to run through the process of CPU Scheduling.
 In Multiprogramming system, CPU will never be idle and keeps on
processing.
 Time Sharing Systems are very similar to Multiprogramming batch
systems.
o In Time sharing systems the prime focus is on minimizing the
response time, while in multiprogramming the prime focus is to
maximize the CPU usage.

1.5.3 Multiprocessor System

 Multiprocessor system consists of several processors that share a

common physical memory.
 Multiprocessor system provides higher computing power and speed.
 In multiprocessor system all processors operate under single OS.
 Multiplicity of the processors and how they do act together are
transparent to the others.

18
Advantages of Multiprocessor Systems

 Enhanced performance.
 Execution of several tasks by different processors concurrently, increases
the system's throughput without speeding up the execution of a single
task.
 If possible, system divides task into many subtasks and then these
subtasks can be executed in parallel in different CPUs. Thereby speeding
up the execution of single task.

1.5.4 Desktop System

 PC operating systems therefore were neither multiuser nor multitasking.

 The goals of these operating systems are for maximizing user
convenience and responsiveness; instead of maximizing CPU and
peripheral utilization.

1.5.5 Distributed Operating System

Distributed systems comprise of many computers that are

interconnected by communication networks. The main benefit of distributed
systems is its low price/performance ratio.

Advantages of distributed operating system

 Fast processing.
 Less load on the host machine.
 As there are multiple systems involved, user at one site can utilize the
resources of systems at other sites for resource-intensive tasks.

19
Types of distributed operating systems

There are two types of distributed operating systems:

1. Client-Server Systems: Centralized server systems to satisfy requests

generated by client systems. Server systems can be categorized as:
a. Compute server systems: provide an interface to which clients can
send requests to perform an action, in response to which they
execute the action and send back results to the client.
b. File server systems: provide a file-system interface where clients
can create, update, read, and delete files.
2. Peer-to-Peer systems: the tasks are partitioned between peers. Peers
make a portion of their resources, such as processing power, disk
storage or network bandwidth directly without the need for central
coordination by servers or stable hosts.

1.5.6 Clustered System

 Clustered computers share storage and are closely linked via LAN
networking.
 Clustered systems like parallel systems in that they gather multiple CPUs
to accomplish computational work.
 Clustered systems differ from parallel systems in that they are composed
of two or more individual systems coupled together.
 Clustering is usually performed to provide high availability.
 A layer of cluster software runs on the cluster nodes. Each node can
monitor one or more of the others. If the monitored machine fails, the
monitoring machine can take ownership of its storage, and restart the
application that were running on the failed machine. The failed machine

20
 can remain down, but the users (clients) of the application would only
see a brief interruption of service. There are two types:
o Asymmetric Clustering: In this, one machine is in hot standby
mode while the other is running the applications. The hot standby
host (machine) does nothing but monitor the active server. If that
server fails, the hot standby host becomes the active server.
o Symmetric Clustering: In this, two or more hosts are running
applications, and they are monitoring each other. This mode is
obviously more efficient, as it uses all the available hardware.
 Parallel clusters allow multiple hosts to access the same data on the
shared storage. Because most operating systems lack support for this
simultaneous data access by multiple hosts, parallel clusters are usually
accomplished by special versions of software and special releases of
applications.

1.5.7 Real-time Operating System

Real-time operating system is defined as an operating system known to

give maximum time for each of the critical operations that it performs. There
are two types:

 Hard real-time OS: guarantees the maximum time for critical operations
and complete them on time.
 Soft real-time OS: can only guarantee a maximum of the time for the
critical task will get priority over other tasks but does not assure of
completing it in a defined time.

21
1.5.8 Handheld System

Handheld systems are usually of limited size due to which most

handheld devices have a small amount of memory, include slow processors,
and small display screens.

1.6 Interrupt

Operating systems are interrupt-driven. If there are no processes to

execute, no I/0 devices to service, and no users to whom to respond, an
operating system will sit quietly waiting for something to happen. Events are
almost always signaled by the occurrence of an interrupt.

(a) No interrupts (b) Interrupts: short I/O wait (c) Interrupts: long I/O wait
Figure 1.7: Program Flow of Control without and with Interrupts

Interrupts are provided primarily to improve CPU utilization. Most I/O

devices are much slower than the processor. For example, consider a PC that
operates at 1 GHz (takes 1 ns), which would allow roughly 109 instructions per
second. Hard disk has a rotational speed of 7200 revolutions per minute (basic
operation on hard disk takes 4 ms), which is 4 million times slower than the

22
processor. Figure 1.7(a) illustrates this situation. The user program performs a
series of WRITE calls interleaved with processing.

 Solid vertical lines represent segments of code in a program.

 Code segments 1, 2, and 3 refer to sequences of instructions that do not
involve I/O.
 The WRITE calls are to an I/O routine that is a system utility and that will
perform the actual I/O operation.
 The I/O program consists of three sections:
1. A sequence of instructions, labeled 4 in the figure, to prepare for the
actual I/O operation. This may include copying the data to be output
into a special buffer and preparing the parameters for a device
command.
2. The actual I/O command. Without the use of interrupts, once this
command is issued, the program must wait for the I/O device to
perform the requested function or repeatedly perform a test
operation to determine if the I/O operation is done.
3. A sequence of instructions, labeled 5 in the figure, to complete the
operation. This may include setting a flag indicating the success or
failure of the operation.
 The dashed line represents the path of instructions execution followed
by the processor. After the first WRITE instruction is encountered, the
user program is interrupted, and execution continues with the I/O
program. After the I/O program execution is complete, execution
resumes in the user program immediately following the WRITE
instruction.

23
 We can illustrate the gain in efficiency of the processor in the following
two cases:

Figure 1.8: Program Timing: Short I/O Wait

1. When the time required for the I/O operation is relatively short: less
than the time to complete the execution of instructions between WRITE
operations in the user program. Figure 1.8 shows a timing diagram based
on the flow of control in Figures 1.7(a) and 1.7(b).
2. When the time required for the I/O operation is relatively long: greater
than the time to complete the execution of instructions between WRITE
operations in the user program. Figure 1.9 shows a timing diagram based
on the flow of control in Figures 1.7(a) and 1.7(c).

24
 Figure 1.9: Program Timing: Long I/O Wait

1.7 System call

System calls provide an interface to call the services available by an OS.

These calls are written in C and C++, and some low-level tasks (tasks where
hardware must be accessed directly) may be written using assembly-language
instructions.
The caller does not need to know how the system call is implemented or
what it does during execution. Rather, it need only obey the application
program interface (API) and understand what the OS will do because of the
execution of that system call. The use of APIs instead of direct system calls
provides for greater program portability between different systems. The API

25
then makes the appropriate system calls through the system call interface,
using a table lookup to access specific numbered system calls, as shown in
Figure 1.10. Thus, most of the details of the OS interface are hidden from the
programmer by the API and are managed by the run-time support library.

Figure 1.10: handling of a user application invoking the open () system call.

System calls occur in different ways, depending on the computer. There

are three methods for passing parameters to OS:

Figure 1.11: Passing of parameters as a table.

1. Registers: is the simplest approach to pass the parameters.

2. Block or Table: In some cases, there may be more parameters than
registers. Thus, parameters are generally stored in a block or table, in

26
 memory, and the address of the block is passed as a parameter in a
register (see Figure 1.11).
3. Stack: Parameters also can be placed onto the stack by the program and
popped on the stack by the OS. Some OSs prefer the block or stack
method because those approaches do not limit the number or length of
parameters being passed.

1.8 Types of System Calls

System calls can be grouped roughly into 6 major categories illustrated
in Table 1.1.
Table 1.1: Types of system calls.
 end, abort
 load, execute.
 create process, terminate process.
Process control  get process attributes, set process attributes.
 wait for time.
 wait event, signal event.
 allocate and free memory
 create file, delete file.
File management  open, close
 read, write, reposition.
 get file attributes, set file attributes
 request device, release device
Device manipulation  read, write, reposition.
 get device attributes, set device attributes.
 logically attach or detach devices
 get time or date, set time or date.
Information
 get system data, set system data.
maintenance  get process, file, or device attributes.
 set process, file, or device attributes
 create, delete communication connection.
Communication  send, receive messages.
 transfer status information
 attach or detach remote devices
 set file security.
Protection  initialize security descriptor.
 set security descriptor group
======================================
27
 Chapter 2

Process management
All multiprogramming operating systems, from single-user systems such
as Windows for end users to mainframe systems such as IBM’s mainframe
operating system, which can support thousands of users, are built around the
concept of the process.

2.1 What is process?

We can show some suggested definitions for the term process,

including:

 A program in execution.
 An instance of a program running on a computer.
 The entity that can be assigned to and executed on a processor.
 A unit of activity characterized by the execution of a sequence of
instructions, a current state, and an associated set of system resources.

We can think of a process as an entity that consists of several elements.

Three essential elements of a process are:

1. Program code: which may be shared with other processes that are
executing the same program,
2. Set of data: associated with program code.
3. Process control block: is data structure containing several elements that
uniquely characterize the process. These elements include the following:
a. Identifier: A unique identifier associated with process, to
distinguish it from all other processes.
28
 b. State: If the process is currently executing, it is in the running state.
c. Priority: Priority level relative to other processes.
d. Program counter: The address of the next instruction in the
program to be executed.
e. Memory pointers: Includes pointers to the program code and data
associated with process, plus any memory blocks shared with other
processes.
f. Context data: data that are present in registers in the processor
while the process is executing.
g. I/O status information: Includes outstanding I/O requests, I/O
devices (e.g., disk drives) assigned to this process, a list of files in
use by the process, and so on.
h. Accounting information: May include the amount of processor time
and clock time used, time limits, account numbers, and so on.

Figure 2.1: Diagram showing CPU switch from process to process.

PCB is created and managed by the OS. The significant point about the
PCB is that it contains enough information so that it is possible to interrupt a
29
running process and later resume execution as if the interruption had not
occurred. PCB is the key tool that enables the OS to support multiple processes
and to provide for multiprocessing. Figure 2.1 shows how the CPU switches
between two processes using PCBs of these two processes.

2.2 Process states

As a process executes, it changes state. The state of a process is the

current activity of that process. Each process may be in one of the following
states:

Figure 2.2: Diagram of process state.

 New. The process is being created.

 Running. Instructions are being executed.
 Waiting. The process is waiting for some event to occur (such as an I/O
completion or reception of a signal).
 Ready. The process is waiting to be assigned to a processor.
 Terminated. The process has finished execution.
It is important to realize that only one process can be running on any
processor at any instant. Many processes may be ready and waiting. The state
diagram corresponding to these states is presented in Figure 2.2.

30
2.3 Process scheduling

The two main objectives of multiprogramming are to:

1. have some process always running, to maximize CPU utilization.

2. switch the CPU among processes so that users can interact with each
program while it is running. That is, deliver acceptable response times
for all programs.

To meet these objectives, the process scheduler selects an available

process from a set of several available processes for execution on the CPU.

2.3.1 Scheduling Queues

All processes in the system are put into a job queue. The processes that
are in ready state are placed in the ready queue. This queue is generally stored
as a linked list. Each PCB includes a pointer field that points to the next PCB in
the ready queue.

Processes waiting for a device to become available or to deliver data are

placed in device queues. There is generally a separate device queue for each
device. Other queues may also be created and used as needed. Figure 2.3
illustrate the scheduling queues.

2.3.2 Schedulers

A process migrates among the various scheduling queues throughout its

lifetime. This is shown in a queuing diagram in Figure 2.4. Each rectangular box
represents a queue. The circles represent the resources that serve the queues,
and the arrows indicate the flow of processes in the system.

31
 Figure 2.3: The ready queue and various 1/0 device queues.

OS must select, for scheduling purposes, processes from these queues in

some fashion. This selection is performed by the appropriate scheduler.
Generally, there are three schedulers:

1. Long-term scheduler (job scheduler): controls the degree of

multiprogramming (the number of processes in memory). It selects
processes from disk and loads them into memory (ready queue) for
execution. We need it only when a process leaves the system. It
executes much less frequently, so it takes more time (minutes) to decide
which process should be selected for execution.
2. Short-term scheduler (CPU Scheduler): selects from among the
processes that are ready to execute and allocates the CPU to one of
them. Often, it executes at least once every 100 milliseconds. It must be
fast. If it takes 10 milliseconds to decide to execute a process for 100

32
 milliseconds, then 10/ (100 + 10) = 9 percent of the CPU is used (wasted)
for scheduling the work.

Figure 2.4: Queuing-diagram representation of process scheduling.

3. Medium-term scheduler: When system loads get high, this scheduler

will swap one or more processes out of the ready queue for a few
seconds, to allow smaller faster jobs to finish up quickly and clear the
system. See the differences in Figures 2.4 and 2.5.

Figure 2.5: Addition of a medium-term scheduling to the queueing diagram.

In general, most processes can be described as either I/O bound, or CPU

bound.
 I/O-bound process is one that spends more of its time doing I/O than it
spends doing computations.
 CPU-bound process using more of its time doing computations.

33
 It is important that the long-term scheduler select a good process mix of
I/O-bound and CPU-bound processes.
 If all processes, are I/0 bound, the ready queue will almost always be
empty, and the short-term scheduler will have little to do.
 If all processes are CPU bound, the I/O waiting queue will almost always
be empty, devices will go unused, and again the system will be
unbalanced.

2.3.3 Context switch

Whenever an interrupt arrives, the CPU must do a state-save of the

currently running process, then switch into kernel mode to handle the
interrupt, and then do a state-restore of the interrupted process.

Similarly, a context switch occurs when the time slice for one process
has expired, and a new process is to be loaded from the ready queue. This will
cause the current process's state to be saved and the new process's state to be
restored. Saving and restoring states involves saving and restoring all registers
and program counters, as well as the PCBs as shown in Figure 2.1.

Context switching happens very frequently, and the overhead of doing

the switching is just lost CPU time, so context switches (state saves and
restores) need to be as fast as possible. Several registers can be used to speed
up the context switch.

2.4 Operations on processes

Here we will discuss two operations on processes: process creation and

termination.

34
 Figure 2.6: A tree of processes on a typical Solaris system.

2.4.1 Process Creation

Processes may create other processes through appropriate system calls,

such as fork. The creating process is called a parent process, and the new
processes are called its child. Each of these new processes may in turn create
other processes, forming a tree of processes. Each process is given a unique
process identifier (PID), which is typically an integer number. The parent PID
(PPID) is also stored for each process. Figure 2.6 shows a typical process tree
for a Solaris system, and other systems will have similar though not identical
trees.

In general, when a process creates a new process there are:

 Three possibilities in terms of resources sharing:

1. New process may be able to obtain its resources directly from the
operating system.
2. The parent may have to partition its resources among its children.

35
 3. The parent may be able to share some resources (such as memory
or files) among several of its children.
 Two possibilities exist in terms of execution:
1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all its children have terminated.
 Two possibilities in terms of address space of new process:
1. The child process is a duplicate of the parent process (it has the
same program and data as the parent).
2. The child process has a new program loaded into it.

2.4.2 Process termination

A process terminates when it finishes executing its final statement and

releases the CPU. Most of the OS use exit() system call to terminate a process.
There are several causes for process termination:

1. Normal Completion: Process completes all tasks and releases the CPU.
2. Protection Error: Process wants to use a resource that is not allowed to
use by that process. For example, if a process wants to WRITE on a file
that is READ ONLY file.
3. I/O Failure: When a process attempts to use an I/O device and I/O
device is not working fine now. For example, a process that wants to
print a file on the printer, but the printer is defective.
4. Parent Request: If a parent process request for terminating the child
process. Then, the child process should be terminated.
5. Parent Termination: When the parent is terminated, child process also
needs to be terminated.

36
 6. Time Over Run: Waiting time is specified for a process that for how
much time a process can wait for a resource. In this time if the process
fails to allocate a resource, then the process needs to be terminated.
7. Arithmetic Error: There is an instruction of a process that is invalid
instruction, the process needs to be terminated. For example, if a
process wants to divide a number by zero.
8. Memory Requirement: A process requires more memory to execute but
the system fails to provide enough memory to the process for its
execution, then the process needs to be terminated.
9. Privileged Instruction: Process try to execute an instruction that is
reserved for only OS.
10. OS Involvement to terminate: In some critical cases, OS takes control of
the process and stops the execution of the process. For example, if a
deadlock occurs, or deadlock can occur, then OS terminates the process.

2.5 Inter-process communication

Processes executing concurrently in the OS may be either independent

processes or cooperating processes.

 A process is independent if it cannot affect or be affected by the other

processes executing in the system. Also, it does not share data with any
other process.
 A process is cooperating if it can affect or be affected by the other
processes executing in the system. Also, it shares data with other
processes.

There are several reasons for providing an environment that allows

process cooperation:

37
  Information sharing: several users may be interested in the same piece
of information (shared file). It is important to provide an environment to
allow concurrent access to such information.
 Computation speedup: often a solution to a problem can be solved
faster if the problem can be broken down into sub-tasks to be solved
simultaneously (especially when multiple processors are involved).
 Modularity: The most efficient architecture may be to break a system
down into cooperating modules.
 Convenience: Even a single user may be multi-tasking, such as editing,
compiling, printing, and running the same code in different windows.

Cooperating processes require some types of inter-process

communication (IPC) mechanism that will allow them to exchange information.
There are two fundamental models of inter-process communication as shown
in figure 2.7:
1. Shared Memory: is faster once it is set up because no system calls are
required, and access occurs at normal memory speeds. However, it is
more complicated to set up, and does not work as well across multiple
computers. Shared memory is generally preferable when large amounts
of information must be shared quickly on the same computer.
2. Message Passing: requires system calls for every message transfer, and
is therefore slower, but it is simpler to set up and works well across
multiple computers. Message passing is generally preferable when the
amount of data to be transfer is small, or when multiple computers are
involved.

38
 Figure 2.7: Communications models. (a) Message passing. (b) Shared memory.

======================================================

39
 Chapter 3

CPU Scheduling
CPU scheduling is the basis of multi-programmed operating systems. By
switching the CPU among processes, the operating system can make the
computer more productive.

3.1 Basic concepts

Almost all programs have some alternating cycle of CPU running and
waiting for I/O. In a simple system running a single process, the time spent
waiting for I/O is wasted. A scheduling system allows one process to use the
CPU while another is waiting for I/O. The challenge is to make the overall
system as efficient and fair as possible.

3.1.1 CPU-I/O Burst Cycle

Almost all processes alternate between two states in a continuing cycle,

as shown in Figure 3.1. Eventually, the final CPU burst ends with a system
request to terminate execution.

 CPU burst of performing calculations.

 I/O burst waiting for data transfer in or out of the system.

3.1.2 CPU Scheduler

Whenever the CPU becomes idle, it is the job of the CPU Scheduler
(short-term scheduler) to select another process from the ready queue to run
next. Note that the ready queue can be implemented as a FIFO queue, a
priority queue, a tree, or simply an unordered linked list.
40
 Figure 3.1: Alternating sequence of CPU and I/O bursts.

3.1.3 Preemptive Scheduling

CPU-scheduling decisions take place under one of four conditions:
1. When a process switches from the running state to the waiting state,
such as for an I/0 request.
2. When a process switches from the running state to the ready state, for
example in response to an interrupt.
3. When a process switches from the waiting state to the ready state, such
as: at completion of I/0 or return from wait().
4. When a process terminates.

For conditions 1 and 4, there is no choice in terms of scheduling. A new

process (if any) must be selected for execution. For conditions 2 and 3 there is
a choice to either continue running the current process or select a different
process.

41
 If scheduling takes place only under conditions 1 and 4, the system is
said to be non-preemptive, or cooperative. Under these conditions, once a
process starts running it keeps running, until it either voluntarily blocks or until
it finishes. Otherwise, the system is said to be preemptive.

3.1.4 Dispatcher

Dispatcher is the module that gives control of the CPU to the process
selected by the scheduler. This function involves:
 Switching context.
 Switching to user mode.
 Jumping to the proper location in the newly loaded program.

The dispatcher should be as fast as possible since it is invoked during

every process switch. The time consumed by the dispatcher is known as the
dispatch latency.

3.2 Scheduling criteria

Many criteria have been suggested for comparing CPU-scheduling

algorithms. The criteria include the following:
 CPU utilization: keep the CPU as busy as possible (100%).
 Throughput: number of processes that are completed per time unit. For
long processes, this rate may be one process per hour; for short
transactions, it may be 10 processes per second.
 Turnaround time: Time required for a process to complete, from
submission time to completion. (Wall clock time). It is the sum of waiting
time to get into memory, waiting in the ready queue, executing on the
CPU, and doing I/O.

42
  Waiting time: How much time processes spend in the ready queue
waiting their turn to get on the CPU.
 Response time. In an interactive system, response time is the time the
system takes to start responding, not the time it takes to output the
response.

It is desirable to maximize CPU utilization and throughput and to

minimize turnaround time, waiting time, and response time.

3.3 Scheduling algorithms

We will explain several common scheduling algorithms, looking at only a
single CPU burst a small number of processes.

3.3.1 First-Come First-Served Scheduling (FCFS)

It is the simplest CPU-scheduling algorithm. With FCFS, the process that
requests the CPU first is allocated the CPU first. The implementation of the
FCFS is easily managed with a FIFO queue like customers waiting in line at the
bank or the post office or at a copying machine. Unfortunately, the average
waiting time under FCFS is often quite long (if the first process takes a long
time).
Example1: Consider the following three processes that arrive at time 0, with
the length of the CPU burst given in milliseconds:

Process Burst Time

P1 24
P2 3
P3 3

If the processes arrive in the order P1, P2, P3, we get the result shown in
the following Gantt chart:

43
 P1 P2 P3
0 24 27 30

The waiting time of P1 is 0 ms, of P2 is 24 ms, and of P3 is 27 ms. Thus,

the average waiting time for three processes is (0 + 24 + 27)/3 = 17 ms.
Example2: consider the same three processes arrive in the order P2, P3, and P1,
the results are shown in the following Gantt chart:

P2 P3 P1
0 3 6 30

The average waiting time is now (6 + 0 + 3)/3 = 3 ms. The total run time
for the three bursts is the same, but here two of the three processes finish
much quicker, and the other process is only delayed by a short amount.

General characteristics of FCFS:

 Average waiting time under an FCFS is not minimal and may vary greatly
if the processes CPU burst times vary greatly.
 FCFS scheduling algorithm is non-preemptive. Once the CPU has been
allocated to a process, this process keeps the CPU until it releases the
CPU, either by terminating or by requesting I/O.
 FCFS is troublesome for time-sharing systems. Since it cannot be fair
between users whose get a share of the CPU at regular intervals.
 FCFS can block the system in a busy dynamic system in a way, known as
the convoy effect. If the CPU gets the processes of the higher burst first,
then the processes of lower burst time may get blocked (they may never
get the CPU if the job in the execution has a very high burst time).

44
3.3.2 Shortest-Job-First Scheduling (SJF)

The idea behind the SJF algorithm is to pick the smallest job first, and
then pick the next smallest job to do next and so on.
Example1: consider the following four processes, with the length of the CPU
burst given in milliseconds and assume that all processes arrive at the same
time.

Process Burst Time

P1 6
P2 8
P3 7
P4 3

Using SJF scheduling, we would schedule these processes according to the

following Gantt chart:

P4 P1 P3 P2
0 3 9 16 24

The average waiting time is (3 + 16 + 9 + 0) / 4 = 7 ms. By comparison, if

we were using the FCFS, the average waiting time would be 10.25 ms.

General characteristics of SJF:

 SJF algorithm is optimal, in that it gives the minimum average waiting

time for a given set of processes.
 SJF suffers from one important problem: How do you know how long the
next CPU burst is going to be?
 SJF algorithm can be either preemptive or non-preemptive. If the CPU
burst of newly arrived process shorter than what is left of the currently
executing process, then:

45
 o A preemptive SJF algorithm will preempt the currently executing
process.
 Sometimes, preemptive SJF is called shortest-remaining-
time-first.
o Whereas a non-preemptive SJF algorithm will allow the currently
running process to finish its CPU burst.

Example2: consider the following four processes, with the length of the CPU
burst given in milliseconds.
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

The resulting preemptive SJF schedule is as depicted in the following

Gantt chart:

P1 P2 P4 P1 P3
0 1 5 10 17 26

Process P1 is started at time 0 since it is the only process in the queue.

Process P2 arrives at time 1. The remaining time for process P1 (7 ms) is larger
than the time required by process P2 (4 ms), so process P1 is preempted, and
process P2 is scheduled. The average waiting time for this example is [(10-1) +
(1-1) + (17-2) + (5-3)]/4 = 26/4 = 6.5 ms (Non-preemptive SJF gives average
waiting time of 7.75 ms and FCFS gives 8.75 ms).

3.3.3 Priority Scheduling

Priority scheduling is a more general case of SJF, in which each job is
assigned a priority and the job with the highest priority gets scheduled first. In

46
practice, priorities are implemented as integers within a fixed range. We will
use low number for high priorities, with 0 being the highest possible priority.
Example1: consider the following five processes, with the length of the CPU
burst given in milliseconds and priority given as integers.

Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

The following Gantt chart shows the scheduling with priority algorithm.
The average waiting time is 8.2 ms:

P2 P5 P1 P3 P4
0 1 6 16 18 19

General characteristics of priority:

 Priorities can be assigned either internally or externally.

o Internal priorities are assigned by the OS using criteria such as
average burst time, ratio of CPU to I/O activity, system resource
use, and other factors available to the kernel.
o External priorities are assigned by users, based on the importance
of the job, fees paid, politics, etc.
 Priority scheduling can be either preemptive or non-preemptive.
 Priority scheduling can suffer from a major problem known as indefinite
blocking, or starvation, in which a low-priority task can wait forever
because there are always some other jobs around that have higher
priority.
o One common solution to this problem is aging, in which priorities
of jobs increase the longer they wait. Under this scheme a low-
47
 priority job will eventually get its priority raised high enough that
it gets run.

3.3.4 Round-Robin Scheduling (RR)

RR likes FCFS scheduling except that:

 CPU bursts are assigned with a small unit of time called time quantum. A
time quantum is generally from 10 to 100 ms in length.
 Preemption is added to enable the system to switch between processes.

The ready queue is implemented as a FIFO queue of processes. CPU

scheduler picks the first process from the ready queue, sets a timer to
interrupt after 1-time quantum, and dispatches the process. There are two
cases will then happen for the process:

1. If the process finishes its burst before the time quantum timer expires,
then it is swapped out of the CPU just like the normal FCFS algorithm.
2. If the timer goes off first, then the process is swapped out of the CPU
and moved to the back end of the ready queue.

Example1: Consider the following three processes that arrive at time 0, with
the length of the CPU burst given in milliseconds and assume that time
quantum, q = 4.

Process Burst Time

P1 24
P2 3
P3 3

The resulting RR schedule is as follows:

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

48
 The average waiting time is 17/3 = 5.66 ms.

Figure 3.2: How a smaller time quantum increases context switches.

General characteristics of RR

 The average waiting time under the RR policy is often long.

 RR scheduling algorithm is designed especially for time-sharing systems.
 The performance of the RR algorithm depends on the size of the time
quantum.
o If the time quantum is large enough, RR reduces to the FCFS.
o If the time quantum is very small, then large time lost with context
switch. We must consider the effect of context switching on the
performance of RR. Figure 3.2 shows this situation with only one
process with CPU burst time equals 10 and three-time quantum.

3.3.5 Multilevel Queue Scheduling

Multilevel queue scheduling algorithm is created for situations which

processes are easily classified into different groups. For example, the ready
queue can be partitioned into separate two queues:

1. Foreground: includes interactive processes,

2. Background: includes batch processes.

49
 These two types of processes have different response-time
requirements and scheduling needs. Foreground processes may have priority
over background processes. Process is assigned to one queue, based on some
property (such as memory size, priority, or process type). Each queue has its
own scheduling algorithm:

 Foreground may be scheduled by an RR algorithm.

 Background may be scheduled by an FCFS algorithm.

Scheduling must also be done between queues, that is scheduling one

queue to get time relative to other queues. There are two common options:

Figure 3.3: Multilevel queue scheduling.

1. Strict priority: no job in a lower priority queue runs until all higher
priority queues are empty. That is, all processes in foreground queue are
served first, then the processes in background queue.
2. RR: Each queue gets a certain amount of CPU time which it can schedule
amongst its processes; i.e., 80% to foreground in RR, whereas 20% to
background in FCFS.

50
 Note that under this algorithm jobs cannot switch from queue to queue.
Once they are assigned a queue, this queue is their queue until they finish.
Figure 3.3 shows a multilevel queue scheduling algorithm with five queues,
listed in order of top-down priority.
Each queue has absolute priority over lower-priority queue. No process
in the batch queue could run unless the queues of system processes,
interactive processes, and interactive editing processes were all empty. If an
interactive editing process entered the ready queue while a batch process was
running the batch process would be preempted.

Figure 3.4: Multilevel feedback queue scheduling.

3.3.6 Multilevel Feedback Queue Scheduling

Multilevel feedback queue scheduling likes the ordinary multilevel

queue scheduling, except jobs may be moved from one queue to another, as
shown in Figure 3.4. The processes may be moved from one queue to another
for a variety of reasons:

1. Process, in a higher-priority queue, that uses too much CPU time will be
moved to a lower- priority queue.
2. Process that waits too long in a lower-priority queue may be moved to a
higher-priority queue.
 This form of aging prevents starvation.

51
 Multilevel feedback queue scheduling is the most flexible, because it can
be tuned for any situation. But it is also the most complex to implement
because it has several parameters that must be adjusted. Some of these
parameters:

1. The number of queues.

2. The scheduling algorithm for each queue.
3. Method used to determine when to upgrade a process to a higher-
priority queue.
4. Method used to determine when to demote a process to a lower-priority
queue.
5. The method used to determine which queue a process enters initially.

Figure 3.4 shows a multilevel feedback queue scheduler with 3 queues:

1. Q0: RR with time quantum 8 milliseconds.

2. Q1: RR time quantum 16 milliseconds.
3. Q2: FCFS.

Scheduling in multilevel feedback queue is done as follows:

1. New process enters queue Q0 which is served according to arrival order.

 When it gains CPU, process receives 8 milliseconds.
 If it does not finish in 8 milliseconds, it is preempted and moved to
queue Q1.
 When Q0 is empty, then scheduler going to Q1.
2. At Q1 process is again served according to arrival order and receives 16
additional milliseconds.
 If it still does not complete, it is preempted and moved to queue Q 2.
 When Q1 is empty, then scheduler going to Q2.

52
 3. Q2 are run on an FCFS only when Q 0 and Q1 are empty.

Note that:

 A process that arrives for Q1 will preempt a process in Q2.

 A process that arrives for Q0 will preempt a process in Q1.
====================================

53
 Chapter 4

Synchronization
Cooperating process is one that can affect or be affected by other
processes executing in the OS. Cooperating processes can:

 Either directly share a logical address space (that is, both code and data)
 Or be allowed to share data only through files or messages. Concurrent
access to shared data may result in data inconsistency.

In this chapter, we discuss various mechanisms to ensure the orderly

execution of cooperating processes that share a logical address space, so that
data consistency is maintained.

4-1 Producer-Consumer cooperating processes

Producer-Consumer problem (also called bounded-buffer problem) is a

classic problem that is used for synchronization between more than one
processes. The producer and consumer share the same memory buffer (as
queue) that is of fixed size.
 Producer process: its job is to generate the data, put it into the buffer,
and again start generating data.
 Consumer process: its job is to consume the data from the buffer.
The code for the producer and consumer processes is:

54
 int counter = 0; // holds the number of items in the buffer
void producer()
{
while (true)
{
item = produceItem();
if (counter == BUFFER_SIZE)
sleep();
/* When sleep is called, the caller is blocked until
another process wakes it up by using the
wakeup routine */
putItemIntoBuffer(item);
counter ++;
if (counter == 1)
wakeup(consumer);
}
}
// =======================================
void consumer()
{
while (true)
{
if (counter == 0)
sleep();
item = removeItemFromBuffer();
counter --;
if (counter == BUFFER_SIZE - 1)
wakeup(producer);
consumeItem(item);
}
}

4.2 Race condition

Although both the producer and consumer routines described above are
correct separately, they may not function correctly when executed
concurrently. This because both the producer and the consumer are adjusting
the value of the variable counter, which can lead to a condition known as
a race condition.

55
 For producer-consumer processes, the race condition may occur in two
situations:

1. If producer process executes the statements "counter ++;" and at the

same time the consumer process executes the statements "counter --;".
The result may be errors in reading the old value or errors in writing the
new value.
2. If instructions are processed in the incorrect order. This may lead to
deadlock.

Example1: suppose that counter = 5 (currently) and that the producer and
consumer processes execute the statements "counter ++;" and "counter --;"
concurrently. Note that, although "counter ++;" and "counter --;" are single
instructions, they are three steps at the hardware level:

1. Fetch counter from memory into a register,

2. Increment or decrement the register,
3. Store the new value of counter back to memory.

If the instructions from the two processes get interleaved, there could be race
condition problem, such as illustrated below:

Rigister1 = counter
Producer: Rigister1 ++
Counter = Rigister1
Rigister2 = counter
Consumer: Rigister2 --
Counter = Rigister2
Interleaving
T0 Producer executes Rigister1 = counter {Rigister1 = 5}
T1 Producer executes Rigister1 ++ {Rigister1 = 6}
T2 Consumer executes Rigister2 = counter {Rigister2 = 5}
T3 Consumer executes Rigister2 -- {Rigister2 = 4}
T4 Producer executes Counter = Rigister1 {Counter = 6}
T5 Consumer executes Counter = Rigister2 {Counter = 4}

56
If we reverse the order of statements T4 and T5 we get the value of counter = 6!
Note that both results 4 and 6 are wrong, the correct result must be counter =
5 after one running for producer and consumer processes.

Example2: Consider the following scenario:

1. The consumer has just read the variable Counter = 0 and is just about to
move inside the if block.
2. Just before calling sleep, the consumer is interrupted, and the producer
is resumed.
3. The producer creates an item, puts it into the buffer, and
increases Counter.
4. Now counter = 1, the producer tries to wake up the consumer.
5. Unfortunately, the consumer was not yet sleeping, and the wakeup call
is lost. When the consumer resumes, it goes to sleep and will never be
awakened again. Since, the consumer is only awakened by the producer
when Counter = 1.
6. The producer will loop until the buffer is full, after which it will also go to
sleep.

Now the two processes are sleeping, and the deadlock occurred.
Generally, the race conditions are difficult to identify and debug, because they
only occur on rare cases, and only when the timing is just exactly right.

What is the solution of this problem? The solution is to only allow one process
at a time to manipulate the value "counter".

4.3 Critical section

Critical Section is the part of a program which tries to access shared

resources (memory location, data structure, CPU or any IO device). The general
57
idea is that if there are n cooperating processes, p1, p2, …, pn, each has a critical
section of code, with the following conditions and terminologies:
do {

entry section

critical section

exit section

remainder section

} while (TRUE);

Figure 4.1: General structure of a typical process Pi.

 Only one process can be allowed to execute in their critical section at

any one time. If one process is already executing its critical section and
another process wishes to do so, then the second process must wait
until the first process has completed its critical section work.
 The code preceding the critical section, and which controls access to the
critical section, is termed the entry section. It acts like a carefully
controlled locking door.
 The code following the critical section is termed the exit section. It
releases the lock on the door, or at least lets the other processes know
that the process is no longer in its critical section.
 The rest of the code not included in critical, entry, or exit sections is
termed the remainder section. See Figure 4.1
The critical section problem needs a solution to synchronize the
different processes. A solution to the critical-section problem must satisfy the
following three conditions:

1. Mutual exclusion: Only one process at a time can be executing in its

critical section.

58
 2. Progress: If one process does not need to execute its critical section
then it should not stop other processes to get into their critical sections.
3. Bounded waiting. Each process must have a limited waiting time. It
should not wait endlessly to access its critical section.
There are several methods can be used to solve critical-section problem
such as: Peterson solution, test-and-set, Semaphore, and Swap.

4.4 Peterson solution

Peterson solution is a classic software-based solution to the critical-

section problem. It is based on two processes, P0 and P1, which alternate
between their critical and remainder sections. Peterson solution requires two
shared data items:

1. int turn: Indicates whose turn it is to enter its critical section. If turn = 0,
then P0 is allowed into its critical section.
2. Boolean flag[i]: Indicates when a process wants to enter its critical
section. When P0 wants to enter their critical section, it sets flag[0] to
true.
do {
flag[0] = TRUE;
turn = 1;
while (flag[1] && turn == 1);

critical section

flag[0] = FALSE;

remainder section

} while (TRUE);

Figure 4.2: The structure of process P0 in Peterson solution.

The structure of process P0 in Peterson solution is shown in Figure 4.2.

The entry and exit sections are enclosed in boxes.
59
  In the entry section P0 first raises a flag indicating a desire to enter its
critical section.
 Then turn is set to 1 to allow the other process P1 to enter its critical
section if process P1so desires.
 The while loop is a busy loop (notice the semicolon at the end), which
makes P0 wait if P1 has its turn and wants to enter its critical section.
 Process P0 lowers the flag[0] in the exit section, allowing process P1 to
continue if it has been waiting.

Peterson solution preserves all three conditions:

 Mutual Exclusion is assured as only one process can access the critical
section at any time.
 Progress is also assured, as a process outside the critical section does not
block other processes from entering the critical section.
 Bounded Waiting is preserved as every process gets a fair chance.

Disadvantages of Peterson solution:

1. It involves busy waiting loop.

2. It is limited to only two processes.
3. It is not guaranteed to work on modern hardware.

4.5 Test-and-Set

Test-and-set is a hardware solution to provide certain atomic operations.

These operations are guaranteed to operate as a single instruction, without
interruption. In Test-and-set, we have a shared lock variable which can take
either of the two values, 0 (unlock) or 1 (lock). Each process, before entering its
critical section, checks the lock:

60
  If the lock is locked (lock = 1), the process waits till the lock becomes
free,
 If the lock is not locked (lock = 0), process takes the lock (set lock = 1)
and executes its critical section (see Figure 4.3).
do {
lock = 0;
while (test_and_set(lock));

critical section

lock = 0;

remainder section

} while (TRUE);
Figure 4.3: The definition of Test-and-Set solution.

To show how the test-and-set mechanism works, consider there are two
processes P0 and P1 trying to enter their critical sections:

 In entry section P0 executes the test-and-set(lock) instruction, since lock

= 0 the while loop is break.
 Then P0 enters its critical section, set lock = 1, and executes.
 Process P1 arrives and in its entry section P1 executes the test-and-
set(lock) instruction, since lock = 1 the while loop keeps the process
P1 busy until the lock value becomes 0 and its condition breaks.
 P0 finishes its critical section and sets the lock value to 0.
 The while loop condition, in process P1, breaks and it enters its critical
section.
 Any other process can enter only after process P1 completes and sets the
lock value to 0.

61
Test-and-set solution preserves only two conditions:

 Mutual Exclusion is assured as only one process can access the critical
section at any time.
 Progress is also assured, as a process outside the critical section does not
block other processes from entering the critical section.

Disadvantages of test-and-set solution:

1. It does not guarantee bounded waiting and may cause starvation. If

there are n processes trying to get into their critical sections:
 The order they will enter their critical sections is not guaranteed,
 The relative rates of the processes to release the lock is not
guaranteed,
o Very fast process could release the lock, complete its remainder
section, and re-lock the lock before a slower process got a chance.
2. It involves busy waiting loop which keeps the CPU busy when the
process is waiting.

Wait(S)
{ while (S <= 0);
S --;
}

----------------------------------------------
Signal(S)
{
S ++;
}
Figure 4.4: The definition of semaphore operations.

4.6 Semaphore

The hardware solution presented in section 4.5 is often difficult for

ordinary programmers to access, particularly:

62
  On multi-processor machines,
 Because they are often platform dependent.

Therefore, most systems offer a software API equivalent called

Semaphore. It is integer variable that is used to solve the critical section
problem using two atomic operations: wait and signal operations, as shown in
Figure 4.4.

 The wait operation decrements the value of its argument S if it is

positive. If S is negative or zero, then no operation is performed.
 The signal operation increments the value of its argument S.

Types of Semaphores

There are two main types of semaphores:

1. Binary Semaphores: can take one of two values 0 or 1. It is easy to be

implemented.
 The wait operation only works when the semaphore is 1,
 The signal operation succeeds when semaphore is 0.
2. Counting Semaphores: can take any integer value. These semaphores
are used to coordinate the resource access by using semaphore count
which is the number of available resources.
 If the resources are added, semaphore count automatically
incremented,
 If the resources are removed, the count is decremented.

In counting semaphores, the counter is initialized to the number of

resources available in the system (in binary semaphore the number of
resources initially available is just one):

63
  If the counting semaphore is greater than zero, then a process can enter
its critical section and use one of the resources.
 When the counter gets to zero, then the process blocks until another
process frees up a resource and increments the counting semaphore
with a signal call.
Semaphores can also be used to synchronize certain operations between
processes. For example, suppose that process P0 must execute statement S0
before process P1 executes statement S1.

1. Create a semaphore named synch that is shared between P0 and P1 and

initialize it to zero.
2. Put in process P0 the code:
S0;
signal( synch );
3. Put in process P1 the code:
wait(synch);
S1;
4. Because synch was initialized to 0, process P1 will block on the wait until
P0 executes the call to signal.

Counting semaphore has no mutual exclusion whereas binary

semaphore has mutual exclusion.

Advantages of Semaphores
 Semaphores allow only one process into the critical section.
 Semaphores are implemented in the machine independent.
 As there is busy waiting in semaphore, there is never a wastage of
process time and resources.
 They allow flexible management of resources.
64
Disadvantage of semaphores
 The operating system must keep track of all calls to wait and signal
semaphore.
 One of the biggest limitations of a semaphore is priority inversion. It is
scheduling problem arises when a high-priority process gets blocked
waiting for a resource that is currently held by a low-priority process.
 Deadlock may occur when multiple processes are blocked, each waiting
for a resource that can only be freed by one of the other blocked
processes.
 Starvation may occur when one or more processes gets blocked forever,
and never get a chance to take their turn in the critical section.
 Semaphore programming is a complicated, so there are chances of not
achieving mutual exclusion.
====================================

65
 Chapter 5

Deadlock
In a multiprogramming environment, several processes may compete for
a finite number of resources. A process requests resources: if the resources are
not available at that time, the process enters a waiting state. Sometimes, a
waiting process is never again able to change state because the resources it
has requested are held by other waiting processes. This situation is called a
deadlock.

5.1 System model

A system consists of a finite number of resources to be distributed

among several competing processes. These resources are partitioned into
several types:

1. Memory space,
2. CPU cycles,
3. files,
4. I/0 devices such as printers and DVD drives.

Each type consists of some number of identical instances:

 If a system has two CPUs, then the resource type CPU has two instances.
 All resources in the same type must be equivalent. The request of this
type can be equally satisfied by any one of the instances in that type.
 If there is some difference between the instances within a type, then
that type needs to be divided into separate types. For example, printers
may need to be separated into: laser printers and color inkjet printers.

66
 A process must request a resource before using it and must release the
resource after using it. A process may request as many resources as it requires
to complete its tasks. A process may utilize a resource in only the following
sequence:
 Request: It requests the resource. If the request cannot be granted
immediately, then the process must wait until it can acquire the
resource.
 Use: It uses the resource, e.g. it prints on the printer or reads from file.
 Release: It releases the resource.

A set of processes is deadlocked when every process in the set is waiting

for a resource that is currently allocated to another process in the set. The
system must know:

 Which resources are free, and which are allocated?

 Which processes allocating resources and which waiting for the
resources to become available.

The resources may be:

 Physical resources: printers, tape drives, memory space, and CPU cycles.
 Logical resources: files and semaphores.

5.2 Deadlock characteristics

5.2.1 Necessary Conditions

A deadlock can occur if the following four conditions hold

simultaneously in a system:
1. Mutual exclusion: At least one resource must be held in a non-sharable
mode. That is, only one process at a time can use the resource. If

67
 another process requests that resource, then this process must be wait
for the resource to be released.
2. Hold and wait: A process must be holding at least one resource and
waiting to acquire additional resources that are currently being held by
other processes.
3. No preemption: Once a process is holding a resource, then that resource
cannot be taken away from that process until the process voluntarily
releases it.
4. Circular wait: A set of waiting processes {P0, Pl, ..., Pn} must exist such
that P0 is waiting for a resource held by P1, P1 is waiting for a resource
held by P2, ..., Pn-1 is waiting for a resource held by Pn and Pn is waiting for
a resource held by P0.

5.2.2 Resource-Allocation Graph

Deadlocks can be described more precisely in terms of a directed graph

called a system resource-allocation graph. This graph has the following
properties:

 It consists of a set of vertices V and a set of edges E.

 The set of vertices V is partitioned into two different types of nodes:
o P = {P1, P2, ..., Pn} the set of all active processes in the system,
o R = {R1, R2, ..., Rm} the set of all resource types in the system.
 The set of edges E is classified into two classes:
o Request edge: A directed edge from process Pi to resource type Rj
is denoted by Pi → Rj; it indicates that Pi requested an instance of
resource type Rj and is currently waiting for that resource.

68
 o Assignment edge: A directed edge from resource type Rj to
process Pi is denoted by Rj → Pi; it indicates that an instance of
resource type Rj has been allocated to process Pi.

Figure 5.1: Resource-allocation graph.

In a graph, we represent the processes as circles and the resource types

as rectangles. Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle. Figure 5.1 shows an
example of the resource-allocation graph.

Some important facts:

1. If the graph contains no cycles, then no process in the system is

deadlocked (Figure 5.1).
2. If the graph contains cycle, then a deadlock may exist.
a. If each resource type has exactly one instance, then a cycle implies
that a deadlock has occurred.
b. If each (or some) resource type has several instances, then a cycle
indicates the possibility of a deadlock, but does not guarantee one
(Figures 5.2 and 5.3).

69
 Figure 5.2: Resource-allocation graph with a deadlock

In Figure 5.2, there are two cycles in the system:

1. P1  R1  P2  R3  P3  R2  P1.
2. P2  R3  P3  R2  P2.

Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the
resource R3, which is held by process P3. Process P3 is waiting for either process
P1 or process P2 to release resource R2. In addition, process P1 is waiting for P2
to release resource R1.
In Figure 5.3, we also have a cycle: P1  R1  P3  R2  P1. However,
there is no deadlock. Observe that process P4 may release its instance of
resource type R2. This resource can then be allocated to P3, breaking the cycle.

Figure 5.3: Resource-allocation graph with a cycle but no deadlock.

70
5.3 Methods for handling deadlock

There are three ways for handling deadlocks:

1. Deadlock prevention or avoidance: Do not allow the system to get into
a deadlocked state.
2. Deadlock detection and recovery: Allow the system to enter a
deadlocked state, detect it, and recover.
3. Ignore the problem all together: Pretend that deadlocks never occur in
the system. This is the one used by most OSs, including UNIX and
Windows. So, the application developer must write programs that
handle deadlocks.

5.4 Deadlock prevention

Deadlocks can be prevented by preventing at least one of the four

required conditions:

1. Mutual Exclusion: Sharable resources such as read-only files, do not

require mutually exclusive access and thus cannot be involved in a
deadlock. But, non-sharable resources such as printer, require the
mutual-exclusion. Generally, we cannot prevent deadlocks by rejecting
the mutual-exclusion condition because some resources are non-
sharable.
2. Hold and Wait: To prevent this condition, processes must be prevented
from holding one or more resources while simultaneously waiting for
one or more others. There are several possibilities for this:
a. All processes request all resources at one time. This can be
wasteful of system resources if a process needs one resource early

71
 in its execution and does not need some other resource until
much later.
b. Processes holding resources must release them before requesting
new resources. This can be a problem if a process has partially
completed an operation using a resource and then fails to get it
after releasing it.
c. Either of the above two methods can lead to starvation if a
process requires one or more popular resources.
3. No Preemption: Preemption of process resource allocations can prevent
this condition of deadlocks when it is possible.
a. One approach is that if a process is forced to wait when
requesting a new resource, then it forced to release all other
resources previously held by this process. It is forced to re-acquire
the old resources along with the new resources in a single
request.
b. Another approach is that when a resource is requested and not
available, then the system looks to see what other waiting
processes currently have those resources. If such a process is
found, then some of their resources may get preempted and
added to the list of resources for which the process is waiting.
c. Either of these approaches may be applicable for resources whose
states are easily saved and restored, such as registers and
memory, but are generally not applicable to other devices such as
printers and tape drives.
4. Circular Wait: One way to avoid circular wait is to number all resources.
For example, if the set of resource types R includes tape drives, disk
drives, and printers, then we can order these resources as follows:

72
 F(tape drive) = 1
F(disk drive) = 5
F(printer) = 12

a. Each process can request resources only in increasing order. That

is, a process can initially request any number of instances of a
resource type Ri. After that, the process can request instances of
resource type Rj if and only if F(Rj) > F(Ri). For example, a
process that wants to use the tape drive and printer at the same
time must first request the tape drive and then request the
printer.
b. Each process requests an instance of resource type Rj must first
release all resources Ri such that F(Ri) ≥ F(Rj). One big challenge in
this scheme is determining the relative ordering of the different
resources.

5-5 Deadlock avoidance

The main difference between deadlock prevention and deadlock

avoidance is that:

 Deadlock prevention ensures that at least one of the necessary

conditions to cause a deadlock will never occur.
 Deadlock avoidance ensures that the system will not enter an unsafe
state.

Thus, to avoid the deadlock this requires more information about each
process. The scheduler needs to know:

 The maximum number of each resource that a process might potentially

use.

73
  What resources may be needed in what order?

When a scheduler sees that starting a process or granting resource

requests may lead to future deadlocks, then that process is just not started, or
the request is not granted.

5.5.1 Safe State

A resource allocation state is defined by the number of available and

allocated resources, and the maximum requirements of all processes in the
system.

A state is safe if the system can allocate all resources requested by all
processes without entering a deadlock state. That is, a state is safe if there
exists a safe sequence of processes {P0, P1, P2, ..., PN} such that all of the
resource requests for Pi can be granted using the resources currently allocated
to Pi and all processes Pj where j < i. (i.e. if all the processes prior to Pi finish
and free up their resources, then Pi will be able to finish also, using the
resources that they have freed up).

Figure 5.4: Safe, unsafe, and deadlocked state spaces.

If a safe sequence does not exist, then the system is in an unsafe state,
which may lead to deadlock. Note that, all safe states are deadlock free, but
not all unsafe states lead to deadlocks as shown in Figure 5.4.

74
 For example, consider a system with 12 tape drives and 3 process. The
tape drivers, at time t0, are allocated as follow:

Process Maximum need Current allocation

P0 10 5
P1 4 2
P2 9 2

Note that there are 3 free tap drivers. Is this a safe state? What is the
safe sequence?

At time t0, the system is in safe state. The sequence <P1, P0, P2> satisfies
the safety condition:

 Process P1 can immediately be allocated all its tape drives and then
return them (system have 5 available tape drives);
 Then process P0 can get all its tape drives and return them (system have
10 available tape drives);
 Finally, process P2 can get all its tape drives and return them (system
have 12 tape drives available).

What happens to the system if, at time t 1, process P2 requests and is

granted one more tape drive?

If, at time t1, process P2 requests and is allocated one more tape drive.
The system is no longer in a safe state. At this point:

 Only process P1 can be allocated all its tape drives. When it returns
them, the system will have only 4 available tape drives.
 Since process P0 is allocated 5 tape drives but has a maximum of 10, it
may request five more tape drives. If it does so, it will have to wait,
because they are unavailable.

75
  Similarly, process P2 may request 6 additional tape drives and must wait,
resulting in a deadlock.

If we had made P2 wait until either of the other processes had finished
and released its resources, then we could have avoided the deadlock. So, the
key to the safe state approach is that when a request is made for resources,
the request is granted only if the resulting allocation state is a safe one.

5.5.2 Resource-Allocation Graph Algorithm

As mentioned previously, if each resource type has exactly one instance,

then cycles in the resource-allocation graph implies to deadlock. In this case
we can add new type of edges called claim edges. A claim edge Pi  Rj
indicates that process Pi may request resource Rj at some time in the future.
This edge looks like a request edge in direction but is represented in the graph
by a dashed line.

Figure 5.5: Left: Resource allocation graph for deadlock avoidance. Right: An unsafe state in
a resource allocation graph.

For this technique to work, all claim edges must be added to the graph
for any process before that process can request any resources.
To illustrate this algorithm, we consider the resource-allocation graph of
Figure 5.5 (Left). Suppose that P2 requests R2. Although R2 is currently free, we
cannot allocate it to P2 since this action will create a cycle in the graph (Figure

76
5.5 (right)). A cycle indicates that the system is in an unsafe state. If P 1 requests
R2, and P2 requests R1, then a deadlock will occur.

5.5.3 Banker's Algorithm

The name was chosen because the algorithm could be used in a banking
system to ensure that the bank never allocated its available cash in a way that
it could no longer satisfy the needs of all its customers.

 When a process starts up, it must declare the maximum allocation of

resources it may request, up to the amount available on the system.
 When a request is made, the scheduler determines whether granting the
request would leave the system in a safe state. If not, then the process
must wait until the request can be granted safely.

The banker's algorithm relies on several key data structures (n is the

number of processes, m is the number of resource types):

1. Available[m]. vector of length m indicates the number of available

resources of each type.
2. Max[n][m]. n x m matrix defines the maximum demand of each process
of each resource.
3. Allocation[n][m]. n x m matrix defines the number of resources of each
type currently allocated to each process.
4. Need[n][m]. n x m matrix indicates the remaining resource need of each
process. Note that Need[i][j] = Max[i][j] - Allocation[i][j] for all i , j.

For simplification, we make the following observations:

 Vector X is less than or equal vector Y if X[i] <= Y[i] for all i.

77
  One row of the Need matrix, Need[i], can be treated as a vector
corresponding to the needs of process Pi, and similarly for Allocation and
Max.

The banker’s algorithm consists of two sub algorithms: safety algorithm

and resource-request algorithm.

Safety Algorithm

To apply the Banker's algorithm, we first need an algorithm for

determining whether a state is safe. Safety algorithm determines if the current
state of a system is safe, according to the following steps:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work
= Available and Finish[i] = false for i = 0, 1, …, n-1.
2. Find an index i such that both
a. Finish[i] == false
b. Need[i] ≤ Work
If no such i exists, go to step 4.
3. Work = Work + Allocation[i]
Finish[i] = true
Go to step 2.
4. If Finish[i] == true for all i, then the system in safe state.

This algorithm may require an order of m x n2 operations to determine

whether a state is safe.

Resource-Request Algorithm

After ensuring that the current state is safe, next we are now ready to
look at the Banker's algorithm itself. Resource-request algorithm determines if
a new request is safe and grants it only if it is safe to do so. Let Request[n][m]

78
indicates the number of resources of each type currently requested by
processes and Request[i] be the request vector for process Pi. If Request[i][j]
== k, then process Pi wants k instances of resource type Rj. When a request for
resources is made by process Pi, the following actions are taken:
1. If Request[i] ≤ Need[i], go to step 2. Otherwise, an error occurs.
2. If Request[i] ≤ Available, go to step 3. Otherwise, Pi must wait.
3. Allocate the resource and modify the state as follows:
Available = Available – Request[i];
Allocation[i] = Allocation[i] + Request[i] ;
Need[i] = Need[i] – Request[i] ;

If the resulting resource-allocation state is safe, the transaction is

completed, and process Pi is allocated its resources. If the new state is unsafe,
then Pi must wait for Request[i], and the old resource-allocation state is
restored.
Example: consider a system with 5 processes P0 through P4 and 3 resource
types A, B, and C. Resource type A has 10 instances, resource type B has 5
instances, and resource type C has 7 instances. Suppose that, at time T0, the
following snapshot of the system has been taken.

Allocation Max Available Need =

Max - Allocation
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1

The system is currently in a safe state. Indeed, the sequence <P1, P3, P4,
P2, P0> satisfies the safety criteria.
What happens if process P1 requests 1 instance of A and 2 instances of C?

79
So, Request[1] = (1, 0, 2). To decide whether this request can be immediately
granted, we first check the following condition:
Request[1] ≤ Available
That is, we check (1, 0, 2) ≤ (3, 3, 2), which is true. We then pretend that this
request has been fulfilled, and we arrive at the following new state:

Allocation Need = Available

Max - Allocation
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1

We must determine whether this new system state is safe. To do that,

we execute our safety algorithm and find that the sequence <P1, P3, P4, P0, P2>
satisfies the safety requirement. Hence, we can immediately grant the request
of process P1.

What about requests of ( 3, 3,0 ) by P4? or ( 0, 2, 0 ) by P0? Can these be safely

granted? Why or why not? Try yourself.

5-6 Deadlock detection

If a system does not employ either a deadlock-prevention or a deadlock

avoidance algorithm, then a deadlock situation may occur. In this environment,
the system may provide:

 An algorithm that examines the state of the system to determine

whether a deadlock has occurred.
 An algorithm to recover from the deadlock.

80
 Figure 5.6: (a) Resource allocation graph. (b) Corresponding wait-for graph

Below, we discuss these two requirements as they related to systems

with:

 Only single instance of each resource type,

 Several instances of each resource type.

5.6.1 Single Instance of Each Resource Type

If each resource type has a single instance, then we can use a variation
of the resource-allocation graph known as a wait-for graph. A wait-for graph
can be constructed from a resource-allocation graph by eliminating the
resources and collapsing the associated edges, as shown in Figure 5.6. An arc
from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a
resource that process Pj is currently holding.

As mentioned previously, cycles in the wait-for graph indicate deadlocks.

This algorithm must maintain the wait-for graph, and periodically search it for
cycles.

81
5.6.2 Several Instances of a Resource Type

The wait-for graph scheme is not applicable to a resource-allocation

system with multiple instances of each resource type. We use an algorithm
that is applicable to such a system. The algorithm employs several time-varying
data structures that are like those used in the banker's algorithm. It follows
these steps:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work
= Available. For i = 0, 1, ..., n-1, if Allocation[i]  0, then Finish[i] = false;
otherwise, Finish[i] = true.
2. Find an index i such that both:
a. Finish[i] == false
b. Request[i] ≤ Work
If no such i exists, go to step 4.
3. Work = Work + Allocation[i]
Finish[i] = true
Go to step 2.
4. If Finish[i] == false for some i, 0  i < n, then the system is in a deadlocked.
Moreover, if Finish[i] == false, then process Pi is deadlocked.

This algorithm requires an order of m x n2 operations to detect whether

the system is in deadlocked state. This algorithm is essentially the same as the
Banker's algorithm, with two subtle differences:

1. In step 1, Banker's Algorithm sets Finish[i] = false for all i. This algorithm
sets Finish[i] = false only if Allocation[i]  zero.
2. In step 4, the basic Banker's Algorithm says that if Finish[i] == true for all
i, that there is no deadlock. This algorithm is more specific, by stating

82
 that if Finish[i] == false for any process Pi, then that process is specifically
involved in the deadlock which has been detected.

Example: consider a system with 5 processes P0 through P4 and 3 resource

types A, B, and C. Resource type A has 7 instances, resource type B has 2
instances, and resource type C has 6 instances. Suppose that, at time T0, we
have the following resource-allocation state:

Allocation Request Available

A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2

The system is not in deadlocked state. Indeed, the sequence <P0, P2, P3,
P1, P4> results in Finish[i] == true for all i.
Suppose that process P2 makes one additional request for an instance of
type C. The Request matrix is modified as follows:

Allocation Request Available

A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 1
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2

Is the system now deadlocked?

The system is now deadlocked. The number of available resources is not

enough to fulfill the requests of the four processes P1, P2, P3, and P4. Thus, a
deadlock exists, consisting of processes P1, P2, P3, and P4.

83
5.7 Recovery from Deadlock

There are three basic approaches to recovery from deadlock:

1. Inform the system operator and allow him to take manual intervention.
2. Terminate one or more processes involved in the deadlock.
3. Preempt resources.

5.7.1 Process Termination

To eliminate deadlocks by aborting a process, we use one of two

methods:

1. Abort all deadlocked processes: This method clearly will break the
deadlock cycle, but at great expense.
2. Abort one process at a time until the deadlock cycle is eliminated: This
is more conservative but requires doing deadlock detection after each
step. In this case there are many factors that can go into deciding which
processes to terminate next:
a. What the process priority is?
b. How long the process has been running, and how close it is to
finishing?
c. How many and what type of resources is the process holding. Are
they easy to preempt and restore?
d. How many more resources does the process need to complete?
e. How many processes will need to be terminated?
f. Whether the process is interactive or batch?

84
5.7.2 Resource Preemption
When preempting resources to relieve deadlock, there are three
important issues to be addressed:
1. Selecting a victim: Deciding which resources to preempt from which
processes involves many of the same decision criteria outlined with
process termination.
2. Rollback: If we preempt a resource from a process, what should be done
with that process? Clearly, it cannot continue with its normal execution;
it is missing some needed resource. We must roll back the process to
some safe state and restart it from that state.
3. Starvation: How do we ensure that starvation will not occur? That is,
how can we guarantee that resources will not always be preempted
from the same process?
=====================================

85
 Chapter 6

Memory management
Previously, we showed how the CPU scheduling can improve both the
utilization of the CPU and the speed of the computer's response to its users.
To increase in computer performance several processes must kept in memory;
that is, they must share memory.

The CPU can access directly only main memory and the registers built
into the processor itself. Any instructions in execution, and any data being
used by the instructions, must be in one of these direct-access storage devices.
If the data are not in memory, they must be moved there before the CPU can
operate on them.

Each process must have a separate memory space. This requires having
the ability to do the following:
1. Determining the range of legal addresses that the process may access.
2. Ensuring that the process can access only these legal addresses.

In this chapter, we discuss various ways to manage memory.

6-1 Hardware protection of memory

In this section we describe several ways of protecting a memory space.

We want a program to be able to share selected parts of memory with other
programs and even other users, and especially we want the operating system
and a user to coexist in memory without the user’s being able to interfere with
the operating system. Even in single-user systems it may be desirable to
protect a user from potentially adjustable system utilities and applications.

86
6.1.1 Fence

The fence is the simplest form of memory protection. It was introduced

in single-user operating systems, to prevent a faulty user program from
destroying part of the resident portion of the operating system. As its name
implies, a fence is a method to confine users to one side of a boundary. There
are two implementations for fence:

1. Fixed fence: Fence is a predefined memory address. This enables the

operating system to reside on one side and the user to stay on the other.
An example of this situation is shown in figure 6.1(a). Unfortunately, this
kind of implementation was very restrictive because a predefined
amount of space was always reserved for the operating system, whether
the space was needed or not. If less than the predefined space was
required, the excess space was wasted. Conversely, if the operating
system needed more space, it could not grow beyond the fence
boundary.
2. Hardware register (often called a fence register). It contains the address
of the end of the operating system. In contrast to a fixed fence, in this
scheme the location of the fence could be changed. Each time a user
program generated an address for data modification, the address was
automatically compared with the fence address:
 If the address was greater than the fence address (that is, in the
user area), the instruction was executed.
 If it was less than the fence address (that is, in the operating
system area), an error condition was raised.
The use of fence registers is shown in figure 6.1(b).

87
 (a) (b)
Figure 6.1: Fence implementation: (a) Fixed fence. (b) Fence register.

A fence register protects in only one direction. In other words, an

operating system can be protected from a single user, but the fence cannot
protect one user from another user. Similarly, a user cannot identify certain
areas of the program as inviolable (such as the code of the program itself or a
read-only data area).

Figure 6.2 A base and a limit register define a logical address space.

6.1.2 Base/Limit registers

As we saw, fence registers hold a smallest physical address bound (a

starting address) but not the size of range (highest address). A highest address

88
can be useful in knowing how much space is selected and in checking for
overflows into “forbidden” areas. To overcome this difficulty, a second register
is often added, as shown in figure 6.2. The second register, called a limit
register, is the offsets from the base register. Thus, the two registers are:

1. Base register: holds the smallest legal physical memory address.

2. Limit register: specifies the size of the range.
Every memory access made by a process is checked against these two
registers, and if a memory access is attempted outside the valid range, then a
fatal error is generated as shown in Figure 6.3. This scheme prevents a user
program from modifying the code or data structures of either the operating
system or other users. It should be obvious that:

 OS has access to all existing memory locations.

 Changing the contents of the base and limit registers is a privileged
activity, allowed only to the OS kernel.

Figure 6.3: Hardware address protection with base and limit registers.

Important point: Erroneous addresses inside a user’s address space can still
affect that program because the base/limit checking guarantees only that each
address is inside the user’s address space. To understand this point let us
consider the following example.

89
Example: a user error might occur with two cases:

 When a subscript is out of range.

 Or an undefined variable generates an address reference within the
user’s space but, unfortunately, inside the executable instructions of the
user’s program.
o In this case, a user can accidentally store data over instructions.
Such an error can let a user by mistake destroy a program, but
(fortunately) only that user’s own program.

We can solve this overwriting problem by using another pair of

base/limit registers, one for the instructions (code) of the program and a
second for the data space. Then:

 Only fetched instructions are relocated and checked with the first
register pair.
 Only data accesses are relocated and checked with the second register
pair.

6.1.2 Address binding

User programs go through several steps (some of which may be

optional) before being executed as shown in Figure 6.4. Addresses in the user
(source) program are generally symbolic such as "count", "i", "temp". These
symbolic names must be mapped or bound to physical memory addresses,
which typically occurs in several stages:

1. Compile Time: If it is known at compile time where a program will reside

in physical memory, then absolute code can be generated by the
compiler, containing actual physical addresses. However, if the load

90
 address changes at some later time, then the program will have to be
recompiled.
2. Load Time: If the location at which a program will be loaded is not
known at compile time, then the compiler must generate relocatable
code, which references addresses relative to the start of the program. If
that starting address changes, then the program must be reloaded but
not recompiled.
3. Execution Time: If a program can be moved around in memory during its
execution, then binding must be delayed until execution time. This
requires special hardware, and is the method implemented by most
modern OSs.

Figure 6.4: Multistep processing of a user program

91
 Figure 6.4 shows the various stages of the binding processes and the
units involved in each stage.

6.1.3 Logical versus Physical Address Space

Logical address (also referred as virtual address) is the address that is

generated by the CPU. Physical address is the address that is seen by the
memory unit. The set of all logical addresses used by a program composes
the logical address space, and the set of all corresponding physical addresses
composes the physical address space.

 Addresses bound at compile time or load time have identical logical and
physical addresses.
 Addresses created at execution time have different logical and physical
addresses.
o In this case the logical address is also known as a virtual address.

Figure 6.5: Dynamic relocation using a relocation register.

The run time mapping of logical to physical addresses is handled by

the memory-management unit, MMU. One approach to perform such mapping
is adding the value in the relocation (base) register to every address generated

92
by a user process. As shown in Figure 6.5, an attempt by the user to address
location 346 is dynamically relocated to location 14346.

The user program deals with logical addresses and never sees the real
physical addresses. The memory-mapping hardware converts logical addresses
into physical addresses.

6.1.4 Dynamic Loading

Rather than loading an entire program into memory at once, dynamic

loading loads up each routine as it is called.

 Its advantage is that unused routines need never be loaded, reducing

total memory usage, and generating faster program startup times.
 Its downside is the overhead of checking to see if a routine is loaded
every time, it is called and then loading it up if it is not already loaded.

6-2 Swapping

A process must be in memory to be executed. A process, who is not

currently use the CPU, can be swapped temporarily out of memory to a
backing store and then brought into memory for continued execution.
Swapping process between memory and backing store is shown in Figure 6.6.

The system maintains a ready queue consisting of all processes whose

swapped out on the backing store or in memory and are ready to run.

 Whenever the CPU scheduler decides to execute a process, it calls the

dispatcher.
 The dispatcher checks to see whether the next process in the queue is in
memory or backing store:

93
 o If it is in backing store:
 If there is free memory, the dispatcher swaps in the desired
process.
 If there is no free memory, it swaps out a process currently
in memory and swaps in the desired process.
 The dispatcher then reloads registers and transfers control to the
selected process.

Figure 6.6: Swapping of two processes using a disk as a backing store.

The context-switch time in such a swapping system is high.

Example: assume that the size of a process is 100 MB, and the backing store is
a standard hard disk with a transfer rate of 50 MB per second. The actual
transfer of the 100 MB process to or from main memory takes:
𝑝𝑟𝑜𝑐𝑒𝑠𝑠 s𝑖𝑧𝑒 100
= = 2 sec = 2000 𝑚𝑖𝑙𝑙𝑖𝑠𝑒𝑐𝑜𝑛𝑑
𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟 𝑟𝑎𝑡𝑒 50

Assuming an average latency of 8 milliseconds, the swap time is 2008

milliseconds. Since we must both swap out and swap in, the total swap time is
about 4016 milliseconds. Notice that the major part of the swap time is
transfer time. We will need 60 seconds for swapping 3 GB process.

94
6-3 Contiguous memory allocation

The memory is usually divided into two partitions:

1. One for OS: usually in low memory address (at address 0).
2. One for the user processes: below OS memory.

To load several user processes into memory at the same time, we need
to consider how to allocate available memory to these processes. In
contiguous memory allocation, each process is contained in a single contiguous
section of memory.

6.3.1 Memory Protection

We can provide memory protection by using relocation register together

with a limit register. With this scheme:

 Each logical address must be less than the limit register.

 The MMU maps the logical address by adding the value in the relocation
register.
 This mapped address is sent to memory.

Figure 6.7: Hardware support for relocation and limit registers.

This is shown in Figure 6.7. The system shown in Figure 6.7 allows the
following:

95
 1. Protection against user programs accessing areas that they should not,
2. Programs to be relocated to different memory starting addresses as
needed,
3. The memory space devoted to the OS to grow or shrink dynamically as
needs change.

6.3.2 Memory Allocation

One of the simplest methods for allocating memory is to divide memory

into several fixed-sized partitions (holes). Each hole contains exactly one
process. In this multiple partition method:

 Memory contains a set of holes of various sizes.

 OS must keep a table indicating which holes are available and which are
occupied.
 When a partition is free, a selected process is loaded into it.
 When the process terminates, the partition becomes available for
another process.

There are many different strategies for finding the best allocation of
memory to processes:

 First fit: Allocate the first hole that is big enough. Searching can start
either at the beginning of the set of holes or at the location where the
previous first-fit search ended. We can stop searching as soon as we find
a free hole that is large enough.
 Best fit: Allocate the smallest hole that is big enough. We must search
the entire list, unless the list is ordered by size. This strategy produces
the smallest leftover hole.

96
  Worst fit: Allocate the largest hole. Again, we must search the entire list,
unless it is sorted by size. This strategy produces the largest leftover
hole, which may be more useful than the smaller leftover hole. Because
this increases the likelihood that the remaining portion will be usable for
satisfying future requests.

Some important remarks:

 The number of partitions bounds the degree of multiprogramming.

 Both first fit and best fit are better than worst fit in terms of decreasing
time and storage utilization.
 First fit and best fit are about equal in terms of storage utilization, but
first fit is faster.

6.3.3 Fragmentation

There are two types of fragmentation:

1. External fragmentation: exists when there is enough total memory
space to satisfy a request, but the available spaces are not contiguous;
storage is fragmented into many small holes. All the memory allocation
strategies suffer from external fragmentation, though first and best fits
experience the problems more than worst fit.
2. Internal fragmentation: This is caused by the fact that memory is
allocated in blocks of a fixed size, whereas the actual memory needed
will rarely be that exact size. For example, let a hole of 18,464 bytes
allocated to process of 18,462 bytes. This left a hole of 2 bytes. Internal
fragmentation also occurs, with all memory allocation strategies.

97
There are two solutions for external fragmentation:

1. Compaction: place all free memory together in one large block.

However, compaction is not always possible. This scheme can be
expensive.
2. Noncontiguous allocation: allow a process to be allocated physical
memory wherever such memory is available. There are two
complementary techniques achieve this solution:
a. Paging,
b. Segmentation.

6-4 Segmentation

Segmentation involves the simple notion of dividing a program into

separate pieces. Each piece has a logical unity, exhibiting a relationship among
all its code or data values. For example, a segment may be the code of a single
procedure, the data of an array, or the collection of all local data values used
by a particular module. Segmentation allows a program to be divided into
many pieces having different access rights.

6.4.1 Basic Method

Segmentation is memory-management scheme that supports the user

view of memory as a collection of variable-sized segments, with no necessary
ordering among segments.

Each segment has a unique name. A code or data item within a segment
is addressed as the pair (name, offset), where:

 name is the name of the segment containing the data item.

98
  offset is its location within the segment. That is, its distance from the
start of the segment (length).

Logically, the programmer pictures a program as a long collection of

segments. Segments can be separately relocated, allowing any segment to be
placed in any available memory locations. The relationship between a logical
segment and its true memory position is shown in Figure 6.8.

 A logical address space is a collection of segments.

 Each segment has a name and a length.
o The user therefore specifies each address by two quantities: a
segment name and an offset.
 The addresses specify both the segment name and the offset within the
segment.

Figure 6.8: User's view of a program.

6.4.2 Segmentation address translation

The operating system must maintain a table of segment names and their
true addresses in memory. This segment table is used to map between logical
and physical addresses. A logical address consists of two parts:

99
 1. Segment name: is used as an index to the segment table.
2. Segment offset: must be between 0 and segment length.

When a program generates an address of the form (name, offset):

 Operating system looks up name in the segment directory and

determines its real beginning memory address.
 Then OS adds the offset to this address, giving the true memory address
of the code or data item.

Figure 6.9: Segment address translation.

This translation is shown in Figure 6.9. For efficiency there is usually one
operating system segment address table for each process in execution. Two
processes that need to share access to a single segment would have the same
segment name and address in their segment tables.

It is more important to observe that, a user’s program does not know

what true memory addresses it uses. It has no way -and no need- to determine
the actual address associated with a (name, offset). The (name, offset) pair is
adequate to access any data or instruction to which a program should have
access.
100
 This hiding of addresses has three advantages for the operating system:

1. The operating system can place any segment at any location or move
any segment to any location, even after the program begins to execute.
Because the operating system translates all address references by a
segment address table, the operating system need only update the
address in that one table when a segment is moved.
2. A segment can be removed from main memory (and stored on an
auxiliary device) if it is not being used currently. (The appearance of
memory to the user is not necessarily what exists.)
3. Every address reference pass through the operating system, so there is
an opportunity to check each one for protection.

Because of this last characteristic, a process can access a segment only if

that segment appears in that process’s segment-translation table. The
operating system controls which programs have entries for a particular
segment in their segment address tables. This control provides strong
protection of segments from access by unpermitted processes. For example,
program A might have access to segments X and Y of user B but not to other
segments of that user or of any other user.

In a straightforward way we can allow a user to have different

protection classes for different segments of a program. For example, one
segment might be read-only data, a second might be execute-only code, and a
third might be writeable data. In a situation like this one, segmentation can
approximate the goal of separate protection of different pieces of a program
(by using tagged architecture).

From above we can say that segmentation offers several protection

benefits:
101
  Many different classes of data items can be assigned different levels of
protection.
 Two or more users can share access to a segment, with potentially
different access rights.
 A user cannot generate an address or access to an unpermitted
segment.

However, segmentation also contain some protection difficulties:

 Each segment has a particular size. However, a program can generate a

reference to a valid segment name, but with an offset beyond the end of
the segment. For example, reference (A, 9999) looks perfectly valid, but
segment A may be only 200 bytes long. Therefore, secure
implementation of segmentation requires the checking of a generated
address to verify that it is not beyond the current end of the segment
referenced. This results in extra expense in terms of time and resources.
This is shown in Figure 6.10. Thus, we need to balance protection with
efficiency, finding ways to keep segmentation as efficient as possible.
 Segment names are inconvenient to encode in instructions and the
operating system’s lookup of the name in a table can be slow. To
overcome these difficulties, segment names are often converted to
numbers by the compiler when a program is translated; the compiler
also appends a linkage table that matches numbers to true segment
names. This is shown in Figure 6.10.

A logical address consists of two parts:

1. Segment number (s): is used as an index to the segment table.

2. Segment offset (d): must be between 0 and segment limit.

102
 a. If it is not, we trap to the operating system (logical addressing
attempt beyond end of segment).
b. When an offset is legal, it is added to the segment base to
produce the address in physical memory of the desired byte.

Segment table is essentially an array of base-limit register pairs.

Figure 6.10: Segmentation hardware.

Example: consider the situation shown in Figure 6.11. We have 5

segments numbered from 0 through 4. The segments are stored in physical
memory as shown. The segment table has a separate entry for each segment,
giving the beginning address of the segment in physical memory (base) and the
length of that segment (limit).

 Segment 2 is 400 bytes long and begins at location 4300.

o Thus, a reference to byte 53 of segment 2 is mapped onto location
4300 + 53= 4353.
 Segment 3 is 1100 bytes long and begins at location 3200.
o A reference to byte 852 of segment 3, is mapped onto location
3200 + 852 = 4052.

103
  Segment 0 is 1000 bytes long and begins at location 1400.
o A reference to byte 1222 of segment 0 would result in a trap to
the OS, as this segment is only 1000 bytes long.

Figure 6.11: Example of segmentation.

6.5 Paging

An alternative to segmentation is paging. Paging is a memory-

management scheme that permits the physical address space of a process to
be noncontiguous. Paging avoids external fragmentation by allocating memory
in equal sized blocks known as pages. It is the most memory management
technique used today. As with segmentation, each address in a paging scheme
is a two-part object, this time consisting of (page, offset).

6.5.1 Basic Method

The basic idea behind paging is that:

104
 Figure 6.12: Paging hardware.

 To divide the physical memory into several equal sized blocks called
frames,
 To divide the programs logical memory space into blocks of the same
size called pages.
 Any page from any process can be placed into any available frame.

The hardware support for paging is illustrated in Figure 6.12. Every

address generated by the CPU is divided into two parts:

1. Page number (p): is used as an index into a page table.

2. Page offset (d): is the displacement within the page.

The page table is used to maps pages to their corresponding frames. The
paging model of memory is shown in Figure 6.13. For example, page 2 of the
program logical memory is currently stored in frame 3 of physical memory.

105
 Figure 6.13: Paging model of logical and physical memory.

6.5.2 Paging address translation

The page size and frame size are defined by the hardware. The size of a
page is typically a power of 2, allowing addresses to be split at a certain
number of bits. If the size of the logical address space is 2m, and a page size is
2n then the high-order m - n bits of a logical address designate the page
number, and the n low-order bits designate the page offset. Thus, the logical
address is as follows:
Page number page offset
p d
m–n n

Each address is again translated by a process like that of segmentation:

The operating system maintains a table of user page numbers and their true
addresses in memory. The page portion of every (page, offset) reference is
converted to a page frame address by a table lookup; the offset portion is
added to the page frame address to produce the real memory address of the
object referred to as (page, offset). This process is illustrated in Figure 6.14.

106
 Figure 6.14: Paging example for a 32-byte memory with 4-byte pages.

Consider the memory in Figure 6.14. Here, in the logical address, n = 2

and m = 4. Page size is 4 bytes and physical memory of 32 bytes (8 pages). Now
we show how the logical address is mapped into physical address. To do this:

1. Firstly, specify the page number and page offset of a given logical
address,
2. Secondly, determine the allocated frame from page table,
3. Finally, use the form:

Physical address = frame number * frame size + page offset

What is the physical address corresponding to logical address 0?

1. Logical address 0 is in page 0, with offset 0.
2. Page 0 is allocated frame 5.

107
 3. Logical address 0 maps to physical address = 5 x 4 + 0 = 20.
What is the physical address corresponding to logical address 3?
1. Logical address 3 is in page 0, with offset 3.
2. Page 0 is allocated frame 5.
3. Logical address 3 maps to physical address = 5 x 4 + 3 = 23.
What is the physical address corresponding to logical address 4?
1. Logical address 4 is in page 1, with offset 0.
2. Page 1 is allocated frame 6.
3. Logical address 4 maps to physical address = 6 x 4 + 0 = 24.
What is the physical address corresponding to logical address 13?
1. Logical address 13 is in page 3, with offset 1.
2. Page 3 is allocated frame 2.
3. Logical address 13 maps to physical address = 2 x 4 + 1 = 9.

Figure 6.15: Free frames (a) before allocation and (b) after allocation.

When a process arrives in the system and requires n pages, at least n

frames must be available in memory. If n frames are available, they are
allocated to this process.

108
  The first page is loaded into one of the allocated frames, and the frame
number is put in the page table for this process.
 The next page is loaded into another frame; its frame number is put into
the page table,
 And so on (see Figure 6.15).
Some important remarks:

 There is no external fragmentation with paging: any free frame can be

allocated to a process that needs it.
 There may be some internal fragmentation: frames are allocated as
units. If the memory requirements of a process do not happen to
coincide with page boundaries, the last frame allocated may not be
completely full.
o For example, if page size is 2,048 bytes, a process of 72,766 bytes
will need 35 pages plus 1,086 bytes. It will be allocated 36 frames,
resulting in internal fragmentation of 2,048 - 1,086 = 962 bytes in
last frame.
o In the worst case, a process would need 11 pages plus 1 byte. It
would be allocated 11 + 1 frames, resulting in internal
fragmentation of almost an entire frame.
 Larger page sizes waste more memory but are more efficient in terms of
overhead.

6.5.3 Protection

Memory protection in a paged environment is ensured by protection

bits kept in the page table.

109
  One bit can be added to the page table to classify the page as read-
write, read-only, read-write-execute, or some combination of these sorts
of things.
 A valid-invalid bit can be added to mask off entries in the page table
that are not in use by the current process.
o If this bit is set to "valid" the associated page is in the process
logical address space and is legal page.
o If it is set to "invalid" the page is not in the process logical address
space and is illegal page.
o OS sets this bit for each page to allow or disallow access to the
page.

Figure 6.16: Valid (v) or invalid (i) bit in a page table.

Example: suppose that in a system with a 14-bit address space (from 0 to 214 =
16383), we have a program that should use only addresses 0 to 10468 (need 6
pages). Given a page size of 2 KB (211), we have the situation shown in Figure
6.16.

110
 Addresses in pages 0, 1, 2, 3, 4, and 5 are mapped normally through the
page table. Any attempt to generate an address in pages 6 or 7 will find that
the valid-invalid bit is set to invalid, and the computer will trap to the OS
(invalid page reference).

Notice that this scheme has created a problem. Because the program
extends only to address 10468, any reference beyond that address is illegal.
However, references to page 5 are classified as valid, so accesses to addresses
up to 12287 are valid. Only the addresses from 12288 to 16383 are invalid. This
problem is a result of the 2-KB page size and reflects the internal
fragmentation of paging.

6.5.4 Shared Pages

An advantage of paging is the possibility of sharing common code. This

consideration is particularly important in a time-sharing environment.
Example: Consider a system that supports 40 users, each of whom executes a
text editor. If the text editor consists of 150 KB of code and 50 KB of data
space, we need 8,000 KB to support the 40 users. If the code is reentrant code
(or pure code) it can be shared as shown in Figure 6.17.
Reentrant code is non-self-modifying code: it never changes during
execution. Thus, two or more processes can execute the same code at the
same time. From Figure 6.17, we see that:
 3 editor pages are shared among 3 processes.
 Each process has its own data page.
 Only one copy of the editor need be kept in physical memory.
 Each user page table maps onto the same physical copy of the editor,
but data pages are mapped onto different frames.

111
 Thus, to support 40 users, we need only one copy of the editor (150 KB),
plus 40 copies of the 50 KB of data space per user. The total space
required is now 150 + 40  50 = 2150 KB instead of 8,000 KB.

Figure 6.17: Sharing of code in a paging environment.

=========================================

112
 Chapter 7

Secondary-storage management
In this chapter, we first introduce an overview of magnetic disks. We
then describe disk-scheduling algorithms, which schedule the order of disk I/O
operations to improve performance.

7.1 Overview of mass-storage structure

In this section, we present a general overview of the physical structure

of secondary and tertiary storage devices.

7.1.1 Magnetic Disks

Magnetic disks have the following properties (see Figure 7.1):

 Magnetic disk consists of several platters.

 Each disk platter has a flat circular shape, like a CD.
 Common platter diameters range from 1.8 to 5.25 inches.
 The two surfaces of a platter are covered with a magnetic material.
 A read -write head flies above each surface of every platter.
 The heads are attached to a disk arm that moves all the heads as a unit.
 The surface of a platter is logically divided into circular tracks which are
subdivided into sectors.
 The set of tracks that are at one arm position makes up a cylinder.
 There may be thousands of concentric cylinders in a disk drive, and each
track may contain hundreds of sectors.
 The storage capacity of common disk drives is measured in gigabytes.

113
 Figure 7.1 Moving-head disk mechanism.

When the disk is in use, a drive motor spins it at high speed. Most drives
rotate 60 to 200 times per second. Disk speed has two parts:
1. The transfer rate is the rate at which data flow between the drive and
the computer.
2. The positioning time sometimes called the random-access time consists
of:
a. Seek time: is the time necessary to move the disk arm to the
cylinder containing the desired cylinder.
b. Rotational latency: is the additional time necessary for the disk to
rotate the desired sector to the disk head.

Disk heads fly over the surfaces on a very thin cushion of air. If they
should accidentally contact the disk, then a head crash occurs, which normally
cannot be repaired; the entire disk must be replaced.

Hard drives can be removable, and some are even hot-swappable,

meaning they can be removed while the computer is running, and a new hard
drive inserted in their place.

114
 Disk drives are connected to the computer via a cable known as the I/O
Bus. Some of the common interface formats include:

1. Enhanced Integrated Drive Electronics, EIDE;

2. Advanced Technology Attachment, ATA;
3. Serial ATA, SATA, Universal Serial Bus, USB;
4. Fiber Channel, FC, and Small Computer Systems Interface, SCSI.

The data transfers on a bus are carried out by special electronic

processors called controllers. The host controller is the controller at the
computer end of the bus. A disk controller is built into each disk drive. To
perform a disk, I/0 operations:
 CPU places commands into the host controller via I/O ports.
 The host controller then sends the command via messages to the disk
controller.
 The disk controller operates the disk-drive hardware to carry out the
command.
 Disk controllers usually have a built-in cache.
o Data transfer between the cache and the disk surface,
o Then data transfer between the cache and the host controller, at
fast electronic speeds.

7-2 Disk scheduling

As we mentioned previously, the access time has two major
components; the seek time and rotational latency. The disk bandwidth is the
total number of bytes transferred, divided by the total time between the first
request for service and the completion of the last transfer. Both bandwidth
and access time can be improved by processing disk I/O requests in a good

115
order. Whenever a process needs disk I/O requests. These disk requests must
include the following information:

 Disk address,
 Memory address,
 Number of sectors to transfer,
 Whether the request is for reading or writing.

For a multiprogramming system with many processes, the disk queue

may have several requests. Thus, when one request is completed, OS chooses
which request to service next. How does the operating system make this
choice? Any one of several disk-scheduling algorithms can be used.

7.2.1 FCFS scheduling

FCFS is simple and fair, but it is not very efficient. That is, it generally
does not provide the fastest service.

Example: consider a disk queue with requests for I/O to blocks on cylinders:
98, 183, 37, 122, 14, 124, 65, 67, in this order.
If the disk head is initially at cylinder 53, it will first move from 53 to 98, then to
183, 37, 122, 14, 124, 65, and finally to 67, for a total head movement of 640
cylinders. This schedule is diagrammed in Figure 7.2.
The moving from 122 to 14 and then back to 124 illustrates the problem
with this schedule. If the requests for cylinders 37 and 14 could be serviced
together, before or after the requests for 122 and 124, the total head
movement could be decreased substantially, and performance could be
thereby improved.

116
 Figure 7.2: FCFS disk scheduling

7.2.2 SSTF scheduling

It seems reasonable to service all the requests close to the current head
position before moving the head far to service other requests. This assumption
is the basis for the shortest seek time first (SSTF) algorithm. The SSTF
algorithm selects the request with the least seek time from the current head
position.
Example: consider a disk queue with requests for I/O to blocks on cylinders:
98, 183, 37, 122, 14, 124, 65, 67, in this order.
According to SSTF algorithm:
1. Cylinder 65 is the closest request to the initial position 53.
2. Once we are at cylinder 65, the next closest request is at cylinder 67.
3. From there, the request at cylinder 37 is closer than the one at 98, so 37
is served next.
4. Continuing, we service the request at cylinder 14, then 98, 122, 124, and
finally 183 (see Figure 7.3).

117
 Figure 7.3: SSTF disk scheduling

This scheduling method results in a total head movement of only 236

cylinders (down from 640 required for the same set of requests under FCFS).
Clearly, this algorithm gives a substantial improvement in performance.
Although the SSTF algorithm is a substantial improvement over the FCFS
algorithm, it is not optimal. In the example, the distance could be reduced still
further to 208 by starting with 37 and then 14 first before processing the rest
of the requests.

7.2.3 Scan scheduling

The scan algorithm is sometimes called the elevator algorithm, since the
disk arm behaves just like an elevator in a building, first servicing all the
requests going up and then reversing to service requests the other way. In scan
algorithm the disk arm starts at one end (initial position) and moves toward
the other end, servicing requests as it reaches each cylinder, until it gets to the
other end of the disk. At the other end, the direction of head movement is
reversed, and servicing continues. The head continuously scans back and forth
across the disk.

Example: consider a disk queue with requests for I/O to blocks on cylinders:
98, 183, 37, 122, 14, 124, 65, 67, in this order.

118
Assume that the disk arm is moving toward 0 from the initial position 53.
According to scan algorithm:
1. In this direction the algorithm will service 37 and then 14.
2. At cylinder 0, the arm will reverse and will move toward the other end of
the disk, servicing the requests at 65, 67, 98, 122, 124, and 183 (see
Figure 7.4).

This algorithm causes the head to move till the end of the disk even if
there are no requests to be serviced. It causes long waiting time for the
cylinders just visited by the head. As a result, the requests at the midrange are
serviced more and those arriving behind the disk arm will have to wait.

Figure 7.4: Scan disk scheduling

Figure 7.5: C-Scan disk scheduling

119
7.2.4 C-Scan scheduling

Circular scan (C-Scan) algorithm is a variant of SCAN designed to provide

a more uniform wait time. C-SCAN moves the head from one end of the disk to
the other, servicing requests along the way. When the head reaches the other
end it immediately returns to the beginning of the disk without servicing any
requests on the return trip (see Figure 7.5).

7.2.5 Look scheduling

Both SCAN and C-SCAN move the disk arm across the full width of the
disk. Look and C-look algorithms are improved versions of the scan and C-scan
algorithms. In look scheduling, the arm goes only as far as the final request in
each direction. Then, it reverses direction immediately without going all the
way to the end of the disk. The main difference between scan scheduling and
look scheduling is:

 Scan scheduling scans all the cylinders of the disk starting from one end
to the other end even if there are no requests at the ends.
 Look scheduling scans all the cylinders of the disk starting from the first
request at one end to the last request at the other end.
o It does not cause the head to move till the ends of the disk when
there are no requests to be serviced.
o It provides better performance as compared to scan algorithm.

Figure 7.6 shows the diagram of C-look algorithm.

120
 Figure 7.6: C-Look disk scheduling

7.2.6 Selection of a Disk-Scheduling Algorithm

How do we choose the best one of many disk-scheduling algorithms?

 SSTF increases performance over FCFS.

 SCAN and C-SCAN perform better for systems that place a heavy load on
the disk, because they are less likely to cause a starvation problem.
 LOOK provides better performance as compared to SCAN scheduling.
 For busier systems, SCAN and LOOK algorithms eliminate starvation
problems.
 With any scheduling algorithm, performance depends heavily on the
number and types of requests.
o Suppose that the queue usually has just one outstanding request.
o Then, all scheduling algorithms behave the same, because they
have only one choice of where to move the disk head: they all
behave like FCFS scheduling.
=========================================

121
Exercises

1. Distinguish between the client-server and peer-to-peer models of

distributed systems.
2. What are the main differences between operating systems for mainframe
computers and personal computers?
3. How do clustered systems differ from multiprocessor systems? What is
required for two machines belonging to a cluster to cooperate to provide
a highly available service?
4. What is the main difficulty that a programmer must overcome in writing
an operating system for a real-time environment?
5. Define the essential properties of the following types of operating
systems:
a. Batch
b. Time sharing
c. Real time
d. Distributed
e. Clustered
f. Handheld
6. The issue of resource utilization shows up in different forms in different
types of operating systems. List what resources must be managed
carefully in the following settings:
a. Mainframe or minicomputer systems
b. Workstations connected to servers
c. Handheld computers
7. What is the purpose of interrupts?

122
8. What are the five major activities of an operating system regarding file
management?
9. What are the three major activities of an operating system regarding
memory management?
10. The services and functions provided by an operating system can be
divided into two main categories. Briefly describe the two categories and
discuss how they differ.
11. It is sometimes difficult to achieve a layered approach if two components
of the operating system are dependent on each other. Identify a scenario
in which it is unclear how to layer two system components that require
tight coupling of their functionalities.
12. What is the main advantage of the layered approach to system design?
What are the disadvantages of using the layered approach?
13. Describe three general methods for passing parameters to the operating
system.
14. What is the main advantage of the microkernel approach to system
design? How do user programs and system services interact in a
microkernel architecture? What are the disadvantages of using the
microkernel approach?
15. In what ways is the modular kernel approach like the layered approach?
In what ways does it differ from the layered approach?
16. Describe the actions taken by a kernel to context-switch between
processes.
17. Describe the differences among short-term, medium-term, and long-term
scheduling.
18. Describe the differences between independent and cooperating
processes.

123
19. Describe the differences between the two methods of inter-process
communication.
20. Including the initial parent process, how many processes are created by
the program shown below?

21. Consider a system running ten I/O-bound tasks and one CPU-bound task.
Assume that the I/O-bound tasks issue an I/O operation once for every
millisecond of CPU computing and that each I/0 operation takes 10
milliseconds to complete. Also assume that the context-switching
overhead is 0.1 millisecond and that all processes are long-running tasks.
Describe the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b. The time quantum is 10 milliseconds
22. Why is it important for the scheduler to distinguish I/0-bound programs
from CPU-bound programs?
23. A CPU-scheduling algorithm determines an order for the execution of its
scheduled processes. Given n processes to be scheduled on one
processor, how many different schedules are possible? Give a formula in
terms of n.

124
24. What advantage is there in having different time-quantum sizes at
different levels of a multilevel queueing system?
25. Explain the differences in how much the following scheduling algorithms
discriminate in favor of short processes:
a. FCFS
b. RR
c. Multilevel feedback queues
26. Which of the following scheduling algorithms could result in starvation?
a. First-come, first-served
b. Shortest job first
c. Round robin
d. Priority
27. Consider the following set of processes, with the length of the CPU burst
given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, Ps,
all at time 0.
a. Draw four Gantt charts that illustrate the execution of these
processes using the following scheduling algorithms: FCFS, SJF,
non-preemptive priority (a smaller priority number implies a
higher priority), and RR (quantum= 1).
b. What is the turnaround time of each process for each of the
scheduling algorithms in part a?

125
 c. What is the waiting time of each process for each of these
scheduling algorithms?
d. Which of the algorithms results in the minimum average waiting
time (over all processes)?
28. Suppose that the following processes arrive for execution at the times
indicated. Each process will run for time listed. In answering the
questions, use non-preemptive scheduling, and base all decisions on the
information you have at the time the decision must be made.

a. What is the average turnaround time for these processes with the
FCFS scheduling algorithm?
b. What is the average turnaround time for these processes with the
SJF scheduling algorithm?
c. The SJF algorithm is supposed to improve performance but notice
that we chose to run process P1 at time 0 because we did not
know that two shorter processes would arrive soon. Compute
what the average turnaround time will be if the CPU is left idle for
the first 1 unit and then SJF scheduling is used. Remember that
processes P1 and P2 are waiting during this idle time, so their
waiting time may increase. This algorithm could be known as
future-knowledge scheduling.
29. Why is it important to keep the size of the critical section as small as
possible?

126
30. As a critical section can be executed by one process at a time. Other
processes must wait until the current thread must finish. Are long critical
sections minimizing the throughput?
31. What is the meaning of the term busy waiting? What other kinds of
waiting are there in an operating system? Can busy waiting be avoided
altogether? Explain your answer.
32. Show that, if the wait() and signal() semaphore operations are not
executed atomically, then mutual exclusion may be violated.
33. Illustrate how a binary semaphore can be used to implement mutual
exclusion among n processes.
34. Briefly describe the characteristics of a complete solution to the critical
section problem.
35. Briefly describe how the semaphore provides mutual exclusion of 2
processes to access their shared common data.
36. Briefly describe the solution of signal(S) and wait(S) implementation
without busy waiting.
37. Is it possible to have a deadlock involving only a single process? Explain
your answer.
38. Consider a system consisting of four resources of the same type that are
shared by three processes, each of which needs at most two resources.
Show that the system is deadlock free.
39. Write a program in C++ or Java language to implement the banker's
algorithm.
40. Modify your solution to Exercise 3 so that it is starvation-free.
41. Consider the traffic deadlock depicted in the following figure.

127
 a. Show that the four necessary conditions for deadlock hold in this
example.
b. State a simple rule for avoiding deadlocks in this system.
42. Assume that there is a single-lane bridge connects the two cities A and B.
People in the two cities use this bridge to deliver their produce to the
neighboring town. The bridge can become deadlocked if a person of city A
and a person of city B get on the bridge at the same time (people of city A
are stubborn and are unable to back up.) Using semaphores, design an
algorithm that prevents deadlock. Initially, do not be concerned about
starvation (the situation in which people of city A prevent people of city B
from using the bridge, or vice versa).
43. Consider the following resource-allocation policy. Requests for and
releases of resources are allowed at any time. If a request for resources
cannot be satisfied because the resources are not available, then we
check any processes that are blocked waiting for resources. If a blocked
process has the desired resources, then these resources are taken away
from it and are given to the requesting process. The vector of resources
for which the blocked process is waiting is increased to include the
resources that were taken away. For example, consider a system with
three resource types and the vector Available initialized to (4,2,2). If
process P0 asks for (2,2,1), it gets them. If P1 asks for (1,0,1), it gets them.

128
 Then, if P0 asks for (0,0,1), it is blocked (resource not available). If P2 now
asks for (2,0,0), it gets the available one (1,0,0) and one that was allocated
to P0 (since P0 is blocked). P0's Allocation vector goes down to (1,2,1),
and its Need vector goes up to (1,0,1).
a. Can deadlock occur? If you answer "yes" give an example. If you
answer "no" specify which necessary condition cannot occur.
b. Can indefinite blocking occur? Explain your answer.
44. Consider the following snapshot of a system:

Answer the following questions using the banker's algorithm:

a. What is the content of the matrix Need?
b. Is the system in a safe state?
c. If a request from process P1 arrives for (0,4,2,0), can the request
be granted immediately?
45. Consider a system consisting of m resources of the same type being
shared by n processes. A process can request or release only one resource
at a time. Show that the system is deadlock free if the following two
conditions hold:
a. The maximum need of each process is between one resource and
m resources.
b. The sum of all maximum needs is less than m + n.
46. Explain the difference between internal and external fragmentation.

129
47. Compare the memory organization schemes of contiguous memory
allocation, pure segmentation, and pure paging with respect to the
following issues:
a. External fragmentation
b. Internal fragmentation
c. Ability to share code across processes
48. What is the purpose of paging the page tables?
49. On a system with paging, a process cannot access memory that it does
not own. Why? How could the operating system allow access to other
memory? Why should it or should it not?
50. Consider a logical address space of 64 pages of 1,024 words each, mapped
onto a physical memory of 32 frames.
a. How many bits are there in the logical address?
b. How many bits are there in the physical address?
51. Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600
KB (in order), how would the first-fit, best-fit, and worst-fit algorithms
place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which
algorithm makes the most efficient use of memory?
52. Consider the following segment table:

What are the physical addresses for the following logical addresses?
a. 0,430

130
 b. 1,10
c. 2,500
d. 3,400
e. 4,112
53. Consider a logical address space of 32 pages with 1,024 words per page,
mapped onto a physical memory of 16 frames.
a. How many bits are required in the logical address?
b. How many bits are required in the physical address?
54. Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4999. The
drive is currently serving a request at cylinder 143, and the previous
request was at cylinder 125. The queue of pending requests, in FIFO
order, is:
86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
Starting from the current head position, what is the total distance (in
cylinders) that the disk arm moves to satisfy all the pending requests for
each of the following disk-scheduling algorithms?
a. FCFS
b. SSTF
c. SCAN
d. LOOK
e. C-SCAN
f. C-LOOK
55. Write a program that simulates the disk-scheduling algorithms.
56. Why is rotational latency usually not considered in disk scheduling? How
would you modify SSTF, SCAN, and C-SCAN to include latency
optimization?

131
57. None of the disk-scheduling disciplines, except FCFS, is truly fair
(starvation may occur).
a. Explain why this assertion is true.
b. Describe a way to modify algorithms such as SCAN to ensure
fairness.
c. Explain why fairness is an important goal in a time-sharing system.
d. Give three or more examples of circumstances in which it is
important that the operating system be unfair in serving I/O
requests.

132