Week 5 Flashcards
Deadlock
Set of processes that each have a resource the other needs
Deadlock conditions
Mutual Exclusion, Hold and Wait, No preemption, Circular Wait
Mutual Exclusion
Limited number of processes that can use a given resource
Hold and Wait
Process has at least one resource and is waiting on another
No preemption
Can’t take away a resource away
Circular wait
P0 waiting on resource held by P1, which waits for P2, …, which waits on P0
Basis of deadlock on a graph
Cycle of resource allocation and no way for the processes to finish.
Methods to stop deadlock
Prevention, Avoidance, Recovery, Ignore
Explain methods of deadlock prevention (4)
Mutual Exclusion: Serialize or spool resource. Not very flexible. Hold and Wait: When holding a resource a process cannot ask for more. Must request all resources at the same time. If you have resources and need to request more, relinquish all and ask again. Not efficient because you have to ask for max resources you may need, which can lead to overcommitment of resources and starvation. Relax Preemption: Take away resources when necessary. E.g. from process holding the most resources or the lowest priority. Requires Rollback. Prevent circular wait. Have a given order the system needs to request resources in which is determined from previous running times. If process asks out of order, it is terminated.
Rollback
Processes regularly checkpoint safe states. When the system takes away a resource from a process, they must reset their state to what it was before they requested the resource. Rollback to this safe state and restart transaction.
Explain method of avoidance
Information up front: process will declare max number of needed resources. Dynamically check resource allocation: Ensure there’s a way for everyone to reach their stated max resource count. System must keep check of the resources given out and left. Ensure safe state is always held by the system.
Safe state
There exists an order we can allocate resources such that all resources can finish with their max resources and not produce deadlock.
Bankers Algorithm
Ensure you can complete with picture. 1. Compare request to available resources. If not available put process to sleep until further resources are released. 2. Compare request to maximum, if its larger than process must be terminated. 3. create temporary new state as if new resources were allocated. 4. Run algorithm on the new state, if it’s not safe, put to sleep. If it is safe, allocate resources.
Explain methods of recovery:
Deadlock detection: Allow system to enter deadlock, which requires to run expensive detection algorithms and look for cycles. Execute recovery scheme. Deadlock Recovery: Terminate processes, either all processes or until the deadlock is resolved. If we preemptively take away resources its not evident which to take away and can lead to starvation if its the same process every time.
Ignore
Hope deadlock never happens, if it does fix it manually.
Load time
Binding done just before execution. Loader loads executable into memory, including data segment and code. Locations of references are kept in the header and loader adjusts them to match where the executable is loaded in memory as they are read into memory. Link outside libraries. Process allows for more than one process to be run.
Execution time
Binding done on the fly during execution. Compilers and linkers generate code with relative addresses (e.g., offsets within the program’s memory layout). The program sees a virtual address space, which the operating system maps to physical memory dynamically. These relative addresses are calculated with respect to the program’s base address. CPU has extra hardware, then when it loads an address it will go and change the address being loaded based on where the program is in memory. Allows for more than one copy to be run.
Compile Time Binding
Compile Time Binding refers to the process of associating program instructions or data with specific memory addresses during the compilation phase of the program lifecycle. This means that all memory references (e.g., variables, functions, or constants) are resolved to absolute or relative addresses when the program is being compiled. Like assembly where address is specified in the code (e.g. 0x100)
Binding
Associates memory addresses with variables or instructions.
Explain process of load time binding
Headers contain pertinent symbols and information about where in the program they are referenced. Loader places program code starting at chosen base address. Loader places values in at relative addresses. Loader then adjusts memory references relative to base pointer. Walks through relocation table and adjusts as it goes.
Explain execution time loading process.
The program doesn’t have fixed absolute memory addresses when compiled. Instead, addresses are resolved during execution. During a context switch, the MMU updates the page table or segment table so that the virtual addresses used by the new program correctly map to its own memory space.
D in header
defined in document
T
Function defined in file
t
External text segment
b
external data segment
