Exam 2 OS Concepts CH5-CH8

What is concurrency?

When things run at the same time, specifically processes and threads

In what systems does concurrency arise?

Multiprogramming - multiple processes on a uniprocessor (multitasking)

Multiprocessing - multiple processes on a multiprocessor

Distributed processing - multiple processes on multiple distributed systems

In what contexts does concurrency occur?

Multiple applications running at once

Structured applications (apps made up of multiple pieces running at once)

OS Structure (OS made of multiple pieces running at once)

What problems arise when running more than one processor at a time?

• Sharing of resources among processes (order of execution becomes critical)

• Allocation of resources (deadlocks)

• Debugging (bugs might be unique to one order of process execution)

What is a race condition?

Multiple processors/threads read and write data so the final results depend on the order of execution

What design/management issues are raised due to concurrency in the OS?

• Keeping track of active processes

• Allocation of resources to each process

• Protecting data/resources from interference of other process

• Results must be independent of speed at which execution occurs relative to other processes

What are three cases in which processes interact with eachother?

• Unaware: independent (competition)

• Indirectly aware: shared resource (cooperation)

• Directly aware: communicate (cooperation)

What problems does competition between processes pose?

Mutual exclusion, deadlock, starvation

What problems does cooperation by sharing pose?

Mutual exclusion, deadlock, starvation, and data coherence

What problems does cooperation by communication pose?

Deadlock, starvation

What are some requirements for mutual exclusion support?

Enforcement (one process at a time in crit section)

Non-Interference (process that halts in non-crit doesn’t affect other processes)

Crit section open → any process wanting entry permitted without delay

Finite time (within crit section)

What three approaches are used to achieve mutual exlcusion?

Software - apps enforcing it through coding

Hardware - disable interrupts/have special machine instructions to support it

OS or Language - OS or language offer support for it

What are software solutions to achieve mutual exclusion?

Dekker’s and Peterson’s Algorithm

What are hardware solutions to achieve mutual exclusion?

Interrupt disabling, special machine instructions

What is interrupt disabling for mutual exclusion?

Allow a process to complete the critical section without being switched to another process

What issues arise from interrupt disabling for mutual exclusion?

Degrades multitasking performance

Doesn’t work on multiprocessor systems where processes execute at once regardless of interrupts

What are special machine instructions for mutual exclusion?

An instruction could be designed that carries out 2 operations against a memory location atomically (without interruption)

What issues arise from special machine instructions for mutual exclusion?

Busy-waiting

Starvation

Deadlock

What are OS or language approaches to achieve mutual exclusion?

Semaphores - uses waits (decrement) and signals (increment), made atomic by provider

Queue used to hold processes waiting on semaphore

What is a strong semaphore?

Queue uses FIFO order

No starvation

What is a weak semaphore?

No queue ordering

Could have starvation

What is a binary semaphore?

Only two values, equally powerful as a general semaphore

Like a flag

What is a counting semaphore?

A general semaphore with n values

How does a semaphore behave?

No way of knowing before a process calls wait if it’ll block or not

When both processes continue running concurrently after a signal, no way to know which will actually run next on a uniprocessor system

Signal might not actually awaken another process/processes

To allow s processes into a critical section

Initialize the semaphore value to that number

Value of a semaphore s: s > 0

s processes may wait WITHOUT delay

Value of a semaphore s: s = 0

no processes waiting

Value of a semaphore s: s < 0

s processes are suspended waiting on s

What is the finite buffer solution?

Can be constructed by adding a semaphore to keep track of the buffer size

How do monitors compare to semaphores?

Equivalent to semaphores but easier to control

What are the chief characteristics of a monitor?

Local data variables accessible on by monitor

Process enters monitor invoking one of its procedures

Only one process may be executing in monitor, others suspended waiting for monitor to be available

What are condition variables?

Monitors use them for synchronization:

• cwait(c) - suspend execution of process calling condition c, monitor available for others

  • csignal(c) - resume exec of some process blocked after a cwait on c. if many, choose one, if none, do nothing

How does a csignal differ from a semaphore signal?

The signal is lost if no one is waiting

What are two requirements for processes that have interact?

Synchronization (for mutual exclusion)

Communication (to exchange information)

What environment does message passing work well in?

Distributed

What are basic message passing commands?

send (destination, message)

receive (source, message)

What are the three combinations of sender and receiver?

Blocking send, blocking receive

Nonblocking send, blocking receive

Nonblocking send, nonblocking receive

Blocking send, blocking receive

Both sender and receiver are blocked until message is delivered

Called a “rendezvous”

Nonblocking send, blocking receive

Sender continues processing such as sending messages as quickly as possible

Receiver is blocked until the requested message arrives

Nonblocking send, nonblocking receive

Neither party is required to wait

Message addressing, direct

specify destination process

Message addressing, indirect

send to mailbox and let receiving process/es pick up whenever ready (flexibility)

What is a deadlock?

Permanent blocking of a set of processes either competing or communicating

Conflicting need for resources

No efficient solution

What are the categories for resources?

Reusable, consumable

Reusable resources

used by one process at a time and is not consumer, ex: a process

Consumable resources

can be created and destroyed, ex: a message

What is a resource allocation graph?

Directed graph that depicts state of the system resources and processes

What are the required conditions for a 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

What are the general approaches to dealing with a deadlock?

Prevention

Avoidance

Detection

Deadlock prevention approaches

Indirect: prevent one of the three preconditions

Direct: prevent the fourth conditions

Deadlock prevention: Mutual exclusion

Difficult since required sometimes

Deadlock prevention: hold and wait

Make processes request all resources at once and blocking until resources can be granted simultaneously

Drawbacks to hold and wait prevention

• process may have to wait a long time for all resources to be free

• process may keep resources for a long time and deny it to other processes

• process may not know in advance what resources it needs

Deadlock prevention: no preemption

Two possibilities:
- if process holding resources can’t get one it needs, release the ones it has an request all again

- if a process needs resource held by another, preempt the process to make it release resources. this requires resources whose state can be saved and restored, such as the processor

Deadlock prevention: circular wait

Require ordering of resource requests, prevents a circle by having requests in forward order, so a process can’t acquire a resource then request one prior to it which another process may hold

May not be efficient

What is deadlock avoidance?

Similar to prevention

Allows the three preconditions but tries to prevent deadlock dynamically as resource requests are made

Allows more concurrency than prevention

Requieres knowledge of future resource request

What are the approaches to deadlock avoidance?

Process initiation denial - constrains whether new process allowed to run

Resource allocation denial - lets a process run but constrains whether its resource requests are granted

Deadlock avoidance: process initiation denial

Process declares max need for each resource

Process only allowed to start if max claim of all current processes + max claim of new process can be met

Doesn’t work well, assumes that all processes will make max resource req at same time, which keeps processes from starting that would have run successfully

Deadlock avoidance: resource allocation denial

An algorithm for this is the “Banker’s Algorithm” a term used by Dijkstra to compare processes + resources to bank reserves + loans

Banker’s Algorithm

Defines state of system as either safe or unsafe

Works by determining if the system would be safe if the resource is granted. Yes, grant. No, block until safe

What is a safe state in the Banker’s Algorithm?

in which a sequence of allocations exists NOT leading to deadlock

What is a unsafe state in the Banker’s Algorithm?

in which there is NO sequence of allocations that will avoid deadlock

What is the claim matrix in the Banker’s Algorithm?

requirement of each process for each resource

What is the allocation matrix in the Banker’s Algorithm?

current allocation to each process of each resource

What is the resource vector in the Banker’s Algorithm?

total amount of each resource in the system

What is the available vector in the Banker’s Algorithm?

total amount of each resource not allocated to any process

Advantages of deadlock avoidance

Less restrictive than deadlock prevention

Not necessary to preempt and rollback processes as in deadlock detection

Disadvantages of deadlock avoidance

Max resources must be known in advance

Process ordering must be independent (not constrained by process synch)

Must be fixed number of resources

Processes can’t exit while holding resources

What is deadlock detection?

Detects deadlocks and takes action if they occur

Performs algorithm periodically to detect deadlock

Uses allocation matrix and available vector as in Banker’s Algorithm

Request matrix states amount of resources being requested by each process

What is the deadlock detection algorithm?

1. Mark each process that has a row in the allocation of all zeroes (holds no resources)

2. For each remaining process, see it is 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 processes are deadlocked

In deadlock detection, how can recovery work?

Abort all deadlocked processes: most common

Back up each deadlocked process to previous checkpoint and restart all processes: could result in same deadlock

Continue aborting deadlocked processes one by one until deadlock resolved: abortion order should be intelligent

Successively preempt resources until deadlock is resolved: choices should be intelligent

Deadlock detection recovery intelligent process choice criteria

Least CPU time so far

Least output so far

Most estimated remaining runtime

Least total resources allocated so far

Least priority

What are the requirements for memory management?

Relocation

Protection

Sharing

Location organization

Physical organization

Memory management: relocation

In multiprogramming systems, program may be loaded into any free area of memory. can be swapped in and out of memory.

Difficult to load back into same memory location

Don’t know in advance where a program will load

Memory management: protection

Memory references each process makes must be checked to ensure they’re allowed

Memory references (like array positions) can be computed dynamically, cant be known in advance

Memory refs checked at run time by hardware

Impossible for OS since each program instruction must be checked

Memory management: sharing

2+ processes may be running same program, so we may want to let them SHARE program code

2+ processes may be working on the same data, so we may want to let them SHARE some memory for data

Protection must allow flexibility for sharing memory

Memory management: logical organization

Memory organized as linear address space

Programs consist of a number of pieces, modules, which have diff attributes like read only

Memory segmentation helps support use of modules

What are some advantages of logical organization of memory management if the system effectively deals with modules?

Modules can be written and compiled independently

Modules can be given diff degrees of protection (read only, exec only, etc)

Modules may be shared among processes

Memory management: physical organization

Memory organized as main memory and secondary storage (disk)

Difficult for programmer to manage moving the program between both environments as it runs

Best to let the memory management system manage moving processes between two types of memory

What is memory partitioning?

Putting memory into regions of fixed boundaries which can be equally or differently sized

What are the problems of equal-sized partitions?

Program may be too large, which is combatted by using overlays, where the program loads pieces of itself overlaying others.

Memory utilization is poor, since small programs occupy a large space (internal fragmentation)

How does unequal-sized partitions solve the problems from equal-sized partitions?

Small programs can be loaded into small regions and large programs can be loaded into large regions to avoid the need for overlays

How does the placement algorithm work?

A single queue is used for all partitions, and a program is assigned to the smallest open partition that holds it

What are the advantages and disadvantages of fixed partitions?

Number of partitions limit the number of active processes

Utilization not as good since it’s likely that part of a partition goes unused

What is dynamic partitioning?

Process given a region exactly as big as required

Size of region set dynamically as each program is loaded

However, this can cause “external fragmentation”

How can external fragmentation be dealt with?

A technique called compaction

What is compaction?

Shifts processes around in memory so there aren’t holes between them

However, this can be time consuming

What are the 3 different placement algorithms for dynamic partitioning?

Best-fit, first-fit, next-fit

What is the best-fit placement algorithm for dynamic partitioning?

Chooses partition closest in size to the process, often the worst because it causes smallest fragments which are unusable by other processes

What is the first-fit placement algorithm for dynamic partitioning?

Chooses first available partition from the beginning of memory that is large enough to hold the process, often the simplest, fastest, and best

What is the next-fit placement algorithm for dynamic partitioning?

Chooses next available partition beginning at previously chosen partition of memory that is large enough to hold the process, though it tends to fragment the end block of memory more than first-fit

What is the buddy system?

A system that divides memory blocks in half until a block that satisfies the request is found

When a divided block is freed, it can be combined to form the original block size

Why wont physical addressing work in equal and unequal partitions + dynamic partitioning?

When processes are swapped in and out of memory, they may be loaded back into different areas and are therefore RELOCATED

What are types of addresses?

Physical address

Logical addressW

What is physical address?

actual memory address, absolute address

What is logical address?

Address from pov of program, independent of current loaded position

Relative address: logical relative to a known point (ie the beginning)