cop4610 exam2

Monitor

A lock + condition variables

Lock

provides mutual exclusion to shared data.

a lock provides two operations
-Acquire()
-Release()

Condition Variable

provides a queue for waiting threads inside a critical section

each conditional variable
-consists of a queue of threads
-Provides three operations
**wait()
**Signal()
**Broadcast()

Hoare vs. Mesa Monitors

Hoare Monitors (used in most textbooks)
-Signal() transfers the CPU directly to a waiting thread.

Mesa Monitors (used in most real operating systems)
-Signal() only puts a waiting thread on the scheduler's ready queue
-By the time the waken thread gets the CPU, the waiting condition may no longer be true and needs to be retested.

Semaphores VS Monitors

We can't quite implement monitors with semaphores.

Condition variables only work inside a lock
-using semaphores inside a lock may deadlock

Condition variables have no history, but semaphores have
-Signal() with an empty queue does nothing
**A subsequent Wait() will wait
-V() increments semaphore
**A subsequent P() will not wait
-Wait() will always wait
-P() might not wait

Deadlock

Occur when threads are waiting for resources with circular dependencies.

Deadlock implies starvation

Preemptable Resource

EX- CPU
can be resolved by reallocation of resources

Nonpreemptable Resource

A resource that cannot be taken away from its current owner without causing computation to fail

Starvation

a thread waits indefinitely

Checkpointing

taking snapshots of system states from time to time

Four Conditions for Deadlocks

limited access (lock-protected resources)

no preemption (if someone has the resource, it cannot be taken away)

wait while holding (holding a resource while requesting and waiting for the next resource)

circular chain of requests

Banker's Algorithm

-A thread states its maximum resource needs in advance.

-The OS allocates resource dynamically as needed. A thread waits if granting its request would lead to deadlocks.

-A request can be granted if some sequential ordering of threads is deadlock free.

Deadlock Recovery Techniques

• Scan the resource allocation graph

• Detect circular chains of requests

• Recover from the deadlock

Interprocess Communication

Processes communicate among address spaces.
-Bug stream ex. pipe
-Message passing (send/receive)
-File system (read and write)
-Shared memory

Direct
-send(P1, message)

System Call

A user process asks the OS to do something on the process's behalf.

Hardware-Supported Mechanisms

Address translation
Dual-mode operation

Software-Supported Mechanisms

Strong Typing
Software Fault Isolation

Steps to switch between kernel and user spaces

-Creates a process and initialize the address space
-Loads the program into the memory
-Initializes translation tables
-Sets the HW pointer to the translation table
-Sets the CPU to user mode
-Jumps to the entry point of the program

Context switching between processes vs. threads

Unlike context switching among threads, to switch among processes
-Need to save and restore pointers to translation tables

To resume process execution
-Kernel reloads old register values
-Sets CPU to user mode
-Jumps to the old program counter

Segment

A logically contiguous memory region

External Fragmentation

memory wasted because the available memory is not contiguous for allocation

Internal Fragmentation

allocated pages are not fully used

Translation Lookaside Buffers

Store recently translated memory addresses for short-term reuses

base and bound translation

• Each process is loaded into a contiguous region of physical memory
• Processes are protected from one another
• Each process "thinks* that it owns a dedicated machine, with memory addresses from 0 to bound.
• An OS can move a process around
  --By copying bits
  --Changing the base and bound registers

Segmentation-based Translation

use a table of base-and-bound pairs

Paging-based translation

memory allocation via fixed-size chunks of memory, or pages

Segmented-paging translation

breaks the page table into segments

• Easier to grow/shrink individual segments
• Finer control of segment accesses
  ** e.g., read-only for shared code segment
  ** Recall the semantics of fork()…
• More efficient use of physical space
• Multiple processes can share the same code segment
• Memory allocation is still complex
  ** Requires contiguous allocation

paged page tables

two-level tree of page tables

Caching

Storing copies of data at places that can be accessed more quickly.

temporal locality

Recently referenced locations are more likely to be referenced soon.

spatial locality

Referenced locations tend to be clustered.

Cache pollution

Leaving behind cache content with no localities.

Translation Lookaside Buffer (TLB)

• Tracks frequently used translations
• Avoids translations in the common case

virtually addressed cache

between the CPU and the translation tables

Physical addressed cache

between the translation tables and the main memory

Design issues of caching

1. How is a cache entry lookup performed?
2. Which cache entry should be replaced when the cache is full?
3. How to maintain consistency between the cache copy and the real data?

Four types of cache misses

1. Compulsory Misses
2. Capacity Misses
3. Competing Cache Misses
4. Policy Misses

Ways to perform TLB lookups

1. sequential search of the TLB table
2. direct mapping - assigns each virtual page to a specific slot int the TLB
3. set associativity- used N TLB banks to perform lookups in parallel
4. fully associative cache- allows looking up all TLB entries in parallel

write-through caching policy

Immediately propagates update through various level of caching.

write-back caching policy

Delays the propagation until the cached item is replaced.

Demand Paging

Allowing pages that are referenced actively to be loaded into memory.

page fault

A referenced page is not in memory.

Transparent

(invisible) mechanisms

• A process does not know how it happened
• It needs to save the processor states and the faulting instruction

Belady's Anomaly

Adding more frames can cause more page faults.

Thrashing

When the memory is overcommitted.

Working Set

Pages that are referenced within the past T seconds.

Steps to carry out a page fault

1. Choose a page
2. If the page has been modified, write its contents to disk
3. Change the corresponding page table entry and TLB entry
4. Load new page into memory from disk
5. Update page table entry
6. Continue the thread

Page replacement policies

• Random Replacement
• FIFO (First In First Out)
• MIN (Optimal)
• LRU (Least-recently Used)
• LFU (Least Frequently Used)

Polling

A CPU repeatedly checks the status of a device.

Interrupt-driven I/Os

A device controller notifies the corresponding device driver when the device is available.

Direct Memory Address

Using an additional controller to perform data movements.

Device Controller

Converting between serial bit stream and a block of bytes.

Device Driver

An OS component that hides the complexity of an I/O device.

Memory-mapped I/O

Making no distinction between device addresses and memory addresses.

Categories of I/O Devices

block device
character device
network device

ways to access a device

Polling
interrupt-driven I/O's
Direct Memory Access (DMA)
Double Buffering

disk arm scheduling policies

1. FCFS (first come, first serve)
2. SSTF (shortest seek time first, ie closest to current disk arm position)
3. SCAN (takes the closest request in the direction of travel, ie elevator)
4. C-SCAN (goes in direction of travel servicing, then restarts at 0)

Disk Platters

coated with magnetic materials for recording

Disk Arm

moves a comb of disk heads

Sector

the smallest unit of disk storage

Cylinder

consists of all tracks with a given disk arm position

Zone Bit Recording

zones near the edge store more information (higher bandwidth)

Track

each disk platter is divided into concentric tracks

Track skew

starting position of each track is slightly skewed

Thermo-calibrations

performed to account for changes of radius due to temperature changes

Seek time

the time to position disk heads (~4 msec on average)

Rotational Latency

the time to rotate the target sector to underneath the head

Transfer Time

the time to transfer bytes

Disk access time

seek time + rotational delay + transfer time

Latency

Seek time + rotational delay

Bandwidth

Bytes transferred / disk access time

Block Device

stores information in fixed-size blocks, each one with its own address
(e.g. disks)

Character Device

delivers or accepts a stream of characters, and individual characters are not addressable
(e.g. keyboards, printers)

Network Device

transmits data packets

Flash Memory

form of solid-state memory similar to ROM

• Holds data without power supply

NOR Flash

used in cellular phones and PDAs
byte addressable
mostly replaced by DRAM + NAND Flash

Flash Translation Layer (FTL)

Write new version elsewhere
Erase the old version later

flash page

The atomic unit in which data is read from flash memory.

1 flash page ~= 1 disk block

flash blocks

consists of 4-64 flash pages
may not be atomic

double buffering

uses two buffers. While one is being used, the other is being filled