Memory Allocation/Memory Management

Act of managing computer memory. Essential requirement is to provide ways to dynamically allocate memory to programs at their request and free when not needed.

1. Memory Pools/Fixed-size block allocation: uses a free list of often same size block of memory and allocates on request. This works well for embedded systems.
2. buddy blocks: In this system memory is allocated from several blocks instead of just one. Memory pools often represent blocks of size of power 2. When a certain size of memory is requested, the pool with minimum size meeting the requirements is used to allocate memory. If no such block is present, a block from higher pool is broken into smaller blocks and then memory is allocated.

Fragmentation

Three types: External, Internal and Data fragmentation

Since the memory is often assigned in blocks of power 2, there would be a waste of memory either internally or externally. Overtime while memory is getting allocated and released, there will holes in between. If there are holes outside the allocated area, it’s called external fragmentation and if there are holes inside the allocated area it’s called internal fragmentation. Data fragmentation occurs when a collection of data in memory is broken into pieces that are not closed together. For example, a file that is not able to fit in contiguous memory.

Translation look-aside buffer (TLB)

A cache that Memory Management Unit uses to improve virtual address translation speed.

Virtual memory is the space seen from a process. The page table keeps track of where the virtual pages are stored in the physical memory. The TLB is implemented as CAM (content addressable memory). CAM key is virtual address and search result is the physical address. If there’s a miss in TLB, translation proceeds by page walk.

Interrupt

Interrupt is a signal to the processor emitted by software or hardware indicating an event that needs immediate attention. The processor responds by suspending its current activities, saving its state and executing a function called interrupt handler (or interrupt service routine, ISR).

Hardware Interrupts are used by devices to communicate that they require special attention. Internally they are generated by sending alerting signals to the processors. Basically give each device a wire (interrupt line) that it can use to signal processor. Hardware interrupts are asynchronous.

Software Interrupts is cause either by an exceptional condition in the processor itself or a special instruction in the instruction set which causes an interrupt when executed. The former is often called a trap (Divide by 0 causes trap) Special instruction is used to interrupt to request services from low level system software such as device drivers. Software interrupts are often used to implement system calls.

Several ways to implement interrupts. Could be implemented using a active wire (level triggered, high or low), edge triggered, message signaled, Doorbell wiki link.

Distributed Shared Memory

Physically separate memories can be addressed globally. Two processors with same address will point to same memory address. Can be implemented at OS level or library level.

Stateful and stateless servers

A stateful server remembers client data from previous request whereas stateless server doesn’t.

State may refer to any information related to client like whether the file is open, or being modified or cached data on client etc.

NFS is a stateless system.

• Each request must be complete since no state is stored - the file has to fully identified and any offsets specified.
• if a server crashes and then recovers, no info was lost since it’s stateless. higher degree of fault tolerence.
• no server overhead for storing client information, and server doesn’t get affected if client crashes.

AFS is stateful System

• Requests are shorter
• cache coherence is possible; server can know which clients are caching which blocks of a file.
• File locking is possible; server can maintain that certain client is locking a file.
• server returns an identifier to client creating a session and keeps track of open files. It is required to maintain state if providing unix file semantics.

Difference between stateful and stateless file systems

• Failure Recovery:
  • A stateful server loses all its valatile state in a crash. Server needs to be aware of client failure to reclaim memory.
• Slow processing and longer request messages in case of stateless systems. Difficult to provide unix file semantics.
• A server employing server-iniitiated cache needs to have state to validate cache.
• UNIX use of file descriptors and implicit offsets is inherently stateful. servers must maintain tables to map file descriptors to inodes and store current offset within file.

Detailed Info

Swapping

When all the process in a multiprogrammed CPU are not able reside in memory at the same time, some of the process that are not scheduled currently or are blocked are transferred to secondary memory. This dynamic moving of process between memotu and disk is called swapping.

Inverted Page Table

Linear Inverted Tables: Rather than mapping virtual addresses to physical addresses, we map physical address to virtual addresses.

More details: https://www.cs.berkeley.edu/~kamil/teaching/sp04/040104.pdf

File Systems

Give at least three strategies that a file system can employ to reduce the time a program spends waiting for data reads to complete.

• Prefetching (Spatial Locality) - A process doing random access will not get the benifits.
• Indexing (Index Most Used Paths) - Accessing files that are not used commonly will be effected.
• Caching - If the data is being changed rapidly, cache will become stale soon and benifits will diminish.

More details: https://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/