Transcript Operation Systems

Operating Systems
Chapter 6
1
What is an operating system?

A program that runs on the hardware and supports



Abstracts and standardises the interface to the user across
different type of hardware


Resource Abstraction
Resource Sharing
Virtual machine hides the messy details witch must be performed.
Manages the hardware resources


Each program gets time with the resource
Each program gets space on the resource
2
Introduction

The aims of an operating system are:


User convenience
System performance

Number of requests serviced per unit time, etc
3
Introduction

Fundamental tasks of an operation system

Management of Programs



Management of Resources


Organize their execution by sharing the CPU
Ensure good user service and efficient use
Efficient allocation/de-allocation without constraining user programs
Security and Protection

Ensure absence of interference with programs and resources by
entities within and outside the operating system
4
Operating Systems


Application programs needs to access the devices
connected to a computer.
Operation System: (system program – slide-19, chapter 2).




is a software layer between the hardware and the user.
provides a consistent application program interface (API).
first program that runs when the computer boots up.
is a program that is always running when the machine is on.
5
Main functions of an operating
system
User/computer interface:
1.
Provides an interface between the user
and the computer
•
Resource manager:
2.
manages all computer’s resources.
•
•
•
•
•
Process manager
Memory manager
Device manager
File manager, etc.
6
A model of an operation
System
User command
interface
Process Manager
Operation System
Memory manager
Resource
management
Device Manager
File manager
Network manager
7
Operating system as a
user/computer interface



A user command such as open, save or print
would correspond a sequence of machinecode instructions.
The user does not need to provide these
sequences of instructions.
Operating system translates these commands
to a machine-code instructions.
8
Operating system as a resource
manager
Resource
management
Process Manager:
• Next program to be executed?
• Time to be given to each program?
Memory manager:
• Best use of the memory to run as
many programs as possible
I/O Device (e.g.printer) Manager:
• Which program should use a particular I/O
device?
Network manager:
• which computer should execute a particular
program?
9
Type of operating systems

Multi-programming


Operating system can handle several programs
at once.
Time-sharing


Operating system allows many user to share
the same computer and interact with it.
Or, in case of a single-user computer (e.g. PC),
the user can work on several programs at the
same time.
10
How the operating system get
started?



Main memory has a small section of permanent
read only memory (ROM)
ROM contains a program, bootstrap.
At the start the CPU runs bootstrap. Which directs
the CPU to load the operation system from disk and
transfer control to it.
11
Main memory
R
O
M
R
A
M
Main memory
Disk storage
Bootstrap
program
Operating
System
Bootstrap
Program
Operating
System
R
O
M
R
A
M
12
Operating system as a
process manager

Coordinates the occupation of the main memory by
different processes and their data.

At any time the operation system may be dealing
with many processes.

e.g. a process may be executed or allowed to wait in
main memory, or swapped out of the main memory.
13
Processes




Definition of a process
Process Scheduling
Operations on Processes
Cooperating Processes
14
What is a process


Process – a program in execution; process execution
must progress in sequential fashion.
A process includes:




program counter
stack
data section
heap
15
Process State

As a process executes, it changes
state





new: The process is being created.
running: Instructions are being
executed.
waiting: The process is waiting for
some event to occur.
ready: The process is waiting to be
assigned to a process.
terminated: The process has
finished execution.
16
Process Control Block (PCB)
Information associated with each process.
 Identifier
 Process state
 Program counter
 CPU registers
 CPU scheduling information
 Memory-management information
 Accounting information
 I/O status information
17
CPU Switch From Process to
Process
The PCB is saved when a
process is removed from the
CPU and another process takes
its place (context switch).
18
Process Scheduling Queues




Job queue – set of all
processes in the system.
Ready queue – set of all
processes residing in main
memory, ready and waiting to
execute.
Device queues – set of
processes waiting for an I/O
device.
Process migration between
the various queues.
19
Schedulers

Long-term scheduler (or job scheduler) –
selects which processes should be brought
into the ready queue.

Short-term scheduler (or CPU scheduler)
– selects which process should be executed
next and allocates CPU.
20
Medium Term Scheduling



Time sharing Operating systems may introduce a medium term scheduler
Removes processes from memory (and thus CPU contention) to reduce the
degree of multiprogramming – swapping
Swapping may be needed to improve the process mix or to free up memory if
it has become overcommitted
21
Intermediate queue
Job
Process queue
request
Ready
queue
CPU
I/O
I/O
I/O
I/O
End
22
Scheduling Criteria



CPU utilization – keep the CPU as busy as possible
Throughput – # of processes that complete their
execution per time unit
Turnaround time – amount of time to execute a particular
process



waiting to get into memory + waiting in the ready queue +
executing on the CPU + I/O
Waiting time – amount of time a process has been waiting
in the ready queue
Response time – amount of time it takes from when a
request was submitted until the first response is produced,
23
Optimization Criteria






Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
In most cases we optimize the average measure
24
Scheduling Algorithms
First-Come, First-Served (FCFS)
Process

Burst Time
P1
24
P2
3
P3
3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1
0


P2
24
P3
27
30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait.
25
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order P2 , P3 , P1
 The Gantt chart for the schedule is:
P2
0




P3
3
P1
6
30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case.
Average waiting time is generally not minimal and may vary
substantially if the process CPU-burst times vary greatly
26
FCFS Scheduling (Cont.)



FCFS is non-preemptive
Not good for time sharing systems where where each user
needs to get a share of the CPU at regular intervals
Short process(I/O bound) wait for one long CPU-bound
process to complete a CPU burst before they get a turn

lowers CPU and device utilization
1. I/O bound processes complete their burst and enter ready queue –
I/O devices idle and I/O bound processes waiting
2. CPU bound process completes CPU burst and moves to I/O device
3. I/O bound processes all quickly complete their CPU bursts and ente
I/O queue – now CPU is idle
27
4. CPU bound completes I/O and executes on CPU; back to step 1
Shortest-Job-First (SJR) Scheduling


Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest
time (on a tie use FCFS)
Two schemes:




nonpreemptive – once CPU given to the process it cannot be
preempted until completes its CPU burst.
preemptive – if a new process arrives with CPU burst length less
than remaining time of current executing process, preempt.
This scheme is know as the shortest-Remaining-Time-First (SRTF).
SJF is optimal – gives minimum average waiting time for a
given set of processes.
28
Example of Non-Preemptive
SJF
Process

Arrival Time
P1
0.0
P2
2.0
P3
4.0
P4
5.0
SJF (non-preemptive)
P1
0

3
P3
7
Burst Time
7
4
1
4
P2
8
P4
12
16
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
29
Example of Preemptive SJF

Process
Arrival Time
Burst Time
P1
P2
P3
P4
0.0
2.0
4.0
5.0
7
4
1
4
SJF (preemptive)
P1
0

P2
2
P3
4
P2
5
P4
7
P1
11
16
Average waiting time = (9 + 1 + 0 +2)/4 = 3
30
Priority Scheduling





A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest priority
(smallest integer  highest priority).
 Can be preemptive (compares priority of process that has
arrived at the ready queue with priority of currently running
process) or non-preemptive (put at the head of the ready
queue)
SJF is a priority scheduling where priority is the predicted next
CPU burst time.
Problem  Starvation – low priority processes may never
execute.
Solution  Aging – as time progresses increase the priority of
the process.
31
Round Robin (RR)


Each process gets a small unit of CPU time (time
quantum), usually 10-100 milliseconds. After this
time has elapsed, the process is preempted and
added to the end of the ready queue.
If there are n processes in the ready queue and the
time quantum is q, then each process gets 1/n of the
CPU time in chunks of at most q time units at once.
No process waits more than (n-1)q time units.
32
Example of RR with Time Quantum = 20
Process
Burst Time
53
17
68
24
P1
P2
P3
P4

The Gantt chart is:
P1
0

P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
Typically, higher average turnaround than SJF,
but better response.
33
Memory Management



When a process is executed it has to be in
main memory as the main memory can be
accessed quicker.
An efficient use of the main memory is an
important task of the operation system.
Different memory management techniques
are used for this purpose.
34
Memory partition



How processes are arranged in the
main memory before been executed?
Fixed-sized partitions
Variable-sized partitions
35
Fixed-sized partitions
OS
8M
8M
8M
8M
8M
36
Variable-sized partitions
OS
8M
2M
4M
8M
18M
37
Swapping





I/O operations are slow
If a running process requires an I/O
operation. The CPU will move to another
process in the main memory.
Suppose the main memory is full of processes
waiting on I/O.
CPU becomes idle
To solve this problem Swapping technique is
used.
38
disk
Main memory
No
Swapping
Long-term
queue
Operation
System
Completed
processes
Main memory
Long-term
queue
With
Swapping
Medium-term
Operation
System
Completed
processes
39
os
a
os
os
os
P1
P1
P1
p2
p2
p3
c
d
os
os
os
b
os
P1
P1
P3
e
p2
P4
P4
P4
P3
p3
p3
f
g
h
40
Fragmentation




Memory is divided into partitions
Each partition has a different size
Processes are allocated space and later freed
After a while memory will be full of small holes!



No free space large enough for a new process even though there
is enough free memory in total
If we allow free space within a partition we have internal
fragmentation
Fragmentation:


External fragmentation = unused space between partitions
Internal fragmentation = unused space within partitions
41
Problems with swapping




Swapped process are I/O output
processes.
I/O processes are slower.
The swapping process is slow as well.
Solution:

Reduce the amount of codes that needs to
be swapped.

Paging
42
Paging

A program is divided into small fixed-sized
chunks(pages).

Main memory is divided into small fixed-sized
chunks (frames).

A page is stored in one frame.

A program is stored in a set of frames. These
frames do not need to be continuous.
43
disk
Process A
page 0
page 1
page 2
page 3
disk
13
14
15
16 In use
17 In use
18
19 In use
20
Process A
13
page 0
page 1
page 2
page 3
14
page 0
of A
page 1
of A
page 2
of A
15
16 In use
use
17 In
page 3
A- page table 18 of A
13
In use
19
14
15
20
18
44
Logical and physical address
disk
Process A
page 0
page 1
page 2
page 3
13
14
page 0
of A
page 1
of A
page 2
of A
15
16 In use
17 In use
page 3
A- page table 18 of A
13
19 In use
14
20
15
18
Page 1
I
.
.
.
J(30)
Logical address(J)
1:30
Physical address(J)
14:30
45
simple paging is not efficient





Better than fixed and variable-sized partitions.
OS - loads all pages of a process in the main
memory.
However, not all pages of a process need to
be in the main memory in order to be
executed.
OS - can still execute a process if only some
of the pages are loaded
Demand paging.
46
Demand paging

Operating system – loads a page only when it is
required

No swapping in or out of unused pages is needed.

Better use of memory.

CPU can access only a number of pages of a process
at one time.

Then asks for more pages to be loaded.
47
Virtual memory






Demand paging gives rise the concept of
virtual memory.
Only a small part of a process needs to be in
main memory at one time.
Programs which require bigger memory that
main memory can still be executed.
Impression of a bigger computer memory.
This concept of the main memory is called
virtual memory.
Demand paging and virtual memory are
widely used in today’s operation systems
(wind-2000, XP).
48
Interrupts
Definition of ‘Interrupt’
Event that disrupts the normal execution
of a program and causes the execution of
special instructions
49
Interrupts
Interrupt
Program
time t
50
Interrupts
Program
time t
51
Interrupts
Interrupt
Program
Program
Interrupt Service Routine
time t
52
Interrupts
fahr= (cent *
9
) +32
5
Interrupt
Program
mov R1, cent mul R1, 9 div R1, 5 add R1, 32
mov fahr, R1
time t
53
Interrupts
Interrupt
Program
Program
mov R1, cent
mul R1, 9
Interrupt Service Routine
time t
54
Interrupts
Interrupt
Program
mov R1, cent
Program
Save
Context
Interrupt
Service
Routine
Restore
Context
mul R1, 9
time t
55
Interrupts
Interrupt
Program
mov R1, cent
Program
Save
Context
eg push R1
Interrupt
Service
Routine
Restore
Context
mul R1, 9
eg pop R1
time t
56
I/O devices

Called peripherals:









Keyboard
Mouse
Speakers
Monitor
scanner
Printer
Disk drive
CD-drive.
OS – manages all I/O operations and devices
57
OS - I/O management

There are four main I/O operations.




Control: tell the system to perform some
action (e.g. rewind tape).
Test: check the status of the device
Read: read data from the device
Write write data to the device.
58
I/O modules
System bus
CPU
Main
memory
I/O module
I/O
device
I/O module
I/O
device
59
Advantages of I/O modules





They allow the CPU to view a wide range of devices
in a simple-minded format
CPU does not need to know details of timing, format,
or electronic mechanics.
CPU only needs to function in terms of a simple read
and write commands.
They help the CPU to work more efficiently
They are 3 ways in which I/O modules can work



Programmed I/O
Interrupt-driven I/O
Direct memory access.
60
Programmed I/O




The CPU controls I/O device directly Via the I/O
modules.
The CPU sends an I/O command the I/O module.
And waits until the I/O operation is completed before
sending another I/O command.
The performance is poor as the CPU spends too
much time waiting the I/O device.
61
Programmed I/O
Issue Read to
I/O module
Check status
Ready
Read word from
I/O module
Write word
To memory
NO
done
Next instruction
yes
62
Interrupt-driven I/O




The CPU issues a command to the I/O module and
then gets on with executing other instructions.
The I/O module interrupts the CPU when it is ready
to exchange data with the CPU.
The CPU then executes the data transfer.
Most computer have interrupt lines to detect and
record the arrival of an interrupt request.
63
Interrupt-driven I/O
Issue Read to
I/O module
CPU goes to do
Other things
Check status
When the status
Is ready the
I/O module sends
An interrupt-signal
Ready
Read word from
I/O module
Write word
To memory
NO
done
Next instruction
yes
64
How does I/O module send an
interrupt to the CPU?




I/O module is linked to the control bus.
I/O module reads a word from the I/O
device.
Puts the word in the data register which is
linked to data bus.
Sends a interrupt signal to the CPU via
control bus.
65
How does CPU know
Interrupt-signal?






The CPU executes an instruction cycle.
An interrupt stage is added at the end of the
cycle.
At the end of an instruction cycle the CPU
checks for interrupts.
The CPU hardware has a wire, interruptrequest line that the CPU can sense.
If no interrupt the CPU carries on executing
next instruction.
Otherwise, it updates the process control
block, save it.
66
How does CPU process
interrupts?





Interrupt detection.
CPU executes Interrupt-handler program.
Interrupt-handler program makes use of the
process control block save earlier.
Interrupt-handler decides what to do with
interrupt.
Then asks the CPU to resume the execution
interrupted.
67
Disadvantages of Interruptdriven I/O




CPU is responsible for managing I/O
data transfer.
Every transferred word must go through
the CPU.
Devices with large transfer, e.g. disk
drive, the CPU wastes time dealing with
data transfer.
Solution: Direct-memory-access(DMA).
68
Direct-memory-access - DMA



Special-purpose processor.
Handles data transfer.
CPU issues to the DMA:





starting address in main memory to read/write to.
Starting address in the I/O device to read/write to.
The number of words to be transferred.
DMA transfers data without intervention from
the CPU.
DMA sends interrupt to the CPU when
transfer is completed.
69
DMA/CPU - bus system





DMA take care data transfer.
CPU free to do other jobs.
However, they can not use the bus at
the same time.
DMA can use the bus only when the
CPU is not using it.
Some times it has to force to CPU to
free the bus, cycles stealing.
70
DMA/CPU
System bus
DMA
CPU
Main
memory
I/O module
I/O
device
71
Summery

OS- memory manager






Fixed-sized partition: waist of memory.
Variable-sized partition: fragmentation.
Swapping. Time wasted in swapping the whole process
Simple paging: process divided into pages and loaded
into main memory(divided into frames).
Demand paging: only the required pages are loaded to
main memory.
OS- I/O manager



Programmed I/O: CPU waste waiting for I/O operation.
Interrupt-driven I/O: CPU responsible for data transfer.
DMA: takes care of data transfer instead the CPU.
72