Computer Memory Management Quiz

Agenda November 21 - Lecture 25

• Reminders: Read chapters 20-22 (Virtual Memory Module 8), chapters 36 and 37 (Devices).
• Project 5: Deliverable for Project 5 - implementing a simple file system is due December 4th. The last demonstration is December 9th.
• Attendance: No class next week.
• Quiz: A quiz is scheduled for December 4th.
• Final Exam: The final exam is scheduled for Thursday, December 12th, from 10:30 AM to 12:30 PM in Beury 160.
• Thanksgiving Holiday: Enjoy the Thanksgiving holiday.

Last Time

• Page Replacement: Covered FIFO, Optimal, and LRU algorithms.
• LRU Approximations: LRU approximations were also discussed.
• Memory Allocation Policies: Policies for managing memory allocation were reviewed.

Today

• Page Replacement: Page replacement policies for managing memory allocation.
• Fetch: Discussed fetch policies related to memory allocation.
• Resident Set Management: Resident set management including fixed/variable allocation with local/global scope.
• Working Set Strategy: Working set strategy for managing memory allocation.
• Memory Mapped Files: Memory mapped files for efficient data transfer.
• Device Management: Device management for interaction with hardware devices.

Quiz 9

• (Graph showing distribution of answers)

True/False Questions

• Storage Block Allocation: Multi-level indexing wastes space for small files. (True or False)
• FAT Implementation: A FAT entry size is dependent on the number of bytes in file system blocks. (True or False)
• Clock Algorithm: A clock algorithm records reference times for determining the LRU page. (True or False)
• Presence Bit: The presence bit indicates if a page is valid in a process's virtual address space. (True or False)

Fetch Policy

• Demand Paging: Brings pages into memory only when referenced. Causes a high number of page faults initially but then usually decreases.
• Prepaging: Brings in multiple pages at once to improve efficiency. This is sometimes effective if pages are arranged contiguously.

Resident Set Management

• Trade-offs: Memory allocation to processes has trade-offs. Smaller allocation leads to more processes, but increases page faults. Larger allocation leads to fewer page faults but reduces the number of processes.
• Resident Set: Resident set comprises a process's currently loaded memory pages.

Policies for Resident Set Size

• Fixed Allocation: Allocates a fixed number of frames for a process; the process will suffer if there's a page fault.
• Variable Allocation: Allows the allocated frames to adjust dynamically over the process lifetime.

Replacement Scope

• Local Scope: Replacement choices affect only the process generating the page fault.
• Global Scope: Consideration expands to all unlocked pages in the memory.

Fixed Allocation, Local Scope

• Page fault rate: High page fault rate if allocation of frames is too small.
• Processor idle time & swapping: Increased times if allocation is too large.

Variable Allocation, Global Scope

• Implementation: Easier to implement compared to local scope in a variable allocation, as allocation can be dynamically modified.
• Free frames: OS manages a list of free frames, assigning frames to active processes when a page fault occurs.
• Growing resident sizes: Causes other processes to suffer if frames are unavailable.
• Page buffering: Page buffering helps to mitigate problems associated with poor allocation choice.

Variable Allocation, Local Scope

• New Process allocation: Allocates a certain number of page frames for a new process.
• Page fault: Page to replace is selected from the resident set.
• Evaluation & performance: Processes are constantly evaluated and re-allocated based on their locality of reference characteristics.

Variable Allocation, Local Scope (Key Elements)

• Assessment: Resident set size changes are based on anticipated future requirements for the currently active processes.
• Criteria: Criteria for determining the resident set size are crucial for efficiency.
• Timing: The timing of when changes in resident set size are made is essential for the optimal performance of the OS

Working Set Concept

• Required pages: A program requires a set of pages to reside in memory for smooth operation.
• Page fault rate & allocation: Page fault rate increases as a program does not have enough frames.
• Optimal Working Set: The optimal working set contains pages highly likely to be used in the near future.
• Program Behavior & Variation: Working set sizes change greatly depending on the type of locality exhibited by the program.

Locality of Reference

Working Set

• Window: A window (of size Δ) is used to determine the pages that make up the working set.
• Page Reference String: The page reference string dictates to which pages to look to when a page fault occurs in order to avoid wasting potentially valuable processing time.
• Working Set Composition: The working set changes over time as the window slides through the page reference string.

Window Size (Width)

• Program Behavior: Program behavior dictates the size of the window, which must be large enough to capture periods of heightened activity but not so large as to become inefficient.

Working Set Algorithm

• Memory Reference: Pages used in the most recent k memory references make up the working set at time t.
• Size Function w(k,t): Defines the size of the working set at a specific point in time or over a specific interval.

Working Set Strategy

• Variable Allocation, Local Scope: Working set of a process is tracked, and the resident set size adjusts based on the pages in its working set.
• Virtual Time: Virtual time is monitored to reflect the changes in a process's working set

Working-Set Model

• Parameters: working-set window - fixing amount of page references, interval △ - (# pages referenced in each interval determines working set size)
• Total Demand Frames (D): The total number of frames that are needed in the set to fit all the application's work in memory.
• Thrashing: D > m (where m is total frames available), meaning that there aren't enough frames to satisfy the total demand of the processes in the system
• Process Suspend: The operating system must suspend one of the processes to ensure system stability.

Thrashing

• Swapping: A state where a system spends most of its time swapping process portions rather than executing instructions.
• Guessing: The operating system guesses and bases allocation off of the recent history to decide which pieces of information are least likely to be used in the near future.

Multiprogramming Effects

• Thrashing: Threshold where processor utilization decreases significantly due to extensive swapping.

Page Replacement using the Working Set Strategy

• Hardware Bits (R&M): Hardware sets bits (R and M) in the page table.
• Timer Interrupt: The timer interrupt periodically resets referenced pages (R bit)
• Page Fault: When a page fault happens, the OS checks if the page is found in the working set. If not, it evicts a page.

Working Set of Processes Determined by Window Size

• (Data representing working sets of processes based on different window sizes over time)

Prepare for the upcoming quiz on memory management principles, specifically focusing on page replacement algorithms, fetch policies, and resident set management. This quiz covers essential concepts from chapters 20-22 and 36-37. Stay sharp and review your knowledge on FIFO, Optimal, and LRU algorithms.