Operating System Final

Deadlock

when there is a set of processes each holding resources and waiting to acquire more resources

Resource allocation graph

shows instantaneous state of a system and its resources

Request edge

directed edge from process to resource

Assignment edge

directed edge from resource instance to process

Deadlock prevention

prohibit at least 1 of the necessary deadlock conditions so deadlock doesn’t happen

Deadlock detection

let deadlocks happen, but provide support for getting out of deadlock

Deadlock avoidance

watch and regulate process behavior so they never cause a deadlock

4 necessary deadlock conditions:

mutual exclusion, hold and wait, no preemption, circular wait

Mutual Exclusion

resources can only be used by one process at a time. Prevent by giving up critical sections (bad)

Hold and wait

processes can have some resources and may ask for more. Prevent by having processes ask for all resources at startup (could lead to starvation)

no preemption

OS gets a resource back only when a process is done using it. Prevent by killing processes and taking their resources (bad)

circular wait

build a cycle of processes such that they are all waiting on resources held by another process. Prevent by imposing a total ordering on all resources (doable)

Claim edge

from process to resource indicating the process may ask for resource in the future, turns to request edge when process asks for resource in future

Safe state

processes can’t cause deadlock no matter what they do

Unsafe state

not necessarily deadlocked but processes could create a deadlock, whether a deadlock happens or not is out of the OS’s control

Banker’s algorithm

check if granting request would keep graph in a safe state before granting the request

Memory

large linearly addressable array of words with 2 regions: the OS and user processes

Address binding

how to choose physical memory addresses where the program will run

Compile time

compiler chooses an address when it builds the program, builds absolute code that must be run in a particular location and rebuilt to run elsewhere

Load time

compiler chooses memory address when program starts running, builds relocatable code that will run wherever but cannot be moved after the program starts

Execution time

compiler chooses memory address when program executes. Can move after program has started running

Static linking

do all linking at build time, application code and libraries linked to one image that is copied into main mem and run

Dynamic linking

link with library code at load time, smaller executable image

Stub

small code piece that finds and replaces itself with a subroutine, useful for libraries

Dynamic loading

load parts of program when they are first needed

overlays

same region of memory used for several subroutines, one after another

Swapping

When main mem is filling up, temporarily remove a process from memory into the backing store, large transfer cost

Backing store

fast large storage used to hold mem contents for processes not inside main mem

Contiguous allocation

all memory for a process must be in one continuous block

Multiple partition allocation

OS has to find room for multiple processes as they arrive and leave

Dynamic storage allocation

To find space for processes, OS must maintain list of allocated regions and list of free holes, must coalesce memory when it is freed

first fit

choose first hole that the block fits into

best fit

find smallest hole that is at east the size of the block

next fit

find next sufficiently large hole after the one last allocated

worst fit

find largest hole and place block there

External fragmentation

small gaps between allocated memory blocks that can’t fit a process, holes too small to use

Internal fragmentation

when a process is given more space than it needs so some of the space it is given is wasted

50% rule

with first fit, if n bytes have been allocated 1/2n will be lost to fragmentation

Compaction

making little fragments into a big fragment, can only do this with execution time address binding

Logical address

what the user program sees (aka virtual address)

Physical address

address meaningful to hardware

Address translation

run-time conversion from logical to physical address, do not need logical/physical distinction for compile or load time address binding

Memory management unit

hardware device that handles mapping logical to physical addresses, part of CPU

Pages

memory allocated as multiple fixed-sized blocks

page table

table that says where process pages are, array of frame numbers indexed by page

Page table base register

holds address of where current page table is located

Copy on write

instead of copying over all of parent memory, only the page table is copied, which reference the parents memory. At first, all pages are set to read-only, only the pages we need to modify are actually copied

Translation look-aside buffer (TLB)

special cache for each CPU core, maps page number straight to frame number to reduce overhead

Page table length register

tells hardware the length of the current page table

Hierarchical page tables

paging the page table to break it up into page sized section, created inner and outer page table

Hashed page table

store sparse mapping from page number to frame number, hash page number to integer, page table liner will have chain of records to deal with collisions

Inverted page table

store address translation by memory frame instead of by process page, decreased storage overhead, more complicated lookup

Demand paging

move seldom used pages into the backing store

page fault

when process tries to access page but it is in backing store, traps to kernel

Pure demand paging

only load in pages when they are first used

Victim page

page to page out when we need to bring a page in

Local replacement policy

victim can only be a process’s own pages

Global replacement policy

any page of any process can be chosen as the victim, will let thrashing spread from one process to others

page replacement algorithm

rule for choosing victim

first in first out

choose victim that has been around the longest

Belady’s anomaly

when more frames yields a higher page fault rate

stack algorithm

immune to belady’s anomaly, having more frames will never choose to throw out a page that would have remained with fewer frames

Optimal page replacement

victim is page that wont be used for the longest, requires knowledge of the future

last recently used

victim is page that wont be used for the longest time, implement timestamp on every ref

last recently used approximation

use reference bit to see which pages are being used

second chance algorithm

let page stay in memory if reference bit is set, clear bit and more to the next potential victim (aka clock algorithm)

Least frequently used

count number of references to each page, replace page with smallest count

enhanced second chance

use both reference and dirty bits, dirty bit tells which pages are more expensive to replace

Page buffering

keep free frames available so that when page fault occurs you can use empty page to bring in faulted page then write out idle page to maintain pool of free frames

minor page fault

when a spare frame contains a page of a process so you don’t need I/O

thrashing

increased page fault rates, system isn’t getting much work done because it is sending more time resolving page faults

proportional allocation

give each process a number of frames proportional to its total memory size

working set

set of pages process is actively using right now

Active list

part of linux 2.4, pages not candidates for replacement

inactive list

part of linux 2.4, pages that make good victims

clean list

part of linux 2.4, pages identical to that in the backing store

dirty list

part of linux 2.4, pages that are not identical to backing store or has been modified

CPU

few processing elements that are independently controllable, lost of cache, run few threads each doing their own thing, acts as host

GPU

lost of processors that are each less powerful and made to do the same thing, little cache, run lots of threads, acts as device

Block

how GPU is organized, a set of many threads that can share memory between them

Grid

a collection of blocks

__global__

run on device, call from host

kernel

block of code used by thread to be run in parallel

CUDA - call to allocate memory

cudaMalloc((void \*\*)&devList, count \*sizeof(int))

CUDA- call to copy memory

cudaMemcpy(devList, myList, count \* sizeof(int), cudaMemcpyHostToDevice)

CUDA- call to free

cudaFree(devResults)

CUDA- call to reset

cudaDeviceReset()

centralized computing

when all processes exist in OS memory, hard to cooperate with other operating systems

distributed computing

allows for resource sharing, computational speedup, reliability, communication and cost effectiveness

Data migration

distributed computing goal where data can be moved to the host using them

Computational migration

execute computation steps/subroutines on the host with the needed resources, run subroutines remotely and keep everything else on host

Process migration

move entire program after it has started running for load balancing or data access

Goals of distributed computing

Scalability, Robustness (tolerate failure), availability, heterogeneity (different types of hosts and devices can cooperate)

Network operating system

use network to access remote resources, often requires special effort

Local Area Network

path between hosts is obvious, hosts have consistent performance characteristics, network has predictable structure, straightforward routing, limits on failures

Wide area network

hosts spread out with irregular networking patterns, obstacles such as routing choices, failed connections, and congestion

Physical layer

what network looks like at a low level, says how you would encode bits and how fast to transmit ex. ethernet

data link layer

organize data into frames to let systems share connection, supports local routing decisions, corrects physical layer errors with the header, delivery of frames in a LAN

Network layer

handles non-trivial routing, organize data into variable length packets, adds additional header info ex. IP

Internet Protocol

best-effort packet delivery service. Each host given unique 32 bit address and each packet is stamped with source and destination address, congestion can cause packets to be dropped/duplicated, no error detection, no congestion control