Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Operating Systems > Memory Management > Flashcards

Memory Management Flashcards

1
Q

mono-programming

A

no memory abstraction
Naive approach: Move each program to a dedicated region
Relocation problem

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

base register

A

operates dynamic allocation

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

limit register

A

enforces protection

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

swapping issue

A

may lead to memory fragmentation → Memory compaction → empty chunks to small to be used

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

problem: allowing extra room for process growth

A

issue: how much room?
memory usage vs. OOM risk

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

What to do on OOMs?

A

kill process
relocate process
swap out

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

bitmap memory allocation

A

finding holes requires slow scanning
slow in finding holes of a certain length

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

list memory allocation

A

slow allocation, slow deallocation
holes sorted by address for fast coalescing

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

linked list memory management

A
  • In practice, a doubly linked is often used ⇒ makes freeing easy
    • Can easily check if previous free
    • Can easily adjust the pointers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

first fit

A

take first fitting hole

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

next fit

A

take next fitting hole
slower than first fit in practice

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

best fit

A

take best fitting hole
prone to fragmentation

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

worst fit

A

take worst fitting hole -> maximise remains
poor performance in practice

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

quick fit

A

keep holes of different size
poor coalescing performance

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

buddy allocation scheme

A

improves quick fit’s coalescing performance

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

buddy allocator

A

Fast and limits external fragmentation but considerable internal fragmentation
Often combined with other allocators
So slab allocator gets memory from buddy and parcels this out to callers of kmalloc()

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

slab allocator

A
  • Allocation + freeing of objects of the same type: very common in OS
    • Speed is of the essence
    • Unfortunately, allocating, initializing, and destroying objects all take timeE.g., list of free chunks → allocation requires traversing list to find a chunk of sufficient size
  • Goal:
    • make metadata for allocator (e.g., to track what memory is free) very fast
    • cache as much as possible
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

SLABs

A
  • slab allocator supports memory allocation for kernel
  • kernel needs many different temporary objects: e.g. dentry
  • temporary kernel objects
    • can be both small and large
    • are often allocated and often freed (efficiency is crucial)
  • the buddy allocator, which operates with areas composed of entire frames of memory, is not suitable for this
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

paging

A
  • Divide physical and virtual memory into pages of fixed size (e.g. 4096 bytes)
  • Translate virtual pages into physical pages (frames)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

total physical memory size

A

page frame * number of frames

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

32 bit systems

A
  • 32 bit address space and 32 page table entries (PTEs)
  • 20 bits for address + 12 to encode other things
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

64-bit systems

A
  • really: 48-bit or 57-bit address space and 64-bit PTEs
  • 2^48 bytes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

two level page table (32 bit)

A

20 bits ⇒ split into two 10 bit parts: the first 10 bits are used as an index to the top-level page table; the second 10 bits are used as an index to the second-level page table

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

four level page table

A

page global directory → page upper directory → page midlevel directory → pte → page
each pte points to the base of the next level → 9 bits give an offset
5 memory accesses needed for each memory access: each table address and the page itself

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

inverted page tables

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

Translation Lookaside Buffer

A
  • Problem: MMU has to translate every single memory access → Performance problem
  • Solution: Cache previous translations(virtual to physical), hoping programs exhibit a high degree of locality.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How many TLBs?

A
  • Super expensive memory: small number of entries (e.g., 64-128)
  • Sometimes separate entries for huge (2MB) pages and normal (4KB) pages
  • Often separate TLBs for code and data
  • 1 per every CPU, but sometimes multiple levels of TLB (L1 TLB vs L2 TLB)
  • separate TLBS for code and data ⇒ 2 per core
28
Q

When to flush TLB?

A
  • When entries change
  • Traditionally: at context switch
    • when you change virtual to physical mapping i.e. when you change the process
  • Improvement: tag TLB entries with id of process (no need to flush if no other process uses your id) → only flush entries when new data is being accessed but not at context switch
29
Q

When to expect many TLB misses?

A
  • after flushes → no entries to be found
  • when the program exhibits little locally - very little addresses in the same area
30
Q

When not to flush?

A

global flag set

31
Q

Software- vs. hardware-managed TLB

A
  • Flexibility vs. EfficiencyE.g., OS may preload TLB entries that it expects to need later (say the entries for a server to which current process sends msg)
32
Q

TLB miss handling

A
  • Walk page tables to find the mapping
    • If mapping found, fill new TLB entry (soft miss)
    • If mapping not found, page fault (hard miss)
33
Q

OS PF handling, cases

A
  • Access violation (segmentation fault)
  • Legal access, PF handler needs to fix up page tables:
    • The page is already in memory (minor PF) OR
    • The page must be fetched from disk (major PF)
34
Q

Page Replacement hw support

A

PTE bits: modified and referenced

35
Q

pr optimal

A
  • Replace page that will be referenced as far in the future as possible
  • Can this algorithm be implemented in practice? Nope
36
Q

pr random

A

replace a random page

37
Q

NRU

A
  • Classes of pages:
    Class 0: R=0, M=0
    Class 1: R=0, M=1
    Class 2: R=1, M=0
    Class 3: R=1, M=1
    (r - referenced, m - modified)
  • Periodically clear R bit for all the pages (set to 0)
  • Replace a page at random, but prioritise class 0, then class 1, etc.
    ⇒ replace the least expensive one
38
Q

FIFO

A

build queue of (faulting) pages and replace the head

39
Q

pr second chance

A
  • Improved FIFO to preserve important pages
  • For each visited page:
    • If R=0 then replace page
    • If R=1 then set R=0 and move page to
      tail
40
Q

pr clock

A
  • Hand points to oldest page
  • When a page fault occurs, the page the hand is pointing to is inspected
  • the action depends on the R bit:R = 0 ⇒ evict the pageR = 1⇒ clear R and advance hand
41
Q

pr LRU

A
  • Idea: Replace page that has been unused for the longest
    • Good predictor for optimal in many (but not all) cases
    • Can LRU ever perform worse than random?
  • HW-assisted solutions:
    • Maintain an ordered page list at each reference
      • Head is LRU page
    • Maintain reference timestamps in PTEs
      • Oldest-timestamp PTE points to LRU page
    • expensive in hardware ⇒ rarely implemented in practice
42
Q

pr NFU

A
  • Maintain per-page counters and periodically add (and clear) the R bit to every counter
  • Replace the page with the lowest counter
  • Problem: NFU never “forgets” pages
    • some pages might have been used a lot before, but are no longer being used ⇒ takes a long time to replace them
43
Q

pr aging

A
  • Improve NFU by:
    • Add R bit to the leftmost bit
    • Shifting counters to the right
  • Offers lower temporal resolution than “real” LRU
  • CLOCK (and variations) more often used in practice
44
Q

working set
w(k, t)

A

set of pages that a process is currently using

  • the set of pages used by the k most recent memory references
  • The function w(k, t) is the size of the working set at time t
45
Q

If (WS in memory) ->

A

few page faults

46
Q

If (memory too small for WS) →

A

If (memory too small for WS) → thrashing

47
Q

thrashing

A

a process is spending more time in paging rather than in executing

48
Q

Demand paging

A
  • Lazily allocate pages to each process
  • Exploits temporal locality to avoid frequent PFs
49
Q

Pre-paging

A
  • Typically based on the working set model, i.e., the set of pages a process currently needs to execute
  • Load the process working set in memory in advance when scheduling the process to avoid frequent PFs
  • Need for working set estimation algorithms
50
Q

bss

A

block started by simple ⇒ contains all data that doesn’t need to be stored in binary

51
Q

Local allocation

A
  • Replaces only pages of the current process
  • Assumes static process memory allocation size
  • Problems:
    • A growing working set leads to trashing
    • A shrinking working set leads to wasted memory
    • memory utilisation is not as good as compared to global
52
Q

Global allocation

A
  • Replaces pages owned by any process. Strategies:
    • Treat every global page equally (or prioritize)
    • Dynamic memory balancing using working set size estimation
    • Selectively swap out processes (or OOM kill)
  • problems:
    • a process can’t control its own page fault rate - other processes can “steal” frames
53
Q

no page fault ⇒
too many page faults ⇒

A

too much memory available
too little memory

54
Q

Load Control (design issue)

A
  • Thrashing can be expected when the combined working sets of all processes exceed the capacity of memory
  • Out of Memory killer (OOM) selectively kills processes when system is low on memory
  • Less drastic approach swaps some processes to nonvolatile storage and releases those pages
    • Similar to two-level scheduling
  • Can also reduce memory usage via compaction/compression
    • Deduplication or same page merging
55
Q

Page Size (design issue)

A
  • Most paging systems support 4KB pages
    • relatively small : limits internal fragmentation / space wastage
    • not too small : limits number of pages to handle, entries in TLB
  • In addition, many support also larger pages. For instance:
    2 MB1GB
56
Q

Design Issues: Separate Instruction and Data Spaces

A
  • Most computers have a single address space shared by program and data
    Ìn the past some systems had a separate address space for instructions and data
  • Nowadays, we still see separate I and D spaces in caches and TLBs, etc.
57
Q

Design Issues: Shared Pages

A
  • Sharing improves efficiency.
  • When one process exits, OS should realise there is another user of the the page
  • Sharing data is trickier than sharing code
    • After fork system call parent and child share program and text
      • To do so efficiently, each gets its own set of page tables, pointing to the same pages
      • Pages are mapped read-only
      • When a process writes to such a page:
        make a copy
        => copy-on-write
58
Q

copy-on-write

A
59
Q

Design Issues: Shared Libraries

A
  • Sharing libraries is very common
    • easy: read-only
  • Typically through Dynamic Link Libraries (DLLs)
    • often as position-independent code
60
Q

Design Issues: Memory mapped files

A
  • Shared libs special cases of memory mapped files
  • As pages are touched→ demand paged from disk
  • When process exits→ write dirty pages back to disk
61
Q

Design Issues: Cleaning policy

A
  • Paging works well if plenty of free pages. What if we run short?
  • Indirect reclaim: Paging daemon sleeps and then evicts pages if free pages are in short supply
    • Flush dirty pages
    • Leave them in memory – easy reuse
62
Q

Page Fault Handling

A
  1. The hardware traps to kernel, saving program counter on stack.
  2. Assembly code routine started to save registers and other volatile info. Calls the page fault handler
  3. System discovers page fault has occurred, tries to discover which virtual page needed
  4. Once virtual address that caused fault is known, system checks to see if address valid and the protection consistent with access
  5. If frame selected dirty, page is scheduled for transfer to nonvolatile storage, context switch takes place, suspending faulting process
  6. As soon as frame clean, operating system looks up disk address where needed page is, schedules disk or SSD operation to bring it in.
  7. When disk or SSD interrupt indicates page has arrived, tables updated to reflect position, and frame marked as being in normal state.
  8. Faulting instruction backed up to state it had when it began and program counter is reset
  9. Faulting process is scheduled, operating system returns to routine that called it.
  10. Routine reloads registers and other state information, returns to user space to continue execution where it left off
63
Q

Separation of Policy and Mechanism

A

the separation is important for managing the complexity of the system.

64
Q

Memory management system is divided into three parts

A
  1. A low-level MMU handler.
  2. A page fault handler that is part of the kernel.
  3. An external pager running in user space.
65
Q

kernel page fault handler

A
  • machine independent
  • contains mechanism for paging
66
Q

external pager

A
  • machine independent
  • can implement the policy

Operating Systems (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions