Operating System Overview

1
Objectives and Functions

2
 Operating System
• A program that controls the execution of application
programs
• An interface between applications and hardware

Main objectives of an OS:

• Convenience: User/Computer Interface

• Efficiency: Resource Manager
• Ability to evolve: Ease of Evolution

3
Operating System as User/ Computer Interface
Application programs
Application
programming interface
Application Libraries/utilities Software
binary interface
Operating system
Instruction Set
Architecture
Execution hardware

Memory
System interconnect
translation Hardware
(bus)

I/O devices
Main
and
memory
networking

Figure 2.1 Computer Hardware and Software Structure

4
Overall Services of OS
• Resource Management: Disk, CPU cycles, memory, etc. must be
managed efficiently to maximize overall system performance
• Resource Abstraction: Software interface to simplify use of hardware
resources
• Virtualization: Supports resource sharing – gives each process the
appearance of an unshared resource

5
 Operating System Services
• Program development
• Program execution
• Access I/O devices
• Controlled access to files
• System access
• Error detection and response
• Accounting

6
The Operating System as Resource Manager

• The OS is responsible for controlling

the use of a computer’s resources,
such as I/O, main and secondary
memory, and processor execution
time

7
Operating System
as Resource Manager

• Functions in the same way as ordinary

computer software
• Program, or suite of programs, executed by
the processor
• Frequently relinquishes control and must
depend on the processor to allow it to regain
control

8
Evolution and Major
Archievement of Operating
Systems

9
Ease of Evolution of Operating Systems

▪ A major OS will evolve over time for a

number of reasons:
Hardware upgrades

New types of hardware

New services

Fixes
▪ OS need regularly update for certain
requirements on its design.
10
 Evolution of
Operating Systems
▪ Stages include:

Time
Sharing
Multiprogrammed Systems
Batch Systems
Simple Batch
Systems
Serial
Processing
11
 Major Achievements

• Operating Systems are among the most

complex pieces of software ever developed
• Major theoretical advances in development
include:
• Processes
• Memory management
• Information protection and security
• Scheduling and resource management
• System structure

12
 Process

• Fundamental to the structure of operating systems

A process can be defined as:

A program in execution

An instance of a running program

The entity that can be assigned to, and executed on, a processor

A unit of activity characterized by a single sequential thread of execution, a

current state, and an associated set of system resources

13
Process Execution States
• For convenience, we describe a process as being in one of several
basic states.
• Most basic:
• Running
• Ready
• Blocked (or sleeping)

14
Process State Transition Diagram
preempt

ready running
dispatch

event occurs wait for event

blocked

15
 Other States
• New
• Exit
• Suspended (Swapped)
– Suspended blocked
– Suspended ready

16
Processes and Threads
• Traditional processes could only do one thing at a time – they were
single-threaded.
• Multithreaded processes can (conceptually) do several things at once
– they have multiple threads.
• A thread is an “execution context” or “separately schedulable” entity.

17
Threads
• Several threads can share the address space of a single process, along
with resources such as files.
• Each thread has its own stack, PC, and TCB (thread control block)
• Each thread executes a separate section of the code and has private data
• All threads can access global data of process

18
Threads versus Processes
• If two processes want to access shared data structures, the OS must
be involved.
• Overhead: system calls, mode switches, context switches, extra execution
time.
• Two threads in a single process can share global data automatically –
as easily as two functions in a single process.

19
 Causes of Errors

• Improper synchronization • Nondeterminate program

• It is often the case that a operation
routine must be suspended • When programs share
awaiting an event elsewhere memory, and their
in the system execution is interleaved by
the processor, they may
• Improper design of the interfere with each other by
signaling mechanism can overwriting common
result in loss or duplication memory areas in
unpredictable ways
• Failed mutual exclusion • The order in which
• More than one user or program programs are scheduled
attempts to make use of a shared may affect the outcome of
resource at the same time any particular program
• There must be some sort of
mutual exclusion mechanism that
• Deadlocks
permits only one routine at a time • It is possible for two or more
to perform an update against the programs to be hung up
file waiting for each other
20
 Components of
a Process
• A process contains • The execution context is
three components: essential:
• An executable program • It is the internal data by
which the OS is able to
• The associated data supervise and control the
needed by the program process
(variables, work space, • Includes the contents of the
buffers, etc.) various process registers
• The execution context • Includes information such as
(or “process state”) of the priority of the process
the program and whether the process is
waiting for the completion
of a particular I/O event

21
 Main Processor
Memory Registers
Process index i

PC
i
Process Management Process
list
j
Base
Limit
b
h

Other
registers

Context
Process
▪ The entire state of the A
Data

process at any instant is Program

(code)
contained in its context
▪ New features can be b
designed and incorporated into Context

the OS by expanding the Process

h Data
context to include any new B
Program
information needed to support (code)
the feature

Figure 2.8 Typical Process Implementation

22
Process (Thread) Scheduling
• Process scheduling decides which process to dispatch (to the Run
state) next.
• In a multiprogrammed system several processes compete for a single
processor
• Preemptive scheduling: a process can be removed from the Run state
before it completes or blocks (timer expires or higher priority process
enters Ready state).

23
Scheduling Algorithms:
• FCFS (first-come, first-served): non-preemptive:
processes run until they complete or, in multi-
programmed systems, until they block themselves
for event wait.
• RR (round robin): preemptive FCFS, based on time
slice
• Time slice = length of time a process can run before
being preempted
• Return to Ready state when preempted

24
Scheduling Goals
• Optimize turnaround time and/or response time
• Optimize throughput
• Avoid starvation (be “fair” )
• Respect priorities
• Static
• Dynamic

25
 Memory Management

• The OS has five principal storage management

responsibilities:

Automatic
Support of Protection
Process allocation Long-term
modular and access
isolation and storage
programming control
management

26
Virtual Memory

• A facility that allows programs to address

memory from a logical point of view, without
regard to the amount of main memory physically
available
• Conceived to meet the requirement of having
multiple user jobs reside in main memory
concurrently

27
Paging

• Allows processes to be comprised of a number of fixed-size

blocks, called pages
• Program references a word by means of a virtual address,
consisting of a page number and an offset within the page
• Each page of a process may be located anywhere in main
memory
• The paging system provides for a dynamic mapping between
the virtual address used in the program and a real address
(or physical address) in main memory

28
 A.1
A.0 A.2
0 0
A.5
1 1
2 2
B.0 B.1 B.2 B.3
3 3
4 4
5 5
6 6
A.7
7 User
A.9
8 program
B
9
A.8
10

User
program
A
B.5 B.6

Main Memory Disk

Main memory consists of a Secondary memory (disk) can
number of fixed-length frames, hold many fixed-length pages. A
each equal to the size of a page. user program consists of some
For a program to execute, some number of pages. Pages for all
or all of its pages must be in programs plus the operating system
main memory. are on disk, as are files.

Figure 2.9 Virtual Memory Concepts

29
 Real
Memory Address
Processor Management
Virtual Unit
Address Main
Memory

Disk
Address

Secondary
Memory

Figure 2.10 Virtual Memory Addressing

30
Information Protection
and Security
• The nature of the
threat that concerns an
organization will vary Main
greatly depending on
the circumstances
issues Availability

• The problem involves

controlling access to
computer systems and Confidentiality
Authenticity
the information stored
in them
Data integrity

31
 Scheduling and
Resource Management

• Key responsibility of
an OS is managing
resources Efficiency
Fairness

• Resource allocation
policies must consider:
Differential
responsiveness

32
 Operating System
Service Call Service
from Process Call
Handler (code)

Long- Short- I/O

Interrupt
Term Term Queues
from Process Interrupt
Queue Queue
Interrupt Handler (code)
from I/O
Short-Term
Scheduler
(code)

Pass Control
to Process

Figure 2.11 Key Elements of an Operating System for Multiprogramming

33
Different Architectural Approaches

• Demands on operating systems require new

ways of organizing the OS

Different approaches and design elements have been tried:

• Microkernel architecture
• Multithreading
• Symmetric multiprocessing
• Distributed operating systems
• Object-oriented design
34
 Microkernel Architecture

• Assigns only a few essential functions to the

kernel:
Address Interprocess
Basic
space communication
scheduling
management (IPC)

• The approach:

Well suited to a
Simplifies Provides
distributed
implementation flexibility
environment

35
 Multithreading

Thread Process
• Technique in
which a process,
executing an Dispatchable unit of work
A collection of one or more
threads and associated system
application, is resources

divided into
threads that can By breaking a single application

run concurrently Includes a processor context and

its own data area for a stack
into multiple threads, a
programmer has greater control
over the modularity of the
application and the timing of
application-related events

Executes sequentially and is

interruptible

36
 Symmetric
Multiprocessing (SMP)
• Term that refers to a computer hardware architecture and also to
the OS behavior that exploits that architecture
• The OS of an SMP schedules processes or threads across all of
the processors
• The OS must provide tools and functions to exploit the
parallelism in an SMP system
• Multithreading and SMP are often discussed together, but the
two are independent facilities
• An attractive feature of an SMP is that the existence of multiple
processors is transparent to the user

37
SMP Advantages

More than one process can be

Performance running simultaneously, each on a
different processor

Failure of a single process does not

Availability halt the system

Performance of a system can be

Incremental
enhanced by adding an additional
Growth processor

Vendors can offer a range of products

Scaling based on the number of processors
configured in the system
38
 Time

Process 1

Process 2

Process 3

(a) Interleaving (multiprogramming, one processor)

Process 1

Process 2

Process 3

(b) Interleaving and overlapping (multiprocessing; two processors)

Blocked Running

Figure 2.12 Multiprogramming and Multiprocessing

39
 OS Design

Distributed Operating
System Object-Oriented Design

• Provides the illusion of a • Lends discipline to the

single main memory space process of adding modular
and a single secondary extensions to a small kernel
memory space plus other • Enables programmers to
unified access facilities, such customize an operating
as a distributed file system system without disrupting
• State of the art for distributed system integrity
operating systems lags that of • Also eases the development
uniprocessor and SMP of distributed tools and full-
operating systems blown distributed operating
systems

40
Fault Tolerance

41
Fault Tolerance

• Refers to the ability of a system or component to continue normal

operation despite the presence of hardware or software faults
• Typically involves some degree of redundancy
• Intended to increase the reliability of a system
• Typically comes with a cost in financial terms or performance
• The extent adoption of fault tolerance measures must be
determined by how critical the resource is

42
 Fundamental Concepts

• The basic measures are:

• Reliability
• R(t)
• Defined as the probability of its correct operation up to time t given that
the system was operating correctly at time t=o
• Mean time to failure (MTTF)
• Mean time to repair (MTTR) is the average time it takes to repair or
replace a faulty element
• Availability
• Defined as the fraction of time the system is available to service users’
requests

43
44
 Class Availability Annual Downtime
Continuous 1.0 0
Fault Tolerant 0.99999 5 minutes
Fault Resilient 0.9999 53 minutes
High Availability 0.999 8.3 hours
Normal Availability 0.99 - 0.995 44-87 hours

Table 2.4 Availability Classes

45
 Faults

• Are defined by the IEEE Standards Dictionary as an erroneous hardware

or software state resulting from:
• Component failure
• Operator error
• Physical interference from the environment
• Design error
• Program error
• Data structure error

• The standard also states that a fault manifests itself as:

• A defect in a hardware device or component
• An incorrect step, process, or data definition in a computer program

46
 Fault Categories

• Permanent
• A fault that, after it occurs, is always present
• The fault persists until the faulty component is replaced or repaired
• Temporary
• A fault that is not present all the time for all operating conditions
• Can be classified as
• Transient – a fault that occurs only once
• Intermittent – a fault that occurs at multiple, unpredictable times

47
 Virtual Machine Approach

• Allows one or more cores to be dedicated to a

particular process and then leave the processor
alone to devote its efforts to that process
• Multicore OS could then act as a hypervisor that
makes a high-level decision to allocate cores to
applications but does little in the way of resource
allocation beyond that

48
Interprocess Communication (IPC)

• Processes (or threads) that cooperate to solve

problems must exchange information.
• Two approaches:
• Shared memory
• Message passing (copying
information from one process address space to
another)
• Shared memory is more efficient (no copying), but
isn’t always possible.

49
Process Synchronization -
• Event ordering – insure that event 2 in process
A happens before event 4 in process B.
• Mutual exclusion - when one process is using a
shared resource, no other process should be
allowed to access the same resource. This is
also referred to as the critical section problem.

50
Mutual Exclusion
• A critical section is the code that accesses shared
data or resources.
• A solution to the critical section problem must
ensure that only one process at a time can execute
its critical section (CS).
• “lock” the critical section.
• Two separate shared resources can be accessed
concurrently.

51
Synchronization
• Processes and threads are responsible for their
own synchronization, but programming languages
and operating systems may have features to help.
• Virtually all operating systems provide some form
of semaphore, which can be used for mutual
exclusion and other forms of synchronization such
as event ordering.

52
Semaphores
• Definition: A semaphore is an integer variable (S) which can only be
accessed in the following ways:
• Initialize (S)
• P(S) // {wait(S)}
• V(S) // {signal(S)}
• The operating system must ensure that all operations are indivisible,
and that no other access to the semaphore variable is allowed

53
Other Mechanisms for Mutual Exclusion
• Spinlocks: a busy-waiting solution
in which a process wishing to enter a critical section continuously
tests some lock variable to see if the critical section is available.
Implemented with various machine-language instructions
• Disable interrupts before entering CS, enable after leaving

54
Deadlock
• A set of processes is deadlocked when each is in the Blocked state
because it is waiting for a resource that is allocated to one of the
others.
• Deadlocks can only be resolved by agents outside of the deadlock

55
Deadlock versus Starvation
• Starvation occurs when a process is repeatedly denied access to a
resource even though the resource becomes available.
• Deadlocked processes are permanently blocked but starving
processes may eventually get the resource being requested.
• In starvation, the resource being waited for is continually in use, while
in deadlock it is not being used because it is assigned to a blocked
process.

56
Causes of Deadlock

• Mutual exclusion (exclusive access)

• Hold (current resources) and wait (for another
resource)
• No preemption
• Circular wait

57
Deadlock Management Strategies
• Prevention: design a system in which at least one of the 4 causes can
never happen
• Avoidance: allocate resources carefully, so there will always be
enough to allow all processes to complete (Banker’s Algorithm)
• Detection: periodically, determine if a deadlock exists. If there is one,
abort one or more processes, or take some other action.

58
End of Operating System Review

59