CSCE4600 Final Flashcards by Sam Tancharoensuksavai

How many milliseconds in 1 second

1000 (10^-3)

How well did you know this?

Not at all

Perfectly

How many microseconds in 1 second

1000000 (10^-6)

How well did you know this?

Not at all

Perfectly

How many nanoseconds in 1 second

(10^-9)

How well did you know this?

Not at all

Perfectly

What are the 3 different types of approaches for the deadlock problem

Detection and Recovery
Prevention
Avoidance

How well did you know this?

Not at all

Perfectly

What are reusable resources

permanent objects with two properties

How well did you know this?

Not at all

Perfectly

What are consumable resources

produced and consumed dynamically

How well did you know this?

Not at all

Perfectly

What are the two properties of reusable resources

1) # of units is constant
2) each unit is available or allocated to
exactly one process

How well did you know this?

Not at all

Perfectly

What are the three properties of consumable resources

1) # of units will vary over time;
2) system can create new units
3) process may request, acquire,
and consume resource units

How well did you know this?

Not at all

Perfectly

T/F: With single unit resources, cycle -> deadlock

True

How well did you know this?

Not at all

Perfectly

What are the 4 points of cycles and knots

deadlock -> cycle
cycle !-> deadlock
expedient & knot -> deadlock
deadlock !-> knot

How well did you know this?

Not at all

Perfectly

What is a blocked state

no action by process Pi will result in a state change,

does not mean deadlock

How well did you know this?

Not at all

Perfectly

What is a secure state

S is not a deadlock state and any state T reachable by S is not a deadlock state

How well did you know this?

Not at all

Perfectly

What is total deadlock

If all processes Pi are deadlocked in state S

How well did you know this?

Not at all

Perfectly

What is a deadlock state

If Pi is deadlocked in state S

How well did you know this?

Not at all

Perfectly

T/F: does a cycle always mean dependency

False

How well did you know this?

Not at all

Perfectly

What are the four conditions for deadlock

1) Mutual Exclusion
2) Nonpreemption
3) Resource waiting
4) Partial Allocating

How well did you know this?

Not at all

Perfectly

What is mutual exclusion

Processes hold resources exclusively, hence making them unavailable to other processes

How well did you know this?

Not at all

Perfectly

What is non preemption

Resources cannot be taken away from a process that is holding them. Only the process can release the resources they hold

How well did you know this?

Not at all

Perfectly

What is resource waiting (Circular Wait)

Processes that request unavailable resources (or units) will block until they become available.

How well did you know this?

Not at all

Perfectly

What is Partial allocation

Processes may hold some resources when they request additional units of the same resource or other resources. (Hold and Wait)

How well did you know this?

Not at all

Perfectly

What is a sink

A node with no outgoing edges

How well did you know this?

Not at all

Perfectly

What is an isolated node

A node with no outgoing and no inbound edges

How well did you know this?

Not at all

Perfectly

What is a path

a sequence (a,b,c ..y,z) of at least two nodes for which (a, b) ε E

How well did you know this?

Not at all

Perfectly

What is a cycle

a path with the same first and last vertex

How well did you know this?

Not at all

Perfectly

What is a reachable set

reachable(z) = {b | there is a path from z to b}

What is a knot

All nodes are reachable from any other node

What is compile time

The compiler translates symbolic addresses to absolute addresses

What is load time

Generates relocatable code if memory location is not known at compile time

What is execution time

binding is delayed until runtime of the process can be moved during its execution from one segment to another

What is a logical address

generated by the CPU; also referred to as virtual address

What is a physical address

address seen by the memory unit

Which address space tends to be larger?

Logical

how many frames is physical memory

2^25

how many frames is logical memory

2^32

what is a relocation register

is added to every address generated by a user process at the time it is sent to memory

What does a relocation register contain

value of smallest physical address

what is a limit register

contains range of logical addresses

logical address must be...

less than the limit register

what is a hole

block of available memory

what is external fragmentation

when we have sufficient space in memory but the space is not contiguous

pros and cons for best fit

pro: better speed and storage utilization, leaves very large holes and very small holes cons: very small holes may be useless, must search entire list

pros and cons for first fit

pros: better speed and storage utilization, leaves "average" size hoes cons: may end up clustering towards top

pros and cons for worst fit

pros: allocates the largest holes cons: must search entire list, worst in terms of storage utilization

what is internal fragmentation

the wasted memory space when the requested memory is slightly smaller than the allocated memory

what is compaction

move allocated blocks such that a single region of free memory is maintained all internal addresses may have to be relocated and not always possible

pros and cons for fixed partition

pro: easy to implement, fast context switches cons: suffers from internal fragmentation, one size does not fit all (example: large processes)

pros and cons for variable partition

pro: no internal fragmentation, allocates just enough for process con: large overhead to keep track of free memory

variable partitioning requires...

coalescing, or combining neighboring small holes into contiguous memory

what is buddy system

splits block into two equal buddies, continuous until smallest block greater than or equal to s is generated

are frames physical memory or logical memory

physical

are pages physical memory or logical memory

logical

used as an index into a page table which contains base address for each page

page number

combined with base address to define the physical memory address

page offset

What are the 4 steps to a basic page replacement

1) find the location of desired page on disk 2) find a free frame (if no free frame use page replacement algo to select victim) 3) read the desired page into new free frame and update page and frame tables 4) resume the process

what does a 1 valid-invalid bit mean

in-memory

what does a 0 valid-invalid bit mean

not in memory

if valid-invalid bit is 0...

page fault

What are the 5 steps to the page fault process

1) look at another table to decide if invalid reference, abort, or just not in memory 2) get empty frame 3) Swap page into frame 4) reset tables, validation bit = 1 5) restart instructions

what is locality

code that is executed frequently and executes a few fragments at one time

what does belady's optimal algorithm do

replace page that will not be used for the longest period of time

free to select a victim from any page in memory

global policies

defines a working set that belongs to the same processes or group of processes and selects a victim from them

local policies

what is thrashing

when a process is busy swapping pages in and out

Compiler: If you know at compile time where the process will reside in memory

then absolute code can be generated (Static)

Loader: If it is not known at compile time where the process will reside in memory

then the compiler must generate relocatable code

how many bytes are in a megabyte

1000000 (10^6)

how many bytes are in a kilobyte

1000 (10^3)