Operating System

By
Fikadu M.
[email protected]
Chapter Three
Memory Management

Lecture 3: Memory Management 3/ 3/ 202

Outline
3

🠶 Introduction
🠶 Basic memory management
🠶 Multiprogramming with variable partitions - swapping
🠶 Virtual memory
🠶 Shared pages
🠶 segmentation

Lecture 3: Memory Management 3/ 3/ 202

4 3.1. Introduction
 Main memory (RAM) is an important resource that must be
carefully managed.

 What every programmer would like is:

 a private,
 infinitely large,
 infinitely fast memory that is also nonvolatile,
 that is, does not lose its contents when the electric power is switched off. While we are at it,
why
not make it inexpensive, too?

 Unfortunately, technology does not provide such memories at

present.
Maybe you will discover how to do it.

Lecture 3: Memory Management 3/ 3/ 202

5 Cont’d
… choice?
What is the second

Lecture 3: Memory Management 3/ 3/ 202

6 Cont’d
… choice?
What is the second

🠶 Over the years, people discovered the concept of a memory hierarchy, in which
computers have:
 a few megabytes of very fast, expensive, volatile cache memory,
 a few gigabytes of medium-speed, medium priced, volatile main memory,
 and a few terabytes of slow, cheap, non-volatile disk storage, not to mention removable
storage, such as DVDs and USB sticks.

🠶 It is the job of the operating system to abstract this hierarchy into a useful model
and then manage the abstraction.

Lecture 3: Memory Management 3/ 3/ 202

7 3.2. Basic Memory
🠶 The part Management
of the operating system that manages (part of) the
memory hierarchy is called the memory manager.

🠶 Memory management is the functionality of

an operating system which handles or manages
primary memory.
🠶 Program must be brought into memory and placed within a process for it
to
be executed.

Lecture 3: Memory Management 3/ 3/ 202

8 Cont’d
🠶 … without Swapping or Paging
Mono-programming

Three simple ways of organizing

memory
- an operating system with one userLecture 3: Memory Management
3/ 3/ 202
9 Cont’d
🠶 …
Multiprogramming with Fixed
Partitions

🠶 Fixed memory partitions

🠶 separate input queues for
each partition
🠶 single input queue
Lecture 3: Memory Management 3/ 3/ 202
1 Cont’d
0
…
Memory management :

 mechanism
 keep track of which parts of memory are in use,
 Keep track of unused (“free”) memory
 Protect memory space
 allocate memory to processes when they need
it,
 de-allocate it when they are done.
 Swap processes: memory <–> disk

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
1
…
Policies

 Decide when to load each process into memory

 Decide how much memory space to allocate each process
 Decide when a process should be removed from memory

🠶 Input queue – collection of processes on the disk that are waiting to be

brought into memory to run the program.

Lecture 3: Memory Management 3/ 3/ 202

1 3.2.1 No memory
2
abstraction
🠶 The simplest memory abstraction is no abstraction at all.

 Early mainframe computers (before 1960),

 early minicomputers (before 1970), and
 early personal computers (before 1980) had no memory abstraction.

 Every program simply saw the physical memory. When a program executed
an instruction like

MOV REGISTERS, 1000

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
3
…just moved the contents of physical memory location 1000 to
🠶 the computer
REGISTER 1.

🠶 Thus the model of memory presented to the programmer was simply physical
memory,
🠶 Under these conditions, it was not possible to have two running programs in
memory at the same time.
🠶 If the first program wrote a new value to, say, location 2000, this would erase
whatever value the second program was storing there.
🠶 Nothing would work and both programs would crash almost immediately.
🠶 When the system is organized in this way, generally only one process at a
time can be running.

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
4
🠶 … of instructions and data to memory addresses can happen at three
Address binding
different stages:

1. Compile time: compile time binding is used to generate the absolute

code. must recompile code if starting location changes.
2. Load time: Must generate relocatable code if memory
location is not known at compile time.
3. Execution time: Binding delayed until run time if the process
can be moved during its execution from one memory segment to
another.

Lecture 3: Memory Management 3/ 3/ 202

1 3.2.2. Swapping
5
🠶 Swapping is a mechanism in which a process can be swapped temporarily out of main
memory to a backing store , and then brought back into memory for continued
execution.

 Backing store – fast disk large enough to accommodate copies of all memory images
for all users;
 Roll out, roll in – swapping variant used for priority-based scheduling algorithms;
lower-priority process is swapped out so higher-priority process can be loaded and
executed.
🠶 Major part of swap time is transfer time; total transfer time is directly
proportional to the amount of memory swapped.

🠶 Modified versions of swapping are found on many systems, i.e., UNIX,

Linux, and Windows95.

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
6
🠶 Schematic…
view of swapping

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
7
…

Lecture 3: Memory Management 3/ 3/ 202

1 Cont’d
8
…process A is in memory. Then processes B and C are created or
🠶 Initially, only
swapped in from disk.

🠶 In Fig. 3-4(d) A is swapped out to disk. Then D comes in and B goes out.

🠶 Finally A comes in again. Since A is now at a different location, addresses

contained in it must be relocated, either by software when it is swapped in or
(more likely) by hardware during program execution. For example, base and
limit registers would work fine here.

Lecture 3: Memory Management 3/ 3/ 202

1 3.2.3. Partitioning
9
 An early method of managing memory
 Pre-virtual memory
 Not used much now

 But, it will clarify the later discussion of virtual memory if

we look first at partitioning:

Virtual Memory has evolved from the partitioning

methods

Lecture 3: Memory Management 3/ 3/ 202

20 Cont’d
…
🠶 There are two types of
partitioning:

1. Fixed partitioning

2. Dynamic partitioning

Lecture 3: Memory Management 3/ 3/ 202

2 Cont’d
1
… memory into
🠶 Partition main
a set of non overlapping
regions called partitions
🠶 Partitions can be of equal
or unequal sizes

Lecture 3: Memory Management 3/ 3/ 202

2 Cont’d
2
…
1. Fixed partitioning
🠶 Equal-size partitions
🠶 Any process whose size is less than or equal to the partition size can be
loaded into an available partition.

🠶 if all partitions are occupied, the operating system can swap a process out
of
a partition

🠶 a program may be too large to fit in a partition. The programmer must then
design the program with overlays

Lecture 3: Memory Management 3/ 3/ 202

2 Cont’d
3
… Problems
🠶 Fixed Partitioning

 A program may not fit in a partition.

 Main memory use is inefficient.

🠶Solution – Unequal Size Partitions

Lecture 3: Memory Management 3/ 3/ 202

24 Cont’d
…
2. Dynamic Partitioning
🠶 Partitions are of variable length and number
🠶 Process is allocated exactly as much memory as required

Dynamic Partitioning Example

 External Fragmentation

🠶 Eventually holes are formed in main memory. This is

called external fragmentation

Lecture 3: Memory Management 3/ 3/ 202

25 Cont’d
🠶 …
Dynamic partitioning example

🠶 A hole of 64K is left after loading 3 processes: not enough room for another process
🠶 Eventually each process is blocked. The OS swaps out process 2 to bring in process
4

Lecture 3: Memory Management 3/ 3/ 202

26 Cont’d
🠶 …
Dynamic partitioning example

🠶 another hole of 96K is created

🠶 Eventually each process is blocked. The OS swaps out process 1 to bring in again process 2 and another hole of 96K is
created...
🠶 Compaction would produce a single hole of 256K

Lecture 3: Memory Management 3/ 3/ 202

2 3.2.4. Placement Algorithm
7
 Operating system must decide which free block to allocate to a process
🠶 Best-fit algorithm
 Chooses the block that is closest in size to the request
 Allocate the smallest hole that is big enough; must entir
search list, unless ordered by size. e
 Produces the smallest leftover hole

🠶 First-fit algorithm
 Scans memory form the beginning and chooses the first available block that is large
enough
 Fastest

🠶 Next-fit
 Scans memory from the location of the last placement

🠶 worst fit
 Allocate the largest hole; must also search entire list. Produces the largest leftover hole

Lecture 3: Memory Management 3/ 3/ 202

28 Relocation
🠶 The programmer does not know where the program will be placed in memory when it
is executed,

🠶 it may be swapped to disk and return to main memory at a different location (relocated)

Lecture 3: Memory Management 3/ 3/ 202

29 3.3. Virtual Memory
🠶 is a technique that allows the execution of processes which are not
completely available in memory.

🠶 The main visible advantage of this scheme is that programs can

be larger than physica l memory.

🠶 separation of user logical memory from physical memory.

 This separation allows an extremely large virtual memory to be provided
for programmers when only a smaller physical memory is available.
 Only part of the program needs to be in memory for execution.
 Logical address space can therefore be much larger than physical
address space.
 Need to allow pages to be swapped in and out.

Lecture 3: Memory Management 3/ 3/ 202

30 Cont’d
…

Lecture 3: Memory Management 3/ 3/ 202

3 Cont’d
1
🠶 … can be implemented
Virtual memory
via:
🠶 Demand paging
🠶 Demand segmentation

Lecture 3: Memory Management 3/ 3/ 202

3 3.3.1. Demand paging
2
🠶 a demand paging system is quite similar to
a paging system with swapping.

🠶 When we want to execute a process, we swap it into memory.

Rather than swapping the entire process into memory, however, we
use a lazy swapper called pager.

🠶 When a process is to be swapped in, the pager guesses which

pages will be used before the process is swapped out again.

🠶 Instead of swapping in a whole process, the pager brings only

those necessary pages into memory.

🠶 Thus, it avoids reading into memory pages that will not be used
in anyway, decreasing the swap time and the amount of
physical memory needed.

Lecture 3: Memory Management 3/ 3/ 202

33 Cont’d
🠶 … into memory only when it is needed.
Bring a page
🠶 Less I/O needed
🠶 Less memory needed
🠶 Faster response
🠶 More users
🠶 Page is needed => reference to it
🠶 invalid reference => abort
🠶 not-in-memory => bring to memory

🠶 Divide logical memory into blocks of same size called

pages.

Lecture 3: Memory Management 3/ 3/ 202

34 Example of paging

Lecture 3: Memory Management 3/ 3/ 202

35 Advantage of DP
🠶 Following are the advantages of Demand Paging

 Large virtual memory.

 More efficient use of memory.
 Unconstrained multiprogramming. There is no limit on
degree of multiprogramming.

Lecture 3: Memory Management 3/ 3/ 202

36 Dis-Advantage of DP
🠶 Following are the disadvantages of Demand Paging

 Number of tables and amount of processor overhead for handling page

interrupts are greater than in the case of the simple paged management
techniques.

Lecture 3: Memory Management 3/ 3/ 202

37 Page replacement algorithm
🠶 Page replacement algorithms are the techniques using which
Operating System decides which memory pages to swap out, write to
disk when a page of memory needs to be allocated.

🠶 Evaluate algorithm by running it on a particular string of

memory references (reference string) and computing
the number of page faults on that string.

🠶 Reference String
The string of memory references is called reference string.
🠶 Want lowest page-fault rate.

🠶 We’ve the following page replacement algorithm:

Lecture 3: Memory Management 3/ 3/ 202

38 First in First out (FIFO)
algorithm
🠶 Oldest page in main memory is the one which will be selected
for replacement.

🠶 The operating system maintains a list of all pages currently in

memory, with the most recent arrival at the tail and the least
recent arrival at the head. On a page fault, the page at the head is
removed and the new page added to the tail of the list. Oldest
page in main memory is the one which will be selected for
replacement.

🠶 Easy to implement, keep a list, replace pages from the tail and
add new pages at the head.
Lecture 3: Memory Management 3/ 3/ 202
39 Cont’d
…

Lecture 3: Memory Management 3/ 3/ 202

40 Optimal page replacement algorithm
🠶 An optimal page-replacement algorithm has the
lowest page-fault rate of all algorithms.

🠶 The optimal page replacement algorithm says

that the page with the highest label should be
removed. If one page will not be used for 8 million
instructions and another page will not be used for
6 million instructions, removing the former.

🠶 Use the time when a page is to be used.

Lecture 3: Memory Management 3/ 3/ 202

4 Cont’d
1
…

Lecture 3: Memory Management 3/ 3/ 202

42 Least recently used(LRU) algorithm
🠶 Page which has not been used for the longest time
in main memory is the one which will be selected
for replacement.

🠶 Easy to implement, keep a list, replace pages

by looking back into time.

Lecture 3: Memory Management 3/ 3/ 202

43 Cont’d
…

Lecture 3: Memory Management 3/ 3/ 202

44 Cont’d
… algorithm
4.Page Buffering

5.Least frequently Used(LFU)

algorithm

6.Most frequently Used(MFU)

algorithm

Lecture 3: Memory Management 3/ 3/ 202

45 Segmentation
🠶 Segmentation is a technique to break memory into logica l
pieces where each piece represents a group of related
information.

🠶 Segmentation can be implemented using or without using

paging.

Lecture 3: Memory Management 3/ 3/ 202

46 Segmentation
🠶 A program is a collection of segments. A segment is a
logical unit such as:
 main program,
 procedure,
 function,
 method,
 object,
 loc al variables, global variables,
 co mmon bloc k,
 stack,
 symbol table, arrays

Lecture 3: Memory Management 3/ 3/ 202

47 Segmentation

Lecture 3: Memory Management 3/ 3/ 202

End of Chapter
Three

Lecture 3: Memory Management 3/ 3/ 202