Quiz 1 Review Notes

Complexity

1. Problem (Classes of)
   • Emergent properties
   • Propagation of effects
   • Incommensurate scaling
2. Sources
   • New requirements
   • New performance targets
3. Coping
   • Modularity
   • Abstraction
   • Hierarchy
   • Layering
4. Symptoms
   • # components
   • # interconnects
   • irregularities, exceptions
   • no concise description
   • > 1 person

Questions

Q: The primary way that hierarchy reduces complexity is that it reduces the size of the individual modules. TRUE / FALSE

A: FALSE: Hierarchy has no direct bearing on module size. Instead, it provides structure for the interconnections between modules. Its primary impact on complexity comes from constructing stable subassemblies and thus reducing the number of modules that interact at each assembly point.

Q: The primary way that modularity reduces complexity is that it eliminates incommensurate scaling. TRUE / FALSE

A: FALSE: Hierarchy has no effect on incommensurate scaling. Its impact on complexity comes from reducing the number of interconnections.

We've discussed 4 principles in dealing with complexity: modularity, abstraction, hierarchy, and layering. For each system organization below, choose the most important principle it uses or implements that makes it effective and explain briefly why the system organization is an example of that principle.

1. Protocol Stack: Layering. Levels transform one set of functionalities into another. Levels also interact only with adjacent levels. Protocol stacks are organized in exactly this manner.
2. Client/Server: Modularity. Isolates client and server address spaces, don't share fate.
3. Virtual Memory: Abstraction. Hides the management of disk, page table, etc from the user giving the appearance of a single address space. Also, Modularity. Virtual memory isolates processes from one another by giving them separate and protected address spaces.
4. RPC: Abstraction. RPC makes client/server computing look like local computing by hiding it beneath a procedure call, hiding the communication mechanism from the user
5. Microkernel: Modularity. Microkernel partitions an OS's functionality into isolated user-level modules (like the file service, etc) thereby minimizing and making well-defined the interactions between the partitions.

Virtual Memory

• Need it to enforce modularity.
• Programs can reference any memory location, so we need to work around this.
• Idea: control which physical memory locations are accessible.
• Interpose a mapping from VAs to PAs.

Virtual Memory Manager (VMM)

• Located in between the processor and physical memory.
• Recording one entry for every VA is too expensive: on the order of physical memory size.
• Typically, we map fixed sized chunks called pages, which map to blocks of physical memory. [see figure 2-11 in the notes]

• Augment processor with PMAR [see figure 2-13 in the notes]

• Trusted intermediary - kernel.
• Has its own address space.
• Only the kernel can access the page maps, and write to PMAR.

1. User mode -> Kernel mode
2. Save PMAR & reload with address of kernel page table
3. Save PC & load with kernel entry point

Threads

• compare to VMM's purpose: enforce modularity for memory
• thread represents state of running program
• threads can be stopped and resumed
• kernel can use time sharing to simulate many virtual CPUs with only one physical CPU.

• preemptive vs non-preemptive
• in preemptive system: when timeslices run out
• in either: when thread is blocking on an event

• multiple threads in a single AS share memory, hence share variables, hence share fate
• if each AS corresponds to a single thread and vice versa (processes), they do not share fate

• Key difference is where the scheduler is implemented: by the user program or by the kernel
• Threading systems can be layered/nested

• problem: race conditions
• wait/notify
• event counts

• reason to choose one over the other: frequency of events vs time it takes to process an event

• mutual exclusion
• locks: acquire, release

• simplest scenario: thread 1 does acquire(L1), acquire(L2), and thread 2 does acquire(L2), acquire(L1). Can deadlock if one thread is preempted in between acquiring locks.
• one way to avoid: number all locks, and always acquire them in ascending order

Resource allocation

To deal with memory access bottlenecks, caches are often used to speed up lookup latencies due to the locality of reference.

There is an inverse relationship between access memory speed and capacity. (for instance, ram is expensive and fast while disks are much cheaper but slower).

If can't fit all of your storage into one storage layer(ie your ram), often people use multi-layered caches (such as using a chunk of memory to store parts of the disk for quick access).

To predict access time with caches, we can use the following equation:

  If the cache hit rate is h:
  Average lookup latency = h*(cache access time) + (1-h)*(cache miss time)

Dealing with read latency on disks

1. seek latency(must find the track)
2. rotational latency (1/2 way around the track) (must find the sector on the track)
3. read throughput (how long to read the bits off the sector)

Page replacement algorithms: There are a bunch of algorithms for determining which objects to keep in the cache. If you have perfect knowledge of the order of accesses, you can pick the optimal replacement ordering using dynamic programming.

Since in most instances you can't predict the future, there are a few approximation algorithms:

• LRU (least recently used)
• MRU (most recently used)
• FIFO (first in first out)

Another scheduling problem is the CPU. Given a preemptive processor, one must figure out when to run what processes and how long to run them for.

Various topics dealing with CPU schedulers:

• Round Robin
• Priority Inversion
• Shortest Job First

Also, there are various Disk Schedulers to determine which writes to do in what order:

• FIFO
• Elevator
• Shortest Seek First

Networks