Opersyst - Module 4 & 5

Deadlock

A _____________ may be defined as the condition wherein a set of processes cannot continue executing because each process is waiting for a resource that is being held or used by another process within the set. A resource may be a printer, a hard disk, a file, a memory location, etc.

Resource-allocation graph

A ______________ is a directed graph that shows which resources are being held by different processes. It also shows what resources are being requested by the processes

Mutual Exclusion

There must be ____________ in the use of resources, i.e., some resources may be used by only one process at any one time. If several processes are allowed to use a resource at the same time, then deadlocks can never occur.

Hold and Wait

This deadlock condition states that processes are allowed to hold resources while waiting to acquire other resources.

No Preemption

This deadlock condition states that resources cannot be taken away from processes by force. A resource may only be released if a process gives it up voluntarily or when the process finishes executing.

Circular Wait

This deadlock condition states that there must be a circular chain of processes wherein each process is waiting for the next process within the chain. If there are three processes in the resource held by process 2, process 2 is waiting for a resource held by process 3, and waiting for a resource held by process 1.

Deadlock prevention

_______________ methods ensure that deadlocks will never occur. Since deadlocks occur if and only if all of the four conditions mentioned in the previous section exist, then deadlocks can be prevented by trying to eliminate at least one of those conditions.

Mutual Exclusion Condition

Eliminating the Mutual Exclusion Condition implies that all resources within a computer system become shareable. Processes are allowed to use the same resource at the same time. A process will no longer have to wait for any of the resources it needs. Deadlocks are therefore prevented.

Hold and Wait Condition

Eliminating this condition implies that a process will not be allowed to hold a resource while requesting to use other resources. This implies that a process has to request all the resources it needs before it can begin executing. Only when it has acquired all these resources will it be allowed to starts its processing. This will ensure that processes can finish its execution without having stop and wait for additional resources. 

No Preemption Condition

Eliminating this condition implies that a process may be stopped anytime and its resources forcibly taken away from it. In this situation, once a process request for a resource that is not available, the process is stopped and its resources released. This will give other processes needing these resources a chance to finish their execution. Deadlocks are therefore prevented. The process that was stopped will have to request again for the resources it needs. Once it has acquired them, the process can then be resumed.

Circular Wait Condition

To eliminate this condition, it is necessary according to some predefined order. This may be accomplished by assigning each resource a unique integer value.

Deadlock avoidance

In ___________, the operating system must gather enough information about processes and resources in order to determine if granting a resource to process will cause the system to go into an unsafe state.

Unsafe state

An _________ is a state that may lead to a deadlock and must therefore be avoided. Request for resources that will lead to unsafe states will not be granted.

Safe state

A system is in a __________ if there is a scheduling order or a sequence of processes in which every process in the sequence can complete its execution.

The priority of the process

A factor in selecting a process to terminate in case of a deadlock that states the lower priority or less critical processes are better candidates for termination than higher priority or more critical processes.

The time execution of the process

A factor in selecting a process to terminate in case of a deadlock, which states that processes that have just started executing are more suitable for termination than processes that have been executing for a relatively longer period of time. In this way, less work will be lost if the termination is necessary.

The number of resources the process still needs to finish executing

A factor in selecting a process to terminate in case of a deadlock which states that a process which needs only a few resources to finish executing has a better chance of getting these resources and thus execute to completion.

Memory manager

 The _________ is the component of the operating system that is responsible for ensuring that memory is shared in an efficient and error-free manner.

Dynamic run-time loading

Address binding is done at run-time. This means that a relative address is converted to a physical address only when it is needed by the CPU. The CPU will first generate the relative address of an instruction or data. This is then converted to a physical address before being sent to the main memory.

Logical Addresses

Addresses generated by the CPU. Using run-time dynamic loading allows the operating system to relocate a process anywhere in main memory while it is executing.

Memory Management Unit (MMU)

A special hardware device called the _________ is used to take care of logical to physical address conversion.

Fixed Partition Memory Allocation Strategies

A Main Memory Allocation strategy where the memory is divided into fixed number of regions or partitions

Internal Fragmentation

A wastage of memory which occurs if the size of the memory partition allocated to a process is larger than the size required by the process

External Fragmentation

A wastage of memory which occurs when there are partitions available but none are big enough for any waiting process

Variable-Partition Memory Allocation Strategies

A Main Memory Allocation strategy which allocates the exact memory space needed by each process

First-fit strategy

In this scheme, the operating system scans main memory from the beginning and the first hole encountered that is large enough for the incoming process will be used.

Best-fit Strategy

For this strategy, the operating system searches the list of holes for the smallest hole that is large enough for the incoming process thereby producing the smallest remaining hole.

Worst-fit Strategy

This is the opposite of the best-fit strategy wherein the operating system searches the list of holes for the largest hole. This strategy therefore produces the largest remaining hole. Unlike in best-fit, the remaining hole produced may be large enough for an incoming process.

Compaction

This is moving the processes upward in main memory so that the free memory locations may be grouped together in one large block

Paging

_________ is a memory management scheme in which a process is allowed to occupy non-contiguous memory space. In paging, processes are divided into equal-sized blocks called  pages while the main memory is also divided into equal-sized blocks called frames.

Free frame list

The operating system uses a list of which frames are free or available for allocation. This is called the _____________.

Page table

The pages of a process may be scattered throughout the memory, the operating system have a mechanism to keep track of where it has placed these pages. This mechanism is in the form of a ________.

Dedicated Register

The simplest and most efficient option is to store the page tables in a ___________. High-speed registers can readily speed up page table accesses

Main memory, Page table base register (PTRB)

 Another option is to keep the page tables in main memory. To locate the page tables easily, the MMU maintains a _______________ which contain a pointer to the location of a page table in memory.

Cache Memory, Translation look-aside buffer (TLB)

The third and more popular option is to use a small but fast __________ called _____________ to store the most recently used page table entries.

Virtual Memory

An extension of paging which allows a process to execute even though not all of its pages are inside the main memory. In other words, the entire process does not have to be loaded into main memory in order to execute.

Frame Allocation

There more available frames there are for a process, the lower the page fault rate will be. This is because if there are more frames, then there will be more pages that can loaded into the main memory. Chances will be high that the pages that will be needed are in the main memory.

Page Replacement

If a page fault occurs, the operating system must load the requested page into the main memory. If there are no free frames available for allocation, the operating system must remove one of the existing pages in memory to free up space for the new page.

Dirty bit

The page table in virtual memory has a ______ for each entry to indicated if a page has been modified or not.

Dirty pages, Clean pages

The page table in virtual memory has a dirty bit for each entry to indicate if a page has been modified or not. Modified pages are often called dirty pages, and unmodified pages are called clean pages.

Optimal algorithm

A page replacement algorithm wherein this algorithm selects the page that will not be needed or referenced for the longest period of time in the future. This algorithms produces the lowest number of page faults among all the algorithms.

First-In, First Out (FIFO) Algorithm

The ________ algorithms selects the pages to be replaced on a first-in, first-out basis, meaning the first page to enter the main memory is the first one to be replaced. In other words, it selects the oldest page in main memory.

Least Recently Used (LRU) Algorithm

The ____________ algorithm selects the least recently used page for replacement. This algorithm exploits the locality of reference principle. Recall that a page that has been referenced recently has a very good chance of being needed again and is thus a good choice for replacement.

Locality of reference

The principle that a computer program tends to access the same memory locations repeatedly over a short period, or access memory locations that are physically close to each other

Local replacement

The page to be replaced belongs to the faulting process

Global replacement

The page to be removed from the main memory may belong to another process