Transcript Memory Management - www.gregvogl.net

Memory Management
Operating Systems
Lecture 4, April 3, 2003
Mr. Greg Vogl
Uganda Martyrs University
Overview
Fixed and Variable Partition
 Paging
 Segmentation
 Virtual Memory and Page Replacement
 Segmented Paging
 Protection and Sharing
 DOS and UNIX Memory Management

April 3, 2003
Operating Systems: Memory
Management
2
Sources
Ritchie Ch. 5-7
 Burgess 5.1-2
 Solomon Part 6

April 3, 2003
Operating Systems: Memory
Management
3
What is stored in memory?
Operating system code and data
 User program code
 User program data


Process Control Blocks
Stack for executing subroutines
 Memory mapped I/O: device drivers
 Screen/display memory (Video RAM)

April 3, 2003
Operating Systems: Memory
Management
4
Memory management goals/tasks

Manage several processes at same time
Load into memory, swap out to disk
 Run processes quickly, use available memory


Protect most processes from each other


But allow some processes to share memory
Ease memory management for programmer
Allocate memory in contiguous logical blocks
 Map logical addresses to physical addresses

April 3, 2003
Operating Systems: Memory
Management
5
Fixed partition memory

Each process gets fixed partition of memory


Use different partition sizes


Usually the OS is put at the bottom (address 0)
Accommodates different possible process sizes
Don’t let a process harm another’s memory

Check that the addresses are in its partition
Every
partition has unused (wasted) space
Not enough space for big new processes?
April 3, 2003
Operating Systems: Memory
Management
6
Variable partition memory
Allocate the memory each process needs
 Free the space of a terminated process
 Put new processes in empty “holes”

Adjacent holes can be merged
 About 2x as many processes as holes
 Holes maybe not right size for new processes
 How to choose a hole to put in a new process?

April 3, 2003
Operating Systems: Memory
Management
7
Storage placement policies

Best fit



Worst fit



Put new process in largest possible hole
Reduces number of big holes, creates few small ones
First fit (or next fit)



Put new process in smallest possible hole
Remaining hole is as small as possible
Put new process in first (or next) hole big enough to fit
No overhead of finding min/max hole sizes
Which is best? Tradeoff: speed vs. space
April 3, 2003
Operating Systems: Memory
Management
8
Memory implementation
Functions to allocate, deallocate, reallocate
 UNIX uses malloc(), free(), realloc()
 C++ uses new and delete operators
 Lists keep track of allocated and free blocks


Keep lists of various-sized holes (powers of 2)
April 3, 2003
Operating Systems: Memory
Management
9
Fragmentation

Gaps of unused storage space
Occurs in all storage devices (memory, disk)
 Wastes space, may also reduce performance


Internal fragmentation
Unused space within a process or block
 Can occur if word size > smallest data size


External fragmentation

Unused space between processes or blocks
April 3, 2003
Operating Systems: Memory
Management
10
Compaction (defragmentation)


Join together used memory; combine holes
Move allocated blocks to an end of memory


Calculate distance the block will move
Add to pointers, then move the data
 Need
to move a lot of things in memory
 Need to find and move all pointers
 Need to suspend processes until done
 Cannot use in time-critical systems
April 3, 2003
Operating Systems: Memory
Management
11
When/how often to compact?
When any process terminates
 When there is no more free memory
 At fixed intervals
 At user(s) request

April 3, 2003
Operating Systems: Memory
Management
12
Coalescing holes

Don’t coalesce


Give entire hole (maybe used later by realloc)
Buddy system
Combined buddies align in powers of 2
 When (de)allocating do the buddy block too

April 3, 2003
Operating Systems: Memory
Management
13
Garbage Collection
Find inaccessible blocks, add to free list
 Conservative

Treat pointer-like memory addresses as pointers
 Not all garbage found


Reference count
Each block stores a count of pointers to itself
 When a block’s count is 0, free the block
 Does not detect circular lists of garbage

April 3, 2003
Operating Systems: Memory
Management
14
Mark and sweep

Algorithm
Mark used blocks using depth-first search
 Sweep (free) unused blocks and compact


Disadvantages
 Not
helpful if memory is almost full
 Must load many swapped pages into memory
April 3, 2003
Operating Systems: Memory
Management
15
Generational
Divide memory into spaces
 Objects are usually short- or long-lived
 Keep long-lived objects in their own spaces
 Clean out mostly empty spaces
 Copy objects to other spaces when accessed

April 3, 2003
Operating Systems: Memory
Management
16
Paging
Each process composed of fixed-size pages
 Memory is also divided into pages (frames)
 Process pages can go anywhere in memory
 No external fragmentation
Internal fragmentation ~ page size


(a process will not usually use all of each page)
Need
April 3, 2003
to keep track of page locations
Operating Systems: Memory
Management
17
Implementing paging

Logical address = page number + displacement
 E.g. 32 bit addr. = 20 bit page no. + 12 bit disp.
 4 GB of addresses: a million pages, 4 KB each

Page table translates page no. to frame no.

Implemented as array of memory page numbers

Page address + displacement  physical address
April 3, 2003
Operating Systems: Memory
Management
18
Segmentation
Each process has variable length pieces
 Segment size determined by programmer

Each subroutine or data takes one or more
 Reflects logical/modular process structure
 No internal fragmentation
 Improved performance (locality of reference)
 External fragmentation

April 3, 2003
Operating Systems: Memory
Management
19
Implementing segmentation

Logical address = segment reference + displacement

Process segment table is like page table

Each segment entry has base address and length

Base address + displacement  physical address
 If
April 3, 2003
displacement > length, segmentation fault!
Operating Systems: Memory
Management
20
Virtual memory
April 3, 2003
Operating Systems: Memory
Management
21
Virtual memory
Process loaded in separate parts
 Dynamic address translation at run time
 Not need all of process in memory to run it
 Only currently accessed code & data pages
 Rest of process stays in secondary storage

Windows reserves a swap file (win386.swp)
 UNIX/Linux often uses a swap partition

April 3, 2003
Operating Systems: Memory
Management
22
Virtual memory benefits
More processes keeping processor busy
 Memory and disk space more fully used
 Few pages of a process needed at one time


Modular programs have locality of reference
Virtual memory > real memory
 A process memory can be > real memory
 Programmer not limited by real memory

April 3, 2003
Operating Systems: Memory
Management
23
Virtual memory using paging

Resident set = a process’s pages in memory
Demand paging: only load pages when needed
 When a required page is not in memory
 A page fault generates an interrupt to request it
 If no free page frames, replace an existing one


Separate page table for each process
Maps page numbers to frame numbers
 Page table register points to process page table

April 3, 2003
Operating Systems: Memory
Management
24
Virtual memory costs
Complexity,
hardware and OS support
Page table takes a lot of space

Must itself be stored in virtual memory
Overhead
of swapping is large
 Too
many page faults can cause thrashing
 Find optimum number of active processes
 Resident sets proportional to process sizes
April 3, 2003
Operating Systems: Memory
Management
25
Page size

How large should pages be? Tradeoffs:
If too small, page table is too big
 If too large, internal fragmentation is too big
 Must be a power of 2 for easy addressing


Pages in most systems are 2 or 4 KB
April 3, 2003
Operating Systems: Memory
Management
26
Page replacement policies
A page is removed from memory, replaced
 Present bit: 1 if in real memory
 Modified bit: 1 if page is modified (“dirty”)


write to secondary storage before replacing
Optimal policy can be known in retrospect
 If performance near optimal, good enough
 Policies: LRU, NRU, FIFO, Clock

April 3, 2003
Operating Systems: Memory
Management
27
Least recently used (LRU)
Replace page not referenced the longest
 Frame is given time stamp when referenced
Overhead for time stamp and finding oldest
Linked list would also have big overhead

April 3, 2003
Operating Systems: Memory
Management
28
Not recently used (NRU)
“page referenced” bit
 All bits are set to 0 periodically
 Bit is set to 1 when page is used
 Any page with 0 can be replaced

April 3, 2003
Operating Systems: Memory
Management
29
First-in first-out (FIFO)
Remove page in memory longest
 Easy to implement using linked list queue
Bad performance: evicts heavily used pages

April 3, 2003
Operating Systems: Memory
Management
30
Clock or second chance
Circular linked list similar to queue
 Add used bit, set to 0 when loaded
 Set used to 1 when referenced
 Use pointer to head of list
 When replacement needed, look for a 0
 Set any 1s to 0
 Same as FIFO but leave recently used pages

April 3, 2003
Operating Systems: Memory
Management
31
Translation lookaside buffer
A memory cache for page table entries
 Hardware buffer in fast storage
 If not in buffer, look in page table as usual
 Holds both virtual and real page numbers
 Associative lookaside buffer often also used


Maps virtual page no. to real page frame no.
April 3, 2003
Operating Systems: Memory
Management
32
Virtual memory using segments
 Facilitates

use of dynamic memory
Segments can grow or be relocated
 Facilitates
process sharing of code and data
 Logical structure ~ physical structure

Reinforces locality principle, good performance
April 3, 2003
Operating Systems: Memory
Management
33
Implementing virtual segments

Virtual address = segment number + displacement
Seg. table register points to current process
 Segment descriptor (table entries) include

Segment base address
 Segment size (limit) to check for address errors
 Bits: in memory, used, rwx access protection

April 3, 2003
Operating Systems: Memory
Management
34
Paged segmented memory
Used in many modern operating systems
 Each segment has whole number of pages

Logical pages mapped to physical pages
 Programmer works with segments
 Operating system manages pages


Virtual address = segment no. + page no. + displacement
One segment table per process, s.t. register
 One page table per segment

April 3, 2003
Operating Systems: Memory
Management
35
Paged segmented memory
April 3, 2003
Operating Systems: Memory
Management
36
Sharing

Sharing
Threads share process info. (PCB, code)
 Shared libraries e.g. dlls in Windows, stdio in C
 Segments shared by processes

April 3, 2003
Operating Systems: Memory
Management
37
Memory Protection

Protection violations that produce errors:
address < base address
 address > limit register + base address
 displacement > page/segment size
 page/segment no. > no. of pages/segments
 read/write/execute segment not permitted

April 3, 2003
Operating Systems: Memory
Management
38
MS-DOS
Designed for Intel CPUs w/ 16-bit registers
 DOS limited at first to 64 KB, then 1 MB



Processes have at least 4 64-KB segments


16 bit addressing, left shifted 4 bits
segment registers: code, data, stack, extra
Process switching is possible
One awakens, the other goes to sleep
 First-fit to find free memory for each segment

April 3, 2003
Operating Systems: Memory
Management
39
MS-DOS memory map
Early DOS memory had fixed uses
 0-640 KB



640 KB-1 MB


DOS files, device drivers, user program(s)
Video RAM, ROM BIOS
1 MB-1MB + 64 KB

High Memory Area: parts of OS
April 3, 2003
Operating Systems: Memory
Management
40
Overlays
Used to divide up a large program
 Process root module is always loaded
 Infrequently used routines put in overlays
 Separate modules use same memory area
 Only one can be loaded at a time

April 3, 2003
Operating Systems: Memory
Management
41
Extended/expanded memory
How can DOS access > 1 MB memory?
 Extended memory: above 1 MB
 Expanded Memory System (EMS):

use memory board, expanded memory manager
 1 MB has 64 16-KB page frames
 Up to 32 MB of additional 16-KB pages
 Address references redirected above 1MB

April 3, 2003
Operating Systems: Memory
Management
42
Windows 3.1

Modes
Real: Intel 8086, 640 KB
 Standard: 286, up to 16 MB, task switching
 Enhanced: 386 virtual memory, multitasking

16-bit segmented addressing (like DOS)
 Win16 API
 DLLs used by applications and Windows

April 3, 2003
Operating Systems: Memory
Management
43
Windows 95, NT

32 bit memory, 4 GB total address space
not segmented
 2 GB process memory
 2 GB system memory




paged, non-paged, physical addressing
64-bit processors and OS are now in use
Win32 API

Win32s has same interface but uses 16 bit code
April 3, 2003
Operating Systems: Memory
Management
44
UNIX

A process has three segments




Text (executable code)
Data (initialised, uninitialised)
Stack (local procedure data and parameters)
Processes can share segments (text, data)
April 3, 2003
Operating Systems: Memory
Management
45
UNIX virtual memory
pages (typically 4 KB)
 Page daemon counts number of free frames
 If too few, remove pages using clock
 If many page faults, remove LRU processes
 Reload processes swapped out a long time

April 3, 2003
Operating Systems: Memory
Management
46