Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/141

Click to flip

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)