Operating Systems
Lecture 7 Memory Management
Memory management
Copyright By PowCoder代写 加微信 powcoder
Contiguous memory allocation
Paging non-contiguous allocation Paging implementation
Segmentation
COMP 2432 2021/2022
Memory Management
cache memory
program code of current process should be avoided.
COMP 2432 2021/2022
Aprogrammustbebroughtfromdiskintomainmemoryand loaded within a process for it to be run.
Executablecode(compiled)orsourcecode(interpreted). Recall that a process is a program in execution.
Main memory/registers are storage that CPU can directly access.
A register can be accessed in one CPU clock cycle.
A main memory access can take many cycles.
Cache sits between main memory and CPU registers to improve memory access time.
How can we manage the memory effectively so as to be shared among many processes?
How can we translate the address in a compiled program to the real address in the computer?
Is there hardware support to help with this task?
How can we protect memory to ensure correct operation?
Writing into the memory of another user must not be allowed. Accidentally writing into memory of your other processes or
Address Binding to Memory
Binding of address refers to the procedure of translating an address in the compiled program code to a memory address when the program is run.
Address binding of instructions and data to memory can happen at three different stages.
Hardware support for dynamic address mapping (e.g., base
and limit registers) is required. COMP 2432 2021/2022
Compile time
If memory location is known ahead, absolute code can be
generated.
Code must be recompiled if starting location changes.
Load time
If memory location is not known at compile time, relocatable
code must be generated.
Addresses are defined after program is loaded.
Execution or run time
If a process can be moved during execution from one memory
segment to another, binding must be delayed until run time.
Address Binding to Memory
Program (.com)
Main memory
Program (.exe)
Main memory
1000: lda 1200 1002: sub #10 1004: sta 1200 1006: brz 1018 .. .
2000: lda 2200 2002: sub #10 2004: sta 2200 2006: brz 2018 .. .
1000: lda 1200 1002: sub #10 1004: sta 1200 1006: brz 1018 .. .
0000: lda 0200 0002: sub #10 0004: sta 0200 0006: brz 0018 .. .
Main memory
0000: lda 0200 0002: sub #10 0004: sta 0200 0006: brz 0018 .. .
COMP 2432 2021/2022
Program (.exe)
0000: lda 0200 0002: sub #10 0004: sta 0200 0006: brz 0018 .. .
Address Binding to Memory
operating system
For each process, there is a
pair of base and limit
registers that define the
address space of the
process. 300040 300040
An address generated should stay between base and base+limit.
Accesstoanaddress beyond the allocated address space is invalid.
420940 880000
This protects a process from
accessing the content of another process.
COMP 2432 2021/2022
Logical and Physical Address
Memory management technique is required to support run-time address-binding. This is because a program may move around during execution.
The key idea behind memory management is the separation of logical address and physical address.
Logical address is the address generated by the CPU, e.g. an instruction refers to an integer stored at a particular address. This is also called a virtual address when it is different from the physical address.
Physical address is the address sent to the main memory.
The logical and physical addresses are the same in both compile-time and load-time address-binding schemes, but the logical and physical addresses differ in run-time address-binding scheme.
Only the translation from virtual to physical address needs to be changed when a program moves around. COMP 2432 2021/2022
Memory Management Unit
Each virtual address must be mapped or translated into a physical address in run-time binding scheme and this occurs once to fetch an instruction and once to fetch each operand.
This translation must be very fast and efficient, so it must be done by hardware.
The hardware device that maps virtual to physical address is called the memory management unit or MMU.
In the simplest MMU solution, the value in a special relocation register is added to every logical address generated by a user process to form the physical address when it is sent to memory. The relocation register is like the base register.
User process only deals with logical addresses. It never sees the real physical addresses. COMP 2432 2021/2022
Memory Management Unit
Use of relocation register for translation.
logical address
physical address
relocation register
COMP 2432 2021/2022
Memory Allocation
COMP 2432 2021/2022
Main memory is usually divided into two partitions.
Resident OS is usually stored in low memory, together with
interrupt vector and interrupt handlers.
User processes are stored in high memory.
Memory allocation is concerned with where a user process is actually placed when it is swapped/moved into main memory.
We assume that the whole process will be stored in the main memory for it to be executed.
Contiguous allocation: allocate a single block of memory of size sufficient to hold the process.
Non-contiguous allocation: chop up the process and allocate multiple blocks of memory to hold the process. The two major schemes are paging and segmentation.
Contiguous Allocation
The most straightforward solution is to allocate a single block of memory to hold a process. This is called contiguous allocation.
One single block to hold one process (single partition). Multiple blocks to hold multiple processes (multiple
partition).
A pair of registers are used to protect user processes from accidentally stepping into each other and changing operating system code and data.
The relocation register contains the value of smallest physical address for the process.
The limit register contains the range (size) of logical address space.
Each logical address must be less than the limit register.
MMU maps logical address dynamically into physical address by adding it to the relocation register. COMP 2432 2021/2022
Contiguous Allocation
Hardware support by MMU.
logical address
physical + address
limit register
relocation register
trap, addressing error
COMP 2432 2021/2022
Contiguous Allocation
Divide the memory into several partitions.
When a partition is free, a job is selected to be loaded into the partition.
Only at most n jobs can be executed if there are n partitions.
Very simple to manage.
Not effective if there are many small jobs since many partitions are only used to very small degree and total free memory is still quite large.
Multiple fixed partition
This was used by one of the earliest and classical
OS, IBM MVS, forty years ago.
Called MFT: Multiprogramming with a Fixed
number of Tasks.
COMP 2432 2021/2022
Contiguous Allocation
Multiple variable partition
Commonly used in IBM MVS.
Called MVT: Multiprogramming with a Variable number of Tasks.
A block of available memory is called a hole.
Holes of various size are scattered throughout the
When a process arrives, it is allocated memory
from a hole large enough to accommodate it.
OS maintains information about allocated partitions and free partitions (i.e. holes), often in the form of linked lists.
COMP 2432 2021/2022
Contiguous Allocation
Memory of 256K with OS consuming first 40K.
Fixed partitions of size 80K, 100K and 36K for
No restriction for MVT.
Free memory
Process Memory need P1 60K
P4 40K P5 50K
Process time 40 10
COMP 2432 2021/2022
Contiguous Allocation
10 5 10 20 15
Not large enough for P4 or P5
COMP 2432 2021/2022
P5 admitted
P3 terminated P4 admitted
P1 terminated P3 admitted
P2 terminated
Contiguous Allocation
Could admit P4
COMP 2432 2021/2022
P1 terminated
P3 admitted P2 terminated
P4 admitted
Contiguous Allocation
When a request for memory allocation arrives and if there are m holes available, which hole is to be used for the request?
First-fit: allocate the first hole that is big enough.
Best-fit: allocate the smallest hole that is big enough. Produce the smallest leftover hole.
Do not waste large holes for future large job.
Worst-fit: allocate the largest hole.
Produce the largest leftover hole.
Ensure that leftover holes are large enough to be useful.
Best- and worst-fit need to maintain a sorted list for sizes of holes or a search is needed.
First- and best-fit are normally performing better than worst-fit.
COMP 2432 2021/2022
Contiguous Allocation
Requests of 212, 417, 112, 426 arrive in that order, for the following configuration.
First-fit
Best-fit
Worst-fit
COMP 2432 2021/2022
Contiguous Allocation
Are your correct? If two requests each of 250 come, how are they handled?
First-fit
Best-fit
Worst-fit
COMP 2432 2021/2022
Contiguous Allocation
A major problem with contiguous allocation is fragmentation. Fragmentation means that memory is available, but somehow
could not be used.
ExternalFragmentation
Total memory space exists to satisfy a request but it is not
contiguous that it could not be used. It is a wastage outside partition.
InternalFragmentation
Memory internal to partition is not used (wastage inside partition).
This happens when a hole is slightly larger than requested size that the overhead to manage the small hole is not justified.
Reduceexternalfragmentationbycompaction.
Move memory content around to place all small free memory holes together to create one large block or hole.
Compaction is possible only if relocation is dynamic.
COMP 2432 2021/2022
Non-Contiguous Allocation
If size of processes vary a lot, it is very difficult to put them efficiently in memory.
For example, in real practice, it is a very hard problem to optimize the storage of a ship for goods of varying size.
It will be much more effective if sizes of all goods are similar so that they can be put in any place.
Container ships only move around fixed size containers.
In memory allocation, the best candidate to serve as a container is the page.
A page is a size of physical memory manipulated as a unit. It often corresponds to a block in the hard disk.
When memory is divided up into pages, it is no longer necessary that consecutive pages be allocated for a process. This is non-contiguous allocation.
The same concept is used in networking, to break up a message into fixed sized packets. COMP 2432 2021/2022
Physical address space may not be contiguous, though logical address space may still be contiguous.
In paging mechanism, physical memory is divided into fixed- sized blocks called frames. The size of a frame is always power of 2 (normally between 512 bytes and 8,192 bytes).
Logical memory is divided into blocks of same size as frames, called pages.
OS keeps track of all the free frames in a frame table.
To run a program of size of n pages, allocate n free frames in memory and load the program into those frames.
Sincetheframesare scattered around, a page table is used to translate logical address to physical address.
COMP 2432 2021/2022
Example: allocating 4 free frames to a process.
2 2021/2022
page number
frame number
page offset
Since each logical address generated by CPU needs to be mapped or translated into a physical address in memory, this translation must be very efficient.
This should be done with hardware support.
The logical address is divided into two parts.
Page number (p): it is used as an index into a page table to look up for base address of each frame in physical memory.
Page offset (d): it is added (or appended) to the base address to form the physical memory address.
Assume that the logical address space is of size 2m and each page (and frame) has a size of 2n.
Logical address has a size of m bits. Page number p contains mn bits.
Page offset d contains n bits.
Paging suffers from internal fragmentation.
COMP 2432 2021/2022
Paging Hardware
11001 0101101101
11110101101101
1024 bytes
COMP 2432 2021/2022
Page Table Implementation
The page table is the key for translation from logical to physical address for a process.
There is one page table for each process and it is kept in the main memory.
A hardware register, called page-table base register (PTBR), points to the page table for a process.
Context switching is fast, since only one register needs to be changed for a newly scheduled process.
Every data/instruction access requires two memory accesses: one for page table and one for data / instruction.
aside Buffer (TLB) to store recently translated logical page numbers. COMP 2432 2021/2022
This extra memory access to page table is expensive. This is solved by a hardware cache called Translation Look-
Page Table Implementation
Translationlook-asidebuffer
2432 2021/2022
11001 0101101101
11101 1011 11001 1111
10001 0111 00101 1100
01001 1010
11011 0010 01101 0110
1111 0101101101
Page Table Implementation
Translation Look-aside Buffer (TLB) is made up of high-speed associative memory (a form of cache) that allows concurrent search for a tag. The drawback is that the hardware cost is high.
TLB is inserted between the translation path from a page number to a frame number. The tag is the page number p, and the value is the frame number f.
We first look up the TLB to for the existence of p and return the value of f. If that is successful, we call it a TLB hit.
For a TLB miss, the data access cost is 2 + c. After the miss, the new pair (p,f) will be inserted into TLB for future use.
Without TLB, data access cost is 2. COMP 2432 2021/2022
Otherwise, that is a TLB miss. We will look up the page table indexed by p to get f.
For a TLB hit, the data access cost is only 1 + c, where c is the cost of cache access and c << 1.
What could be a typical value of h ? Page Table Implementation
Let the TLB hit ratio be h (0 h 1). This hit ratio depends on the number of entries (size) of TLB.
Effective memory access time is the expected time to perform a memory access.
Translation time = h x cache access time + (1 – h) x (cache access time + memory access time) = cache access time + (1 – h) x memory access time.
Effective access time = translation time + memory access time = cache access time + (2 – h) x memory access time.
Memory access time = 100 ns.
Cache access time = 20 ns.
Effective access time = 20 + (2 – h) x 100 = 220 – 100h.
If TLB hit ratio is 80%, effective access time = 140 ns.
If TLB hit ratio is 90%, effective access time = 130 ns.
If TLB hit ratio is 99%, effective access time = 121 ns.
Access latency for fast L1 cache is only 1 ns.
Accesstimeswouldbe121,111,102nsrespectively.COMP24322021/2022
Page Table Implementation
A fast recap on powers of 2 for Computing
Lecture 7 COMP 2432 2021/2022
page number
page offset
Page Table Implementation
Assume that a logical address is of 32 bits, that a page and a frame are of size 4KB, and that the main memory is of size 64MB.
m=32 (length of full logical address)
n=12 (page and frame size of 4K = 212, length of offset d)
m -n=20 (length of page number p).
There will be 64M/4K = 16384 = 214 frames, so 14 bits are needed to store the frame number (length of f =14).
Each page table entry therefore needs 2 bytes for storing this frame number.
If a small-sized process has a size of 256K, it would need 256K/4K = 64 entries in the page table, i.e., it needs a page table of size 128 bytes, i.e. 1 page for the page table.
If a medium-sized process has a size of 8M, it would need 8M/4K = 2K entries in the page table, i.e., it needs a page table of size 4K bytes, just fit inside 1 page. So 8M is the maximum process size for a small page table. COMP 2432 2021/2022
page number
page offset
Page Table Implementation
COMP 2432 2021/2022
Now assume logical address of 32 bits, page and frame size of 4KB, and main memory of size 512MB.
m=32 and n=12 (length of d) so m -n=20 (length of p).
There will be 512M/4K = 131072 frames, so 17 bits are needed
to store the frame number (length of f =17).
As it is more than 2 bytes, each page table entry needs 4
bytes (17 bits for frame number, plus other information).
If a huge process uses up the whole address space (defining
many big arrays), it could have 220 entries in the page table. The size of the page table will then be 220 x 4 bytes = 4MB.
We could not store this large page table in consecutive block of memory, so we need to find a way to handle this table.
Three possible solutions: Hierarchical paging
Hashed page table
Inverted page table
Hierarchical Paging
A logical address (on 32-bit machine with 4KB page size) is
words, break up logical address space into multiple page tables.
divided into:
apagenumberconsistingof20bits. a page offset consisting of 12 bits.
Page table is itself paged, page number is further divided into:
a 10-bit second level page number.
a 10-bit second level page offset.
We call the second level page table the outer page table.
You could have a second outer page table if needed.
Here p1 is an index into the outer page table and p2 is the displacement within the page of the outer page table.
Note that the effective memory access time will increase for
accessing several page tables.
page number
page offset
10 10 12 COMP 2432 2021/2022
Break up page table to be stored into multiple pages. In other
Memory Protection
A program may not use up all pages in page table. Some pages in may be read-only (e.g. program text).
“valid” indicates that the associated page is in process’ logical address space and is a legal page.
“invalid” indicates that the page is not in logical address space. Accessing it will generate a trap to OS.
A hardware page-table length register (PTLR) is often used to check for validity of a logical address.
COMP 2432 2021/2022
Memory protection is implemented by associating one or more protection bits with each page, e.g., we may attach a valid-invalid bit to each page table entry:
Shared Pages
Use of paging allows easy sharing of program code with private data.
One copy of read-only code is shared among processes (e.g. editor).
Each process keeps a separate copy of its private data.
Private data can ap
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com