CSC 342 Computer Operating Systems: Main Memory Study Notes

Instructor Information

Course Instructor: Prof. Mohammed Almulla
Program: Computer Science
School: Engineering and Computing, AIU

Background

A program must be transferred from disk into memory and placed within a process to execute it.
Main memory and registers are the only types of storage that the CPU can access directly.
The memory unit only recognizes a stream of addresses and associated read or write requests.
Register access can occur in one CPU clock cycle or less, whereas memory access can take multiple cycles, potentially causing a stall in CPU operations.
A cache is utilized between the main memory and CPU registers to improve access times.
Memory protection is essential to ensure the correct operation of processes and prevent unauthorized access.

Base and Limit Registers

Base Register: Defines the starting physical address of a user process in memory.
Limit Register: Defines the size of the logical address space for a process.
The CPU checks every memory access generated in user mode to ensure it falls within the range defined by the base and limit registers.

Logical vs. Physical Address Space

The distinction between logical and physical address space is crucial for memory management.
Logical Address: Generated by the CPU; also known as a virtual address.
Physical Address: The actual address visible to the memory unit.
In compile-time and load-time address-binding schemes, logical and physical addresses are the same; they differ in execution-time address-binding schemes.
Logical Address Space: The set of all logical addresses generated by a program.
Physical Address Space: The set of all physical addresses that correspond to a program's logical addresses.

Memory-Management Unit (MMU)

The MMU is a hardware device that maps virtual addresses to physical addresses at runtime.
In a basic scheme, the value in the relocation register (also called the base register) is added to every address generated by a user process before it is sent to memory.
Earlier operating systems, like MS-DOS on Intel 80x86 architecture, utilized four relocation registers.
The user program interacts with logical addresses and does not directly interact with physical addresses.
Execution-time binding occurs during memory access, allowing mapping of logical to physical addresses.

Dynamic Relocation

Dynamic relocation allows a routine to be loaded into memory only when it is called, optimizing memory usage by avoiding loading unused routines.
All code segments are kept on disk in a relocatable load format.
This method is beneficial for handling large code sizes under infrequent execution scenarios.
No special support is typically required from the operating system; thus, it is implemented through careful program design.
The operating system can assist by providing libraries to facilitate dynamic loading.

Context Switch Time Including Swapping

If the next process to be run on the CPU is not already in memory, a swap must occur.
Context switch time can be significant if large processes are involved.
Example: A 100MB process swapped to a hard disk with a transfer rate of 50MB/sec requires:
- Swap out time: 2000 ms
- Swap in time: 2000 ms
- Total context switch switching component time: 4000 ms (4 seconds)
Context switch time can be reduced by minimizing the size of memory swapped based on actual usage.
System calls such as request_memory() and release_memory() allow processes to inform the OS of memory utilization.

Contiguous Allocation

Main memory must efficiently support both operating system functions and user processes due to its limited resource nature.
Contiguous Allocation: One of the earliest memory allocation methods, organizing main memory into two major partitions:
- Resident Operating System: Typically stored in low memory; contains the interrupt vector.
- User Processes: Located in high memory; each user process resides in a single contiguous section of memory.
Relocation registers are implemented to protect user processes from accessing each other’s memory and modifying the OS's code and data.
- The base register holds the smallest physical address, and the limit register contains the extent of logical addresses allowed.
The MMU facilitates dynamic mapping of logical addresses to protect memory allocations.

Multiple-Partition Allocation

In multiple-partition allocation, the degree of multiprogramming is restricted by the number of active partitions.
Variable-Partition Sizes: Allocates partitions depending on the requirements of the processes, enhancing efficiency.
A hole is any block of available memory that can be allocated to incoming processes.
Processes are granted memory allocations from holes that can accommodate their size.
When a process exits, its partition is freed up, allowing for adjacent free partitions to be combined.
The operating system keeps track of:
- Allocated partitions
- Free partitions (holes)

Dynamic Storage-Allocation Problem

First-fit Allocation: Allocates the first memory hole large enough to meet the request.
Best-fit Allocation: Allocates the smallest available hole that satisfies the request; requires searching the entire list unless organized.
- Produces the smallest leftover memory hole.
Worst-fit Allocation: Allocates the largest available hole and requires searching through the entire list.
- This may lead to the largest leftover space but is generally inefficient.
Efficiency Insights: First-fit and best-fit allocation are generally faster and show better memory utilization compared to worst-fit.

Fragmentation

Fragmentation refers to inefficiencies that prevent processes from being assigned to memory blocks because of their size.
External Fragmentation: Occurs when total memory exists to meet a request, but it's not contiguous, making it unusable.
Both first-fit and best-fit strategies can contribute to external fragmentation.
Analysis of external fragmentation reveals that with N allocated blocks, approximately 0.5 N blocks may be lost.
- Approximately 1/3 could be unusable under the 50-percent rule.
Internal Fragmentation: Happens when allocated memory exceeds requested memory.
- For example, in a multiple-partition system, if an 18,464 bytes hole is allocated to a request of 18,462 bytes, there remains a 2 bytes hole that is unused.

Solutions to Fragmentation

Mitigation Approach for Internal Fragmentation: Break the memory into fixed-size blocks and allocate memory based on these block sizes.
Compaction: The process of shuffling memory contents to place all free memory together in one large block.
Compaction is dependent on dynamic relocation and occurs at execution time.
In I/O operations, it is essential to latch jobs in memory while involved in I/O and manage I/O through OS buffers.
Both internal and external fragmentation issues extend to backing stores.
Key complementary techniques are segmentation and paging to address fragmentation.

Segmentation

Segmentation is a memory management scheme that aligns with the user’s view of memory
- A program is organized into several segments, where each segment is a logical unit like:
- Main program
- Procedures
- Functions
- Objects
- Local and global variables
- Stacks
- Arrays
User's View of a Program: Illustrates the logical address structures and organization within the memory as segments.

Segmentation Architecture

Logical Addresses: Comprise a two-tuple:
Compilers automatically generate segments reflecting the input program.
A potential segmentation layout might include:
1. Code segment
2. Global variables segment
3. Heap segment
4. Stack segments for each thread
5. Standard library segment
Segment Table: Maps logical to physical addresses with entries containing:
- Base: Starting address where segments reside.
- Limit: Length of each segment.
Segment-table base register (STBR): Points to the location of the segment table in memory.
Segment-table length register (STLR): Indicates how many segments a program uses; legal segment number must be less than STLR.

Segmentation Example

An example includes five segments numbered from 0 to 4.
- Each segment entry in the segment table contains:
- Base address where that segment resides in physical memory.
- Length of that segment.
- For instance, Segment 2 is 400 bytes long and starts at memory location 4300:
- Accessing byte 53 of segment 2 maps to physical address 4353 = 4300 + 53.
- An attempt to access byte 1222 of segment 0 would trap an error as that segment's length is only 1000 bytes.

Paging

Paging is a memory management technique designed to:
- Eliminate external fragmentation and the complication of varying memory sizes for chunks.
- Integrated into various operating systems, including mainframes and smartphones.
Paging Mechanics:
- Divide physical memory into fixed-size units known as frames.
- Typical frame size is a power of 2, ranging from 512 bytes to 16 megabytes.
- Divide logical memory into same-sized blocks referred to as pages.
- The operating system tracks free frames for efficient allocation to running programs (N pages require N free frames).
- A page table translates logical to physical memory addresses and the backing store is also divided into pages, although internal fragmentation may still occur.

Address Translation Scheme

The CPU's generated address is structured into:
- Page Number (p): Used to index into the page table, containing the base address for each physical page
- Page Offset (d): Combined with the base address to yield the final physical address sent to memory.
For a logical address space described as 2^m with a page size of 2^n.

Paging Hardware

The paging process involves the following key components:
- Logical Address: produced by the CPU for memory access.
- Physical Address: after translation based on the page table.
Example of logical address: a logical address broken down into components:
- Page number (p)
- Page offset (d).

Paging Model of Logical and Physical Memory

Illustrates how logical memory maps onto physical memory utilizing a structured relationship through the page table.

Paging Example

Consider a scenario where:
- n=2 and m=4 representing a 32-byte memory divided into 4-byte pages.
- Logical address 0 translates into physical address 20 as follows:
- Logical Address Mapping Process:
  - Page 0, Offset 0 issued, with Page Table indicating Page 0 is loaded into Frame 5.
  - Thus, calculation: Physical Address = (Frame Number × Page Size) + Offset = (5 × 4) + 0 = 20.
- Conversely, logical address 3 translates to physical address 23, computed similarly.
- Paging avoids external fragmentation since any free frame can be allocated, but introduces some internal fragmentation.

Internal Fragmentation Calculation

For a page size of 2048 bytes and process size of 72,766 bytes, 35 pages plus an 1,086 byte result in the consequent internal fragmentation:
- Internal\,Fragmentation = 2048 - 1086 = 962 \,bytes
Worst-case Fragmentation: One frame minus one byte.
On average, fragmentation amounts to half the frame size.
Desirability of Small Frame Sizes: Handling fragmentation concerns weighed against tracking overhead for each page-table entry.
Disk input/output efficiencies improve when transferring larger data volumes.
Current convention typically uses pages between 4 KB and 8 KB, with systems supporting even larger sizes.
Solaris Example: Employs page sizes of 8 KB and 4 MB, based on data characteristics.

Implementation of Page Table

The page table is maintained exclusively in main memory.
Page-table base register (PTBR): Points to the current location of the page table.
Page-table length register (PTLR): Informs the size of the page table.
Each access for data or instruction requires two memory accesses:
- One access for the page table and another for the actual data/instruction.
- This lead to efficiency loss is mitigated by a fast lookup through translation lookaside buffers (TLBs) which serve as associative memory caches.

Paging Hardware with TLB

The integration of TLBs into the paging architecture enhances the performance by caching recently accessed page table entries, reducing memory access times significantly.