Systems Key Concepts

Papers of Significance

• Lamport and Clocks
• Berkley Fast File System
• LFS
• Chord
• Mach Kernel
• L4 Kernel

Architecture

• CISC vs RISC: A complex instruction is one that operates directly on memory without explicitly involving a load or store. Complex instructions involve less work in compilation since general functions have a closer match to compiler instructions. Reduced instructions may require more work on compilation, but execution time is similar. The benefit of RISC is that less transistors are required on the chip to implement the variety of complex instructions.

OS

Communication

• IPC
  • Shared Memory: easy to set up, but problem arise regarding consistency
  • Message Passing: set up a communication channel then you can communicate with send and recv calls.
• RPC System
  • Sequential Consistency vs. Causal Consistency

Distributed Systems

• Checkpointing
  • Coordinated vs uncoordinated: In coordinated checkpointing, all related processes halt at a given point (barrier). Once the coordinator has determined all processes have successfully checkpointed, the system continues. In uncoordinated checkpointing, processes checkpoint independently of other processes. Uncoordinated checkpointing is scalable and does not require all processes halt at a barrier, so forward progress can continue. However, if inconsistencies are found for a given checkpoint, the processes must roll-back to a previous checkpoint and see if the inconsistency still exists. It may be possible that new inconsistencies are generated, leading to further roll-backs. This can lead to a domino-effect where many roll backs are required and little forward progress is made. Another disadvantage of uncoordinated checkpointing is that processes are required to have more than 1 checkpoint saved.
  • Communication Induced Checkpointing: This is a hybrid approach with two kinds of checkpoints taken local and forced.
    • Z-Cycles:
• Distributed Hash Tables: The paper which best covered this from the Advanced OS class was Chord. In short data is mapped to keys and each node has a table of nodes so that when a key k is requested it either holds the key or can direct the query to a node in closer proximity to k.
  • Chord: A logical overlay ring network is formed. Given n nodes each node contains <math> 2^{log\; n} </math> successors in its finger table. We can cut the distance to a node by half or better for every jump giving <math>log\; n</math> query time.
• Distributed Shared Memory: physically separate memory is addressed as one (logically shared) address space.
• Load Balancing
  • Processor Affinity
• Two Phase Commit Algorithm: is a distributed algorithm which determines whether the actors of a transaction commit or roll-back a transaction. The algorithm consists of a (1) commit request phase and a (2) commit phase.
  • Commit request phase:
    1. The coordinator sends a query to commit message to all cohorts and waits until it has received a reply from all cohorts.
    2. The cohorts execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log.
    3. Each cohort replies with an agreement message (cohort votes Yes to commit), if the cohort's actions succeeded, or an abort message (cohort votes No, not to commit), if the cohort experiences a failure that will make it impossible to commit
  • Commit phase: In the commit phase the coordinator either sends a commit message or a undo message which the other process acknowledge and then release locks on resources held.

• Process Migration(and associated state):

File Systems

• Access Control List: is a list of entities that have access to objects of a file system, and what control mechanisms the entity has available.
• Indexing
• Network File Systems
• Journaling File Systems
• Log-based File Systems
• Fragmentation (Internal vs External)
• RAID
• Write Through vs Write Back (cache)

I/O

• Interrupt Driven vs Polling

Kernel Varieties

• Monolithic
• Micro-Kernel
• Exo-Kernel

Memory

• Associativity (Cache): The associativity of the cache is defined as the number of locations which new entries may be placed. There is a trade-off between spending more time and energy searching the cache for entries vs the time to insert entries. The associativity can also affect the frequency of cache misses.
  • Fully Associative: If a cache is fully associative, then new entries to the cache may be placed anywhere in the cache space. This allows for greater flexibility and less time taken to insert into a cache, but finding an object in the cache takes greater time.
  • Direct Mapped: With a direct mapping each entry in main memory has a single designated location in the cache.
• DMA
• NUMA
• UMA
• Management

• Paging vs Segmentation:
• Priority
  • Dynamic vs Static
  • Demand Page

Virtual Memory

A program's address space which is not shared with other programs is considered virtual memory. Virtual memory hides the complexities of the physical memory. Each process has a virtual view in which it has access to a large space of contiguous memory represented by pages.

The Memory Management Unit converts virtual addresses into physical addresses. The MMU stores and maintains the TLB.

1. TLB lookup results in hit or miss
   • TLB: helps translate virtual addresses into physical addresses faster
     • Process/Task Identifier Tag
     • TLB Flush
2. On miss a page walk must occur to find the physical address.
   • Page Tables: map virtual memory to physical memory in a system.
     • 1 page table per process
     • Swapping: Moving memory or processes between main memory and the backing store.
3. If physical memory is full the page might have been swapped to disk and
   1. The data is loaded from disk to a page frame in physical memory, pushing some other page onto secondary storage.

• On demand paging
• Thrashing: when time spent resolving page faults takes becomes a dominant factor in the workload.

• • Hierarchical Paging: Creates a tree like hierarchy of page tables where the first page table points to a secondary page table which points to the page and the corresponding entry.
  • Inverted Page Tables: Off-chip extension to the regular TLB that uses normal RAM. Table is indexed by actual memory addresses, and each element holds the related virtual addresses, this decreases the size of the page table, but increases the time required to use it as processes must search through the table to find the entry for their virtual address
• Double Buffering

• Page-Size Tradeoff
  • Smaller page sizes mean more TLB misses.
  • Larger page sizes mean less pages to keep track of.
  • Larger page sizes might correspond to greater internal fragmentation.
  • Page size vs disk access - larger pages may correspond to less pages loaded from disk and a smaller seek time.

Scheduling

• Schedulers
  • Measures of scheduler performance:
    • CPU Utilization
    • Turnaround Time:
    • Throughput: how many jobs are completed per unit time
    • Waiting Time: time each job spends in the ready queue

• Priority Inversion: When a higher priority task is indirectly preempted by a lower priority task.
  • Solutions: Priority Inheritance, Priority Ceiling, Disabling Interrupts to Critical Section.

Threads/Processes

• Context Switch: Save the registers, the program counter, process id, open files, priority, and the stack pointer to the Process Control Block.
• Dead Locks: The conditions required for deadlock are:
  1. Mutual Exclusion: only one process may be allowed access to a resource.
  2. Hold and Wait: processes holding a resource may request additional resources
  3. No Preemption: processes may not forcibly remove resources from other processes
  4. Circular wait: multiple processes form a chain of resource needs, in which one process in the chain holds the resource needed by another.
• Load Balancing
  • Processor Affinity
• SMT/Hypterthreading: provides a higher utilization of CPU resources. Processors can perform multiple instructions per cycle, so by taking instructions from multiple threads with no dependencies, it can give the illusion of two threads running simultaneously. Switching between the register sets for each thread is done in hardware, making the switches cheaper.
• Process Control Block: a protected data structure in memory that stores the information needed for a context switch for each process as well as a pointer to the next PCB.

Synchronization

In regards to the coordination of lightweight processes

• Mutex: is an algorithm which is designed to protect critical sections of code from being simultaneously executed. Critical sections of code are sections of codes which contain access to a shared resource. Common examples of mutex algorithms include flags, counters and queues.

• Transactions: provide a atomic framework for read and write operations. (Additionally see Log Based File Systems).

Transactions must satisfy four properties, atomicity, 'consistency, isolation, durability. The last two properties may need some further explanation. Isolation means that other processes cannot access data that is undergoing a transaction, but has not yet completed. Durability is the ability for a transaction based system to recover any committed operations in the event of failure.

• • Commit applies operations after consistency and safety has been verified.
  • Abort rolls back actions that would have been fulfilled by the commit operation.

In order to roll back actions a certain amount of auxiliary data must be stored about the operations that have taken place but have not yet been committed.

Virualization

• Shadow Page Table
• Hypervisor

Other

• Modes
  • Kernel Mode
  • User Mode

• Scaling
  • Weak Scaling
  • Strong Scaling

• Volatile

Networks

• ARQ
• Ethernet
  • CSMA/CD MAC Protocol
• IP
  • Datagram Fragmentation and Reassembly
• Sliding Window Protocol
• Router vs Switch vs Bridge
• TCP
  • Three way handshake