UNIT 1

AN INTRODUCTION TO OPERATING SYSTEMS

A computer is a general purpose device that can execute sequences of instructions presented in a
formal format to perform numerical calculations and other tasks.

Revise: block diagram of a computer, concept of memory hierarchy.

Computer science is the study of computer systems and computing processes.

Read: Newell, A., Perlis, A. J. and Simon, H. I. 1967. Is ‘computer science’ science or engineering?
Science, 167(3795): 1373-1374.

Computer hardware is the collection of all physical elements of the computer system.
Computer software is the collection of all programs stored in and executed by a computer system.

Application software performs specific task for the user.

System software operates and controls the computer system, and provides a platform to run
application software.

An operating system is a piece of software that manages all the resources of a computer system,
both hardware and software, and provides an environment in which the user can execute his/her
programs in a convenient and efficient manner.

Operating systems exist because they offer a reasonable way to solve the problem of creating a
usable computer system.

An operating system –
- manages the computer hardware
- facilitates execution of application programs
- acts as an intermediary between the user and the computer hardware
- designed to be convenient and efficient

User
Application programs
Operating system
Computer hardware

The operating system provides the means for proper use of the resources in the operation of the
computer system.

Design goals –
- convenience (ease of use) - personal computers
- efficiency (proper resource allocation) - high performance computers
- energy conservation - handheld devices
- minimal user interference - embedded devices
2 Bedtime Stories on Operating Systems

An operating system acts as an –

- Resource allocator
- Control program

First operating system –

- ATLAS (Manchester Univ., late 1950s – early 1960s)
- evolved from control programs

Types of operating systems –

- Single process operating system [MS DOS, 1981]
- Batch-processing operating system [ATLAS, Manchester Univ., late 1950s – early 1960s]
- Multiprogramming operating system [THE, Dijkstra, early 1960s]
- Multitasking operating system [CTSS, MIT, early 1960s]

Multiprogramming increases CPU utilization by keeping multiple jobs (code and data) in the
memory so that the CPU always has one to execute.
Job 1
Job 2
Job 3
Operating system

Multitasking is a logical extension of multiprogramming.

CPU executes multiple tasks by switching among them.
The switching is very fast.
Requires an interactive (hands-on) computer where the user can directly interact with the computer.
Response time should be minimal.

A kernel is that part of the operating system which interacts directly with the hardware and
performs the most crucial tasks.
A microkernel is much smaller in size than a conventional kernel and supports only the core
operating system functionalities.
A shell, also known as a command interpreter, is that part of the operating system that receives
commands from the users and gets them executed.

A system call is a mechanism using which a user program can request a service from the kernel for
which it does not have the permission to perform.
User programs typically do not have permission to perform operations like accessing I/O devices and
communicating other programs.
A user program invokes system calls when it requires such services.
System calls provide an interface between a program and the operating system.
System calls are of different types.
E.g. – fork, exec, getpid, getppid, wait, exit.

Dual-mode operation –
- User mode
- Kernel mode / supervisor mode / system mode / privileged mode
Mode bit– 0: kernel, 1: user
Request using a system call
An Introduction to Operating Systems 3

Duties of an operating system –

- Process management
- creating and deleting user and system processes
- suspending and resuming processes
- interprocess communication
- process synchronization
- deadlock handling
- Memory management
- Keeping track of which part of memory is being used by which job
- Allocating and deallocating memory space
- Storage management
- file system management
- creating, deleting and manipulating files and directories
- mass storage management
- free space management
- storage allocation
- disk scheduling
- Caching
- Input-output management

Operating system services –

- Helpful to the user
- user interface (CUI/shell and GUI)
- program execution
- I/O operation
- file system manipulation
- communication
- error detection
- Helpful to the system
- resource allocation
- accounting
- protection and security

Operating system structures –

- Monolithic [MS DOS, Unix, Linux]
- Layered [THE]
- Microkernel [Mach, MINIX]

A real-time operating system (RTOS) has well-defined and fixed time constraints which have to be
met or the system will fail.
An RTOS is used when rigid time constraints have been placed on the operation of processes or flow
of data.
4 Bedtime Stories on Operating Systems

An RTOS is often used in the control device in a dedicated application.

Hard- and soft- RTOS.
Applications: embedded systems, robotics, scientific utilities, etc.

Operating systems for smart phones –

- CPUs of smart phones are made to be much slower to conserve energy

Booting is the process of starting the computer and loading the kernel.
When a computer is turned on, the power-on self-tests (POST) are performed.
Then the bootstrap loader, which resides in the ROM, is executed.
The bootstrap loader loads the kernel or a more sophisticated loader.

Is a device driver a part of the operating system?

Case studies: CP/M, MS DOS, Unix, Linux, Windows, etc.

http://amturing.acm.org –
- Kenneth Lane Thompson
- Frederick Phillips Brooks, Jr.
- Barbara Liskov

Chapters: 1 and 2.
Sections: 1.1, 1.4 – 1.9, 1.11, 2.1 – 2.5, 2.7 and 2.10.
 UNIT 2
PROCESS AND PROCESS SCHEDULING

A process is a program in execution.

A process is a unit of work in a computer system.
The terms process and job are used interchangeably.

A process comprises of –
- text section containing the program code
- current activity represented by the values of the program counter and other registers
- program stack
- data section containing global variables
- heap
Stack max

↑
Heap
Data
Text 0

A program is a passive entity while a process is an active entity.

Process state is defined by the current activity of the process.

As a process executes, its state changes.

Only one process can be in the running state at any instant.

Many processes can be ready or waiting.

Each process is internally represented by the operating system by a process control block (PCB) also
called task control block.
PCB contains all information associated with the process –
- Process state
- Values of program counter and other registers
- CPU scheduling information - priority, pointer to scheduling queue, etc.
- Accounting information - process id, CPU- and real- time used, time limits, etc.
- I/O status information - list of i/o devices allocated, list of open files, etc.
6 Bedtime Stories on Operating Systems

P0 P1

Executing Interrupt / system call Idle

Save state in PCB0
Load state from PCB1
Executing
Idle
Interrupt / system call
Save state in PCB1
Load state from PCB0 Idle
Executing

Process scheduling is selecting one process for execution out of all the ready processes.
The objective of multiprogramming is to have some process running at all times so as to maximize
CPU utilization.
The objective of multitasking is to switch the CPU among the processes so frequently that the user
can interact with each process while it is running.
To meet these objectives the process scheduler selects one of the available processes for execution.

Scheduling queues are used to perform process scheduling.

As a process enters the system, it is put in a job queue that contains all the processes in the system.
The processes that are residing in the memory and are ready for execution are kept in the ready
queue.
The ready queue is implemented as a linked list of PCBs with a header containing pointers to the first
and the last PCBs.
The list of the processes waiting for a particular i/o device is called a device queue.
Each device has its own device queue.

A queuing diagram shows how the processes migrate among the various scheduling queues.
Process and Process Scheduling 7

There are three types of schedulers.

A process migrates among the various scheduling queues throughout its lifetime.
The operating system has to select the processes from the queues according to some criteria.
The selection is done by the appropriate scheduler.

A long-term scheduler (job scheduler) selects processes from those submitted by the user and loads
them into the memory.
The long-term scheduler controls the degree of multiprogramming which is represented by the
number of processes in the memory.
It is invoked less frequently.

A short-term scheduler (CPU scheduler) selects one of the processes in the memory and allocates
the CPU to it.
The short-term scheduler is invoked frequently and should be very fast.

The long-term scheduler should select a proper mix of CPU-bound processes and i/o-bound
processes.
A CPU-bound process spends most of its time doing computations.
An i/o-bound process spends most of its time doing i/o.

Some multitasking operating systems, like Unix and Windows, do not use long-term schedulers.
All new processes are put in the memory for the perusal of the short-term scheduler.

A medium-term scheduler removes processes from the memory and from the competition for the
CPU, thus reducing the degree of multiprogramming.
The processes can be later reintroduced in the memory and their executions can be resumed.
This scheme is called swapping.
Swapping may be used to improve process mix and to free up some memory in uncontrollable
circumstances.

Context switching is done to switch between processes.

Switching the CPU to another process requires saving the state of the current process and reloading
the state of another process.
States are saved into and reloaded from PCBs.
Context-switch time is a pure overhead as the system does not do any useful work during a control
switch.
Context-switch time depends highly on the hardware.
Context switching is faster on RISC processors with overlapped register windows.

Process creation is one process creating another process.

The processes are called parent process and child process, respectively.
Each process has a unique id.
A process may obtain resources either from its parent or from the operating system directly.
8 Bedtime Stories on Operating Systems

A parent process may continue executing with its children processes or may wait for them to
complete.
A process may be a duplicate of its parent process (same code and data) or may have a new program
loaded into it.

Process termination marks the deletion of the PCB of the process.

A parent process may terminate a child process –
- if it has exceeded its resource usage
- if its result is no more needed
- if the parent process is terminating and the operating system does not allow an orphan
process (this may lead to cascading process terminations)

Typically, the kernel is the first process to be created, is the ancestor of all other processes and is at
the root of the process tree.

A zombie process is a process that has terminated but its PCB still exists because its parent has not
yet accepted its return value.

Interprocess communication –
- Reasons –
- information sharing
- computational speedup
- modularity
- convenience
- Models –
- shared memory
- message passing [send(P,message) and receive(id,message)]

A thread is the smallest sequence of instructions that can be managed independently by a

scheduler.
A thread is a component of a process.
Multiple threads can exist within the same process, executing concurrently and share resources such
as memory.
The threads of a process share its instructions (executable code) and its context (the values of its
variables at any given moment).

Difference between process and thread –

- processes are typically independent while threads exist as parts of a process
- processes carry considerably more state information than threads, whereas multiple threads
within a process share process state as well as memory and other resources
- processes have separate address spaces, whereas threads share their address space
- processes interact only through system-provided inter-process communication mechanisms
- context switching between threads in the same process is typically faster than context
switching between processes

Advantages of multi-threaded programming –

- responsiveness
- faster execution
- better resource utilization
- easy communication
- parallelization
Process and Process Scheduling 9

The execution of a process consists of alternate CPU bursts and i/o bursts, starting and ending with
CPU bursts.

The CPU scheduler is invoked when a process –

- switches from running state to waiting state (condition 1)
- switches from running state to ready state (condition 2)
- switches from waiting state to ready state (condition 3)
- terminates (condition 4)

In non-preemptive scheduling or cooperating scheduling, a process keeps the CPU until it

terminates or switches to the waiting state.
Some machines support non-preemptive scheduling only.
E.g. – Window 3.1x.

In preemptive scheduling, a process can be forced to leave the CPU and switch to the ready queue.
E.g. – Unix, Linux, Windows 95 and higher.

CPU scheduling is optional for conditions 2 and 3, but necessary in the other two conditions.

MS DOS does not support multiprogramming, hence no CPU scheduling.

A dispatcher is the module of the operating system that gives control of the CPU to the process
selected by the CPU scheduler.
Steps –
- switching context
- switching to user mode
- jumping to the proper location in the user program
Dispatch latency is the time taken to stop a process and start another.
Dispatch latency is a pure overhead.

Scheduling criteria –
- ↑ CPU utilization - percentage
- ↑ Throughput - number of processes completed per unit time
- ↓ Turnaround time - time from submission to completion (time spent in different
queues + time spent in CPU + time spent in different i/o
devices)
- ↓ Waiting time - time spent in ready queue (only)
- ↓ Response time - time from submission to first response
Variance in response time should be minimal.

Gantt chart (Henry Gantt)

Scheduling algorithms are used to select a process for execution.

There are several well known scheduling algorithms.

First-come first-served (FCFS) scheduling –

- non-preemptive
- high average waiting time
- convoy effect - several small processes may need to wait if a large process is given the CPU
10 Bedtime Stories on Operating Systems

Exercise 1.
Process Arrival time (ms) CPU burst time (ms)
P1 0 24
P2 1 3
P3 2 3
Calculate throughput, average turnaround time and average waiting time.

Shortest-job-first (SJF) scheduling –

- process with the smallest next CPU burst is selected
- FCFS to break ties
- more appropriate term: shortest-next-CPU-burst-first
- optimal, but cannot be implemented

We may predict the length of the next CPU burst.

We use exponential average.
τn+1 = αtn + (1-α)τn, where 0 < α < 1.
If α = 0, predicted length is constant.
If α = 1, predicted length is equal to that of the last (actual) CPU burst.
Typically, α = 0.5.
τ0 = constant or system average.

SJF can be either preemptive or non-preemptive.

Preemptive SJF = shortest-remaining-time-first.

Exercise 2.
Process Arrival time (ms) CPU burst time (ms)
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Calculate throughput, average turnaround time and average waiting time for (a) non-preemptive
and (b) preemptive scheduling.

Priority scheduling –
- CPU is allocated to the process with the highest priority
- priority range be 0 to 7 (say), with 0 representing the highest or the lowest priority
- priority may depend on internal factors (time limit, memory requirement, number of open
files, etc.) and external factors (user, department, etc.)
- may be preemptive or non-preemptive
- SJF is a special case of priority scheduling, with priority inversely proportional to predicted
next CPU burst length
- may cause starvation, i.e. indefinite blocking of processes
- aging: gradually increase the priority of a process waiting for a long time
- priority inversion: a low-priority process gets the priority of a high-priority process waiting
for it
Process and Process Scheduling 11

Exercise 3.
Process Arrival time (ms) CPU burst time (ms) Priority
P1 0 8 7
P2 2 4 5
P3 4 6 0 (highest)
P4 6 4 1
Dispatch latency = 1 ms.
Calculate CPU utilization, throughput, average turnaround time and average waiting time for (a)
non-preemptive and (b) preemptive scheduling.

Round robin (RR) scheduling –

- a small time quantum or time slice is defined
- the ready queue is treated as a circular queue
- each process is allocated the CPU for one time quantum
- preemptive
- if time quantum is too large, then RR behaves like FCFS
- if time quantum is too small, then RR behaves like processor sharing
- rule of thumb: 80% CPU bursts should be shorter than the time quantum

Exercise 4.
Process Arrival time (ms) CPU burst time (ms)
P1 0 18
P2 2 4
P3 4 6
P4 6 12
Calculate throughput, average turnaround time and average waiting time for (a) time quantum = 8
ms and (b) time quantum = 2 ms.

Multilevel queue scheduling –

- the ready queue is partitioned into several queues
- a process is permanently assigned to one queue
- each queue has its own scheduling algorithm
- inter-queue scheduling: preemptive priority scheduling or RR (80% time for foreground
processes and 20% time for background processes)

FCFS

RR

RR

FCFS

FCFS
12 Bedtime Stories on Operating Systems

Exercise 5.
Process Arrival time (ms) CPU burst time (ms) Queue
P1 0 18 Q2
P2 2 4 Q2
P3 4 6 Q1 (highest-priority)
P4 6 12 Q2
Q1: FCFS
Q2: RR, time quantum = 2 ms
Inter-queue: preemptive priority scheduling
Calculate throughput, average turnaround time and average waiting time.

Multilevel feedback queue scheduling –

- allows processes to move between queues
- inter-queue scheduling: preemptive priority scheduling
- a process waiting too long in a low-priority queue may be moved to a high-priority queue

Exercise 6.
Process Arrival time (ms) CPU burst time (ms)
P1 0 32
P2 2 10
P3 4 16
P4 6 30
Calculate throughput, average turnaround time and average waiting time.

Comparison –
☺ 
First come first served Simple Inefficient (high turnaround
scheduling time, waiting time and
response time)
Shortest job first scheduling Most efficient Impossible to implement
Priority scheduling Low waiting time for high Indefinite blocking of low
priority processes priority processes
Round robin scheduling Efficient and no indefinite Too much context switching
blocking of processes
Multilevel queue scheduling Low waiting time for high Complex
priority processes
Multilevel feedback queue Fast turnaround for short Complex
scheduling processes
Process and Process Scheduling 13

Multiple processor scheduling –

- multiprocessor systems: homogeneous or heterogeneous
- CPU scheduling approaches
- asymmetric multiprocessing - one processor performs scheduling for all
- symmetric multiprocessing - each processor is self-scheduling
- e.g. – Linux supports symmetric multiprocessing
- processor affinity –
- because of high cost of invalidating and repopulating caches, migration of processes
from one processor to another is avoided
- attempt is made to keep a process at a given processor
- hard- and soft- affinity
- load balancing –
- attempt to keep all processors equally loaded
- pull migration, push migration, combination
- only for symmetric systems
- counteracts the benefits of processor affinity

Chapters: 3 – 5.
Sections: 3.1 – 3.4, 4.1, 4.2 and 5.1 – 5.4.