1/62
Looks like no tags are added yet.
what is a program?
a file on the disk
what is a process?
a program that is running
what is included in a process state?
memory (its address space), registers, and the kernel state
what is an address space and what address does it begin at for each process?
the range of addresses a process believes it owns, starting at 0

what is included in a process’s memory (address space)?
code, data, heap, and stack

what is the stack and how does it grow?
memory for function calls, and grows negatively

what is the heap and how does it grow?
memory you ask for while the program runs, using malloc() and give back with free(), it grows positively

what is a thread and what is included in it?
one stream of execution inside a process, it has its own registers and stack but shares code, globals, and heap with other threads of the same process
how is a process created?
load the program’s code and data from disk into memory
allocate the stack
create the heap
set up I/O: open three file descriptors: STDIN (input), STDOUT (output), STDERR (errors). Initialize registers
start running: hand CPU to the process
what is time sharing?
one process at a time gets the entire CPU
what is space sharing?
all processes get part of the memory and disk
what is mechanism?
the context switch: how to switch from one process to another, the mechanism of saving one process’s registers and restoring another’s so the second one continues where it left off
what is policy?
the scheduler: which process should run next
what is the running, ready, and blocked running states?
running: on the CPU currently
ready: could run, waiting for its turn
blocked: waiting for something slow, like an I/O
what is the idle process?
a low priority “idle” process that the OS runs if every process is blocked
what is the PCB and what is included in it?
process control block, and includes the process ID (PID), its state, a pointer to its parent, saved registers (“CPU context”), a pointer to its address space, and list of open files
what is user mode?
the restricted mode normal programs run in, can’t touch hardware directly
what is kernel mode?
the privileged mode the OS runs in (full access)
what is a system call?
a request from a program to the OS to do something privileged, like reading a file
what is trap?
a special instruction that jumps from user mode into the kernel and raises the privilege level. return-from-trap goes back and lowers it
what is an interrupt?
a signal that stops what the CPU is doing so the OS can handle an event
what is the trap table?
a table set up by the OS at boot, that tells the hardware which OS code to run for each kind of trap or interrupt
what is direct execution?
letting a program run straight on the CPU with no supervision
what are the problems of direct execution?
could do something illegal (touch another process’s memory or touch hardware)
could do something slow (I/O)
could run forever
what is limited direction execution?
running on the bare CPU whenever possible, but intercept when needed
how can a program do something privileged?
make a system call, which traps into the kernel. the kernel checks the request, does the work, and returns-from-trap
what is the cooperative approach for getting the CPU back, and what is the problem with this?
wait until the process makes a system call, calls yield(), or crashes. the problem is that a process stuck in an infinite loop never gives control back
what is the non-cooperative approach for getting the CPU back?
the OS sets a hardware timer and when it fires, the process running is paused, its state is saved, and the OS decides what to run next
what does fork() do?
creates a new child process that is a copy of the parent
on success, returns 0 in the child
on success, returns the child’s PID in the parent
on failure, returns a negative number in the parent and no child exists
what does exec() do?
replaces the current process’s memory with a new program loaded from disk
on success, it never returns
what does wait() do?
makes the parent block until a child finishes
what does exit() do?
ends the current process
what are the steps when creating and switching to the child?
OS allocates a new PCB
copies the parent’s address space
marks the child Ready and puts it on the process list, then returns different values to each
on a timer interrupt, or a blocking call like wait(), the OS saves the running process’s registers into its PCB, restores the other’s, and switches to it
what is a job/task?
another word for process
what is a scheduler?
the OS policy that picks which ready process runs next
what is preemption?
the OS forcibly stopping a running process to run another
what is the formula for turnaround time?
completion − arrival
what is the formula for response time?
first run − arrival
what is utilization and should it be maximized or minimized?
fraction of the time the CPU is busy; maximize
what is FIFO, its pros and cons, and is it preemptive or non-preemptive?
first in, first out: run jobs in arrival order, each to completion
pro: simple
con: convoy effect (one long job makes all the short jobs wait)
non-preemptive
what is SJF, its pros and cons, and is it preemptive or non-preemptive?
shortest job first: pick the ready job with the shortest total run time
pro: optimal for average turnaround when all jobs arrive at the same time
con: late short jobs stuck
non-preemptive
what is STCF, its pros and cons, and is it preemptive or non-preemptive?
shortest time to completion first: every time a new job arrives, compare its run time with the remaining time of the current job. run whichever will finish first
pro: good average turnaround with late arrivals
con: bad response for long jobs
preemptive
what is RR, its pro and cons, and is it preemptive or non-preemptive?
round robin: run each job consecutively for one time slice
pros: good response time
cons: bad turnaround time
preemptive
what is MLFQ, its pros and cons, and is it preemptive or non-preemptive?
multi-level feedback queue: several queues, each priority level. higher queues have short time slices, lower queues have longer time slices.
MLFQ rules:
if prio(A) > prio(B), A runs
if prio(A) = prio(B), run in RR
a new job starts at the top priority
once a job uses up it allotment at a level, its priority drops one level
after some period S, move all jobs to the top queue
preemptive
what is lottery, its pros and cons, and is it preemptive or non-preemptive?
each job holds tickets. each time slice, pick a random winning ticket: its owner runs
pros: over a long time, shares come out right
cons: over a short time, luck can make it unfair
preemptive
what is stride, its pros and cons, and is it preemptive or non-preemptive?
each job’s stride = (big number) ÷ (its tickets)
each job has a pass counter starting at 0
each slice: run the job with the lowest pass, then add its stride to its pass
cons: a new job starts at pass 0, so it monopolizes the CPU until it catches up
preemptive
what is CFS, and is it preemptive or non-preemptive?
completely fair scheduler: always runs the job that has had the least fair share so far, keeping the jobs in a sorted tree
when are the schedulers equivalent?
FIFO = SJF when jobs arrive in order of length, shortest first (or all have the same length)
SJF = STCF when all jobs arrive at the same time
RR = FIFO when the time slice at least as long as every job
what is physical memory?
RAM
what is a virtual address?
the address a program uses, hardware translates it into a physical address
what is a segmentation fault?
the error raised when a program uses an address it is not allowed to use
what is the base in base and bounds?
where the region starts in physical memory
what is the bounds in base and bounds?
how big the region is
what is the rule for translating virtual address into physical address?
if virtual address < bounds: physical = virtual + base
otherwise: segmentation fault
what are the pros and the cons of base and bounds?
pros: isolation achieved, and translation is cheap
cons: the whole address space must be contiguous, including the large unused gap between heap and stack, which wastes memory
what is internal and external fragmentation?
internal fragmentation: wasted space inside a region that was given out (unused gap between heap and stack in base and bounds)
gaps in process’s virtual memory
external fragmentation: free space between allocated regions in physical memory, chopped into holes too small to use
gaps in physical memory
how does segmentation work?
give each logical piece (code, heap, stack) its own base and bounds. each segment is contiguous by itself, but the segments can be anywhere in physical memory, and the unused gap between heap and stack takes no physical memory
how do you figure out the physical address in segmentation?
for code, heap:
look at the top 2 bits to figure out which segment: (00 = code, 01 = heap, 10 = stack)
figure out the offset: offset = VA - 8192 (the same as the bottom 12 bits)
if offset < segment size, physical = base + offset. otherwise, segmentation fault
for stack:
make the offset negative. negative offset = offset - 4096
if |negative offset| is less than or equal to (the stack size), physical = base + negative offset. otherwise, segmentation fault
what is a page in paging?
a fixed-size chunk of the virtual address space
what is a page frame in paging?
a fixed-size slot of physical memory, the same size as a page
what is a VPN in paging?
virtual page number: which page a virtual address is in
what is a PFN in paging?
page frame number or PPN: which physical frame a page is stored in
what is the formula for page table size?
(# of pages) x (size of one PTE)