9, 10

Question 1

What are the four functional requirements of a memory manager?

Answer 1

Abstraction

Allocation

Isolation

Memory Sharing

Question 2

What is the purpose of abstraction in a memory manager?

How does abstraction handle memory addresses?

Answer 2

To make the memory management (MM) appear larger than the physical machine memory and present it as an array of contiguously addressed bytes.

It uses an abstract set of logical addresses to reference physical memory.

Question 3

What is the allocation function of a memory manager?

Answer 3

To allocate primary memory to processes as requested.

Question 4

What is the role of isolation in memory management?

Answer 4

To enable mutually exclusive use of memory by processes, ensuring no interference between them.

Question 5

How does the memory manager handle memory sharing?

Answer 5

It enables memory to be shared by processes when required

Question 6

When is swapping used in memory management?

How does the operating system perform swapping?

Where is the swapped-out process stored?

Answer 6

Swapping is used when a program must be loaded into main memory (MM) but there is not enough room, so another process is moved to secondary storage to make room.

The OS selects a process to swap out and replaces it with another process from secondary storage. Only parts of the process space not already on disk are swapped out.

Swapped-out processes can be stored either in an arbitrary file, which introduces file management overhead, or in a special partition on the disk called the swap space, which is more efficient.

Question 7

What does the compiler/linker do during process creation regarding memory addresses?

How does the memory management subsystem handle processes loaded into physical memory?

Answer 7

It associates logical addresses to every instruction and data.

The subsystem decides what to load, when, and where. It translates logical addresses to physical addresses for each process in memory.

Question 8

How is a virtual address translated into a physical address in main memory?

Answer 8

The physical address is calculated by adding the start address of the process in physical memory to the virtual address of the data. ‘

For example, if the start address is 0x61000 and the virtual address is 0xA11, the physical address is 0x61A11.

Question 9

What is memory paging?

Answer 9

Memory paging divides the process address space into segments of identical sizes called pages.

These pages are mapped to page frames of the same size in main memory, enabling non-contiguous storage.

Question 10

What are the advantages of memory paging?

Answer 10

No external fragmentation.

Programs don’t need to be stored contiguously.

Internal fragmentation is limited to the size of one page.

Only the required pages are loaded into memory.

Question 11

How is a process stored in main memory using paging?

Answer 11

A process is divided into pages, each loaded into any free page frame in main memory. The size of a page equals the size of a page frame.

Question 12

What is internal fragmentation in paging?

Answer 12

Internal fragmentation occurs when the last page of a process does not completely fill a page frame, leading to wasted memory space.

Question 13

Example Scenario:

Assume main memory has 1300 lines, each page/frame has 100 lines, and the OS requires 280 lines. If Process P1 requires 350 lines, how many free frames remain?

Answer 13

The OS uses 3 frames (280 lines), and Process P1 uses 4 frames (350 lines). There are 13 total frames in memory, leaving 6 free frames.

Question 14

What are the remaining challenges in memory paging?

Answer 14

Keeping track of where pages are stored.

Providing a mechanism for address binding (logical to physical address translation).

Deciding which pages to load into main memory and when.

Question 15

What are “pages” and “page frames” in memory paging?

Answer 15

Pages are segments of a process’s address space, while page frames are segments of main memory.

Each page maps to a page frame for storage.

Question 16

What is the purpose of a page table in memory paging?

Answer 16

The page table keeps track of which box (page) of each pallet (process) is located on which shelf (frame) in secondary storage.

Question 17

What is one solution for keeping track of where pages are stored in memory paging?

Where is the address of the page table saved?

What is an advantage of this solution?

What is a disadvantage?

Answer 17

Maintaining a page table for each process

In the process’ process control block PCB

Easy to find a page in main memory, requiring only a single look-up in the page table.

Consumes a lot of memory if each process has tens of thousands of pages.

Question 18

What is another solution for keeping track of where pages are stored in memory paging?

Answer 18

Maintaining a single inverted page table, also called a frame table.

Question 19

What does an inverted page table record?

What is an advantage of using an inverted page table?

What is a disadvantage of using an inverted page table?

Answer 19

It records which page of which process is loaded in which frame.

Memory consumption is constant and independent of the number of processes or their size.

It is time-consuming to find the location of a page in main memory, requiring as many look-ups as there are frames.

Question 20

What is the purpose of address binding in memory paging?

Answer 20

It translates virtual addresses into physical addresses during code execution

Question 21

What does the virtual address consist of?

How about the physical address?

Answer 21

the page number p, followed by the offset

the frame number f, followed by the offset, which is the same as in the virtual address

Question 22

How to find how many pages there are?

How about page size?

What is the size of the virtual memory?

Answer 22

if the page number in a virtual adrdress is described in |p| bits, it is likely that there are 2^|p| pages

if offset is described in |w| bits, then 2^|w| is the page size

2^(|p|+|w|)

Question 23

How to find how many frames there are?

How about frame size?

How about physical memory size?

Answer 23

if frame number is described in |f| bits, then 2^|f| frames

2^|w|

2^(|f|+|w|)

Question 24

What is the role of the Page Table Base Register (PTBR)?

Answer 24

It provides fast access to the page table in hardware-supported systems.

Question 25

What are the memory access requirements when using page tables for address binding?

What inputs must be given?

Answer 25

Two memory accesses are needed: one for the page table and one for the actual data.

page nr p and offset w

Question 26

How does address translation work using a frame table?

What is the disadvantage of address binding using a frame table?

Answer 26

The frame table checks all entries to locate the frame corresponding to the virtual address.

It requires as many memory accesses as there are entries in the frame table.

Question 27

What is the Translation Look-aside Buffer (TLB)?

How does the TLB accelerate address translation?

What happens during a TLB miss?

What information does the TLB store?

Answer 27

A small cache in the processor that keeps track of the most recently used pages in main memory.

By storing the frame IDs of the most recently accessed pages, reducing memory access times.

The page table is used to locate the page, or a page fault is generated if the page is not in physical memory.

Only the frame ID of the most recently accessed pages, not the actual data or instructions.

Question 28

How can the third problem be solved, i.e., deciding which page to load and when?

What problems arise from this solution?

Answer 28

By using demand paging, i.e., bringing a page into main memory only when it is accessed for the first time.

Determining how long pages should stay in memory.
Determining how many pages of each process should be kept in main memory.
Determining what to do if there are no more free frames

Question 29

How can page table extensions be used and what three additional bits do they involve?

Answer 29

Keep track of the state of process pages

Status bit indicates whether page is currently in memory

Referenced/Use bit indicates whether page has been referenced recently, potentially used by replacement policies

Modified/Dirty bit indicates whether page contents have been altered

Question 30

What problem do multi-level page tables solve?

How is the virtual address divided in a multi-level page table?

What is the purpose of the PTR (Pointer to Page Table Register)?

What are the advantages of multi-level page tables?

What are the disadvantages of multi-level page tables?

Answer 30

They address scalability issues of single-level page tables in systems with large virtual address spaces.

Page ID High (p1) for the first-level page table.
Page ID Low (p2) for the second-level page table.
Offset (w) for the word within the page.

It stores the pointer to the first-level page table for fast access during address translation.

Reduced memory overhead by allocating memory only for active tables.
Scalable for large virtual address spaces.
Efficient use of memory by avoiding allocation for unused address space.

Increased lookup overhead due to multiple memory accesses.
Greater complexity compared to single-level tables.

Question 31

What are some outstanding implementation issues in regards to page tables and frame tables?

Answer 31

Load control policicies (how many pages resident in MM)

Replacement strategies (which pages to swap out if there is a lack of space)

Sharing (sharing data and code between processes)

Question 32

What is demand paging?

Answer 32

Demand paging is a memory management scheme where a page is loaded into memory only when it is referenced, reducing initial loading time.

Question 33

What happens when a running process tries to access data or instructions at a virtual address (va)?

What occurs if the required page is not in main memory?

What does the page fault handler do if the page is not in the address space of the process?

What does the page fault handler do if the page is in the process’s address space?

What is updated after loading a page into a frame?

Answer 33

The system checks if the page containing va is in main memory using the TLB or page table.

A page fault occurs.

The process is stopped.

It checks for an empty frame in main memory to load the page; if none are available, it selects a page to swap out.

The page tables are updated to reflect the new mapping.

Question 34

What is Effective Access Time (EAT) in demand paging?

Answer 34

A performance metric calculated as:

EAT=(1−p) × memoryaccesstime + p × (page-faultservicetime)

where p is the page fault rate.

Question 35

What does a page fault rate (ppp) of 0 and 1 indicate?

Answer 35

p = 0 means no page faults occur

p = 1 means every memory reference results in a page fault

Question 36

Why can page faults significantly degrade performance?

How can we reduce the page fault rate in demand paging?

Answer 36

Page faults involve time-consuming processes like swapping pages in and out of memory, causing slowdowns.

Pre-paging: Preload pages likely to be accessed soon, such as super pages.
Keep the Working Set in Main Memory: Maintain pages that are actively reused.

Question 37

What is thrashing in demand paging?

What are common causes of thrashing?

What is an example of a situation causing thrashing?

Answer 37

Thrashing occurs when pages in active use are constantly swapped out and replaced, leading to excessive page faults and poor performance.

Two different processes competing for the same frame.
Two pages of the same process competing for the same frame.

A loop in a program repeatedly accessing two pages, causing constant swapping between the two pages.

Question 38

What are two options for assigning frames to processes?

Answer 38

All processes compete for all frames, and if a page must be swapped out, it can come from any process.

Each active process is assigned a fixed number of rames based on some criteria. When selecting a page to swap out, it can only be a page from the process loading a new page, or any other lower priority process

Question 39

What is the MN replacement strategy?

Answer 39

Selects the page which will not be used for the longest time in the future

Question 40

What is the LRU replacement strategy?

Answer 40

Selects the page that is least recently used

Question 41

What is the FIFO replacement strategy?

Answer 41

Selects the apge that has been resident in main memory for the longest timeA

Question 42

What is the working set in memory management?

What does t represent in the working set formula?

What does τ represent in the working set formula?

What is j in the formula W(t,τ)={rj∣t−τ<j≤t}?

How do you calculate the working set at time t?

What is the purpose of the working set?

Answer 42

The working set is the set of pages a process has accessed in the last τ memory references, kept in main memory to optimize performance.

t is the current time (or the current memory reference position).

τ is the window size, or the number of past memory references to consider for the working set.

j is the index (position) of a memory reference in the reference string.

Identify the unique pages accessed in the last τ references (from t−τ - to t).

To keep frequently accessed pages in memory, reducing page faults and improving efficiency.

Question 43

What happens if τ is too small or too large

Answer 43

Too small: Important pages might be removed, causing page faults.

Too large: Memory may be wasted on less frequently accessed pages.

Question 44

What happens if the sum of the working set sizes exceeds the main memory size?

What are the options to choose a process for removal from memory?A:

Answer 44

One process is removed from main memory to prevent thrashing.

Lowest priority process (unlikely to run soon).
Last process activated (considered least important).
Smallest process (least expensive to swap out).
Largest process (frees the most page frames).

Question 45

What are the advantages of virtual memory?

How about the disadvantages?

Answer 45

Advantages:.
Process size is no longer restricted to main memory size.
Memory is used more efficiently:
Eliminates external fragmentation (with paging).
Reduces internal fragmentation.
Program placement in memory doesn’t need to be decided at design time.
Facilitates dynamic linking of program segments.
Allows sharing of code and data by sharing access to pages.

Disadvantages:
Increased processor hardware costs.
Increased overhead for handling page faults.
Increased software complexity to prevent thrashing.