Cs414 Operating Systems

Front 1

Memory Mapped I/O

Back 1

- I/O devices appear as regular memory to CPU;
- regular loads/stores for accessing device;
- this is more commonly used;

Front 2

Programmed I/O

Back 2

- also called "channel" I/O;
- CPU has separate bus for I/O devices;
- special instructions are requried;

Front 3

Device controllers have...

Back 3

- 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);

Front 4

To write data to a device: (6)

Back 4

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)

Front 5

DMA

Back 5

Direct Memory Access
- transfer data directly between device and memory (no CPU intervention)
- device controller transfers blocks of data

Front 6

DMA interrupts when...

Back 6

when block transfer completed (instead of when one byte is completed)

Front 7

DMA useful for...

Back 7

high-speed I/O devices

Front 8

Two types of interrupts

Back 8

1) Maskable (can be turned off)
2) Nonmaskable (can't be turned off, because they signify serious error like unrecoverable memory error)

Front 9

Interrupt vector contains...

Back 9

addresses of interrupt handlers for each device (can chain and then search if there are more devices than places in vector)

Front 10

Traps and exceptions

Back 10

Software generated interrupt

Front 11

Traps

Back 11

User program requires OS service (caused by system calls)

Front 12

Exceptions

Back 12

User program acts silly
- divide by 0, or memory access violation
- just a performance optimization

Front 13

Protect against infinite loops

Back 13

- 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

Front 14

Protected/privileged instructions

Back 14

- 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

Front 15

Dual Mode Operation

Back 15

- user mode and kernel mode
- OS runs in kernel mode, user programs in user mode
- mode bit provided by hardware

Front 16

How to change mode to kernel?

Back 16

System call

Front 17

How to return from system call?

Back 17

RTI to reset to user

Front 18

How do user programs do something privileged?

Back 18

Call OS procedure

Front 19

System calls and APIs

Back 19

SC most commonly accessed by programs using APIs (Win32, POSIX, Java) because easier to use

Front 20

Solution to reduce system call overhead

Back 20

- perform some system functionality in user mode
- Libraries (DLLs) cache results or buffering ops

Front 21

Dual mode solves technical and social problems... name them

Back 21

Technical: have process/memory quotas
Social: yell at idiots that crash machines

Front 22

Last pure bastion of fascism

Back 22

Operating Systems! (because they use system feedback rather than blind fairness)

Front 23

OS jobs for process management (5)

Back 23

- 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

Front 24

OS jobs for memory management (3)

Back 24

- 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

Front 25

Disk access methods (2)

Back 25

sequential or random

Front 26

OS jobs for file/storage management (5)

Back 26

- 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

Front 27

OS jobs for disk management

Back 27

- free space management
- storage allocation
- disk scheduling

Front 28

tertiary storage

Back 28

magnetic tape drives, CD, DVD drives and platters

Front 29

WORM

Back 29

write once, read many times

Front 30

RW

Back 30

read-write

Front 31

solid-state disks

Back 31

electronic RAM disks

Front 32

memory hierarchy (4)

Back 32

magnetic disk ->
main memory ->
cache ->
hardware register

Front 33

I/O subsystem components (3)

Back 33

- memory management component that includes buffering, caching, and spooling
- general device-driver interface
- drivers for specific hardware devices

Front 34

compute-server system

Back 34

client sends requests to perform action (read data)

Front 35

file-server system

Back 35

file-system interface (create, update, read, delete files), like a web server sends files to browsers

Front 36

5 categories of system calls

Back 36

- process control
- file manipulation
- device manipulation
- information maintenance
- communications

Front 37

Good technique for designing an OS

Back 37

- modularity is important
- sequence of layers or using a microkernel

Front 38

virtual machine

Back 38

- 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

Front 39

OSes are written in...

Back 39

a systems-implementation language, or in a higher-level language
- improves their implementation, maintenance, and portability

Front 40

to create an OS for a particular machine configuration

Back 40

perform system generation

Front 41

mode for modifying page tables

Back 41

kernel (aka supervisor or protected)
- generates exception if you attempt to modify

Front 42

how an OS is like any other program

Back 42

- it has a main() function that gets called only once (during boot)
- consumes resources (memory)
- can do silly things like generate errors

Front 43

MS-DOS structure

Back 43

-simple
application program |
resident system program ||
MS-DOS device drivers |||
vvv
ROM BIOS device drivers------

Front 44

Disadvantages of MS-DOS

Back 44

- not modular
- inefficient
- low protection or security

Front 45

OS layered structure advantages

Back 45

- simplicity of construction
- ease of debugging
- extensible

Front 46

OS layered structure disadvantages

Back 46

- defining the layers
- each layer adds overhead

Front 47

Hardware Adaptation Layer (HAL)

Back 47

- Extensions and Additional Device Drivers
- Device Drivers
- Interrupt handlers
- Boot and initialization

Front 48

microkernel structure

Back 48

- moves as much as possible from kernel into "user" space
- user modules communicate with message passing

Front 49

benefits of microkernel structure

Back 49

- easier to extend
- easier to port the OS to new architectures
- more reliable (less code running in kernel mode)
- more secure

Front 50

examples of microkernel structure

Back 50

Mach, QNX

Front 51

detriments of microkernel structure

Back 51

- performance overhead of user to kernel space communication

Front 52

most modern OSes implement...

Back 52

kernel modules

Front 53

kernel modules

Back 53

- 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

Front 54

examples of kernel modules structures

Back 54

Solaris, Linux, MAC OS X

Front 55

uses for virtual machines

Back 55

- system building
- protection

Front 56

con of virtual machines

Back 56

implementation

Front 57

types of OS structures (5)

Back 57

- Monolithic
- Layered
- Microkernel
- Modular
- Virtual Machines

Front 58

Monolithic advantage

Back 58

performance

Front 59

Monolithic disadvantages

Back 59

difficult to extend, debug, secure, and make reliable

Front 60

Layered advantages

Back 60

- simplicity of construction
- debugging
- extensible

Front 61

Layered disadvantages

Back 61

- defining layers
- performance overhead

Front 62

Microkernel advantages

Back 62

- easy to extend, port
- more reliable and secure

Front 63

Microkernel disadvantages

Back 63

performance overhead

Front 64

Modular advantages

Back 64

monolithic performance with layered flexibility

Front 65

Modular disadvantages

Back 65

modules can still crash system

Front 66

Virtual machines advantages

Back 66

- protection/isolation
- great systems building tool

Front 67

Virtual Machines disadvantage

Back 67

difficult to implement

Front 68

process

Back 68

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

Front 69

components of a process

Back 69

- the unit of execution
- the unit of scheduling
- thread of execution + address space

Front 70

program consists of...

Back 70

- 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)

Front 71

rel. between process and program

Back 71

a process is executing a program

Front 72

"Execution State" of a process

Back 72

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

Front 73

PCB

Back 73

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

Front 74

context switch

Back 74

all registers loaded into CPU and modified
(saves register values of that process, loads new ones)
- very machine dependent

Front 75

costs of context switch

Back 75

- cost of loading/storing registers to/from main memory
- opportunity cost of flushing useful caches
- wait for pipeline to drain in pipelined processes

Front 76

TLB

Back 76

Translation Lookaside Buffer
= cache of useful page tables

Front 77

creating processes

Back 77

boot starts first process
other processes are started as children, like a tree (parent/child relationships)

Front 78

fork() does...

Back 78

- gets new address space
- parent and child still share EVERYTHING (memory, OS state)

Front 79

pipeline

Back 79

each process produces work for the next stage that consumes it

Front 80

cooperating processes can be used...

Back 80

- 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

Front 81

thread of control

Back 81

defines where the process is currently executing (that is the PC and registers)

Front 82

full process includes...

Back 82

- address space (defining all the code and data pages)
- OS resources and accounting info
- thread of control

Front 83

what do lightweight processes share?

Back 83

- code and data (address space)
- same privileges
- share almost everything in the process

Front 84

what DON'T lightweight processes share?

Back 84

program counter, registers, and stack pointer

Front 85

idea behind LWP

Back 85

separate idea of process (address space, accounting, etc) from that of the minimal "thread of control" (PC, SP, registers)?

Front 86

difference between processes and threads

Back 86

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)

Front 87

thread

Back 87

- 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

Front 88

process

Back 88

- 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

Front 89

LWP

Back 89

Lightweight Processes
- another name for kernel threads

Front 90

Kernel threads are slow because...

Back 90

- thread op still requires system call
- kernel threads may be overly general
- kernel doesn't trust user (lots of checking)

Front 91

user-level threads represented by... (4)

Back 91

- program counter
- registers
- stack
- small control block

Front 92

cooperative threading

Back 92

threads yield to each other

Front 93

pre-emptive threading

Back 93

rely on CPU scheduler to interrupt threads and start next one

implemented with timer - timer handler decides which thread to run next

Front 94

multiplexing user-level threads

Back 94

package sees kernel-level "virtual" processors, and schedules threads to run on these processors

Front 95

many-to-one model

Back 95

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

Front 96

one-to-one model

Back 96

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

Front 97

many-to-many model

Back 97

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

Front 98

thread gives up control of LWP under following conditions (4)

Back 98

synchronization
lower priority
yielding
time slicing

Front 99

bound threads

Back 99

permanently mapped to single, dedicated LWP

Front 100

unbound threads

Back 100

may move among LWPs in set

Front 101

Two-level model

Back 101

combination of one-to-one and "strict" many-to-many models
- flexible, best of both worlds

Front 102

Multithreading issues

Back 102

- 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)

Front 103

PThreads

Back 103

- a POSIX stsandard API for thread creation and synchronization
- common in UNIX OSes (Solaris, Linux MAC OS X)

Front 104

POSIX

Back 104

Portable Operating System Interface for uniX

Front 105

to create a new thread in Linux...

Back 105

clone()
- child shares address space of parent task (process)

Front 106

creating java threads...(2)

Back 106

- extending thread class
- implementing the runnable interface

Front 107

long term scheduler

Back 107

- loads a job in memory
- runs infrequently

Front 108

short term scheduler

Back 108

- select ready process to run on CPU
- should be fast

Front 109

middle term scheduler (aka swapper)

Back 109

reduce multiprogramming or memory consumption

Front 110

process model

Back 110

process alternates between CPU and I/O bursts

Front 111

problem with process model

Back 111

don't know job's type before running

Front 112

scheduling evaluation metrics...underlying assumption:

Back 112

"response time" most important for interactive jobs (I/O bound)

Front 113

CPU utilization

Back 113

percentage of time that the CPU is not idle

Front 114

throughput

Back 114

completed processes per time unit

Front 115

turnaround time

Back 115

time from submission to completion

Front 116

waiting time

Back 116

time spent on the waiting queue

Front 117

response time

Back 117

response latency

Front 118

predictability

Back 118

variance of quantitative criteria for evaluating sched algoritm

Front 119

the perfect CPU scheduler

Back 119

- minimize latency
- maximize througput
- maximize utilization (keep I/O busy)
- fairness, no one starves

Front 120

Problem cases for scheduling

Back 120

- 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)

Front 121

sched alg: FCFS

Back 121

- jobs are scheduled in order of arrival
- nonpreemptive
- problem: average wait time depends on arrival order
- advantage: really simple

Front 122

convoy effect

Back 122

CPU bound job holds CPU until done

result: poor I/O device utilization

Front 123

sched alg: LIFO

Back 123

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

Front 124

sched alg: SJF

Back 124

shortest job first
- choose job with shortest next CPU burst
- provably optimal for minimizing average wait time

Front 125

problem with SJF

Back 125

impossible to know length of next CPU burst

Front 126

sched alg: SRTF

Back 126

shortest remaining time first
- preemptive SJF

Front 127

exponential averaging

Back 127

based on past experience, estimate next CPU burst length

Front 128

priority scheduling

Back 128

- 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)

Front 129

round robin

Back 129

- 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)

Front 130

Gantt chart

Back 130

chart of which process is running for what time chunk (like a timeline)

Front 131

time quantum

Back 131

don't choose too high (you wind up with FCFS)

don't choose too low (spending all your time on context switching)

Front 132

multilevel queue scheduling

Back 132

- multiple ready queues based on job type

Front 133

gang scheduling

Back 133

run all threads belonging to a process together with a multiprocessor

Front 134

two-level scheduling

Back 134

medium level scheduler

schedule processes, and within processes schedule threads

Front 135

space-based affinity

Back 135

assign threads to processors

improve cache hit ratio, but can bite under low-load condition

Front 136

real-time scheduling policies

Back 136

- rate monotonic (just one scalar priority related to periodicity of the job

- earliest deadline first (EDF) - dynamic but more complex (priority = deadline)

Front 137

race condition

Back 137

timing dependent error involving shared state

Front 138

critical section goals (4)

Back 138

- safety (mutex)
- liveness (progress)
- bounded waiting
- fairness

Front 139

Dekker's algorithm

Back 139

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;
}

Front 140

mutex

Back 140

provides mutual exclusion

Front 141

spinlock

Back 141

busy waiting loops continuously on entry code (problematic in real multiprogramming systems)