OPERATING SYSTEMS

(18CS43)
 Acknowledgment

The contents used in this presentation are

courtesy of textbook “Abraham Silberschatz,
Peter Baer Galvin, Greg Gagne, Operating
System Principles 7th edition, Wiley-India,
2006”
 Syllabus- Module 1
Introduction to operating systems, System structures: What
operating systems do;Computer System organization; Computer
System architecture; Operating System structure; Operating System
operations; Process management; Memory management; Storage
management; Protection and Security; Distributed system; Special-
purpose systems; Computing environments.

Operating System Services; User - Operating System interface;

System calls; Types of system calls; System programs; Operating system
design and implementation; Operating System structure; Virtual
machines; Operating System generation; System boot.

Process Management Process concept; Process scheduling;

Operations on processes; Inter process communication
Course outcomes: The students should be
able to:

 Demonstrate need for OS and different types of OS

 Discuss suitable techniques for management of
different resources
 Illustrate processor, memory, storage and file system
commands
 Explain the different concepts of OS in platform of
usage through case studies
 Text Books:
1. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne,
Operating System Principles 7th edition, Wiley-India, 2006.

Reference Books
1. Ann McHoes Ida M Fylnn, Understanding Operating System, Cengage Learning,
6th
Edition
2. D.M Dhamdhere, Operating Systems: A Concept Based Approach 3rd Ed,
McGraw-
Hill, 2013.
3. P.C.P. Bhatt, An Introduction to Operating Systems: Concepts and Practice 4th
Edition,
PHI(EEE), 2014.
4. William Stallings Operating Systems: Internals and Design Principles, 6th Edition,
Pearson.
Chapter 1: Introduction
 Chapter 1: Introduction
 1.1 What Operating Systems Do
 1.2 Computer-System Organization
 1.3 Computer-System Architecture
 1.4 Operating-System Structure
 1.5 Operating-System Operations
 1.6 Process Management
 1.7 Memory Management
 1.8 Storage Management
 1.9 Protection and Security
 1.10 Distributed system
 1.11 Special-purpose systems
 1.12 Computing Environments
 Objectives

 To describe the basic organization of computer

systems

 To provide a grand tour of the major components of

operating systems

 To give an overview of the many types of computing

environments

 To explore several open-source operating systems

 What is an Operating System?

 An operating system is a program that manages a

computer’s hardware

 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.1 What OS do?

 A computer system can be divided roughly into four

components:

o The hardware,
o The operating system,
o The application programs,
o The users
Four Components of a Computer System
 Computer System Structure
 Computer system can be divided into four components:
 Hardware – provides basic computing resources
CPU, memory, I/O devices
 Application programs – define the ways in which the
system resources are used to solve the computing
problems of the users
Word processors, compilers, web browsers, database
systems, video games
 Operating system
Controls and coordinates use of hardware among
various applications and users
 Users
People, machines, other computers
 1.1.2 What Operating Systems Do
 Depends on the point of view
 Users View
 Users want convenience, ease of use and good performance
 Don’t care about resource utilization
 But shared computer such as mainframe or minicomputer
must keep all users happy
 Users of dedicate systems such as workstations have
dedicated resources but frequently use shared resources from
servers
 Handheld computers are resource poor, optimized for usability
and battery life
 Some computers have little or no user interface, such as
embedded computers in devices and automobiles
System View

 OS is a resource allocator

 Manages all resources

 CPU time, memory space, file-storage space, I/O devices, and
so on
 Decides between conflicting requests for efficient and fair
resource use

 OS is a control program

 Controls execution of programs to prevent errors and

improper use of the computer
 1.2 Computer System Organization
 1.2.1 Computer-system operation
 One or more CPUs, device controllers connect through common bus
providing access to shared memory
 Concurrent execution of CPUs and devices competing for memory
cycles
 To ensure orderly access to the shared memory, a memory controller
synchronizes access to the memory
 Computer Startup
 bootstrap program is loaded at power-up or reboot
 Typically stored in ROM or EPROM, generally known as
firmware
 Initializes all aspects of system- from CPU registers to device
controllers to memory contents
 Loads operating system kernel and starts execution

 Once the kernel is loaded and executing, it can start providing

services to the system and its users.

 Some services are provided outside of the kernel, by system

programs that are loaded into memory at boot time to become
system processes, or system daemons that run the entire
time the kernel is running.
 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
 The occurrence of an event is usually signaled by an
interrupt from either the hardware or the software
 Hardware – through signals
 Software –system call
 When the CPU is interrupted, it stops what it is doing

 Immediately transfers execution to a fixed location.

 The fixed location usually contains the starting address

where the service routine for the interrupt is located.

 The interrupt service routine executes; on completion, the

CPU resumes the interrupted computation
• Each computer design has its own interrupt mechanism, but several
functions are common
• The interrupt must transfer control to the appropriate interrupt service
routine
• The straightforward method for handling this transfer would be to
invoke a generic routine to examine the interrupt information

• The routine, in turn, would call the interrupt-specific handler

However, interrupts must be handled quickly.

• Since only a predefined number of interrupts is possible, a table of

pointers to interrupt routines can be used instead to provide the
necessary speed– interrupt vector

• The interrupt routine is called indirectly through the table, with no

intermediate routine needed
 1.2.2 Storage Structure
• The CPU can load instructions only from memory

• Any programs to run must be stored there

• General-purpose computers run most of their programs from

rewritable memory, called main memory (also called random-access
memory, or RAM).

• Main memory commonly is implemented in a semiconductor

technology called dynamic random-access memory (DRAM) (has
array of memory words)

Load and store instructions(main memory to register-load , register to

memory- store)

Instruction-execution cycle
 Storage Structure
 Main memory –
 Main memory is usually too small to store all needed
programs and data permanently.
 Typically volatile
 Secondary storage – extension of main memory that provides
large nonvolatile storage capacity
 Hard 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
 Solid-state disks – faster than hard disks, nonvolatile
 Storage Hierarchy

 Storage systems organized in hierarchy

 Speed
 Cost
 Volatility
Storage-Device Hierarchy
 1.2.3 I/O structure
 CPUs and multiple device controllers

 Device controller is in charge of specific type of device

 Device controller has local buffer and a set of special purpose

registers

 Data moves from device to local buffer

 OS has device drivers for each device controller

 Device drivers understands device controller

 To start an I/O operation,
 Device driver loads the appropriate registers within the device
controller
 Device controller checks the content of the registers to
determine what action to take
 Controller starts the data movement between device and local
buffer
 On completion controller informs the driver through an interrupt
 Driver returns the control to OS

 Interrupt driven I/O

 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 one interrupt is generated per block, rather than the one
interrupt per byte
How a Modern Computer Works

A von Neumann architecture

 1.3 Computer-System Architecture

 Single processor systems

 Multiprocessor systems

 Clustered systems
 1.3.1 Single-Processor Systems
 On a single processor system, there is one main CPU capable
of executing a general-purpose instruction set, including
instructions from user processes
 Almost all single processor systems have other special-
purpose processors as well such as disk, keyboard and so on
 All of these special-purpose processors run a limited
instruction set and do not run user processes
 Sometimes, they are managed by the operating system
 For example, a disk-controller microprocessor receives a
sequence of requests from the main CPU and implements its
own disk queue and scheduling algorithm. This arrangement
relieves the main CPU of the overhead of disk scheduling
 PCs contain a microprocessor in the keyboard to convert the
keystrokes into codes to be sent to the CPU
 1.3.2 Multiprocessor systems
 Multiprocessors systems growing in use and importance
 Also known as parallel systems, tightly-coupled
systems
 Advantages include:
1. Increased throughput
2. Economy of scale
3. Increased reliability – graceful degradation or fault
tolerance
 Two types:
1. Asymmetric Multiprocessing – each processor is
assigned a specie task.
2. Symmetric Multiprocessing – each processor
performs all tasks
Symmetric Multiprocessing Architecture
 A Dual-Core Design
 Multi-chip and multicore
 Systems containing all chips
 Chassis containing multiple separate systems
 1.3.3 Clustered Systems
 Like multiprocessor systems, but multiple systems working
together
 Usually sharing storage via a storage-area network (SAN)
 Provides a high-availability service which survives failures
Asymmetric clustering has one machine in hot-standby
mode
Symmetric clustering has multiple nodes running
applications, monitoring each other
 Some clusters are for high-performance computing (HPC)
Applications must be written to use parallelization
 Some have distributed lock manager (DLM) to avoid
conflicting operations
Clustered Systems
 1.4 Operating System Structure

 Multiprogramming (Batch system) needed for

efficiency
 Single user cannot keep CPU and I/O devices busy at all
times
 Multiprogramming organizes jobs (code and data) so CPU
always has one to execute
 A subset of total jobs in system is kept in memory

 One job selected and run via job scheduling

 When it has to wait (for I/O for example), OS switches to
another job
Memory Layout for Multiprogrammed System
Operating System Structure

 Timesharing (multitasking) is logical extension in which

CPU switches jobs so frequently that users can interact with
each job while it is running, creating interactive computing
 Response time should be < 1 second
 Each user has at least one program executing in memory
process
 If several jobs ready to run at the same time  CPU
scheduling
 If processes don’t fit in memory, swapping moves them
in and out to run
 Virtual memory allows execution of processes not
completely in memory
 1.5 Operating-System Operations
 Interrupt driven (hardware and software)
 Hardware interrupt by one of the devices
 Software interrupt (exception or trap):
 Software error (e.g., division by zero)

 Request for operating system service

 Other process problems include infinite loop, processes modifying

each other or the operating system
 Since the operating system and the users share the hardware and
software resources of the computer system, we need to make sure that
an error in a user program could cause problems only for the one
program running
 Without protection against these sorts of errors, either the computer
must execute only one process at a time or all output must be suspect.
 A properly designed operating system must ensure that an incorrect (or
malicious) program cannot cause other programs to execute incorrectly.
 Operating-System Operations (cont.)
 1.5.1 Dual-mode operation allows OS to protect itself and other
system components
 User mode (1) and kernel mode (0)
 Mode bit provided by hardware
Provides ability to distinguish when system is running user
code or kernel code
Some instructions designated as privileged, only
executable in kernel mode
System call changes mode to kernel, return from call
resets it to user
 Increasingly CPUs support multi-mode operations
 i.e. virtual machine manager (VMM) mode for guest VMs
Transition from User to Kernel Mode
 1.5.2 Timer
 OS should have control over CPU
 Cannot allow a user program to get stuck
 A timer can be set to interrupt the computer after a specified
period
 Period can be fixed or variable
 The operating system sets the counter.
 Every time the clock ticks, the counter is decremented.
 When the counter reaches 0, an interrupt occurs
 1.6 Process Management

 A process is a program in execution. It is a unit of work within

the system. Program is a passive entity, process is an active
entity.
 Process needs resources to accomplish its task
 CPU, memory, I/O, files
 Initialization data
 Process termination requires reclaim of any reusable resources
 Single-threaded process has one program counter specifying
location of next instruction to execute
 Process executes instructions sequentially, one at a time,
until completion
 Multi-threaded process has one program counter per thread
 Process Management Activities
The operating system is responsible for the following activities in
connection with process management:

 Creating and deleting both user and system processes

 Scheduling processes and threads on the CPUs
 Providing mechanisms for process synchronization
 Providing mechanisms for process communication
 Providing mechanisms for deadlock handling
 1.7 Memory Management
 To execute a program all (or part) of the instructions must be in
memory
 All (or part) of the data that is needed by the program must be
in memory.
 Memory management determines what is in memory and when
 Optimizing CPU utilization and computer response to users
 Memory management activities
 Keeping track of which parts of memory are currently being
used and by whom
 Deciding which processes (or parts thereof) and data to
move into and out of memory
 Allocating and deallocating memory space as needed
 1.8 Storage Management
 OS provides uniform, logical view of information storage
 Abstracts physical properties to logical storage unit - file
 Each medium is controlled by device (i.e., disk drive, tape drive)
 Varying properties include access speed, capacity, data-transfer rate,
access method (sequential or random)

 1.8.1 File-System management

 Files usually organized into directories
 Access control on most systems to determine who can access what
 OS activities include
 Creating and deleting files and directories

 Primitives to manipulate files and directories

 Mapping files onto secondary storage

 Backup files onto stable (non-volatile) storage media

 1.8.2 Mass-Storage Management
 Usually disks used to store data that does not fit in main memory or data that
must be kept for a “long” period of time
 Proper management is of central importance
 Entire speed of computer operation hinges on disk subsystem and its
algorithms
 OS activities
 Free-space management
 Storage allocation
 Disk scheduling
 Some storage need not be fast
 Tertiary storage includes optical storage, magnetic tape
 Still must be managed – by OS or applications
 Varies between WORM (write-once, read-many-times) and RW (read-
write)
 1.8.3 Caching

 Cache management
 Cache size
 Replacement policy
 Performance of Various Levels of Storage

Movement between levels of storage hierarchy can be explicit or implicit

 Migration of data “A” from Disk to Register

 Multitasking environments must be careful to use most recent

value, no matter where it is stored in the storage hierarchy

 Multiprocessor environment must provide cache coherency in

hardware such that all CPUs have the most recent value in their
cache
 Distributed environment situation even more complex
 Several copies of a datum can exist
 1.8.4 I/O Systems
 One of purposes of OS is to hide the peculiarities of
specific hardware devices from the user.

 I/O subsystem components:

 Memory management componets:-buffering,caching and
spooling
 General device-driver interface
 Drivers for specific h/w devices

 Only device driver knows the peculiarities of the specific

device to which it is assigned
 1.9 Protection and Security
 Protection – any mechanism for controlling access of processes or users
to resources defined by the OS

 Security – defense of the system against internal and external attacks

 Huge range, including denial-of-service, worms, viruses, identity theft,
theft of service

 Systems generally first distinguish among users, to determine who can do

what
 User identities (user IDs, security IDs) include name and associated
number, one per user
 User ID then associated with all files, processes of that user to
determine access control
 Group identifier (group ID) allows set of users to be defined and
controls managed, then also associated with each process, file
 Privilege escalation allows user to change to effective ID with more
rights
 1.10 Distributed Systems
 Distributed computing
 Collection of separate, possibly heterogeneous, systems
networked together
Network is a communications path, TCP/IP most
common - Local Area Network (LAN)
- Wide Area Network (WAN)
- Metropolitan Area Network (MAN)
- Personal Area Network (PAN)
 Network Operating System provides features between
systems across network
Communication scheme allows systems to exchange
messages
Illusion of a single system
 1.11 Special-Purpose Systems
1.11.1 Real-Time Embedded Systems
 Real-time embedded systems most prevalent form of
computers
 Vary considerable, special purpose, limited purpose OS,
real-time OS
 Use expanding

 Many other special computing environments as well

 Some have OSes, some perform tasks without an OS

 Real-time OS has well-defined fixed time constraints

 Processing must be done within constraint
 Correct operation only if constraints met
1.11.2 Multimedia systems
 Audio and video

1.11.3 Handheld systems

 PDA, cellphones etc
 1.12 Computing Environments - Traditional
1.12.1 Computing Environments - Traditional
 Stand-alone general purpose machines
 But blurred as most systems interconnect with others (i.e., the
Internet)
 Portals provide web access to internal systems
 Network computers (thin clients) are like Web terminals
 Mobile computers interconnect via wireless networks
 Networking becoming ubiquitous – even home systems use
firewalls to protect home computers from Internet attacks
 1.12.2 Computing Environments – Client-Server
 Client-Server Computing
 Dumb terminals supplanted by smart PCs
 Many systems now servers, responding to requests
generated by clients
Compute-server system provides an interface to client to
request services (i.e., database)
File-server system provides interface for clients to store
and retrieve files
 1.12.3 Computing Environments - Peer-to-Peer
 Another model of distributed system
 P2P does not distinguish clients and servers
 Instead all nodes are considered peers
 May each act as client, server or both
 Node must join P2P network
Registers its service with central lookup service on
network, or
Broadcast request for service and respond to requests
for service via discovery protocol
 Examples include Napster and Gnutella, Voice over IP
(VoIP) such as Skype
 Web based computing
 Become ubiquitous
 PC, workstations, handled PDAs, cell phones provides
access
 Increases emphasis on networking
 Devices include wired, wireless, faster network
connectivity by networking technology
 Web based computing has given rise to load balancing
 Which distribute network connections among a pool of
similar servers
 Web has increased the complexity of devices
End of Chapter 1
Chapter 2: Operating-System
Structures
 Chapter 2: Operating-System Structures
 2.1 Operating System Services
 2.2 User Operating System Interface
 2.3 System Calls
 2.4 Types of System Calls
 2.5 System Programs
 2.6 Operating System Design and Implementation
 2.7 Operating System Structure
 2.8 Virtual Machines
 2.9 Operating System Generation
 2.10System Boot
 Objectives
 To describe the services an operating system provides to
users, processes, and other systems

 To discuss the various ways of structuring an operating system

 To explain how operating systems are installed and customized

and how they boot
 2.1 Operating System Services
 Operating systems provide an environment for execution of
programs and services to programs and users
 One set of operating-system services provides functions that
are helpful to the user:
 User interface - Almost all operating systems have a user
interface (UI).
Varies between Command-Line (CLI), Graphics User
Interface (GUI), Batch
 Program execution - The system must be able to load a
program into memory and to run that program, end
execution, either normally or abnormally (indicating error)
 I/O operations - A running program may require I/O, which
may involve a file or an I/O device
 Operating System Services (Cont.)
 One set of operating-system services provides functions that are helpful to
the user (Cont.):
 File-system manipulation - The file system is of particular interest.
Programs need to read and write files and directories, create and delete
them, search them, list file Information, permission management.
 Communications – Processes may exchange information, on the same
computer or between computers over a network
 Communications may be via shared memory or through message
passing (packets moved by the OS)
 Error detection – OS needs to be constantly aware of possible errors
 May occur in the CPU and memory hardware, in I/O devices, in user
program
 For each type of error, OS should take the appropriate action to
ensure correct and consistent computing
 Debugging facilities can greatly enhance the user ’ s and
programmer’s abilities to efficiently use the system
 Operating System Services (Cont.)

 Another set of OS functions exists for ensuring the efficient operation of the
system itself via resource sharing
 Resource allocation - When multiple users or multiple jobs running
concurrently, resources must be allocated to each of them
 Many types of resources - CPU cycles, main memory, file storage,
I/O devices.
 Accounting - To keep track of which users use how much and what
kinds of computer resources
 Protection and security - The owners of information stored in a
multiuser or networked computer system may want to control use of that
information, concurrent processes should not interfere with each other
 Protection involves ensuring that all access to system resources is
controlled
 Security of the system from outsiders requires user authentication,
extends to defending external I/O devices from invalid access
attempts
A View of Operating System Services
2.2.1 User Operating System Interface - CLI
CLI or command interpreter allows direct command entry
 Sometimes implemented in kernel, sometimes by systems
program
 Sometimes multiple flavors implemented – shells eg-
Bourne shell, C shell, Korn shell etc
 Primarily fetches a command from user and executes it
 Sometimes commands built-in, sometimes just names of
programs like rm file.txt
If the latter, adding new features doesn’t require shell
modification
2.2.2 User Operating System Interface - GUI
 User-friendly desktop metaphor interface
 Usually mouse, keyboard, and monitor
 Icons represent files, programs, actions, etc
 Various mouse buttons over objects in the interface cause
various actions (provide information, options, execute
function, open directory (known as a folder)
 Invented at Xerox PARC
 Many systems now include both CLI and GUI interfaces
 Microsoft Windows is GUI with CLI “command” shell
 Apple Mac OS X is “Aqua” GUI interface with UNIX kernel
underneath and shells available
 Unix and Linux have CLI with optional GUI interfaces (CDE,
KDE, GNOME)
 2.3 System Calls

 Programming interface to the services provided by the OS

 Typically written in a high-level language (C or C++ and also
assembly-language instructions)
 Example of System Calls
 System call sequence to copy the contents of one file to
another file
 System Calls…

 Most accessed by programs via a high-level Application

Programming Interface (API) rather than direct system call
use

 API – functions, parameters and return values– eg read()

 Reasons to use API than system call is:
 Support portability
 Reduce complexity
 \Three most common APIs are Win32 API for Windows, POSIX
API for POSIX-based systems (including virtually all versions of
UNIX, Linux, and Mac OS X), and Java API for the Java virtual
machine (JVM)
Example of Standard API
 System Call Implementation
 System call interface – link between system call and function name in the
API

 Typically, a number associated with each system call

 System-call interface maintains a table indexed according to these
numbers

 The system call interface invokes the intended system call in OS kernel and
returns status of the system call and any return values

 The caller need know nothing about how the system call is implemented
 Just needs to obey API and understand what OS will do as a result call
 Most details of OS interface hidden from programmer by API
 Managed by run-time support library (set of functions built into
libraries included with compiler)
API – System Call – OS Relationship
 System Call Parameter Passing
 Often, more information is required than simply identity of
desired system call
 Exact type and amount of information vary according to OS
and call
 Three general methods used to pass parameters to the OS
 Simplest: pass the parameters in registers
 In some cases, may be more parameters than registers
 Parameters stored in a block, or table, in memory, and
address of block passed as a parameter in a register
This approach taken by Linux and Solaris

 Parameters placed, or pushed, onto the stack by the

program and popped off the stack by the operating system
 Block and stack methods do not limit the number or length of
parameters being passed
Parameter Passing via Table
 2.4 Types of System Calls
 1. Process control
 create process, terminate process
 end, abort
 load, execute
 get process attributes, set process attributes
 wait for time
 wait event, signal event
 allocate and free memory
 Dump memory if error
 Debugger for determining bugs, single step execution
 Locks for managing access to shared data between
processes
 Standard C Library Example
 C program invoking printf() library call, which calls write()
system call
 Example: MS-DOS
 Single-tasking
 Shell invoked when system
booted
 Simple method to run
program
 No process created
 Single memory space
 Loads program into
memory, overwriting all but
the kernel
 Program exit -> shell
reloaded
At system startup running a program
 Example: FreeBSD
 Unix variant
 Multitasking
 User login -> invoke user’s choice of
shell
 Shell executes fork() system call to
create process
 Executes exec() to load program
into process
 Shell waits for process to terminate
or continues with user commands
 Process exits with:
 code = 0 – no error
 code > 0 – error code
 Types of System Calls
 2. File management
 create file, delete file
 open, close file
 read, write, reposition
 get and set file attributes
 3. Device management
 request device, release device
 read, write, reposition
 get device attributes, set device attributes
 logically attach or detach devices
 Types of System Calls (Cont.)
 4. Information maintenance
 get time or date, set time or date
 get system data, set system data
 get and set process, file, or device attributes
 5. Communications
 create, delete communication connection
 send, receive messages if message passing model to host
name or process name
From client to server
 Shared-memory model create and gain access to memory
regions
 transfer status information
 attach and detach remote devices
 Types of System Calls (Cont.)

 Protection
 Control access to resources
 Get and set permissions
 Allow and deny user access
Examples of Windows and Unix System Calls
 2.5 System Programs
 System programs provide a convenient environment for
program development and execution.
 Most users’ view of the operation system is defined by
system programs, not the actual system calls
 System Programs
 Provide a convenient environment for program development and
execution
 Some of them are simply user interfaces to system calls; others
are considerably more complex
 1. File management - Create, delete, copy, rename, print, dump,
list, and generally manipulate files and directories
 2. Status information
 Some ask the system for info - date, time, amount of available
memory, disk space, number of users
 Others provide detailed performance, logging, and debugging
information
 Typically, these programs format and print the output to the
terminal or other output devices
 Some systems implement a registry - used to store and
retrieve configuration information
 System Programs (Cont.)
 3. File modification
 Text editors to create and modify files
 Special commands to search contents of files or perform
transformations of the text
 4. Programming-language support –
 Compilers, assemblers, debuggers and interpreters sometimes
provided
 5. Program loading and execution-
 Absolute loaders, relocatable loaders, linkage editors, and overlay-
loaders, debugging systems for higher-level and machine language
 6. Communications - Provide the mechanism for creating virtual
connections among processes, users, and computer systems
 Allow users to send messages to one another’s screens, browse
web pages, send electronic-mail messages, log in remotely,
transfer files from one machine to another
 2.6 Operating System Design and Implementation

 Design and Implementation of OS not “ solvable ” , but some

approaches have proven successful
 Internal structure of different Operating Systems can vary widely
 Start the design by defining goals and specifications
 Affected by choice of hardware, type of system ( batch, time shared
single user, multi user, distributed, real time or general purpose)
 User goals and System 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
 Operating System Design and Implementation (Cont.)

 Important principle to separate

Policy:Whatwillbedone?
Mechanism: How to do it?

 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 (example – timer)
 Specifying and designing an OS is highly creative task of
software engineering
 Implementation
 Much variation
 Early OSes in assembly language
 Then system programming languages like Algol, PL/1
 Now C, C++
 Actually usually a mix of languages
 Lowest levels in assembly
 Main body in C
 Systems programs in C, C++, scripting languages like PERL,
Python, shell scripts
 More high-level language easier to port to other hardware
 But slower, more storage requirement
 2.7 Operating System Structure
 General-purpose OS is very large program

 Various ways to structure ones

 Simple structure – MS-DOS
 More complex -- UNIX
 Layered – an abstrcation
 Microkernel –Mach
 Module
 Hybrid
2.7.1 Simple Structure -- MS-DOS
 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
 Non Simple Structure -- UNIX
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
 Traditional UNIX System Structure

Beyond simple but not fully layered

2.7.2 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
2.7.3 Microkernel System Structure
 Moves as much from the kernel into user space
 Mach example of microkernel
 Mac OS X kernel (Darwin) partly based on Mach
 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
 Detriments:
 Performance overhead of user space to kernel space
communication
 Microkernel System Structure

Application File Device user

Program System Driver mode

messages messages

Interprocess memory CPU kernel

Communication managment scheduling mode

microkernel

hardware
2.7.4 Modules
 Many modern operating systems implement loadable kernel modules
 Uses object-oriented approach
 Each core component is separate
 Each talks to the others over known interfaces
 Each is loadable as needed within the kernel
 Overall, similar to layers but with more flexible
 Linux, Solaris, etc
Solaris Modular Approach
2.7.4 Hybrid Systems
 Most OSes today do not strictly adhere to one architecture, but are
hybrids of several.

Mac OS X
 The Max OSX architecture relies on the Mach microkernel for basic
system management services, and the BSD kernel for additional
services.
 Application services and dynamically loadable modules ( kernel
extensions ) provide the rest of the OS functionality:
 2.8 Virtual Machines
 To abstract the hardware of a single computer into several different
execution environment.
 The concept of a virtual machine is to provide an interface that looks
like independent hardware, to multiple different OSes running
simultaneously on the same physical hardware.
 Each OS believes that it has access to and control over its own CPU,
RAM, I/O devices, hard drives, etc.
 One obvious use for this system is for the development and testing of
software that must run on multiple platforms and/or OSes.
 One obvious difficulty involves the sharing of hard drives, which are
generally partitioned into separate smaller virtual disks(mini disk) for
each operating OS.
 Virtual machines first appeared as the VM Operating System for IBM
mainframes in 1972.
2.8.1 Implementation
 Implementation may be challenging, partially due to the
consequences of user versus kernel mode.
 Each of the simultaneously running kernels needs to operate in
kernel mode at some point, but the virtual machine actually runs
in user mode.
 So the kernel mode has to be simulated for each of the loaded
OSes, and kernel system calls passed through the virtual
machine into a true kernel mode for eventual HW access.
 The virtual machines may run slower, due to the increased levels of
code between applications and the HW, or they may run faster, due
to the benefits of caching or spooling. ( And virtual devices may
also be faster than real devices, such as RAM disks which are
faster than physical disks. )
2.8.2 Benefits

 Each OS runs independently of all the others, offering protection

and security benefits.
 Sharing of physical resources is not commonly implemented, but
may be done by
 1. share a minidisk and thus files
 2. define network of VM
 Virtual machines are a very useful tool for OS development, as
they allow a user full access to and control over a virtual machine,
without affecting other users operating the real machine.
 This approach can also be useful for product development and
testing of SW that must run on multiple OSes / HW platforms.
2.8.3 Examples
1. VMware
 Abstracts the 80x86 hardware platform, allowing simultaneous
operation of multiple Windows and Linux OSes
2. The Java Virtual Machine
 Java was designed to be platform independent, by running Java
only on a Java Virtual Machine(JVM), of which different
implementations have been developed for numerous different
underlying HW platforms.
 Java source code is compiled into Java byte code in .class files.
 The JVM implements memory management and garbage collection.
 Java byte code may be interpreted as it runs, or compiled to native
system binary code using just-in-time ( JIT ) compilation.
 The first native binary code is cached, so that the next time that
piece of code is encountered it can be used directly.
 Some hardware chips have been developed to run Java byte code
directly, which is an interesting application of a real machine being
developed to emulate the services of a virtual one!
 2.9 Operating System Generation
 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
 Used to build system-specific compiled kernel or system-tuned
 Can general more efficient code than one general kernel
 OSes may be designed and built for a specific HW configuration at a
specific site, but more commonly they are designed with a number of
variable parameters and components, which are then configured for a
particular operating environment.
 Operating Systems is normally distributed on disk or CD-ROM. To
generate system special program is used.
 2.9 Operating System Generation
 SYSGEN program reads from given file and Information that is
needed to configure an OS include:
 What CPU(s) are installed on the system, and what optional
characteristics does each have?
 How much RAM is installed? ( This may be determined
automatically, either at install or boot time. )
 What devices are present? The OS needs to determine which
device drivers to include, as well as some device-specific
characteristics and parameters.
 What OS options are desired, and what values to set for particular
OS parameters. The latter may include the size of the open file
table, the number of buffers to use, process scheduling ( priority )
parameters, disk scheduling algorithms, number of slots in the
process table, etc.
 At one extreme system administrator can use it to modify OS
source code and can be edited, re-compiled, and linked into a new
kernel.
 More commonly configuration tables determine which modules to
link into the new kernel, and what values to set for some key
important parameters. This approach may require the configuration
of complicated makefiles.
 At the other extreme a system configuration may be entirely
defined by table driven data. All code is always part of system, and
selection occurs at execution time.
 Once a system has been regenerated, it is usually required to reboot
the system to activate the new kernel.
 2.10 System Boot
 When power initialized on system, execution starts at a fixed memory
location
 Firmware ROM used to hold initial boot code
 Operating system must be made available to hardware, so hardware
can start it
 Small piece of code – bootstrap loader, stored in ROM or
EEPROM locates the kernel, loads it into memory, and starts it
 Sometimes two-step process where boot block at fixed location
loaded by ROM code, which loads bootstrap loader from disk
 Common bootstrap loader, GRUB(grand unified boot loader),
allows selection of kernel from multiple disks, versions, kernel
options
 Kernel loads and system is then running
End of Chapter 2
Chapter 3: Processes
 Chapter 3: Processes

 3.1 Process Concept

 3.2 Process Scheduling
 3.3 Operations on Processes
 3.4 Interprocess Communication
 Objectives

 To introduce the notion of a process -- a program in execution,

which forms the basis of all computation

 To describe the various features of processes, including scheduling,

creation and termination, and communication

 To explore interprocess communication using shared memory and

message passing
 3.1 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
 Multiple parts
 The program code, also called text section
 Current activity including program counter, processor registers
 Stack containing temporary data
Function parameters, return addresses, local variables
 Data section containing global variables
 Heap containing memory dynamically allocated during run time
Process Concept (Cont.)

 Program is passive entity stored on disk (executable file), process is

active
 Program becomes process when executable file loaded into
memory
 Execution of program started via GUI mouse clicks, command line
entry of its name, etc
 One program can be several processes
 Consider multiple users executing the same program
Process in Memory
3.1.2 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 processor
 terminated: The process has finished execution
 Suspend Ready
 Suspend wait
Diagram of Process State
3.1.3 Process Control Block (PCB)
Information associated with each process
(also called task control block)
 Process state – running, waiting, etc
 Program counter – location of instruction to next
execute
 CPU registers – contents of all process-centric
registers
 CPU scheduling information- priorities, scheduling
queue pointers
 Memory-management information – memory
allocated to the process
 Accounting information – CPU used, clock time
elapsed since start, time limits
 I/O status information – I/O devices allocated to
process, list of open files
CPU Switch From Process to Process
3.1.4 Threads

 So far, process has a single thread of execution

 Consider having multiple program counters per process

 Multiple locations can execute at once
Multiple threads of control -> threads

 Must then have storage for thread details, multiple program

counters in PCB
 3.2 Process Scheduling

 Maximize CPU use, quickly switch processes onto CPU for time
sharing
 Process scheduler selects among available processes for next
execution on CPU
 Maintains scheduling queues of processes
 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
 Processes migrate among the various queues
Ready Queue And Various I/O Device Queues
 Representation of Process Scheduling

 Queueing diagram represents queues, resources, flows

3.2.2 Schedulers
 Process – migrates among various queues
 OS must select processes form these queues in some fashion
 The selection process is carried out by the appropriate scheduler
 Long-term scheduler (or job scheduler) – selects which
processes should be brought into the ready queue
 Long-term scheduler is invoked infrequently (seconds, minutes)
 (may be slow)
 The long-term scheduler controls the degree of
multiprogramming
 Short-term scheduler (or CPU scheduler) – selects which
process should be executed next and allocates CPU
 Sometimes the only scheduler in a system
 Short-term scheduler is invoked frequently (milliseconds) 
(must be fast)
 Schedulers
 Long term scheduler should make a careful selection
 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
 Long-term scheduler strives for good process mix

 In some systems long term scheduler may be absent

 Example- time sharing systems like UNIX and Microsoft Windows
 Addition of Medium Term Scheduling
 Medium-term scheduler can be added if degree of multiple
programming needs to decrease
 Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping
3.2.3 Context Switch
 When CPU switches to another process, the system must save the
state of the old process and load the saved state ( state restore)
for the new process via a context switch
 Context of a process represented in the PCB
 Context-switch time is overhead; the system does no useful work
while switching
 The more complex the OS and the PCB  the longer the
context switch
 Time dependents on the memory speed, the number of registers
that must be copied and the existence of special instructions
 Also dependent on hardware support
 Some hardware provides multiple sets of registers per CPU 
context switch simply requires changing the pointer to the
current register set
 3.3 Operations on Processes

 System must provide mechanisms for:

 process creation,
 process termination,
 and so on as detailed next
3.3.1 Process Creation
 Parent process create children processes, which, in turn create
other processes, forming a tree of processes
 Generally, process identified and managed via a process
identifier (pid)
 Resource sharing options
 Parent and children share all resources
 Children share subset of parent’s resources
 Parent and child share no resources
 Execution options
 Parent and children execute concurrently
 Parent waits until children terminate
 A Tree of Processes in Linux

init
pid = 1

login kthreadd sshd

pid = 8415 pid = 2 pid = 3028

bash khelper pdflush sshd

pid = 8416 pid = 6 pid = 200 pid = 3610

emacs tcsch
ps
pid = 9204 pid = 4005
pid = 9298
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
C Program Forking Separate Process
Creating a Separate Process via Windows API
3.3.2 Process Termination

 Process executes last statement and then asks the operating

system to delete it using the exit() system call.
 Returns status data from child to parent (via wait())
 Process’ resources are deallocated by operating system

 Parent may terminate the execution of children processes using

the abort() system call. Some reasons for doing so:
 Child has exceeded allocated resources
 Task assigned to child is no longer required
 The parent is exiting and the operating systems does not
allow a child to continue if its parent terminates
Process Termination

 Some operating systems do not allow child to exists if its parent has
terminated. If a process terminates, then all its children must also be
terminated.
 cascading termination. All children, grandchildren, etc. are
terminated.
 The termination is initiated by the operating system.
 The parent process may wait for termination of a child process by
using the wait()system call. The call returns status information and
the pid of the terminated process
pid = wait(&status);
 If no parent waiting (did not invoke wait()) process is a zombie
 If parent terminated without invoking wait , process is an orphan
 3.4 Interprocess Communication
 Processes within a system may be independent or cooperating
 Independent - if it cannot affect or be affected by the other processes executing
in the system – do not share data with any
 Cooperating process can affect or be affected by other processes, including
sharing data
 Reasons for cooperating processes:
 Information sharing
 Computation speedup
 Modularity
 Convenience
 Cooperating processes need interprocess communication (IPC)

 Two models of IPC

 Shared memory
 Message passing
Communications Models
(a) Message passing. (b) shared memory.
 Message passing is good for exchanging smaller amount of data
 Easier to implement
 Shared memory allows maximum speed
 Faster than message passing because message passing requires
system calls
3.4.1 Interprocess Communication – Shared Memory
 An area of memory shared among the processes that wish to
communicate
 A shared-memory region resides in the address space of the
process creating the shared-memory segment
 The other process must attach it to their address space
 The communication is under the control of the users processes not
the operating system.

 Major issues is to provide mechanism that will allow the user

processes to synchronize their actions when they access shared
memory.

 Synchronization is discussed in great details in Chapter 5.

Producer-Consumer Problem
 Example for cooperating processes

 Producer process produces information that is consumed by a consumer process

 Example : a compiler may produce assembly code which is consumed by an
assembler
 One solution to this is shared memory
 To allow producer and consumer to run concurrently we must have available a
buffer that can be filled by producer and emptied by consumer
 A producer will produce one item while the consumer is consuming another item
 Synchronization is important

 Two types of buffer can be used

 unbounded-buffer places no practical limit on the size of the buffer
 bounded-buffer assumes that there is a fixed buffer size
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

 If in == out buffer is empty
 If ((in+1)%BUFFER_SIZE) == out buffer is full
Bounded-Buffer – Producer

item next_produced;
while (true) {
/* produce an item in next produced */
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
}
Bounded Buffer – Consumer

item next_consumed;
while (true) {
while (in == out)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

/* consume the item in next consumed */

}
 3.4.2 Interprocess Communication – Message Passing
 Mechanism for processes to communicate and to synchronize their
actions without sharing the address space
 Useful for distributed systems where processes reside on different
systems

 IPC facility provides two operations:

 send(message)
 receive(message)

 The message size is either fixed or variable

 Fixed size easy to implement, programming becomes difficult
 Variable size difficult to implement, easy for programming
Message Passing (Cont.)

 If processes P and Q wish to communicate, they need to:

 Establish a communication link between them
 Exchange messages via send/receive
 Implementation issues:
 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?
Message Passing (Cont.)

 Implementation of communication link

 Physical:
Sharedmemory
Hardware bus

Network

 Logical:
 Direct or indirect

 Synchronous or asynchronous

 Automatic or explicit buffering

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
 This scheme is symmetry in addressing means both sender and receiver must
name each other
 Asymmetry in addressing, here only sender names the recipient
 send (P, message) – send a message to process P
 receive ( id, message) – receive a message from any process; the id is set to
the name of the process with which communication has taken place
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
 Indirect Communication
 Operations
 create a new mailbox (port)
 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
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.
 Mailbox may be owned by a process or by OS
 If mailbox is owned by a process, we can distinguish between the
owner ( only receive messages) and the user ( who can only send
the messages)
 Owned by OS, mailbox is independent and is not attached to any
particular process

 OS must allow a process to do the following

 Create a mailbox
 Send and receive messages through the mailbox
 Delete the mailbox
 Synchronization
 Message passing may be either blocking or non-blocking
 Blocking is considered synchronous
 Blocking send -- the sender is blocked until the message is received
 Blocking receive -- the receiver is blocked until a message is available
 Non-blocking is considered asynchronous
 Non-blocking send -- the sender sends the message and continue
 Non-blocking receive -- the receiver receives:
 A valid message, or
 Null message
 Different combinations possible
 If both send and receive are blocking, we have a rendezvous
Synchronization (Cont.)

 Producer-consumer becomes trivial

message next_produced;
while (true) {
/* produce an item in next produced */
send(next_produced);
}
message next_consumed;
while (true) {
receive(next_consumed);

/* consume the item in next consumed */

}
Buffering

 Queue of messages attached to the link.

 implemented in one of three ways
1. Zero capacity – no messages are queued on a link. 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
End of Chapter 3