operating systems

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/62

encourage image

There's no tags or description

Looks like no tags are added yet.

63 Terms

1
New cards

what is a program?

a file on the disk

2
New cards

what is a process?

a program that is running

3
New cards

what is included in a process state?

memory (its address space), registers, and the kernel state

4
New cards

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

<p>the range of addresses a process believes it owns, starting at 0</p>
5
New cards

what is included in a process’s memory (address space)?

code, data, heap, and stack

<p>code, data, heap, and stack</p>
6
New cards

what is the stack and how does it grow?

memory for function calls, and grows negatively

<p>memory for function calls, and grows negatively</p>
7
New cards

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

<p>memory you ask for while the program runs, using malloc() and give back with free(), it grows positively</p>
8
New cards

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

9
New cards

how is a process created?

  1. load the program’s code and data from disk into memory

  2. allocate the stack

  3. create the heap

  4. set up I/O: open three file descriptors: STDIN (input), STDOUT (output), STDERR (errors). Initialize registers

  5. start running: hand CPU to the process


10
New cards

what is time sharing?

one process at a time gets the entire CPU

11
New cards

what is space sharing?

all processes get part of the memory and disk

12
New cards

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

13
New cards

what is policy?

the scheduler: which process should run next

14
New cards

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

15
New cards

what is the idle process?

a low priority “idle” process that the OS runs if every process is blocked

16
New cards

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

17
New cards

what is user mode?

the restricted mode normal programs run in, can’t touch hardware directly

18
New cards

what is kernel mode?

the privileged mode the OS runs in (full access)

19
New cards

what is a system call?

a request from a program to the OS to do something privileged, like reading a file

20
New cards

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

21
New cards

what is an interrupt?

a signal that stops what the CPU is doing so the OS can handle an event

22
New cards

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

23
New cards

what is direct execution?

letting a program run straight on the CPU with no supervision

24
New cards

what are the problems of direct execution?

  1. could do something illegal (touch another process’s memory or touch hardware)

  2. could do something slow (I/O)

  3. could run forever


25
New cards

what is limited direction execution?

running on the bare CPU whenever possible, but intercept when needed

26
New cards

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

27
New cards

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

28
New cards

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

29
New cards

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


30
New cards

what does exec() do?

replaces the current process’s memory with a new program loaded from disk

  • on success, it never returns


31
New cards

what does wait() do?

makes the parent block until a child finishes

32
New cards

what does exit() do?

ends the current process

33
New cards

what are the steps when creating and switching to the child?

  1. OS allocates a new PCB

  2. copies the parent’s address space

  3. marks the child Ready and puts it on the process list, then returns different values to each

  4. 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


34
New cards

what is a job/task?

another word for process

35
New cards

what is a scheduler?

the OS policy that picks which ready process runs next

36
New cards

what is preemption?

the OS forcibly stopping a running process to run another

37
New cards

what is the formula for turnaround time?

completion − arrival

38
New cards

what is the formula for response time?

first run − arrival

39
New cards

what is utilization and should it be maximized or minimized?

fraction of the time the CPU is busy; maximize

40
New cards

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


41
New cards

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


42
New cards

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


43
New cards

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


44
New cards

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:

  1. if prio(A) > prio(B), A runs

  2. if prio(A) = prio(B), run in RR

  3. a new job starts at the top priority

  4. once a job uses up it allotment at a level, its priority drops one level

  5. after some period S, move all jobs to the top queue

  • preemptive


45
New cards

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


46
New cards

what is stride, its pros and cons, and is it preemptive or non-preemptive?

  1. each job’s stride = (big number) ÷ (its tickets)

  2. each job has a pass counter starting at 0

  3. 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


47
New cards

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

48
New cards

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


49
New cards

what is physical memory?

RAM

50
New cards

what is a virtual address?

the address a program uses, hardware translates it into a physical address

51
New cards

what is a segmentation fault?

the error raised when a program uses an address it is not allowed to use

52
New cards

what is the base in base and bounds?

where the region starts in physical memory

53
New cards

what is the bounds in base and bounds?

how big the region is

54
New cards

what is the rule for translating virtual address into physical address?

if virtual address < bounds: physical = virtual + base

otherwise: segmentation fault

55
New cards

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

56
New cards

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


57
New cards

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

58
New cards

how do you figure out the physical address in segmentation?

for code, heap:

  1. look at the top 2 bits to figure out which segment: (00 = code, 01 = heap, 10 = stack)

  2. figure out the offset: offset = VA - 8192 (the same as the bottom 12 bits)

  3. if offset < segment size, physical = base + offset. otherwise, segmentation fault


for stack:

  1. make the offset negative. negative offset = offset - 4096

  2. if |negative offset| is less than or equal to (the stack size), physical = base + negative offset. otherwise, segmentation fault


59
New cards

what is a page in paging?

a fixed-size chunk of the virtual address space

60
New cards

what is a page frame in paging?

a fixed-size slot of physical memory, the same size as a page

61
New cards

what is a VPN in paging?

virtual page number: which page a virtual address is in

62
New cards

what is a PFN in paging?

page frame number or PPN: which physical frame a page is stored in

63
New cards

what is the formula for page table size?

(# of pages) x (size of one PTE)