Os Final Exam

Front 1

4 conditions needed for deadlock

Back 1

1. No preemption

2. Circular wait

3. Hold and wait

4. Mutual exclusion

Front 2

Deadlock prevention techniques

Back 2

Prevent any of the 4 conditions needed

Front 3

Deadlock avoidance technique

Back 3

Banker's algorithm

Front 4

Vectors needed in the banker's algorithm

Back 4

1. Allocated

2. Max

3. Need

4. Available

Front 5

Deadlock detection technique for system with one instance of each resource type.

Back 5

Wait-for graph (remove the resource nodes and collapse its edges). A cycle means there is a deadlock.

Front 6

Deadlock detection technique for system with multiple instances of each resource type.

Back 6

Use something similar to banker's algorithm with vectors: Allocation, Request, Available.

Front 7

Ways to recover from deadlock.

Back 7

1. Abort all deadlocked processes or,

2. Abort one process at a time until the deadlock cycle is eliminated.

Front 8

Issues with resource preemption.

Back 8

1. Selecting a victim

2. Rollback considerations

3. Starvation

Front 9

Base register

Back 9

Holds the smallest legal physical memory address

Front 10

Limit register

Back 10

Specifies the size of the range

Front 11

Describe swapping

Back 11

A process can be temporarily swapped out of memory into a backing store and then swapped back in when needed. This allows the total physical address space of all processes that is needed to exceed the capacity.

Front 12

First fit

Back 12

Find the first hole big enough for the process.

Front 13

Best fit

Back 13

Find the smallest hole the process can fit into.

Front 14

Worst fit

Back 14

Get the biggest hole available for the process.

Front 15

Internal fragmentation vs. external fragmentation

Back 15

External fragmentation: There is enough memory available for the process, but it is not contiguous.

Internal fragmentation: Physical memory is broken down into blocks and memory is allocated based on block size. Holes can be left within that block - those are internal.

Front 16

Segment table

Back 16

User provides two-dimensional address (segment # and offset). The segments must be mapped to actual physical address. Each entry in the table has a segment base and a segment limit.

Front 17

Page

Back 17

Refers to block of logical memory

Front 18

Frame

Back 18

Refers to a block of physical memory

Front 19

TLB

Back 19

Translation lookaside buffer - smaller, faster version of the page table allowing for faster lookup of the page to frame mapping

Front 20

Page table

Back 20

Maps the page to the frame, uses offset

Front 21

RAID

Back 21

Redundant arrays of independent disks

Front 22

RAID 0

Back 22

Non-redundant striping

Front 23

RAID 1

Back 23

Mirrored discks

Front 24

RAID 2

Back 24

Memory style error-correcting codes

Front 25

RAID 3

Back 25

bit-interleaved parity

Front 26

RAID 4

Back 26

Block interleaved parity

Front 27

RAID 5

Back 27

Block interleaved distributed parity

Front 28

RAID 6

Back 28

P + Q redundancy (error correcting codes used instead of parity bits).

Front 29

5 disk scheduling algorithms

Back 29

1. FCFS

2. Scan (elevator)

3. C-Scan

4. SSTF (shortest seek time first)

5. Look

Front 30

7 Directory operations

Back 30

1. Read

2. Write

3. Append

4. Delete

5. Copy

6. Execute

7. Change protection

Front 31

LRU (virtual memory)

Back 31

Least-recently used

There is a clock or counter on the system and the page has a time-of-use field. When the page is accessed by the memory, it gets the counter timestamp on it. The oldest one can then be selected as the victim to get swapped out of memory and put onto backing store.

Front 32

Second-chance algorithm (virtual memory)

Back 32

A page gets a reference bit. If it gets modified since it was loaded into memory then we don't select it as a victim. If it the bit is zero, when it's turn comes up according to the FIFO algorithm, then we can get rid of it. If we do skip over it, we set the bit to 0 because it only gets one second chance.

Front 33

How to detect thrashing

Back 33

Page fault frequency: too many faults means thrashing. Not enough faults means it has too many frames so we take some of its processes away.

Front 34

What is a dirty bit used for?

Back 34

In page replacement, it prevents us from unnecessarily doubling time to get rid of old page and bring in new page. If the bit is 1, we know we have to write out that page's contents to memory before we dump it. If it's 0, then it hasn't been updated since last added to memory so we won't have to re-write it and will thus save some time.

Front 35

When is a process thrashing?

Back 35

When it is spending more time paging than executing.