Chapter 1: Introduction

● What is an Operating System?

● Mainframe Systems
● Desktop Systems
● Multiprocessor Systems
● Distributed Systems
● Clustered System
● Real -Time Systems
● Handheld Systems
● Computing Environments

1.1 Silberschatz, Galvin and Gagne ©2002

 What is an Operating System?

● A program that acts as an intermediary between a user of a

computer and the computer hardware.
● Operating system goals:
● Execute user programs and make solving user problems easier.
● Make the computer system convenient to use.
● Use the computer hardware in an efficient manner.

1.2 Silberschatz, Galvin and Gagne ©2002

 Computer System Components

1. Hardware – provides basic computing resources (CPU,

memory, I/O devices).
2. Operating system – controls and coordinates the use of the
hardware among the various application programs for the
various users.
3. Applications programs – define the ways in which the system
resources are used to solve the computing problems of the users
(compilers, database systems, video games, business
programs).
4. Users (people, machines, other computers).

1.3 Silberschatz, Galvin and Gagne ©2002

Abstract View of System Components

1.4 Silberschatz, Galvin and Gagne ©2002

 Operating System Definitions

● Resource allocator – manages and allocates resources.

● Control program – controls the execution of user programs and
operations of I/O devices .
● Kernel – the one program running at all times (all else being
application programs).

1.5 Silberschatz, Galvin and Gagne ©2002

 Mainframe Systems

● Reduce setup time by batching similar jobs

● Automatic job sequencing – automatically transfers control
from one job to another. First rudimentary operating system.
● Resident monitor
● initial control in monitor
● control transfers to job
● when job completes control transfers pack to monitor

1.6 Silberschatz, Galvin and Gagne ©2002

Memory Layout for a Simple Batch System

1.7 Silberschatz, Galvin and Gagne ©2002

 Multiprogrammed Batch Systems

Several jobs are kept in main memory at the same time, and the
CPU is multiplexed among them.

1.8 Silberschatz, Galvin and Gagne ©2002

 OS Features Needed for Multiprogramming

● I/O routine supplied by the system.

● Memory management – the system must allocate the memory
to several jobs.
● CPU scheduling – the system must choose among several jobs
ready to run.
● Allocation of devices.

1.9 Silberschatz, Galvin and Gagne ©2002

 Time-Sharing Systems–Interactive Computing

● The CPU is multiplexed among several jobs that are kept in

memory and on disk (the CPU is allocated to a job only if the
job is in memory).
● A job swapped in and out of memory to the disk.
● On-line communication between the user and the system is
provided; when the operating system finishes the execution of
one command, it seeks the next “control statement” from the
user’s keyboard.
● On-line system must be available for users to access data and
code.

1.10 Silberschatz, Galvin and Gagne ©2002

 Desktop Systems

● Personal computers – computer system dedicated to a single

user.
● I/O devices – keyboards, mice, display screens, small printers.
● User convenience and responsiveness.
● Can adopt technology developed for larger operating system’
often individuals have sole use of computer and do not need
advanced CPU utilization of protection features.
● May run several different types of operating systems
(Windows, MacOS, UNIX, Linux)

1.11 Silberschatz, Galvin and Gagne ©2002

 Parallel Systems

● Multiprocessor systems with more than on CPU in close

communication.
● Tightly coupled system – processors share memory and a clock;
communication usually takes place through the shared memory.
● Advantages of parallel system:
● Increased throughput
● Economical
● Increased reliability
● graceful degradation
● fail-soft systems

1.12 Silberschatz, Galvin and Gagne ©2002

 Parallel Systems (Cont.)

● Symmetric multiprocessing (SMP)

● Each processor runs and identical copy of the operating system.
● Many processes can run at once without performance
deterioration.
● Most modern operating systems support SMP
● Asymmetric multiprocessing
● Each processor is assigned a specific task; master processor
schedules and allocated work to slave processors.
● More common in extremely large systems

1.13 Silberschatz, Galvin and Gagne ©2002

Symmetric Multiprocessing Architecture

1.14 Silberschatz, Galvin and Gagne ©2002

 Distributed Systems

● Distribute the computation among several physical processors.

● Loosely coupled system – each processor has its own local
memory; processors communicate with one another through
various communications lines, such as high-speed buses or
telephone lines.
● Advantages of distributed systems.
● Resources Sharing
● Computation speed up – load sharing
● Reliability
● Communications

1.15 Silberschatz, Galvin and Gagne ©2002

 Distributed Systems (cont)

● Requires networking infrastructure.

● Local area networks (LAN) or Wide area networks (WAN)
● May be either client-server or peer-to-peer systems.

1.16 Silberschatz, Galvin and Gagne ©2002

General Structure of Client-Server

1.17 Silberschatz, Galvin and Gagne ©2002

 Clustered Systems

● Clustering allows two or more systems to share storage.

● Provides high reliability.
● Asymmetric clustering: one server runs the application while
other servers standby.
● Symmetric clustering: all N hosts are running the application.

1.18 Silberschatz, Galvin and Gagne ©2002

 Real-Time Systems

● Often used as a control device in a dedicated application such

as controlling scientific experiments, medical imaging systems,
industrial control systems, and some display systems.
● Well-defined fixed-time constraints.
● Real-Time systems may be either hard or soft real-time.

1.19 Silberschatz, Galvin and Gagne ©2002

 Real-Time Systems (Cont.)

● Hard real-time:
● Secondary storage limited or absent, data stored in short term
memory, or read-only memory (ROM)
● Conflicts with time-sharing systems, not supported by
general-purpose operating systems.

● Soft real-time
● Limited utility in industrial control of robotics
● Useful in applications (multimedia, virtual reality) requiring
advanced operating-system features.

1.20 Silberschatz, Galvin and Gagne ©2002

 Handheld Systems

● Personal Digital Assistants (PDAs)

● Cellular telephones
● Issues:
● Limited memory
● Slow processors
● Small display screens.

1.21 Silberschatz, Galvin and Gagne ©2002

Migration of Operating-System Concepts and Features

1.22 Silberschatz, Galvin and Gagne ©2002

 Computing Environments

● Traditional computing
● Web-Based Computing
● Embedded Computing

1.23 Silberschatz, Galvin and Gagne ©2002

 Chapter 2: Computer-System Structures

● Computer System Operation

● I/O Structure
● Storage Structure
● Storage Hierarchy
● Hardware Protection
● General System Architecture

2.1 Silberschatz, Galvin and Gagne ©2002

Computer-System Architecture

2.2 Silberschatz, Galvin and Gagne ©2002

 Computer-System Operation

● I/O devices and the CPU can execute concurrently.

● Each device controller is in charge of a particular device type.
● Each device controller has a local buffer.
● CPU moves data from/to main memory to/from local buffers
● I/O is from the device to local buffer of controller.
● Device controller informs CPU that it has finished its operation
by causing an interrupt.

2.3 Silberschatz, Galvin and Gagne ©2002

 Common Functions of Interrupts

● Interrupt transfers control to the interrupt service routine

generally, through the interrupt vector, which contains the
addresses of all the service routines.
● Interrupt architecture must save the address of the interrupted
instruction.
● Incoming interrupts are disabled while another interrupt is
being processed to prevent a lost interrupt.
● A trap is a software-generated interrupt caused either by an
error or a user request.
● An operating system is interrupt driven.

2.4 Silberschatz, Galvin and Gagne ©2002

 Interrupt Handling

● The operating system preserves the state of the CPU by storing

registers and the program counter.
● Determines which type of interrupt has occurred:
● polling
● vectored interrupt system
● Separate segments of code determine what action should be
taken for each type of interrupt

2.5 Silberschatz, Galvin and Gagne ©2002

Interrupt Time Line For a Single Process Doing Output

2.6 Silberschatz, Galvin and Gagne ©2002

 I/O Structure

● After I/O starts, control returns to user program only upon I/O
completion.
● Wait instruction idles the CPU until the next interrupt
● Wait loop (contention for memory access).
● At most one I/O request is outstanding at a time, no simultaneous
I/O processing.
● After I/O starts, control returns to user program without waiting
for I/O completion.
● System call – request to the operating system to allow user to wait
for I/O completion.
● Device-status table contains entry for each I/O device indicating
its type, address, and state.
● Operating system indexes into I/O device table to determine
device status and to modify table entry to include interrupt.

2.7 Silberschatz, Galvin and Gagne ©2002

 Two I/O Methods

Synchronous Asynchronous

2.8 Silberschatz, Galvin and Gagne ©2002

Device-Status Table

2.9 Silberschatz, Galvin and Gagne ©2002

 Direct Memory Access Structure

● Used for high-speed I/O devices able to transmit information at

close to memory speeds.
● Device controller transfers blocks of data from buffer storage
directly to main memory without CPU intervention.
● Only on interrupt is generated per block, rather than the one
interrupt per byte.

2.10 Silberschatz, Galvin and Gagne ©2002

 Storage Structure

● Main memory – only large storage media that the CPU can
access directly.
● Secondary storage – extension of main memory that provides
large nonvolatile storage capacity.
● Magnetic disks – rigid metal or glass platters covered with
magnetic recording material
● Disk surface is logically divided into tracks, which are subdivided
into sectors.
● The disk controller determines the logical interaction between the
device and the computer.

2.11 Silberschatz, Galvin and Gagne ©2002

Moving-Head Disk Mechanism

2.12 Silberschatz, Galvin and Gagne ©2002

 Storage Hierarchy

● Storage systems organized in hierarchy.

● Speed
● Cost
● Volatility
● Caching – copying information into faster storage system; main
memory can be viewed as a last cache for secondary storage.

2.13 Silberschatz, Galvin and Gagne ©2002

Storage-Device Hierarchy

2.14 Silberschatz, Galvin and Gagne ©2002

 Caching

● Use of high-speed memory to hold recently-accessed data.

● Requires a cache management policy.
● Caching introduces another level in storage hierarchy. This
requires data that is simultaneously stored in more than one
level to be consistent.

2.15 Silberschatz, Galvin and Gagne ©2002

Migration of A From Disk to Register

2.16 Silberschatz, Galvin and Gagne ©2002

 Hardware Protection

● Dual-Mode Operation
● I/O Protection
● Memory Protection
● CPU Protection

2.17 Silberschatz, Galvin and Gagne ©2002

 Dual-Mode Operation

● Sharing system resources requires operating system to ensure

that an incorrect program cannot cause other programs to
execute incorrectly.
● Provide hardware support to differentiate between at least two
modes of operations.
1. User mode – execution done on behalf of a user.
2. Monitor mode (also kernel mode or system mode) – execution
done on behalf of operating system.

2.18 Silberschatz, Galvin and Gagne ©2002

 Dual-Mode Operation (Cont.)

● Mode bit added to computer hardware to indicate the current

mode: monitor (0) or user (1).
● When an interrupt or fault occurs hardware switches to monitor
mode.
Interrupt/fault

monit
user
or
set user mode

Privileged instructions can be issued only in monitor mode.

2.19 Silberschatz, Galvin and Gagne ©2002

 I/O Protection

● All I/O instructions are privileged instructions.

● Must ensure that a user program could never gain control of the
computer in monitor mode (I.e., a user program that, as part of
its execution, stores a new address in the interrupt vector).

2.20 Silberschatz, Galvin and Gagne ©2002

Use of A System Call to Perform I/O

2.21 Silberschatz, Galvin and Gagne ©2002

 Memory Protection

● Must provide memory protection at least for the interrupt vector

and the interrupt service routines.
● In order to have memory protection, add two registers that
determine the range of legal addresses a program may access:
● Base register – holds the smallest legal physical memory address.
● Limit register – contains the size of the range
● Memory outside the defined range is protected.

2.22 Silberschatz, Galvin and Gagne ©2002

Use of A Base and Limit Register

2.23 Silberschatz, Galvin and Gagne ©2002

Hardware Address Protection

2.24 Silberschatz, Galvin and Gagne ©2002

 Hardware Protection

● When executing in monitor mode, the operating system has

unrestricted access to both monitor and user’s memory.
● The load instructions for the base and limit registers are
privileged instructions.

2.25 Silberschatz, Galvin and Gagne ©2002

 CPU Protection

● Timer – interrupts computer after specified period to ensure

operating system maintains control.
● Timer is decremented every clock tick.
● When timer reaches the value 0, an interrupt occurs.
● Timer commonly used to implement time sharing.
● Time also used to compute the current time.
● Load-timer is a privileged instruction.

2.26 Silberschatz, Galvin and Gagne ©2002

 Network Structure

● Local Area Networks (LAN)

● Wide Area Networks (WAN)

2.27 Silberschatz, Galvin and Gagne ©2002

Local Area Network Structure

2.28 Silberschatz, Galvin and Gagne ©2002

Wide Area Network Structure

2.29 Silberschatz, Galvin and Gagne ©2002

 Chapter 3: Operating-System Structures

● System Components
● Operating System Services
● System Calls
● System Programs
● System Structure
● Virtual Machines
● System Design and Implementation
● System Generation

3.1 Silberschatz, Galvin and Gagne ©2002

 Common System Components

● Process Management
● Main Memory Management
● File Management
● I/O System Management
● Secondary Management
● Networking
● Protection System
● Command-Interpreter System

3.2 Silberschatz, Galvin and Gagne ©2002

 Process Management

● A process is a program in execution. A process needs certain

resources, including CPU time, memory, files, and I/O devices,
to accomplish its task.
● The operating system is responsible for the following activities
in connection with process management.
● Process creation and deletion.
● process suspension and resumption.
● Provision of mechanisms for:
● process synchronization
● process communication

3.3 Silberschatz, Galvin and Gagne ©2002

 Main-Memory Management

● Memory is a large array of words or bytes, each with its own

address. It is a repository of quickly accessible data shared by
the CPU and I/O devices.
● Main memory is a volatile storage device. It loses its contents
in the case of system failure.
● The operating system is responsible for the following activities
in connections with memory management:
● Keep track of which parts of memory are currently being used and
by whom.
● Decide which processes to load when memory space becomes
available.
● Allocate and deallocate memory space as needed.

3.4 Silberschatz, Galvin and Gagne ©2002

 File Management

● A file is a collection of related information defined by its

creator. Commonly, files represent programs (both source and
object forms) and data.
● The operating system is responsible for the following activities
in connections with file management:
● File creation and deletion.
● Directory creation and deletion.
● Support of primitives for manipulating files and directories.
● Mapping files onto secondary storage.
● File backup on stable (nonvolatile) storage media.

3.5 Silberschatz, Galvin and Gagne ©2002

 I/O System Management

● The I/O system consists of:

● A buffer-caching system
● A general device-driver interface
● Drivers for specific hardware devices

3.6 Silberschatz, Galvin and Gagne ©2002

 Secondary-Storage Management

● Since main memory (primary storage) is volatile and too small

to accommodate all data and programs permanently, the
computer system must provide secondary storage to back up
main memory.
● Most modern computer systems use disks as the principle
on-line storage medium, for both programs and data.
● The operating system is responsible for the following activities
in connection with disk management:
● Free space management
● Storage allocation
● Disk scheduling

3.7 Silberschatz, Galvin and Gagne ©2002

 Networking (Distributed Systems)

● A distributed system is a collection processors that do not share

memory or a clock. Each processor has its own local memory.
● The processors in the system are connected through a
communication network.
● Communication takes place using a protocol.
● A distributed system provides user access to various system
resources.
● Access to a shared resource allows:
● Computation speed-up
● Increased data availability
● Enhanced reliability

3.8 Silberschatz, Galvin and Gagne ©2002

 Protection System

● Protection refers to a mechanism for controlling access by

programs, processes, or users to both system and user
resources.
● The protection mechanism must:
● distinguish between authorized and unauthorized usage.
● specify the controls to be imposed.
● provide a means of enforcement.

3.9 Silberschatz, Galvin and Gagne ©2002

 Command-Interpreter System

● Many commands are given to the operating system by control

statements which deal with:
● process creation and management
● I/O handling
● secondary-storage management
● main-memory management
● file-system access
● protection
● networking

3.10 Silberschatz, Galvin and Gagne ©2002

 Command-Interpreter System (Cont.)

● The program that reads and interprets control statements is

called variously:

● command-line interpreter
● shell (in UNIX)

Its function is to get and execute the next command statement.

3.11 Silberschatz, Galvin and Gagne ©2002

 Operating System Services

● Program execution – system capability to load a program into memory

and to run it.
● I/O operations – since user programs cannot execute I/O operations
directly, the operating system must provide some means to perform
I/O.
● File-system manipulation – program capability to read, write, create,
and delete files.
● Communications – exchange of information between processes
executing either on the same computer or on different systems tied
together by a network. Implemented via shared memory or message
passing.
● Error detection – ensure correct computing by detecting errors in the
CPU and memory hardware, in I/O devices, or in user programs.

3.12 Silberschatz, Galvin and Gagne ©2002

 Additional Operating System Functions

Additional functions exist not for helping the user, but rather for
ensuring efficient system operations.
● Resource allocation – allocating resources to multiple users or
multiple jobs running at the same time.
● Accounting – keep track of and record which users use how much
and what kinds of computer resources for account billing or for
accumulating usage statistics.
● Protection – ensuring that all access to system resources is
controlled.

3.13 Silberschatz, Galvin and Gagne ©2002

 System Calls

● System calls provide the interface between a running program

and the operating system.
● Generally available as assembly-language instructions.
● Languages defined to replace assembly language for systems
programming allow system calls to be made directly (e.g., C,
C++)
● Three general methods are used to pass parameters between a
running program and the operating system.
● Pass parameters in registers.
● Store the parameters in a table in memory, and the table address is
passed as a parameter in a register.
● Push (store) the parameters onto the stack by the program, and
pop off the stack by operating system.

3.14 Silberschatz, Galvin and Gagne ©2002

Passing of Parameters As A Table

3.15 Silberschatz, Galvin and Gagne ©2002

 Types of System Calls

● Process control
● File management
● Device management
● Information maintenance
● Communications

3.16 Silberschatz, Galvin and Gagne ©2002

 MS-DOS Execution

At System Start-up Running a Program

3.17 Silberschatz, Galvin and Gagne ©2002

UNIX Running Multiple Programs

3.18 Silberschatz, Galvin and Gagne ©2002

 Communication Models
● Communication may take place using either message passing or
shared memory.

Msg Passing Shared Memory

3.19 Silberschatz, Galvin and Gagne ©2002

 System Programs

● System programs provide a convenient environment for

program development and execution. The can be divided into:
● File manipulation
● Status information
● File modification
● Programming language support
● Program loading and execution
● Communications
● Application programs
● Most users’ view of the operation system is defined by system
programs, not the actual system calls.

3.20 Silberschatz, Galvin and Gagne ©2002

 MS-DOS System Structure

● MS-DOS – written to provide the most functionality in the least

space
● not divided into modules
● Although MS-DOS has some structure, its interfaces and levels of
functionality are not well separated

3.21 Silberschatz, Galvin and Gagne ©2002

MS-DOS Layer Structure

3.22 Silberschatz, Galvin and Gagne ©2002

 UNIX System Structure

● UNIX – limited by hardware functionality, the original UNIX

operating system had limited structuring. The UNIX OS
consists of two separable parts.
● Systems programs
● The kernel
● Consists of everything below the system-call interface and
above the physical hardware
● Provides the file system, CPU scheduling, memory
management, and other operating-system functions; a large
number of functions for one level.

3.23 Silberschatz, Galvin and Gagne ©2002

UNIX System Structure

3.24 Silberschatz, Galvin and Gagne ©2002

 Layered Approach

● The operating system is divided into a number of layers

(levels), each built on top of lower layers. The bottom layer
(layer 0), is the hardware; the highest (layer N) is the user
interface.
● With modularity, layers are selected such that each uses
functions (operations) and services of only lower-level layers.

3.25 Silberschatz, Galvin and Gagne ©2002

An Operating System Layer

3.26 Silberschatz, Galvin and Gagne ©2002

OS/2 Layer Structure

3.27 Silberschatz, Galvin and Gagne ©2002

 Microkernel System Structure

● Moves as much from the kernel into “user” space.

● Communication takes place between user modules using
message passing.
● Benefits:
- easier to extend a microkernel
- easier to port the operating system to new architectures
- more reliable (less code is running in kernel mode)
- more secure

3.28 Silberschatz, Galvin and Gagne ©2002

Windows NT Client-Server Structure

3.29 Silberschatz, Galvin and Gagne ©2002

 Virtual Machines

● A virtual machine takes the layered approach to its logical

conclusion. It treats hardware and the operating system kernel
as though they were all hardware.
● A virtual machine provides an interface identical to the
underlying bare hardware.
● The operating system creates the illusion of multiple processes,
each executing on its own processor with its own (virtual)
memory.

3.30 Silberschatz, Galvin and Gagne ©2002

 Virtual Machines (Cont.)

● The resources of the physical computer are shared to create the

virtual machines.
● CPU scheduling can create the appearance that users have their
own processor.
● Spooling and a file system can provide virtual card readers and
virtual line printers.
● A normal user time-sharing terminal serves as the virtual machine
operator’s console.

3.31 Silberschatz, Galvin and Gagne ©2002

 System Models

Non-virtual Machine Virtual Machine

3.32 Silberschatz, Galvin and Gagne ©2002

 Advantages/Disadvantages of Virtual Machines

● The virtual-machine concept provides complete protection of

system resources since each virtual machine is isolated from all
other virtual machines. This isolation, however, permits no
direct sharing of resources.
● A virtual-machine system is a perfect vehicle for
operating-systems research and development. System
development is done on the virtual machine, instead of on a
physical machine and so does not disrupt normal system
operation.
● The virtual machine concept is difficult to implement due to the
effort required to provide an exact duplicate to the underlying
machine.

3.33 Silberschatz, Galvin and Gagne ©2002

 Java Virtual Machine

● Compiled Java programs are platform-neutral bytecodes

executed by a Java Virtual Machine (JVM).
● JVM consists of
- class loader
- class verifier
- runtime interpreter
● Just-In-Time (JIT) compilers increase performance

3.34 Silberschatz, Galvin and Gagne ©2002

Java Virtual Machine

3.35 Silberschatz, Galvin and Gagne ©2002

 System Design Goals

● User goals – operating system should be convenient to use,

easy to learn, reliable, safe, and fast.
● System goals – operating system should be easy to design,
implement, and maintain, as well as flexible, reliable,
error-free, and efficient.

3.36 Silberschatz, Galvin and Gagne ©2002

 Mechanisms and Policies

● Mechanisms determine how to do something, policies decide

what will be done.
● The separation of policy from mechanism is a very important
principle, it allows maximum flexibility if policy decisions are
to be changed later.

3.37 Silberschatz, Galvin and Gagne ©2002

 System Implementation

● Traditionally written in assembly language, operating systems

can now be written in higher-level languages.
● Code written in a high-level language:
● can be written faster.
● is more compact.
● is easier to understand and debug.
● An operating system is far easier to port (move to some other
hardware) if it is written in a high-level language.

3.38 Silberschatz, Galvin and Gagne ©2002

 System Generation (SYSGEN)

● Operating systems are designed to run on any of a class of

machines; the system must be configured for each specific
computer site.
● SYSGEN program obtains information concerning the specific
configuration of the hardware system.
● Booting – starting a computer by loading the kernel.
● Bootstrap program – code stored in ROM that is able to locate
the kernel, load it into memory, and start its execution.

3.39 Silberschatz, Galvin and Gagne ©2002

 Chapter 4: Processes

● Process Concept
● Process Scheduling
● Operations on Processes
● Cooperating Processes
● Interprocess Communication
● Communication in Client-Server Systems

4.1 Silberschatz, Galvin and Gagne ©2002

 Process Concept

● An operating system executes a variety of programs:

● Batch system – jobs
● Time-shared systems – user programs or tasks
● Textbook uses the terms job and process almost
interchangeably.
● Process – a program in execution; process execution must
progress in sequential fashion.
● A process includes:
● program counter
● stack
● data section

4.2 Silberschatz, Galvin and Gagne ©2002

 Process State

● As a process executes, it changes state

● new: The process is being created.
● running: Instructions are being executed.
● waiting: The process is waiting for some event to occur.
● ready: The process is waiting to be assigned to a process.
● terminated: The process has finished execution.

4.3 Silberschatz, Galvin and Gagne ©2002

Diagram of Process State

4.4 Silberschatz, Galvin and Gagne ©2002

 Process Control Block (PCB)

Information associated with each process.

● Process state
● Program counter
● CPU registers
● CPU scheduling information
● Memory-management information
● Accounting information
● I/O status information

4.5 Silberschatz, Galvin and Gagne ©2002

Process Control Block (PCB)

4.6 Silberschatz, Galvin and Gagne ©2002

CPU Switch From Process to Process

4.7 Silberschatz, Galvin and Gagne ©2002

 Process Scheduling Queues

● Job queue – set of all processes in the system.

● Ready queue – set of all processes residing in main memory,
ready and waiting to execute.
● Device queues – set of processes waiting for an I/O device.
● Process migration between the various queues.

4.8 Silberschatz, Galvin and Gagne ©2002

Ready Queue And Various I/O Device Queues

4.9 Silberschatz, Galvin and Gagne ©2002

Representation of Process Scheduling

4.10 Silberschatz, Galvin and Gagne ©2002

 Schedulers

● Long-term scheduler (or job scheduler) – selects which

processes should be brought into the ready queue.
● Short-term scheduler (or CPU scheduler) – selects which
process should be executed next and allocates CPU.

4.11 Silberschatz, Galvin and Gagne ©2002

Addition of Medium Term Scheduling

4.12 Silberschatz, Galvin and Gagne ©2002

 Schedulers (Cont.)

● Short-term scheduler is invoked very frequently (milliseconds)

⇒ (must be fast).
● Long-term scheduler is invoked very infrequently (seconds,
minutes) ⇒ (may be slow).
● The long-term scheduler controls the degree of
multiprogramming.
● Processes can be described as either:
● I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts.
● CPU-bound process – spends more time doing computations; few
very long CPU bursts.

4.13 Silberschatz, Galvin and Gagne ©2002

 Context Switch

● When CPU switches to another process, the system must save

the state of the old process and load the saved state for the new
process.
● Context-switch time is overhead; the system does no useful
work while switching.
● Time dependent on hardware support.

4.14 Silberschatz, Galvin and Gagne ©2002

 Process Creation

● Parent process create children processes, which, in turn create

other processes, forming a tree of processes.
● Resource sharing
● Parent and children share all resources.
● Children share subset of parent’s resources.
● Parent and child share no resources.
● Execution
● Parent and children execute concurrently.
● Parent waits until children terminate.

4.15 Silberschatz, Galvin and Gagne ©2002

 Process Creation (Cont.)

● Address space
● Child duplicate of parent.
● Child has a program loaded into it.
● UNIX examples
● fork system call creates new process
● exec system call used after a fork to replace the process’ memory
space with a new program.

4.16 Silberschatz, Galvin and Gagne ©2002

Processes Tree on a UNIX System

4.17 Silberschatz, Galvin and Gagne ©2002

 Process Termination

● Process executes last statement and asks the operating system

to decide it (exit).
● Output data from child to parent (via wait).
● Process’ resources are deallocated by operating system.
● Parent may terminate execution of children processes (abort).
● Child has exceeded allocated resources.
● Task assigned to child is no longer required.
● Parent is exiting.
● Operating system does not allow child to continue if its parent
terminates.
● Cascading termination.

4.18 Silberschatz, Galvin and Gagne ©2002

 Cooperating Processes

● Independent process cannot affect or be affected by the

execution of another process.
● Cooperating process can affect or be affected by the execution
of another process
● Advantages of process cooperation
● Information sharing
● Computation speed-up
● Modularity
● Convenience

4.19 Silberschatz, Galvin and Gagne ©2002

 Producer-Consumer Problem

● Paradigm for cooperating processes, producer process produces

information that is consumed by a consumer process.
● unbounded-buffer places no practical limit on the size of the
buffer.
● bounded-buffer assumes that there is a fixed buffer size.

4.20 Silberschatz, Galvin and Gagne ©2002

 Bounded-Buffer – Shared-Memory Solution
● Shared data
#define BUFFER_SIZE 10
Typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
● Solution is correct, but can only use BUFFER_SIZE-1 elements

4.21 Silberschatz, Galvin and Gagne ©2002

 Bounded-Buffer – Producer Process

item nextProduced;

while (1) {
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}

4.22 Silberschatz, Galvin and Gagne ©2002

 Bounded-Buffer – Consumer Process

item nextConsumed;

while (1) {
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}

4.23 Silberschatz, Galvin and Gagne ©2002

 Interprocess Communication (IPC)

● Mechanism for processes to communicate and to synchronize

their actions.
● Message system – processes communicate with each other
without resorting to shared variables.
● IPC facility provides two operations:
● send(message) – message size fixed or variable
● receive(message)
● If P and Q wish to communicate, they need to:
● establish a communication link between them
● exchange messages via send/receive
● Implementation of communication link
● physical (e.g., shared memory, hardware bus)
● logical (e.g., logical properties)

4.24 Silberschatz, Galvin and Gagne ©2002

 Implementation Questions

● How are links established?

● Can a link be associated with more than two processes?
● How many links can there be between every pair of
communicating processes?
● What is the capacity of a link?
● Is the size of a message that the link can accommodate fixed or
variable?
● Is a link unidirectional or bi-directional?

4.25 Silberschatz, Galvin and Gagne ©2002

 Direct Communication

● Processes must name each other explicitly:

● send (P, message) – send a message to process P
● receive(Q, message) – receive a message from process Q
● Properties of communication link
● Links are established automatically.
● A link is associated with exactly one pair of communicating
processes.
● Between each pair there exists exactly one link.
● The link may be unidirectional, but is usually bi-directional.

4.26 Silberschatz, Galvin and Gagne ©2002

 Indirect Communication
● Messages are directed and received from mailboxes (also
referred to as ports).
● Each mailbox has a unique id.
● Processes can communicate only if they share a mailbox.
● Properties of communication link
● Link established only if processes share a common mailbox
● A link may be associated with many processes.
● Each pair of processes may share several communication links.
● Link may be unidirectional or bi-directional.

4.27 Silberschatz, Galvin and Gagne ©2002

 Indirect Communication

● Operations
● create a new mailbox
● send and receive messages through mailbox
● destroy a mailbox
● Primitives are defined as:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A

4.28 Silberschatz, Galvin and Gagne ©2002

 Indirect Communication

● Mailbox sharing
● P1, P2, and P3 share mailbox A.
● P1, sends; P2 and P3 receive.
● Who gets the message?
● Solutions
● Allow a link to be associated with at most two processes.
● Allow only one process at a time to execute a receive operation.
● Allow the system to select arbitrarily the receiver. Sender is
notified who the receiver was.

4.29 Silberschatz, Galvin and Gagne ©2002

 Synchronization

● Message passing may be either blocking or non-blocking.

● Blocking is considered synchronous
● Non-blocking is considered asynchronous
● send and receive primitives may be either blocking or
non-blocking.

4.30 Silberschatz, Galvin and Gagne ©2002

 Buffering

● Queue of messages attached to the link; implemented in one of

three ways.
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous).
2. Bounded capacity – finite length of n messages
Sender must wait if link full.
3. Unbounded capacity – infinite length
Sender never waits.

4.31 Silberschatz, Galvin and Gagne ©2002

 Client-Server Communication

● Sockets
● Remote Procedure Calls
● Remote Method Invocation (Java)

4.32 Silberschatz, Galvin and Gagne ©2002

 Sockets

● A socket is defined as an endpoint for communication.

● Concatenation of IP address and port
● The socket [Link]:1625 refers to port 1625 on host
[Link]
● Communication consists between a pair of sockets.

4.33 Silberschatz, Galvin and Gagne ©2002

Socket Communication

4.34 Silberschatz, Galvin and Gagne ©2002

 Remote Procedure Calls

● Remote procedure call (RPC) abstracts procedure calls between

processes on networked systems.
● Stubs – client-side proxy for the actual procedure on the server.
● The client-side stub locates the server and marshalls the
parameters.
● The server-side stub receives this message, unpacks the
marshalled parameters, and peforms the procedure on the
server.

4.35 Silberschatz, Galvin and Gagne ©2002

Execution of RPC

4.36 Silberschatz, Galvin and Gagne ©2002

 Remote Method Invocation

● Remote Method Invocation (RMI) is a Java mechanism similar

to RPCs.
● RMI allows a Java program on one machine to invoke a method
on a remote object.

4.37 Silberschatz, Galvin and Gagne ©2002

Marshalling Parameters

4.38 Silberschatz, Galvin and Gagne ©2002

 Chapter 5: Threads

● Overview
● Multithreading Models
● Threading Issues
● Pthreads
● Solaris 2 Threads
● Windows 2000 Threads
● Linux Threads
● Java Threads

5.1 Silberschatz, Galvin and Gagne ©2002

Single and Multithreaded Processes

5.2 Silberschatz, Galvin and Gagne ©2002

 Benefits

● Responsiveness

● Resource Sharing

● Economy

● Utilization of MP Architectures

5.3 Silberschatz, Galvin and Gagne ©2002

 User Threads

● Thread management done by user-level threads library

● Examples
- POSIX Pthreads
- Mach C-threads
- Solaris threads

5.4 Silberschatz, Galvin and Gagne ©2002

 Kernel Threads

● Supported by the Kernel

● Examples
- Windows 95/98/NT/2000
- Solaris
- Tru64 UNIX
- BeOS
- Linux

5.5 Silberschatz, Galvin and Gagne ©2002

 Multithreading Models

● Many-to-One

● One-to-One

● Many-to-Many

5.6 Silberschatz, Galvin and Gagne ©2002

 Many-to-One

● Many user-level threads mapped to single kernel thread.

● Used on systems that do not support kernel threads.

5.7 Silberschatz, Galvin and Gagne ©2002

Many-to-One Model

5.8 Silberschatz, Galvin and Gagne ©2002

 One-to-One

● Each user-level thread maps to kernel thread.

● Examples
- Windows 95/98/NT/2000
- OS/2

5.9 Silberschatz, Galvin and Gagne ©2002

One-to-one Model

5.10 Silberschatz, Galvin and Gagne ©2002

 Many-to-Many Model

● Allows many user level threads to be mapped to many kernel

threads.
● Allows the operating system to create a sufficient number of
kernel threads.
● Solaris 2
● Windows NT/2000 with the ThreadFiber package

5.11 Silberschatz, Galvin and Gagne ©2002

Many-to-Many Model

5.12 Silberschatz, Galvin and Gagne ©2002

 Threading Issues

● Semantics of fork() and exec() system calls.

● Thread cancellation.
● Signal handling
● Thread pools
● Thread specific data

5.13 Silberschatz, Galvin and Gagne ©2002

 Pthreads

● a POSIX standard (IEEE 1003.1c) API for thread creation and

synchronization.
● API specifies behavior of the thread library, implementation is
up to development of the library.
● Common in UNIX operating systems.

5.14 Silberschatz, Galvin and Gagne ©2002

Solaris 2 Threads

5.15 Silberschatz, Galvin and Gagne ©2002

Solaris Process

5.16 Silberschatz, Galvin and Gagne ©2002

 Windows 2000 Threads

● Implements the one-to-one mapping.

● Each thread contains
- a thread id
- register set
- separate user and kernel stacks
- private data storage area

5.17 Silberschatz, Galvin and Gagne ©2002

 Linux Threads

● Linux refers to them as tasks rather than threads.

● Thread creation is done through clone() system call.
● Clone() allows a child task to share the address space of the
parent task (process)

5.18 Silberschatz, Galvin and Gagne ©2002

 Java Threads

● Java threads may be created by:

● Extending Thread class

● Implementing the Runnable interface

● Java threads are managed by the JVM.

5.19 Silberschatz, Galvin and Gagne ©2002

Java Thread States

5.20 Silberschatz, Galvin and Gagne ©2002

 Chapter 6: CPU Scheduling

● Basic Concepts
● Scheduling Criteria
● Scheduling Algorithms
● Multiple-Processor Scheduling
● Real-Time Scheduling
● Algorithm Evaluation

6.1 Silberschatz, Galvin and Gagne ©2002

 Basic Concepts

● Maximum CPU utilization obtained with multiprogramming

● CPU–I/O Burst Cycle – Process execution consists of a cycle of
CPU execution and I/O wait.
● CPU burst distribution

6.2 Silberschatz, Galvin and Gagne ©2002

Alternating Sequence of CPU And I/O Bursts

6.3 Silberschatz, Galvin and Gagne ©2002

Histogram of CPU-burst Times

6.4 Silberschatz, Galvin and Gagne ©2002

 CPU Scheduler

● Selects from among the processes in memory that are ready to

execute, and allocates the CPU to one of them.
● CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state.
2. Switches from running to ready state.
3. Switches from waiting to ready.
4. Terminates.
● Scheduling under 1 and 4 is nonpreemptive.
● All other scheduling is preemptive.

6.5 Silberschatz, Galvin and Gagne ©2002

 Dispatcher

● Dispatcher module gives control of the CPU to the process

selected by the short-term scheduler; this involves:
● switching context
● switching to user mode
● jumping to the proper location in the user program to restart that
program
● Dispatch latency – time it takes for the dispatcher to stop one
process and start another running.

6.6 Silberschatz, Galvin and Gagne ©2002

 Scheduling Criteria

● CPU utilization – keep the CPU as busy as possible

● Throughput – # of processes that complete their execution per
time unit
● Turnaround time – amount of time to execute a particular
process
● Waiting time – amount of time a process has been waiting in
the ready queue
● Response time – amount of time it takes from when a request
was submitted until the first response is produced, not output
(for time-sharing environment)

6.7 Silberschatz, Galvin and Gagne ©2002

 Optimization Criteria

● Max CPU utilization

● Max throughput
● Min turnaround time
● Min waiting time
● Min response time

6.8 Silberschatz, Galvin and Gagne ©2002

 First-Come, First-Served (FCFS) Scheduling

Process Burst Time

P1 24
P2 3
P3 3
● Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1 P2 P3

0 24 27 30

● Waiting time for P1 = 0; P2 = 24; P3 = 27

● Average waiting time: (0 + 24 + 27)/3 = 17

6.9 Silberschatz, Galvin and Gagne ©2002

 FCFS Scheduling (Cont.)

Suppose that the processes arrive in the order

P2 , P3 , P1 .
● The Gantt chart for the schedule is:

P2 P3 P1

0 3 6 30
● Waiting time for P1 = 6; P2 = 0; P3 = 3
● Average waiting time: (6 + 0 + 3)/3 = 3
● Much better than previous case.
● Convoy effect short process behind long process

6.10 Silberschatz, Galvin and Gagne ©2002

 Shortest-Job-First (SJR) Scheduling

● Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest time.
● Two schemes:
● nonpreemptive – once CPU given to the process it cannot be
preempted until completes its CPU burst.
● preemptive – if a new process arrives with CPU burst length less
than remaining time of current executing process, preempt. This
scheme is know as the
Shortest-Remaining-Time-First (SRTF).
● SJF is optimal – gives minimum average waiting time for a
given set of processes.

6.11 Silberschatz, Galvin and Gagne ©2002

 Example of Non-Preemptive SJF

Process Arrival Time Burst Time

P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
● SJF (non-preemptive)

P1 P3 P2 P4

0 3 7 8 12 16

● Average waiting time = (0 + 6 + 3 + 7)/4 - 4

6.12 Silberschatz, Galvin and Gagne ©2002

 Example of Preemptive SJF

Process Arrival Time Burst Time

P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
● SJF (preemptive)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16
● Average waiting time = (9 + 1 + 0 +2)/4 - 3

6.13 Silberschatz, Galvin and Gagne ©2002

 Determining Length of Next CPU Burst

● Can only estimate the length.

● Can be done by using the length of previous CPU bursts, using
exponential averaging.

6.14 Silberschatz, Galvin and Gagne ©2002

Prediction of the Length of the Next CPU Burst

6.15 Silberschatz, Galvin and Gagne ©2002

 Examples of Exponential Averaging

● α =0
● τn+1 = τn
● Recent history does not count.
● α =1
● τn+1 = tn
● Only the actual last CPU burst counts.
● If we expand the formula, we get:
τn+1 = α tn+(1 - α) α tn -1 + …
+(1 - α )j α tn -1 + …
+(1 - α )n=1 tn τ0
● Since both α and (1 - α) are less than or equal to 1, each
successive term has less weight than its predecessor.

6.16 Silberschatz, Galvin and Gagne ©2002

 Priority Scheduling

● A priority number (integer) is associated with each process

● The CPU is allocated to the process with the highest priority
(smallest integer ≡ highest priority).
● Preemptive
● nonpreemptive
● SJF is a priority scheduling where priority is the predicted next
CPU burst time.
● Problem ≡ Starvation – low priority processes may never
execute.
● Solution ≡ Aging – as time progresses increase the priority of
the process.

6.17 Silberschatz, Galvin and Gagne ©2002

 Round Robin (RR)

● Each process gets a small unit of CPU time (time quantum),

usually 10-100 milliseconds. After this time has elapsed, the
process is preempted and added to the end of the ready queue.
● If there are n processes in the ready queue and the time
quantum is q, then each process gets 1/n of the CPU time in
chunks of at most q time units at once. No process waits more
than (n-1)q time units.
● Performance
● q large ⇒ FIFO
● q small ⇒ q must be large with respect to context switch,
otherwise overhead is too high.

6.18 Silberschatz, Galvin and Gagne ©2002

 Example of RR with Time Quantum = 20

Process Burst Time

P1 53
P2 17
P3 68
P4 24
● The Gantt chart is:

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

● Typically, higher average turnaround than SJF, but better

response.

6.19 Silberschatz, Galvin and Gagne ©2002

Time Quantum and Context Switch Time

6.20 Silberschatz, Galvin and Gagne ©2002

Turnaround Time Varies With The Time Quantum

6.21 Silberschatz, Galvin and Gagne ©2002

 Multilevel Queue

● Ready queue is partitioned into separate queues:

foreground (interactive)
background (batch)
● Each queue has its own scheduling algorithm,
foreground – RR
background – FCFS
● Scheduling must be done between the queues.
● Fixed priority scheduling; (i.e., serve all from foreground then
from background). Possibility of starvation.
● Time slice – each queue gets a certain amount of CPU time which
it can schedule amongst its processes; i.e., 80% to foreground in
RR
● 20% to background in FCFS

6.22 Silberschatz, Galvin and Gagne ©2002

Multilevel Queue Scheduling

6.23 Silberschatz, Galvin and Gagne ©2002

 Multilevel Feedback Queue

● A process can move between the various queues; aging can be

implemented this way.
● Multilevel-feedback-queue scheduler defined by the following
parameters:
● number of queues
● scheduling algorithms for each queue
● method used to determine when to upgrade a process
● method used to determine when to demote a process
● method used to determine which queue a process will enter when
that process needs service

6.24 Silberschatz, Galvin and Gagne ©2002

 Example of Multilevel Feedback Queue

● Three queues:
● Q0 – time quantum 8 milliseconds
● Q1 – time quantum 16 milliseconds
● Q2 – FCFS
● Scheduling
● A new job enters queue Q0 which is served FCFS. When it gains
CPU, job receives 8 milliseconds. If it does not finish in 8
milliseconds, job is moved to queue Q1.
● At Q1 job is again served FCFS and receives 16 additional
milliseconds. If it still does not complete, it is preempted and
moved to queue Q2.

6.25 Silberschatz, Galvin and Gagne ©2002

Multilevel Feedback Queues

6.26 Silberschatz, Galvin and Gagne ©2002

 Multiple-Processor Scheduling

● CPU scheduling more complex when multiple CPUs are

available.
● Homogeneous processors within a multiprocessor.
● Load sharing
● Asymmetric multiprocessing – only one processor accesses the
system data structures, alleviating the need for data sharing.

6.27 Silberschatz, Galvin and Gagne ©2002

 Real-Time Scheduling

● Hard real-time systems – required to complete a critical task

within a guaranteed amount of time.
● Soft real-time computing – requires that critical processes
receive priority over less fortunate ones.

6.28 Silberschatz, Galvin and Gagne ©2002

Dispatch Latency

6.29 Silberschatz, Galvin and Gagne ©2002

 Algorithm Evaluation

● Deterministic modeling – takes a particular predetermined

workload and defines the performance of each algorithm for
that workload.
● Queueing models
● Implementation

6.30 Silberschatz, Galvin and Gagne ©2002

Evaluation of CPU Schedulers by Simulation

6.31 Silberschatz, Galvin and Gagne ©2002

Solaris 2 Scheduling

6.32 Silberschatz, Galvin and Gagne ©2002

Windows 2000 Priorities

6.33 Silberschatz, Galvin and Gagne ©2002