Section 1
Preview this deck
atomic operation
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (54)
Section 1
(50 cards)
atomic operation
-runs to completion or not at all -on uniprocessor, atomic if no context switch can occur in middle of op
4 conditions for correctness in critical section
-safety: only 1 thread in crit section at a time -liveness: thread must be guaranteed to eventually enter crit section if no threads currently in it -bounded wait: if thread wants to enter crit section, bound on # of threads that can enter before it -failure atomicity: ok if thread dies in crit section
phase 2 of OS development
-cheap hardware, expensive humans -interactive timesharing uses multiple terminals at once -new issues: response time and thrashing; more protection, sharing, and concurrency needed -new features: shell, filesys, interactivity, VM
boot sequence
-boot program loaded from ROM, which checks machine config, builds config struct describing hw, and loads OS kernel w config struct -kernel data structs and hw device states init -processes created to start op -after basic stuff, runs user programs, or idle loop if nothing available (system mgmt, low power) and wakes on hw interrrupts
PCB vs TCB
-PCB has process-specific info like owner, PID, heap ptr, active thread, ptrs to thread info -TCB has thread-specific info like stack ptr, PC, thread state, reg vals, ptr to PCB
how to use a monitor
-acquire lock at the start of function, temp release lock if missing other res (use cond var) and reacquire when all available, op on shared data, then release lock
process control block
-dynamic kernel data struct kept in mem that reps exec state and location of process when not exec -contains PID, PC, ESP, contents of general regs, mem mgmt info, owner name, list of open files (any process exec state not in addr space)
kernel-level threads
-OS knows it exists, so managed and scheduled by kernel alongside processes -small context switch between threads bc must get val of regs, PC, and ESP; less than process context switch bc same addr space -when thread does I/O, OS can choose another thread from same process -multithreading -OS has threads (idle, init) -indep threads are deterministic & don't share state; cooperating threads do & give concurrency
atomic read-modify-write instruction
-atomically reads val from mem into reg and writes new val -new instr on uniprocessor -on multiprocessor, must invalidate val in other processes' caches, and lock mem bus to prevent other processors from accessing mem until done -test&set or compare&swap
MLFQ
-approx of SJF -round robin used at each priority level; once done with one level, run jobs out of next level -can lead to starvation, so can give each queue fraction of CPU time or bump up all priorities periodically -the higher the priority, the shorter the time slice priority drops if does not block in time slice, but can raise if blocks early -prioritizes I/O bound
3 interfaces of OS
-AMI (abstract machine interface): between OS and apps; contains API, mem access model, set of legal instr -API (app programming interface); system calls -HAL (hw abstraction layer): between OS and hardware
race condition
-result changes based on scheduling -when things can happen in the wrong order -need synch if any interleaving can yield incorrect result
SJF
-sched job w least amount of work until blocking or terminating -prioritizes I/O bound jobs -max throughput -can be preemptive or not
dual mode execution
-user mode: can't directly address I/O, manip OS mem, set mode bit, disable/enable interrupts, or halt machine -kernel mode: unrestricted access
phase 1 of OS development
-hw expensive, humans cheap 1: one user at a time, but didn't utilize capability fully 2: batch processing uses hw better but no protection and idle during I/O 3: overlap of I/O & computation w interrupts; concurrency within single process 4: multiprogramming has multiple processes running at same time; req mem protection and reloc
cpu scheduler
-selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them -execs when process switches from running to blocked, process created or terminated, interrupt -helps provide illusion of infinite memory
monitor
-lock and 0+ condition vars to manage concurrent access to shared data -lock ensures only 1 thread active in monitor at once, and mutex for shared data -cond vars let threads block waiting for an event in a crit section -encapsulate shared data and allow ops on it, provide mutex, let threads synch in crit section
measures of performance
-efficiency/overhead: is overhead of OS worth it? -also fairness, response time, throughput, and predictability
producers/consumers problem
-global buffer of fixed size n -producer puts items, consumer consumes -what happens if producer produces past capacity? or consumer depletes buffer?
how to evaluate an OS
-reliability: consistently performs to specs, (mostly) error-free, availability (% time system useful) -security: policy & mechanism; allow legit sharing but prevent illegal access; strong fault iso -portability: doesn't have to change if hardware does; can support future apps
features req for protection
-privileged instr only for kernel mode -timer interrupts that let kernel preempt running process to prevent process from taking control -mem protection
semaphore
-generalized lock w atomic up and down ops -value that represent amt of res, not just busy/free -supports queue of waiting threads -binary (same as lock) or counted -used for mutex, control access to res pool, general synch bc down and up can be called by different threads
parts of process state
-code, PC, exec stack w ESP, static data, heap & its ptr, CPU reg vals, OS res in use, PID, exec state
things needed to control processes
-set and change priority -support debugging (ptrace() lets process be controlled by another process) -alarm/timer to preempt
ways to prevent deadlock
-order locks and grab them in a preset order, but difficult to maintain order globally and may take up res for longer -can prevent hold and wait -preempt resources -prevent circular wait by having sufficient resources
thread
-entity exec seq on instr -each process has at last 1 but can have more multithreading can improve performance and better rep task structure -benefits: cheaper to create, cheaper to context switch, easier to communicate
switching from user to kernel mode
1: user program state saved -privileged hw register points to exception stack; on switch, some of interrupted process regs on exception stack before handler runs, then handler pushes the rest; reverse on return -don't use user level stack bc could have invalid addr; don't want kernel state in user space 2: hardware ID reason, chooses entry in interrupt vector; invokes correct handler
threads and the address space
-process's threads share same address space, so any data can by accessed by any thread -each thread has own (unprotected) stack, and exclusive use of CPU regs when exec
busy waiting with test&set
-while loop for test&set causes busy waiting; could be ok if short crit section -priority inversion possible (thread waiting for lock has higher priority than thread using lock) -low latency to get lock bc once free, waiting thread gets it as soon as sched -can voluntarily yield CPU if don't get lock -better to busy wait on lock than crit section w lock indicator var
ways to enter the kernel
-exceptions: user program does something wrong or tries to exec privileged instr; synch -interrupts: stops currently exec process; asynch -system calls/traps: user req OS service; synch on return, incr pc if synch
deadlock
-2+ threads waiting on event that can only be generated by those same threads -not the same as starvation, though does imply it
necessary and sufficient conditions for deadlock
-mutual exclusion: at least one thread has exclusive access to resource -hold & wait: thread holds resources until has all, but another thread has res it needs -circular wait -no preemption: thread only releases res voluntarily; cannot be forced -need to break one of the conditions to stop deadlock
fork()
-fork makes copy of process that called it, and returns different value to child vs parent -begin exec from same point right after fork -each has own memory and copy of everything -every command typed into shell is child process
process
-program during execution; basic unit of exec -each instance of program is new process -main abstraction for protection -at min req mem and CPU regs
lock
-lets one thread prevent another thread from doing something -lock before crit section, unlock when done, wait if already locked -provides mutual exclusion -acquire: wait until lock is free, then grab -release: unlock and wake up any waiting thread
mutual exclusion
-when one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources -applies whether read or write
problems with semaphores
-still global vars -too many purposes -easy to use incorrectly or mess up -makes code difficult to read and write
kill()
-used by parent to terminate child but also just to communicate between processes -sends specified signal to process by PID -receiving process's signal handler goes off signal is user-level interrupt
phase 3 of OS development
-v cheap hw, v expensive humans -personal computing: tried to elim multiprog, concurrency, and protection, but wasted people's time -parallel & distrib computing: give people multiple computers to increase performance, reliability, and sharing of specialized res
exec()
-process overlaid with new program, same pid -can specify args; code, stack, heap change -same process running different program
wait()
-parent process waits for child to terminate; allows it to get return value -parents is put to sleep, then unblocked when child calls exit()
user-level threads
-threads the OS doesnt know about -thread library used to manage the threads (user can define scheduling policy) -threads must yield to other threads -minimal context switch: just save thread state and load new thread's state; happens if interrupted by signal or voluntarily yields -if one thread blocks, whole process blocks
FCFS/FIFO
-jobs sched in arrival order -low overhead, v fast -job runs until completion or block on I/O -non-preemptive
scheduling policy metrics
-CPU utilization, throughput, turnaround time, response time, waiting time -predictability also important -minimize overhead, be fair to each process
ideal synch solution
-satisfies correctness properties and isn't confusing to reason about -no busy waiting; block when waiting -symmetric; not specific to # threads
exit()
-called once program finishes exec -closes open files, deallocs mem & rel OS data structures, checks if parent alive (if so, becomes zombie, otherwise dead)
round robin
-adds timer and preemption to FCFS -minimizes response time -each process run for its quantum, then moved to back of queue -choose quantum where context switching ~ 1%
problems with disabling interrupts
-can disable until done modifying crit section, but can't wait too long bc will lose interrupts that need a response -interrupt state is part of thread state -disabling interrupts doesn't work on multiprocessors
3 hats of the OS
-referee: manage shared resources, provide isolation/protection, communication -illusionist: seems like more resources exist than actually do; involves virtualization of processor and memory -glue: interfaces with hardware so the programmer doesn't have to; provides filesys, VM, networking
system calls
-user requests kernel level service using API, parameters passed by calling convention -specific system call handler; then ID req service & params, exec, put result in reg, then RTI to user
Section 2
(4 cards)