Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
141 Cards in this Set
- Front
- Back
Memory Mapped I/O
|
- I/O devices appear as regular memory to CPU;
- regular loads/stores for accessing device; - this is more commonly used; |
|
Programmed I/O
|
- also called "channel" I/O;
- CPU has separate bus for I/O devices; - special instructions are requried; |
|
Device controllers have...
|
- data-in register (to receive input from device);
- data-out register (to send output to device); - status register (read by host to determine device state); - control register (written by host to invoke command); |
|
To write data to a device: (6)
|
1) Host repeatedly reads busy bit in status register until clear
2) Host sets write bit in command register and writes output in data-out register 3) Host sets command-ready bit in control register 4) Controller notices command-ready bit, sets busy bit in status register 5) Controller reads command register, notices write bit: reads data-out register and performs I/O (magic) 6) Controller clears command-ready bit, clears the error bit (to indicate success) and clears the busy bit (to indicate its finished) |
|
DMA
|
Direct Memory Access
- transfer data directly between device and memory (no CPU intervention) - device controller transfers blocks of data |
|
DMA interrupts when...
|
when block transfer completed (instead of when one byte is completed)
|
|
DMA useful for...
|
high-speed I/O devices
|
|
Two types of interrupts
|
1) Maskable (can be turned off)
2) Nonmaskable (can't be turned off, because they signify serious error like unrecoverable memory error) |
|
Interrupt vector contains...
|
addresses of interrupt handlers for each device (can chain and then search if there are more devices than places in vector)
|
|
Traps and exceptions
|
Software generated interrupt
|
|
Traps
|
User program requires OS service (caused by system calls)
|
|
Exceptions
|
User program acts silly
- divide by 0, or memory access violation - just a performance optimization |
|
Protect against infinite loops
|
- set a timer to generate an interrupt in a given time
- before transferring to user, OS loads timer with time to interrupt - OS decrements until it reaches 0, and then gets interrupted and OS regains control |
|
Protected/privileged instructions
|
- direct user access to some hardware resources (direct access to I/O devices)
- instructions that manipulate memory management state (page table pointers, TLB load, etc) - setting of special mode bits - halt instruction |
|
Dual Mode Operation
|
- user mode and kernel mode
- OS runs in kernel mode, user programs in user mode - mode bit provided by hardware |
|
How to change mode to kernel?
|
System call
|
|
How to return from system call?
|
RTI to reset to user
|
|
How do user programs do something privileged?
|
Call OS procedure
|
|
System calls and APIs
|
SC most commonly accessed by programs using APIs (Win32, POSIX, Java) because easier to use
|
|
Solution to reduce system call overhead
|
- perform some system functionality in user mode
- Libraries (DLLs) cache results or buffering ops |
|
Dual mode solves technical and social problems... name them
|
Technical: have process/memory quotas
Social: yell at idiots that crash machines |
|
Last pure bastion of fascism
|
Operating Systems! (because they use system feedback rather than blind fairness)
|
|
OS jobs for process management (5)
|
- creating and deleting both user and system processes
- suspending and resuming processes - providing mechanisms for process synchronization - providing mechanisms for process communication - providing mechanisms for deadlock handling |
|
OS jobs for memory management (3)
|
- keep track of which parts of memory are being used and by whom
- deciding which process and data to move in and out of memory - allocating and deallocating memory space as needed |
|
Disk access methods (2)
|
sequential or random
|
|
OS jobs for file/storage management (5)
|
- creating and deleting files
- creating and deleting directories to organize files - supporting primitives for manipulating files and directories - mapping files onto secondary storage - backing up files onto nonvolatile storage media |
|
OS jobs for disk management
|
- free space management
- storage allocation - disk scheduling |
|
tertiary storage
|
magnetic tape drives, CD, DVD drives and platters
|
|
WORM
|
write once, read many times
|
|
RW
|
read-write
|
|
solid-state disks
|
electronic RAM disks
|
|
memory hierarchy (4)
|
magnetic disk ->
main memory -> cache -> hardware register |
|
I/O subsystem components (3)
|
- memory management component that includes buffering, caching, and spooling
- general device-driver interface - drivers for specific hardware devices |
|
compute-server system
|
client sends requests to perform action (read data)
|
|
file-server system
|
file-system interface (create, update, read, delete files), like a web server sends files to browsers
|
|
5 categories of system calls
|
- process control
- file manipulation - device manipulation - information maintenance - communications |
|
Good technique for designing an OS
|
- modularity is important
- sequence of layers or using a microkernel |
|
virtual machine
|
- takes the layered approach, and treats both the kernel of the operating system and the hardware as though they were hardware
- other OSes may be loaded on top |
|
OSes are written in...
|
a systems-implementation language, or in a higher-level language
- improves their implementation, maintenance, and portability |
|
to create an OS for a particular machine configuration
|
perform system generation
|
|
mode for modifying page tables
|
kernel (aka supervisor or protected)
- generates exception if you attempt to modify |
|
how an OS is like any other program
|
- it has a main() function that gets called only once (during boot)
- consumes resources (memory) - can do silly things like generate errors |
|
MS-DOS structure
|
-simple
application program | resident system program || MS-DOS device drivers ||| vvv ROM BIOS device drivers------ |
|
Disadvantages of MS-DOS
|
- not modular
- inefficient - low protection or security |
|
OS layered structure advantages
|
- simplicity of construction
- ease of debugging - extensible |
|
OS layered structure disadvantages
|
- defining the layers
- each layer adds overhead |
|
Hardware Adaptation Layer (HAL)
|
- Extensions and Additional Device Drivers
- Device Drivers - Interrupt handlers - Boot and initialization |
|
microkernel structure
|
- moves as much as possible from kernel into "user" space
- user modules communicate with message passing |
|
benefits of microkernel structure
|
- easier to extend
- easier to port the OS to new architectures - more reliable (less code running in kernel mode) - more secure |
|
examples of microkernel structure
|
Mach, QNX
|
|
detriments of microkernel structure
|
- performance overhead of user to kernel space communication
|
|
most modern OSes implement...
|
kernel modules
|
|
kernel modules
|
- uses object-oriented approach
- each core component is separate - each talks to the others over known interfaces - each is loadable as needed within the kernel |
|
examples of kernel modules structures
|
Solaris, Linux, MAC OS X
|
|
uses for virtual machines
|
- system building
- protection |
|
con of virtual machines
|
implementation
|
|
types of OS structures (5)
|
- Monolithic
- Layered - Microkernel - Modular - Virtual Machines |
|
Monolithic advantage
|
performance
|
|
Monolithic disadvantages
|
difficult to extend, debug, secure, and make reliable
|
|
Layered advantages
|
- simplicity of construction
- debugging - extensible |
|
Layered disadvantages
|
- defining layers
- performance overhead |
|
Microkernel advantages
|
- easy to extend, port
- more reliable and secure |
|
Microkernel disadvantages
|
performance overhead
|
|
Modular advantages
|
monolithic performance with layered flexibility
|
|
Modular disadvantages
|
modules can still crash system
|
|
Virtual machines advantages
|
- protection/isolation
- great systems building tool |
|
Virtual Machines disadvantage
|
difficult to implement
|
|
process
|
task created by the OS, running in a restricted virtual machine environment - a virtual CPU, virtual memory environment, interface to the OS via system calls
|
|
components of a process
|
- the unit of execution
- the unit of scheduling - thread of execution + address space |
|
program consists of...
|
- code: machine instructions
- data: variables stored and manipulated in memory - DLLs: libraries that were not compiled or linked with the program (possibly shared with other programs) - mapped files: memory segments containing variables (frequently used in db programs) |
|
rel. between process and program
|
a process is executing a program
|
|
"Execution State" of a process
|
indicates what it is doing
1) Ready: waiting to be assigned to the CPU 2) Running: executing instructions on the CPU 3) Waiting: waiting for an event, e.g., I/O completion |
|
PCB
|
Process Control Block
-has all the details of a process: process ID process state general purpose registers stack pointer program counter accounting info security credentials username of owner queue pointers signal masks memory management |
|
context switch
|
all registers loaded into CPU and modified
(saves register values of that process, loads new ones) - very machine dependent |
|
costs of context switch
|
- cost of loading/storing registers to/from main memory
- opportunity cost of flushing useful caches - wait for pipeline to drain in pipelined processes |
|
TLB
|
Translation Lookaside Buffer
= cache of useful page tables |
|
creating processes
|
boot starts first process
other processes are started as children, like a tree (parent/child relationships) |
|
fork() does...
|
- gets new address space
- parent and child still share EVERYTHING (memory, OS state) |
|
pipeline
|
each process produces work for the next stage that consumes it
|
|
cooperating processes can be used...
|
- to gain speedup by overlapping activities or working in parallel
- to better structure an application as set of cooperating processes - to share information between jobs |
|
thread of control
|
defines where the process is currently executing (that is the PC and registers)
|
|
full process includes...
|
- address space (defining all the code and data pages)
- OS resources and accounting info - thread of control |
|
what do lightweight processes share?
|
- code and data (address space)
- same privileges - share almost everything in the process |
|
what DON'T lightweight processes share?
|
program counter, registers, and stack pointer
|
|
idea behind LWP
|
separate idea of process (address space, accounting, etc) from that of the minimal "thread of control" (PC, SP, registers)?
|
|
difference between processes and threads
|
process has address space and general process attributes
thread defines a sequential execution stream within a process processes are the containers that threads run in (only one process per thread, many threads per process) |
|
thread
|
- no data segment or heap
- cannot live on its own, must be inside process - inexpensive creation - inexpensive context switching thread dies, its stack is reclaimed |
|
process
|
- has code/data/heap and other segments
- must be at least one thread in a process - threads within a process share code/data/heap, share I/O, but each has its own stack and registers - expensive creation - expensive context switching - if a process dies, its resources are reclaimed and all threads die |
|
LWP
|
Lightweight Processes
- another name for kernel threads |
|
Kernel threads are slow because...
|
- thread op still requires system call
- kernel threads may be overly general - kernel doesn't trust user (lots of checking) |
|
user-level threads represented by... (4)
|
- program counter
- registers - stack - small control block |
|
cooperative threading
|
threads yield to each other
|
|
pre-emptive threading
|
rely on CPU scheduler to interrupt threads and start next one
implemented with timer - timer handler decides which thread to run next |
|
multiplexing user-level threads
|
package sees kernel-level "virtual" processors, and schedules threads to run on these processors
|
|
many-to-one model
|
many user level threads, one LWP
- thread creation, scheduling, synchronization done in user space - mainly used in language systems, portable libraries + fast (no system calls) + few system dependencies (portable) - no parallel execution of threads - all threads block when one uses synchronous I/O |
|
one-to-one model
|
one user-level thread per LWP
- thread creation, scheduling, synch require system calls - Linux Threads, Windows NT, Windows 2000, OS/2 + more concurrency + better multiprocessor performance - each user thread requires creation of kernel thread - each thread requires kernel resources; limits # of total threads |
|
many-to-many model
|
many user-level threads to many LWPs (cross in the middle)
- U < L, no benefits of multithreading - U > L, some threads may have to wait for an LWP |
|
thread gives up control of LWP under following conditions (4)
|
synchronization
lower priority yielding time slicing |
|
bound threads
|
permanently mapped to single, dedicated LWP
|
|
unbound threads
|
may move among LWPs in set
|
|
Two-level model
|
combination of one-to-one and "strict" many-to-many models
- flexible, best of both worlds |
|
Multithreading issues
|
- semantics of fork() and exec() system calls
- thread cancellation (asynch vs deferred cancellation) - signal handling (which thread to deliver to?) - thread pools (creating new threads, unlimited number of threads) - thread specific data - scheduler activations (maintaining correct number of sched threads) |
|
PThreads
|
- a POSIX stsandard API for thread creation and synchronization
- common in UNIX OSes (Solaris, Linux MAC OS X) |
|
POSIX
|
Portable Operating System Interface for uniX
|
|
to create a new thread in Linux...
|
clone()
- child shares address space of parent task (process) |
|
creating java threads...(2)
|
- extending thread class
- implementing the runnable interface |
|
long term scheduler
|
- loads a job in memory
- runs infrequently |
|
short term scheduler
|
- select ready process to run on CPU
- should be fast |
|
middle term scheduler (aka swapper)
|
reduce multiprogramming or memory consumption
|
|
process model
|
process alternates between CPU and I/O bursts
|
|
problem with process model
|
don't know job's type before running
|
|
scheduling evaluation metrics...underlying assumption:
|
"response time" most important for interactive jobs (I/O bound)
|
|
CPU utilization
|
percentage of time that the CPU is not idle
|
|
throughput
|
completed processes per time unit
|
|
turnaround time
|
time from submission to completion
|
|
waiting time
|
time spent on the waiting queue
|
|
response time
|
response latency
|
|
predictability
|
variance of quantitative criteria for evaluating sched algoritm
|
|
the perfect CPU scheduler
|
- minimize latency
- maximize througput - maximize utilization (keep I/O busy) - fairness, no one starves |
|
Problem cases for scheduling
|
- blindness about job types (I/O goes idle)
- optimization involves favoring jobs of types A over B (Lots of A's, B's starve) - interactive process trapped behind others (response time sucks for no reason) - priority inversion: A depends on B, A's priority > B's (B never runs) |
|
sched alg: FCFS
|
- jobs are scheduled in order of arrival
- nonpreemptive - problem: average wait time depends on arrival order - advantage: really simple |
|
convoy effect
|
CPU bound job holds CPU until done
result: poor I/O device utilization |
|
sched alg: LIFO
|
Last in First out
- newly arrived jobs are placed at the head of the ready queue - improves response time for newly created threads - problem: may starve early processes |
|
sched alg: SJF
|
shortest job first
- choose job with shortest next CPU burst - provably optimal for minimizing average wait time |
|
problem with SJF
|
impossible to know length of next CPU burst
|
|
sched alg: SRTF
|
shortest remaining time first
- preemptive SJF |
|
exponential averaging
|
based on past experience, estimate next CPU burst length
|
|
priority scheduling
|
- choose next job based on priority
- for SJF, priority = expected CPU burst - can be either preemptive or non-preemptive problem: starvation solution: age process (increase priority over time) |
|
round robin
|
- often used for timesharing
- ready queue is a circular queue (FIFO) - each process given a time slice - run for quantum or until it blocks - allocates uniformly (fairly) |
|
Gantt chart
|
chart of which process is running for what time chunk (like a timeline)
|
|
time quantum
|
don't choose too high (you wind up with FCFS)
don't choose too low (spending all your time on context switching) |
|
multilevel queue scheduling
|
- multiple ready queues based on job type
|
|
gang scheduling
|
run all threads belonging to a process together with a multiprocessor
|
|
two-level scheduling
|
medium level scheduler
schedule processes, and within processes schedule threads |
|
space-based affinity
|
assign threads to processors
improve cache hit ratio, but can bite under low-load condition |
|
real-time scheduling policies
|
- rate monotonic (just one scalar priority related to periodicity of the job
- earliest deadline first (EDF) - dynamic but more complex (priority = deadline) |
|
race condition
|
timing dependent error involving shared state
|
|
critical section goals (4)
|
- safety (mutex)
- liveness (progress) - bounded waiting - fairness |
|
Dekker's algorithm
|
CSEnter(int i){
inside[i] = true; while(inside[j]){ if(turn == j){ inside[i] = false; while(turn == j) continue; inside[i] = true; } } } CSExit (int i){ turn=j; inside[i] = false; } |
|
mutex
|
provides mutual exclusion
|
|
spinlock
|
busy waiting loops continuously on entry code (problematic in real multiprogramming systems)
|