Memory Management Flashcards

1
Q

Explain the concept of a memory hierarchy

A

Few MB of volatile quickly accessible expensive cache memory
Few GB of volatile medium speed medium expense main memory
Few TB of nonvolatile slow speed cheap disk memory
(May also have removable storage)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How can multiple programs be run at the same time with no memory abstraction?

A

OS saves entire contents of memory to a disk file then brings in and runs next program. This works so long as there is only one program in memory at a time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain memory addresses

A

A memory address is a memory abstraction. These are fixed length sequences of digits. This means memory location 28 in 1 program will be different to that in the memory address of another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the base and limit registers used for? What is a disavantage?

A

Base register contains the physical address where program begins in memory (tells you how far offset actual address is_ and limit register has the length of the program. Access is aborted if memory trying to be accessed is greater than or equal to limit register. The disadvantage is having to perform addition and comparison on every memory address.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What approaches have been developed to deal with memory overload?

A

1) swapping: bringing each process into memory in its entirety, running for a time then swapping it out
2) virtual memory: allows programs to run even when they are only partially in main memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain swapping

A

Bringing each process into memory in its entirety, running for a time then swapping it out to disk. If a dynamically sized process needs more space, but cannot grow and swap area on disk is full, this process will have to be temporarily suspended or killed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Is memory compaction done often?

A

No, as it requires a lot of CPU time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Who manages dynamically assigned memory?

A

The OS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How can we keep track of memory usage?

A

1) Bitmap

2) Free lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Explain memory management with bitmaps. What is the disadvantage of them?

A

Memory is divided into allocation units with each unit having a corresponding bit (0 if free, 1 if full or vice versa).
The disadvantage is that if something of size k units enters, k consecutive 0 bits must be found which is a long operation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Explain memory management with linked lists

A

Each entry in the linked list is either a hole or a process (H or P). These are sorted by address. Multiple holes in a row are combined into one.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Explain the first fit algorithm

A

Memory manager scans along until a hole of big enough size is found. This is fast as limited searching needs to be done

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Explain the next fit algorithm

A

This starts searching the list at the place it last left off, rather than the start, to find a hole of big enough size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Explain the best fit algorithm

A

Best fit searches entire list and takes the smallest adequate hole. Best fit is slower than first fit as it searches entire list. This results in wasted memory as it leaves lots of little holes, which nothing can fit in. Best fit and first fit can be same time if the list is only a list of holes (not processes)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Explain the worst fit algorithm

A

Worst fit searches entire list and takes biggest hole, such that breaking it up will cause large holes to be left.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Explain the quick fit algorithm

A

Maintains separate lists for holes of different but common sizes. Merges can be expensive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the memory allocation algorithms?

A

1) First fit
2) Next fit
3) Best fit
4) Worst fit
5) Quick fit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What solutions are available to the problem of having programs larger than memory?

A

1) Breaking programs into overlays

2) Virtual memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Explain the concept of virtual memory

A

Only parts of program have to be in main memory at once.
Each program has an address space broken into chunks (contiguous range of addresses) called pages. Pages are mapped onto physical memory, but not all pages have to be in memory to run. When program references part of address space that isn’t in physical memory, the OS will retrieve this piece and reexecute instruction after a page fault occurs.
This means that pages do not have to be in contiguous memory sections themselves.
This is the illusion that the user has all of the memory for their process. This should solve the problem of external fragmentation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Explain paging

A

This is a technique used by virtual memory systems. In this, pages are stored on disk and retrieved by OS in the case of a page fault when required. Whole pages must be sent, not parts.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are virtual addresses?

A

Each program has a virtual address space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What happens to virtual addresses on computers without virtual memory? What about computers with virtual memory?

A

Without: Virtual address is put directly onto memory bus, causing physical memory word with same address to be read/written
With: Virtual address goes to MMU that maps virtual addresses onto physical memory addresses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

With 64KB of virtual address space and 32KB of physical memory, if we get 16 virtual pages, how many page frames will there be?

A
  1. This means only 8 of the virtual pages are mapped onto physical memory at a time. Present/absent bit keeps track of which pages are physically present in memory.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What does the present/absent or valid bit do?

A

Present/absent bit keeps track of which pages are physically present in memory in the case of virtual memory being used

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Explain the mapping of virtual addresses onto physical addresses

A

Virtual address is split into virtual page number (high-order bits) and an offset (low-order bits). The virtual page number is used as an index into page table to find entry for that virtual page.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Describe the structure of a page table entry

A

Page frame number followed by present/absent or valid bit, followed by protection, followed by modified, followed by referenced, followed by caching disabled

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What does protection do in a page table entry?

A

Tells what kind of accesses are permitted. Normally this will be 2 bits: 0 for read/write, 1 for read only. This could be 3 bits however with read/write, read only and executing the page

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What does modified do in a page table entry?

A

Keeps track of page usage. This bit tells whether the page has been modified. When page is loaded back to disk, if it hasn’t been modified (clean) the version on disk doesn’t need to be altered. If this is a dirty bit, it must be reloaded to disk.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does referenced bit do in a page table entry?

A

This tells whether the page is being used or not in the case of swapping out for a page fault. If page fault occurs, it would be wiser to swap out pages not being referenced.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What does caching disabled bit do in a page table entry?

A

This allows caching to be disabled for the page

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What are the 2 major issues faced in paging?

A

1) Mapping from virtual to physical addresses must be fast

2) If virtual address space is large, the page table will be large

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Explain how the TLB works

A

When MMU needs to translate virtual memory address, the hardware checks to see if virtual memory address is in TLB. The page frame is taken directly from TLB (no need to visit the page table).
If the virtual memory address isn’t in the TLB, the MMU will look up the page in the page table, and evict an entry in TLB, replacing it with this memory address. The alternative would be to hand control to OS to locate this page.
This is a sort of memory cache holding recently accessed page table entries.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

How do we process a TLB miss?

A

Go to page table and perform indexing operations to locate page being referenced

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What’s the difference between a hard miss and soft miss?

A

Hard: when page isn’t in memory or TLB
Soft: when page isn’t in TLB, but is in memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What 2 types of TLB misses are there?

A

Hard: when page isn’t in memory or TLB
Soft: when page isn’t in TLB, but is in memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What page tables are available for large memories?

A

1) Multilevel page table

2) Inverted page table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is the address in a paged system?

A

page number ∗ page size + offset where page size is 2 raised to the power of the number of bits in the offset
To map to physical page frame: take new page fram * page size (same as above) + offset (same as above)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is the goal of memory management?

A

Abstraction

Keep track of what parts of memory are free and what parts aren’t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Explain external fragmentation

A

When process exits or is swapped out it leaves a region of memory free. Unless a neighbour is already free, this space can only hold process of equal or smaller size. Something smaller will leave even smaller hole causing lots of tiny little holes which arent usable

40
Q

What are the 2 main concepts to virtual memory?

A

Segmentation and paging

41
Q

How does the MMU work?

A

When CPU accesses memory, it gives the virtual address to the MMU. MMU sends corresponding physical address to memory as the target of read/write operation.
Typically, the CPU of code executing in kernel mode can provide a way of directly accessing memory, avoiding MMU.

42
Q

Do virtual and physical address spaces have to be the same size?

A

No

43
Q

How many bits are there in a virtual address?

A

Almost always some power of 2

44
Q

What do number of bits in a system correspond to?

A

Number of addresses

45
Q

Where is OS located in memory?

A

Always at bottom

46
Q

If a virtual page is moved to disk then back to memory again, will it be in the same spot?

A

Not necessarily

47
Q

What is internal fragmentation?

A

The amount of memory needed by a process rarely is an exact multiple of page size, but a process must be allocated an integer number of pages. This means memory is wasted - a fraction of each page for each process.

48
Q

What are the differences between internal and external fragmentation?

A

Internal fragmentation occurs within a process and relates to page size, while external fragmentation is outside a process and refers to the fragments of memory left over during swapping into/out of memory.

49
Q

Can the size of a page change?

A

No, these are fixed

50
Q

What are the two parts of a virtual address?

A

Virtual page number and an offset within that page (that tells us where in the page the instruction occurs). Offsets carry through in the map.

51
Q

How many bits is 1kb?

A

1024 (2^10). So 2kb is 2048 (2^11) bits and 4kb is 4096 2(^12) bits

52
Q

How do we get offset from page size?

A

2^offset = page size

53
Q

How do we get page size from offset?

A

page size = 2^offset

54
Q

How do we get page size from frame size?

A

They’re the same

55
Q

How do we calculate the size of page table/number of page table entries?

A

Size of page table = bits of address - offset

56
Q

What happens if the present/absent bit is 0 in a page table entry or the permission (protection) bit does not match what is expected?

A

Page fault - if this is do with permission, process will terminate

57
Q

Explain multilevel page tables

A

Instead of storing the entire page table in memory, why not have some sort of a pointer where we break it up? So you dont have to load whole thing is. Have some indirection pointers.

58
Q

Is there a page table per process?

A

Yes

59
Q

Why does each process need its own page table?

A

Protection

60
Q

Name something stored in MMU registers

A

If a directory is used, physical address of directory and length of directory and length of each fragment.

61
Q

How can we distinguish between user and system spaces of a virtual address?

A

System space: high bit set
User space: high bit clear
Could also use an extra permission bit in PTE (page table entry)

62
Q

When can processes access system space?

A

Only when making system call

63
Q

Where is the page fault handler? Why?

A

Main memory. Otherwise it would have a page fault trying to find itself.

64
Q

What are the 2 types of locality?

A

Spatial: If a location was recently referenced, locations NEAR it are likely to be referenced soon.
Temporal: If a location was recently referenced, it is likely to be referenced again soon
These are orthogonal.

65
Q

What page replacement policies exist?

A

Optimal policy: from all pages in main memory, pick page whose next reference is as far forward in future as possible. Unfortunately, this would require knowledge about actions of processes, which may not be available. Provides bound on how good algorithm can be.
Random policy: pick page at random to remove. High bound on how bad algorithm can be. In garbage collector cases, you can’t get better than this bound. This ignores spacial and temporal locality.
Working set policy: remove p

66
Q

Explain the FIFO algorithm

A

First in first out works by selecting page that has been in main memory the longest and removing it. Poor performance as it ignores principle of locality

67
Q

Explain principle of locality

A

Page replacement algorithms rely on the future following trends of the past. There are two types of locality: spatial and temporal

68
Q

Explain LRU algorithm

A

Least recently used. Picks page that is unused for the longest time.

69
Q

Explain LFU algorithm

A

Least frequently used. Use a counter to check how many times this page has been used. Couple with clock to remove page.

70
Q

What page removal algorithms exist?

A

FIFO
LRU
LFU
The clock algorithm

71
Q

Explain the clock algorithm

A

Slowly sweeps through memory clearing the ‘referenced’ bit of each page. If this bit is still clear when the clock comes back around to it, this means the page wasn’t used in this time and is candidate for replacement. It would be a good idea to use 2 hands - one resetting referenced bits and 1 slightly behind checking them. This will stop regularly accessed junk pages coming through

72
Q

What is a page in the free page pool?

A

One that is flagged as being ‘okay’ to be swapped out to disk. These are potential pages which can be swapped out

73
Q

Explain the free page pool

A

This tries to anticipate what will happen in long run. Maintain a list of pages that are okay to be swapped out - if a page needs to be swapped, we can pick one from this pool.

74
Q

What is the page write daemon?

A

Paging in a page from a dirty page frame costs 2 disk accesses: 1 to write old page to disk and 1 to read new page. If paging disk is unused, daemon can find old dirty pages, write them to disk and put them in free page pool

75
Q

Explain thrashing

A

If number of processes in memory is too high, each process will only have a few page frames, meaning that page fault rates will be high. The queue of processes waiting for disk will become longer and CPU will be underused.

76
Q

How many disk access does paging in a page from a dirt frame cost?

A

2: 1 to write old page to disk and 1 to read new page

77
Q

How can we deal with thrashing

A

1) recognise that thrashing is about to happen and prevent it
2) recognise that thrashing is happening and stop it
3) we can use the working set policy

78
Q

What is the working set principle?

A

Process should not run unless set of pages containing memory (working set) regions it needs regularly is in memory

79
Q

What is a working set?

A

Set of pages containing memory pages regularly needed by a process. That is, set of pages process has referenced in last N instructions

80
Q

What should be done to a process whose working set isn’t in main memory?

A

a) have more pages allocated to it

or b) move it entirely to disk

81
Q

How do working sets work in practice?

A

We must approximate or estimate the working set. We could substitute clock tick for instruction in definition -> That is, set of pages process has referenced in last N [clock tick]

82
Q

Explain locality shift

A

Some programs can be divided into different phases that access different bits of code (eg. compiler passes). When program finishes one phase and starts another, it momentarily has sharp increase in size of working set. Page fault rate band should be adjusted to accommodate this.

83
Q

What is a page fault rate band?

A

This is the band that describes the appropriate range of pages. It lies somewhere between there being not enough (causing lots of page faults) and there being too many (I/O slow)

84
Q

Explain the working set policy

A

When processes in memory all have their working sets and there are page frame available, OS may bring in new process from disk. Alternatively, if there are no page frames available and a process doesn’t have its working set, a process must be swapped to disk

85
Q

Explain COW

A

Copy on write. Instead of copying all pages of parent process at the time of a fork, OS only copies page tables., then copies as necessary

86
Q

What is swap space?

A

Memory images of some processes may have to be kept on disk. These parts of memory are called swap space

87
Q

What is a solution to external fragmentation?

A

Memory compaction. Moving processes to one contiguous section of memory

88
Q

What are the two main concepts of virtual memory?

A

Paging and Segmentation

89
Q

Are pages and frames the same size?

A

Yes

90
Q

What are MMU checks?

A

Check selected entry from Page Table Entry has appropriate valid bit and permission bit

91
Q

How are page faults regarding memory handled?

A

If it’s due to permission, terminate process. Otherwise retrieve page from disk and load to memory.

92
Q

Why do we use the TLB?

A

It speeds up paging

93
Q

Why does each process need its only page table?

A

Security

94
Q

When can a process access system space?

A

Only when mode bit corresponding to kernel permissions is set

95
Q

Where is the page fault handler kept?

A

Must be in memory - otherwise what would happen if page fault occurred with page fault handler?

96
Q

What page replacement policies are there?

A

Optimal policy: from all the pages in main memory, pick the page whose next reference is as far in the future as possible. This requires foreknowledge of the actions of all programs, which is just about never available. Establishes the high bound on how good an algorithm can be.
Random policy: pick a page at random. Establishes the high bound on how bad a realistic algorithm can be. In some cases (e.g. during garbage collection) one cannot do better than this bound.