OS
Popularity (by total correct streak): 105
Popularity (by number of users): 1
| Concurrency occurs in the following contexts: | Multiple Applications - running at once; structured applications - apps made of multiple pieces running at once; OS structure- OS made of multiple pieces running at once | |
| Some of the problems in running more than one process at a time (interleaved uniprocessor or multiprocessor): | Sharing of resources among processes, for example, a variable. If two or more processes use a variable, then the order of execution may be critical.....Allocation of resources. (Deadlocks)..... Debugging: since bug may be due to particular order of process execution and therefore hard to reproduce. | |
| race condition | the outcome of two processes accessing the same variable depends on their relative order of execution | |
| What problems does concurrency pose to the OS? | Keep track of various active processes (use PCBs and other structures)..... Allocate resources (CPU, Memory, Files, I/O devices) to each process..... Protect data and resources of each process from interference from other processes..... Process results must be independent of the speed at which execution occurs relative to other processes. | |
| Competition poses three problems: | Mutual Exclusion....Deadlock....Starvation | |
| Mutual Exclusion | Critical resource: only one process at a time can use it. Example is a printer. Critical sections: portion of program using a critical resource. Only one program at a time is allowed in its critical section. | |
| Deadlock example | example: two processes want two resources but each owns only one. | |
| Starvation | A process competing for a resource never receives it due to scheduling of other processes. | |
| data coherence | keeping data in a consistent state | |
| Achieving Mutual Exclusion - There are three general approaches: | Software: let the applications enforce it themselves through coding. Hardware: disable interrupts or have special machine instructions to support mutual exclusion. Operating System or Language: let the OS or programming language offer support for this capability. | |
| What are some requirements for mutual exclusion support? | Enforcement. Only one process at a time in its critical section..... Non-interference. A process that halts in its non-critical section does not affect other processes..... No deadlock or starvation of processes needing to enter critical section..... When critical section is open, any process wanting entry should be permitted entry without delay..... No assumptions about process speeds or number of CPUs..... Finite time inside critical section. | |
| Two ways hardware can support mutual exclusion: | 1) Interrupt disabling 2) Special machine instructions | |
| Interrupt Disabling | In a uniprocessor system, processes cannot have overlapped execution, but only interleaved execution..... Interleaving occurs when a process is interrupted..... Disabling interrupts lets a process complete its critical section without worrying about being interrupted and switched to another process. | |
| Problems with Interrupt Disabling | Degrades multitasking performance.... Doesn’t work on multiprocessor system where multiple processes execute at once regardless of interrupts. | |
| Special Machine Instructions | Access to a memory location by a process excludes simultaneous access by other processes..... | |
| Advantages to special machine instructions are: | Works on uniprocessor or shared-memory multiprocessor....Simpler than pure software approach....Permits multiple critical sections, each with its own variable | |
| Drawbacks to special machine instructions are: | Busy-waiting....Starvation possible since the process that runs next is arbitrary.....Deadlock is possible if p1 enters the critical section and is interrupted by a higher priority process p2. p2 cannot enter due to p1, and p1 will not be scheduled due to p2. | |
| Semaphores: | Semaphores are an OS or language mechanism to support concurrency. A semaphore is a variable with an integer value.Queue is used to hold processes waiting on the semaphore. Semaphore operations are made atomic by the provider. | |
| Strong semaphore: | queue uses FIFO order. No starvation. | |
| Weak semaphore: | no queue ordering. Could have starvation. | |
| Binary semaphore: | only two values, 0 and 1, but equally powerful as the general semaphore. Like a flag. | |
| Counting semaphore: | a general semaphore with n values. | |
| In general, there is no way to know before a process calls wait whether it will: | block or not. | |
| When a process calls signal to awaken a waiting process: | both processes will continue running concurrently, so on a uniprocessor system, there is no way to know which one will actually proceed next. | |
| A monitor is a software module with these chief characteristics: | Local data variables are accessible only by the monitor ....Process enters monitor by invoking one of its procedures ....Only one process may be executing in the monitor at a time, others are suspended waiting for the monitor to become available | |
| A monitor uses ______________ for synchronization. | condition variables | |
| cwait(c) | suspend execution of the calling process on condition c. The monitor is now available for others. | |
| csignal(c) | resume execution of some process blocked after a cwait on c. If there are many, choose one, if there are none, do nothing. | |
| How is the monitor signal different from a semaphore signal | In the monitor, the signal is lost if no one is waiting. | |
| What two requirements does Message Passing satisfy? | Synchronization (for mutual exclusion) ....Communication (to exchange information) | |
| Direct Addressing: | specify destination process. | |
| Indirect Addressing: | send to mailbox and let receiving process(es) pickup whenever they are ready. (flexibility) | |
| Deadlock | permanent blocking of a set of processes that either compete for resources or communicate with each other. There is no efficient solution. | |
| Two categories of resources: | Reusable: used by one process at a time and is not consumed .... Consumable: Can be created and destroyed. | |
| resource allocation graph | directed graph that depicts a state of the system of resources and processes. Each resource and process is represented by a node. Dots within a resource node represent instances of that resource. An edge from a process to a resource represents a resource request. An edge from a dot within a resource node to a process indicates a resource has been assigned to the process. | |
| Required Conditions for Deadlock | Mutual exclusion, Hold and wait, No preemption, Circular wait | |
| Mutual exclusion: | only one process may use resource at a time | |
| Hold and wait: | a process may hold allocated resources while awaiting assignment of other resources. | |
| No preemption: | no resource can be forcibly removed from a process holding it. | |
| Circular wait: | a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain. | |
| There are three general approaches to dealing with deadlocks: | Prevention – prevent conditions necessary for deadlock. Avoidance – allows first three conditions, avoids fourth condition dynamically. Detection – detects if deadlock occurs, then deals with it. | |
| Two approaches to Deadlock Prevention | Indirect: prevent one of the three preconditions. Direct: prevent the fourth condition (circular wait). | |
| Prevention: Mutual Exclusion | Hard to prevent since some resources require it. | |
| Prevention: Hold and Wait | can be prevented by making process request all of its resources at one time and blocking it until all of the resources can be granted simultaneously. | |
| Prevention: Hold and Wait Drawbacks | a process may have to wait a long time before all of its resources are free..... A process may acquire and keep resources a long time during which they are denied to other processes..... A process may not know in advance what resources it will need. | |
| Prevention: No Preemption; Two possibilities: | If a process holding resources cannot acquire a resource it needs, it must release the ones it has and start over. If a process needs a resource held by another process, preempt the process and make it release its resources. This approach requires resources whose state can be easily saved and restored, such as the processor. | |
| Prevention: Circular Wait | Require an ordering of resource requests by resource type. Ordering prevents a circle by having all requests be forward in order, so that a process can’t acquire a resource then request one prior to it which another process may be holding. As with preventing hold-and-wait, it may not be efficient to do this. | |
| Deadlock Avoidance | Similar to deadlock prevention. Allows the three preconditions but tries to prevent deadlock dynamically as resource requests are made. Allows more concurrency than prevention. Requires knowledge of future resource requests. | |
| Deadlock Avoidance; Two approaches: | Process initiation denial: constrains whether a new process is allowed to run. Resource allocation denial: lets a process run but constrains whether its resource requests are granted. | |
| Process Initiation Denial | Each process declares its maximum need for each resource. A process is only allowed to start if the maximum claim of all current processes plus the maximum claim of the new process can be met. | |
| Process Initiation Denial drawback | This strategy doesn’t work well because it assumes the worst case, that all processes will make their maximum resource requests at the same time, which is unlikely. So it may keep processes from starting that actually would have run successfully. | |
| Resource Allocation Denial | An algorithm for resource allocation denial is the “Banker’s Algorithm”, a term used by Dijkstra to compare processes and resources to bank reserves and loans. | |
| This algorithm defines the state of the system as either safe or unsafe. | Banker’s Algorithm | |
| The banker’s algorithm makes use of matrices and vectors: | Claim matrix: requirement of each process for each resource. Allocation matrix: current allocation to each process of each resource. Resource vector: total amount of each resource in the system. Available vector: total amount of each resource not allocated to any process. | |
| Deadlock Avoidance Advantages | Less restrictive than deadlock prevention. Not necessary to preempt and rollback processes as in deadlock detection. | |
| Deadlock Avoidance Disadvantages | Maximum resource needs must be known in advance Process ordering needs to be independent (not constrained by any process synchronization). Must be a fixed number of resources. Processes can’t exit while holding resources. | |
| Deadlock Detection | Periodically, the system performs an algorithm to detect deadlock. This can be done at each resource request, or less frequently due to the overhead involved. | |
| Deadlock Detection Algorithm | 1) Mark each process that has a row in the allocation matrix of all zeroes (holds no resources). 2) For each remaining process see if its resource requests can be met by the current available resources. 3) Mark all such rows and temporarily add their current allocation to the available list. - If there are unmarked processes at the end of these steps, then these unmarked processes are deadlocked. | |
| Dining Philosophers Problem | The Dining Philosophers problem is a classic concurrency problem. The problem involves five philosophers sitting down to eat spaghetti. The philosophers require two forks each to eat. A deadlock occurs if they all pickup their first fork before anyone can get a second fork. |
Quisition is a browser-based flashcard system that repeats old cards and introduces new ones at optimal time intervals. You can create your own card packs or use those developed by others.
