Exam 2 Flashcards
Name the two causes of disk I/O delays and explain.
seek time - the amount of time it takes for the read/write head to move to the correct track on the disk
rotational latency - the amount of time for the disk to rotate so that the sector in the track is under the read/write head and able to get information
Name the four necessary and sufficient conditions for deadlock to occur
mutual exclusion
hold and wait
circular wait
no preemption
Explain mutual exclusion
each resource is available or allocated to exactly one process; resources are not shared
Explain hold and wait
a process is holding resources can request and wait for an additional resources
Explain circular wait
a circular chain of processes where each process is waiting on a resource that is held by the next process in the chain
ex. dining philosopher’s problem - every philosopher was holding their left fork and waiting for the left fork
Explain no preemption
resources allocated to a process may not be forcibly taken away
Explain deadlock
the state of indefinite waiting that processes may reach when competing for system resources or attempting to communicate
Name the four ways to prevent deadlock…
attack mutual exclusion
attack hold and wait
attack circular wait
attack no preemption
Explain the ‘attack mutual exclusion’ deadlock prevention method…
avoid assigning resources unless necessary
limit the number of processes that are allowed to request resources
ex. daemons for devices
Explain the ‘attack hold and wait’ deadlock prevention method…
disallow processes to hold resources while waiting for additional resources
all resources must be allocated to the process before it can start - must have full set!; if the process needs an additional resource, the process must temporarily release all resources
breaks the wait part!
Explain the problems associated with the ‘attack hold and wait’ deadlock prevention method…
process may not know what it needs when it starts
resources tied up longer than necessary and underutilized
delayed if lots of resources are needed - starvation
break the hold part - process requires a new resource and must release all resources to acquire new resources - another process may grab what the process needs allowing both to complete - would just have to wait
Explain the ‘attack circular wait’ deadlock prevention method…
allow processes to have only one resource at a time
globally order all processes into categories by number - when numbering processes, think of the normal way things are processed
a process can only request from a higher numbered category in the resource chain
a process can release resources in a higher numbered category to request lower numbered category resources - higher numbered category resources may be requested again
When globally ordering all processes, why should output devices have a high numbered category?
output devices are needed at the end of a process; for example, it doesn’t make sense to give up everything to print!
Give an example of globally ordering all processes into categories…
if you have requested and been granted a resource in category 2, you can no longer request from category 1, 4 can’t request 1, 2, 3; must be held further down resource chain than I am;
if a process needs a resource from category 2, the process will release resources in category 3 to get to resources in category 2 - can always request again!
preemptible
can be interrupted; can be taken away from a process without a problem (without fail)
non-preemptible
can’t be interrupted; cause process to fail, cause erroneous result, cause extra work; considered a deadlock; ex. print job taken away
Describe how deadlock can be detected…
deadlock detection involves maintaining information of the current resource-allocation state and invoking an algorithm that uses the information of the resource-allocation state to detect deadlock
each resource type has one instance - construct a resource graph and search for a cycle - cycle indicates deadlock; resource-allocation graph algorithm
each resource type has multiple instances - use the detection algorithm over the array structures; when the algorithm completes, any unmarked processes are deadlocked
What does a process to a resource indicate?
process is requesting one instance of the resource type; request
What does a resource to a process indicate?
one instance of a resource type has been allocated to the process; acquired
How often should the deadlock detection algorithm be invoked (2)…
invoked every time a process requests a resource that cannot be immediately allocated - os can identify the specific process that caused deadlock along with the processes that are in deadlock; tons of overhead
invoked periodically; deadlock reduces the CPU utilization and system throughput - CPU utilization drops below a certain percentage the algorithm is invoked - ~40%
Describe the Banker’s Algorithm…
answer
Describe the Detection Algorithm…
answer
Name the 4 ways deadlock can be recovered from…
preemption
rollback
killing processes
avoidance
Explain the ‘preemption’ deadlock recovery method…
resource is taken away from a process and the process is suspended; when the process that gets the preempted resource completes, the resource is returned to the original process
only works for some scenarios
Describe an example of the ‘preemption’ deadlock recovery method…
process locked part of a database, could unlock and allow another process access, when process finishes, can re-lock
if the process was in the middle of something, the process could fail causing both processes to fail, ex. disk burning
Explain the ‘rollback’ deadlock recovery method…
OS periodically creates checkpoints for each process; a process in deadlock is rolled back to a defined checkpoint - usually when a process requests resources
this process looks at priority - rollback process with low priority first; low runtime - hasn’t accomplished a large amount of work relative to other processes
will have to do rework, but the system won’t crash
What is a checkpoint and how is it used?
data structure that stores the state of a process, resource states, and time stamp and is stored in a file that is used to restart a process in a previous state before deadlock occurred
only thing saved at checkpoints are things that have changed
Explain the ‘killing processes’ deadlock recovery method…
process in deadlock or process that is holding needed resources is killed
kill low priority process with short runtimes
Give an example of a good process to kill…
compilation of a development system
Explain the ‘avoidance’ deadlock recovery method…
decide whether or not to allocate a request
suspend if process can’t have resource at current time
wake up process when resource is available
Name the file attributes…
permissions creator owner timestamp size location type
Describe the file attribute, ‘permissions’…
who can access the file and what can they do with the access they have
read, write, execute
owner, group, world
Describe the file attribute, ‘creator’…
who created the file
Describe the file attribute, ‘owner’…
who owns the file
Describe the file attribute, ‘timestamp’,,,
may have one or all of the following:
when was the file created
when was the file last modified - will always have this!
when was the file last accessed
Describe the file attribute, ‘size’…
how much data is stored in the file
Describe the file attribute, ‘location’…
where is the file stored in the computer system
which disk is in on
What are file attributes?
maintains the file and controls file access as to how it can and should be used; may be on some systems and not others
Name the 4 ways to implement files…
contiguous allocation
linked list allocation
linked list allocation with table
i-nodes
Describe the method of implementing files via contiguous allocation…
files are located in a contiguous series of blocks on a disk - the last block will usually be wasted because blocks are rarely even numbered
need to know the size and starting address of the file to implement
causes disk fragmentation
files that increase in size must move to a larger space
Describe the method of implementing files via linked list allocation…
random access is slow
directory stores the address of the first block
first item of each block contains the address of the next block - only works for a file in sequential order
blocks don’t have all the data, but do have a pointer to the next piece
Describe the method of implementing files via linked list allocation with a table…
table in memory with the same number of blocks on disk - entry for every block whether free or used!
random access is faster because chain is in memory and not on disk
first block is stored at location X on disk; location X in table stores the memory location of second block on disk
Describe the method of implementing files via i-nodes…
contains file attributes and list of block addresses
pointers to blocks in a file
memory should be proportional to file size
fixed size - if file is bigger, the last block will be a pointer to the next block
~ 1/2 of the last block will always be empty
Name the 5 issues in disk space management…
block size caching free blocks fragmented disks disk quotas
Describe the ‘block size’ issue of disk space management…
too small and will span multiple blocks
too large and the last block on the disk will have wasted space
Describe the ‘caching’ issue of disk space management…
needs to maintain file integrity
blocks modified in cache must be written out to disk
Describe the ‘free blocks’ issue of disk space management…
list of available blocks
bitmap kept - one bit per block and 1 represents a free block
Describe the ‘fragmented disks’ issue of disk space management…
file blocks are spread out which reduces performance
easier to store information
do not defragment a solid state!!!
Describe the ‘disk quotas’ issue of disk space management…
limits how much data can be stored
quota table keeps track of hard limits, soft limits, and current usage
if hard limit is hit, the system manager will have to unlock account - must delete stuff!
Describe race conditions…
two or more tasks race to the shared resource simultaneously
process that writes to the resource last will succeed
Describe critical sections…
code in a process that accesses and uses a shared resource; every process that needs to access a shared resource has its own critical section
used to prevent race conditions
ex. car driving on road A and car driving on road B, the critical section is the intersection of roads A and B
Conditions for critical section solution…
only one process can be executing its critical section at a time (mutual exclusion)
no process outside a critical section can block another process
no process should have to wait indefinitely to enter its critical section
Describe the purpose of device controllers…
they directly control devices for main CPU
all device controllers are able to operate the devices at the same time the main CPU is carrying out some task
purpose is to provide part of the interface between devices and processes, or function as a bridge between device and OS
Describe the purpose of device driver software…
computer program that operates or control a device that is attached to the computer
provides a software interface to hardware device, enabling other OS and computer programs to access hardware functions without knowledge of hardware being used
translates commands specific to make and model of device being used
Describe what a file system does…
provides users the ability to put data into files and to find and use files that have been previously created
FMS doesn’t have knowledge about how the data in the file is organized
store files in nonvolatile memory
user can access files with filename in a given directory
deal with how the file is structured, names of files, who has access, how are things used and protected, how are things saved, how do we keep track of space available when a new file has to be created
