Transcript Lecture Notes

Memory Management
CS 342 – Operating Systems
Ibrahim Korpeoglu
Bilkent University
Department of Computer Engineering
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
1
Memory Management


Memory is an important resource that must
be carefully managed.
Cost, size, and volatility are important
parameters of memory chips.


Therefore we have a memory hierarchy


There is no single memory technology that is good in all
these parameters.
Registers, Cache, Main Memory, Disk, Tape…
The part of the OS that manages the memory
hierarchy is called the Memory Manager.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
2
Memory Manager Jobs



Its is job is to keep track of which parts of
memory are used by which programs and
which parts are free.
Allocate memory when programs need it, and
de-allocate it when programs finished.
Manage swapping of programs between
memory and disk.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
3
Basic Memory Management

Two classes of memory management
systems


That move processes back and forth between
memory and disk
That have all processes in memory during
execution until termination.

We will look to this first.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
4
Basic Memory Management

Memory management that has a process in
memory until termination.



Mono-programming without Swapping or Paging
Multiprogramming with Fixed Partitions
Modeling Multiprogramming


Analysis of Multiprogramming System Performance
Relocation and Protection
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
5
Mono-programming


Run one program at a time
OS and one program will exists in the memory
Device
Drivers
in ROM
Operating
System in
ROM
0xFFFF..
User
Program
in RAM
User
Program
Operating
System in
RAM
User
Program
In RAM
0
a)
Early Mainframes
CS 342 – Operating Systems
Spring 2003
0
b)
Palmtop Computers
and
Embedded Systems
© Ibrahim Korpeoglu
Bilkent University
Operating
System in
RAM
0
c)
MS-DOS running
Early PCs
6
Multiprogramming with Fixed
Partitions


Modern systems allow multiple programs to
run at the same time.
This allows high CPU utilization:



While a process in blocked for I/O, an other one
can use CPU.
Divides the memory into n partitions (possible
each with different sizes)
The partitioning can be done at system boot
up time.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
7
Ways to use fixed partitions - 1
800K
Partition 4
When a job arrives, put it
into a queue for the first
partition that is big
enough to hold the job in
memory.
700K
Partition 3
400K
Partition 2
200K
Partition 1
Multiple Input Queues.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
Operating
System
100K
0
8
Ways to use fixed partitions - 2
800K
Partition 4
When job arrives, they are
put into a single input queue
700K
Partition 3
400K
Single Input
Queue
Partition 2
200K
Partition 1
Which job to select
when a partition
becomes free?
CS 342 – Operating Systems
Spring 2003
Operating
System
© Ibrahim Korpeoglu
Bilkent University
100K
0
9
Ways to use fixed partitions - 2

Selecting a Job when a partition become
free!


1) Select the first job from the start of queue that
fits in to the available partition.
2) Search all the jobs and find the largest sized
job that fits into the available partition.


Discriminates against small jobs.
Solve by counting the skip overs for the fitting jobs. If a job
is skipped k times, then don’t skip it in the next search
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
10
Modeling Multiprogramming



Multiprogramming improves CPU utilization.
Assume a process spends a fraction p
(0<=p<=1) of its waiting for I/O to complete.
With n process in memory (n: degree of
multiprogramming):


The chance that all n processes are waiting for I/O
is: pn
The CPU utilization is then: 1-pn.
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
11
1
1-(0.2)**x
1-(0.5)**x
1-(0.8)**x
0.9
0.8
20% I/O Wait
0.7
0.6
50% I/O Wait
0.5
0.4
0.3
80% I/O Wait
0.2
0.1
0
0
2
CS 342 – Operating Systems
Spring 2003
4
6
Degree of Multiprogramming
© Ibrahim Korpeoglu
Bilkent University
8
10
12
80% average I/O wait
Memory
Size
OS
Size
program
Size
#programs
that can
fit
(degree of
multiprogramin
g)
CPU
utilization
Percent
Increase in
CPU utilization
32MB
16MB
4MB
4
60%
-
48MB
16MB
4MB
8
83%
38%
64MB
16MB
4MB
12
93%
12%
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
13
Analysis of Multiprogramming
Systems

Assume 4 jobs arrive to a batch system ayt
10:00 am in the morning precisely at the
following moments:





Job 1: 10:00am (requires 4 minutes of CPU)
Job 2: 10:10am (requires 3 minutes of CPU)
Job 3: 10:15am (requires 2 minutes of CPU)
Job 4: 10:20am (requires 1 minute of CPU)
When does each job completes?
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
14
Analysis of Multiprogramming
Systems p = 0.8 and n is in {1, 2, 3, 4}
Process
1
Process
2
Process
3
Process
4
CPU idle
.80
.64
.51
.41
pn
CPU busy
.20
.36
.49
.59
1-pn
CPU/process
.20
.18
.16
.15
(1-pn)/n
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
15
Analysis of Multiprogramming
Systems
Job 1 ends
.9
2.0
1
Job 1 ends
minutes
.8
.3
Job 2 ends
.9
2
.8
.3
.9
.1
Job 3 ends
3
.8
Job 2 starts
.3
.9
Job 3 ends
.9
.3
Job 3 starts
4
.1
.7
Job 3 starts
0
10
15
Time
20
22
Time is relative to Job 1’s arrival
CS 342 – Operating Systems
Spring 2003
© Ibrahim Korpeoglu
Bilkent University
28.2
27.6
31.7
minutes
16