Final Exam Review - All Chapters and Tutorials, Focused on 6-9

Question 1

How do resources work in a model?

Answer 1

There are resource types (R1, R2, …, Rm), which can be CPU cycles, memory space, etc., and each resource type Ri has Wi instances (System with 2 CPUs, resource type CPU has 2 instances)

Question 2

May a deadlock involve the same resource types or different resource types? True/False?

Answer 2

True

Question 3

What 4 conditions must be held simultaneously for deadlock to occur?

Answer 3

Mutual exclusion, hold and wait, no preemption, circular wait

Question 4

Can a deadlock occur with mutex locks?

Answer 4

Yes, if the order of acquiring the mutex locks create a deadlock scenario Ex: thread_one first acquires mutex_one then mutex_two, thread_two first acquires mutex_two then mutex_one. If they both get their first mutex lock at the same time, deadlock occurs.

Question 5

How are the vertices (V) partitioned in a resource-allocation graph?

Answer 5

P = {P1, P2, …, Pn} (set consisting of all processes) and R = {R1, R2, …, Rn} (set consisting of all resource types)

Question 6

What edges (E) exist in a resource-allocation graph?

Answer 6

Request edges (directed edge from Pi -> Rj) and assignment edges (directed edge from Rj -> Pi)

Question 7

What are claim edges?

Answer 7

Noted by dashed lines, point from a process to a resource that it may want to request in the future

Question 8

What is a cycle in a resource-allocation graph?

Answer 8

A closed walk with no repetitions of vertices (except the ending vertex) and edges.

Question 9

What if there’s a cycle in a resource-allocation graph?

Answer 9

If there’s one resource instance, then there’s a deadlock; If there’s multiple resource instances, then there’s the possibility of a deadlock

Question 10

What if there’s no cycle in a resource-allocation graph?

Answer 10

There’s no deadlock

Question 11

How do you ensure deadlock prevention?

Answer 11

Make sure that at least one of the 4 deadlock conditions are not held

Question 12

What’s a method that can break the “hold and wait” condition?

Answer 12

Each process requests and is allocated all its resources before execution

Question 13

How do you ensure deadlock avoidance?

Answer 13

By requiring that the system has some additional priori information available, as well as requiring each process to declare the maximum number of resources of each type that it may need

Question 14

How do you know if the system is in a safe state?

Answer 14

If there exists a sequence <P1, P2, …, Pn> of all processes such that each process can be satisfied by the currently available resources, including recently released resources from other processes beforehand

Question 15

What is the importance of a safe state?

Answer 15

All safe states are deadlock free, but not all unsafe states lead to deadlocks (Avoidance means ensuring the system is never in an unsafe state)

Question 16

What is needed for the Banker’s algorithm?

Answer 16

n (# of processes), m (# of resource categories), Available[m], Max[n][m], Allocation[n][m], Need[n][m] (note: Need[i][j] = Max[i][j] - Allocation[i][j] for all i, j), Work (Initially equals Available, then if Need <= Work, Work = Work + Allocation

Question 17

How do you perform deadlock detection?

Answer 17

For a single instance of each resource type, a deadlock exists in the system if and only if the wait-for graph contains a cycle (Nodes are processes Pi -> Pj if Pi is waiting for P); For several instances, then use the banker’s algorithm to see if it finishes (use only involved processes which does not have any resources allocated)

Question 18

How do you recover from a deadlock?

Answer 18

Choose a blocked process, preempt it (releasing its resources), run the detection algorithm, and iterate it until the state is not a deadlock state

Question 19

What are the different types of addresses/address spaces?

Answer 19

Logical (AKA virtual, generated by CPU) and physical (seen by memory unit)

Question 20

What are the purpose of base and limit registers?

Answer 20

They define the logical address space

Question 21

How does address protection work?

Answer 21

If a memory access is attempted outside the valid range, a fatal error is generated

Question 22

What stages does address binding have?

Answer 22

Compile time, load time, execution time

Question 23

What kind of addresses do the stages of address binding use?

Answer 23

Compile time (absolute addresses, like 74014 – 75002), load time (R - R+100, where R will be decided until load time), and execution time (Binding delayed until run time if the process can be moved during its execution from one memory segment to another)

Question 24

What maps logical memory to physical memory?

Answer 24

The memory-management unit (MMU)

Question 25

What are the different kinds of linking?

Answer 25

Static (library modules get fully included) and dynamic (stubs are used, small pieces of code, to minimize data included)

Question 26

Why does swapping occur?

Answer 26

If there is not enough memory available for all running processes, then some processes that aren’t currently using the CPU may have their memory swapped out to the backing store

Question 27

Why is it important to swap processes out of memory only when there are no pending I/O operations?

Answer 27

Pending I/O operations could write into the wrong process’s memory space

Question 28

What is internal fragmentation?

Answer 28

Total memory space exists to satisfy a request but is not contiguous

Question 29

What is external fragmentation?

Answer 29

Allocated memory may be slightly larger than requested memory, this size difference is memory internal to a partition, but not being used

Question 30

What are the solutions to fragmentation?

Answer 30

Compaction (squeeze all processes together), segmentation, and paging (Divide physical memory into a number of equal sized blocks called frames, and to divide a program’s logical memory space into blocks of the same size called pages.)

Question 31

How does segmentation work?

Answer 31

Use segment table to map segment-offset addresses to physical addresses

Question 32

How does paging work?

Answer 32

Divide physical memory into a number of equal sized blocks called frames, and to divide a program’s logical memory space into blocks of the same size called pages. Avoids external fragmentation

Question 33

What is a page table used for?

Answer 33

A page table is used to look up what frame a particular page is stored in at the moment.

Question 34

What’s the relation between frames and pages?

Answer 34

Pages are stored in frames

Question 35

What is the Translation Look-aside Buffer (TLB)?

Answer 35

A special small fast lookup hardware cache, maps logical addresses to physical addresses

Question 36

What is the idea behind demand paging?

Answer 36

When a process is swapped in, not all pages are swapped in at once, only the necessary ones are

Question 37

How is the page fault rate measured?

Answer 37

0 <= p <= 1, 0 being no page faults, 1 being every page reference is a fault

Question 38

How is effective access time measured?

Answer 38

EAT = (1 – p) x memory access + p x (page fault overhead)

Question 39

What does Copy-on-Write do?

Answer 39

It allows both parent and child processes to initially share the same pages in memory, and only allows modified pages to be copied

Question 40

What does page replacement do?

Answer 40

It prevents over-allocation of memory

Question 41

What is the purpose of using a modify/dirty bit?

Answer 41

indicates whether or not the page has been changed since it was last loaded in from disk, reduces page transfer overhead

Question 42

What is the purpose of a reference string?

Answer 42

Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string

Question 43

Explain Belady’s Anomaly

Answer 43

For some page replacement algorithms, adding more frames can cause more page faults!

Question 44

What are the frame allocation methods?

Answer 44

Maximum (total frames in the system) and minimum (each process needs a minimum number of frames to guarantee successful running)