Shared Flashcard Set

Details

CSCI 2530 Test 2
Chapter 5 - 8
64
Computer Science
Undergraduate 3
03/29/2010

Additional Computer Science Flashcards

 


 

Cards

Term
Multiprogramming
Definition
: The management of multiple processes within a uniprocessor system
Term

Multiprocessing

Definition
The management of multiple processes within a multiprocessor
Term

Distributed processing

Definition

The management of multiple processes executing on multiple, distributed computer systems.

E. G clusters

Term
Concurrency
Definition

 

 

Managing the interaction of all of these processes

 

encompasses a host of design issues, including

communication among processes,
sharing of and competing for resources (such as memory, files, and I/O access),
synchronization of the activities of multiple processes, and

 allocation of processor time to processes

 

Term
Difficulties of
Concurrency
Definition

Sharing of global resources
Optimally managing the allocation of resources
Difficult to locate programming errors as results are not deterministic and reproducible.

Term

 

Multiple applications

 

Definition

:

 Sharing Time.  Multiprogramming was invented to allow processing time to be dynamically shared among a number of active applications.

Term

 

Structured applications:


 

Definition
 Extension of modular design. As an extension of the principles of modular design and structured programming, some applications can be effectively programmed as a set of concurrent processes.
Term

Operating system structure

Definition

OS themselves implemented as a set of processes or threads.
The same structuring advantages apply to systems programs, and we have seen that operating systems are themselves often implemented as a set of processes or threads.

Term
Race Condition
Definition

Multiple processes or threads read and write data items
They do so in a way where the final result depends on the order of execution of the processes.
The output depends on who finishes the race last.

Term
Mutual exclusion
Definition

Only one process at a time is allowed in the critical section for a resource
A process that halts in its noncritical section must do so without interfering with other processes
No deadlock or starvation

Term

 

What design and management issues are raised by the existence of concurrency?
The 4 OS issues

 

Definition

 

The OS must
Keep track of various processes
Allocate and de-allocate resources
Protect the data and resources against interference by other processes.
Ensure that the processes and outputs are independent of the processing speed

 

Term

Processes unaware of each other:

Definition
Independent processes that are not intended to work together.
E.G. multiprogramming of multiple independent processes.
Although the processes are not working together, the OS needs to be concerned about competition for resources.
E.G. two independent applications may both want to access the same disk or file or printer.
Term

Processes indirectly aware of each other:

Definition
Processes that are not necessarily aware of each other by their respective process IDs but that share access to some object, such as an I/O buffer.

 Such processes exhibit cooperation in sharing the common object

Term

Processes directly aware of each other:

Definition
Processes that are able to communicate with each other by process ID and that are designed to work jointly on some activity.

 Again, such processes exhibit cooperation.

Term
Critical section
Definition
A section of code within a process that requires access to shared resources and that must not be executed while another process is in a corresponding section of code.
Term
Critical Resource
Definition
During the course of execution, each process will be sending commands to the I/O device, receiving status information, sending data, and/or receiving data. We will refer to such a resource as a ________.
Term
Deadlock
Definition

when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set
Typically involves processes competing for the same set of resources
No efficient solution


Neither will release the resource that it already owns until it has acquired the other resource and performed the function requiring both resources

Term
Starvation
Definition

a situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.

The OS may grant access to resources to a number of processes while neglecting another

Term

Need for mutual exclusion.

Definition
Suppose two or more processes require access to a single nonsharable resource, such as a printer.
During the course of execution, each process will be sending commands to the I/O device, receiving status information, sending data, and/or receiving data.
Term
6 requirements for mutual exclusion
Definition

1. M.E. must be enforced:only 1 process at a time is allowed into its critical section, among all processes that have critical sections fro the same resource or shared object

2.A process that halts in its noncritical section must do so without interfering with other processes.

3.It must not be possible for a process requiring access to a critical section to be delayed indefinitely: no deadlock or starvation.

4.When no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delay.

5.No assumptions are made about relative process speeds or number of processes
6.A process remains inside its critical section for a finite time only

Term

Interrupt Disabling

Definition
A process runs until it invokes an operating system service or until it is interrupted
Disabling interrupts guarantees mutual exclusion
Will not work in multiprocessor architecture
Term

Semaphore: 

Definition
An integer value used for signalling among processes.
Only three operations may be performed on a semaphore, all of which are atomic:
initialize,
Decrement (semWait)

        -increment. (semSignal

Term
3 operations that are defined on semaphores?
Definition

1. A semaphore may be initialized to a nonnegative integer value.

2. The semWait operation decrements the semaphore value.

If the value becomes negative, then the process executing the semWait is blocked.
Otherwise, the process continues execution.

3. The semSignal operation increments the semaphore value.

If the resulting value is less than or equal to zero, then a process blocked by a semWait operation, if any, is unblocked.

Term
queue
Definition
used to hold processes waiting on the semaphore
Term
Binary Semaphore
Definition
A semaphore that takes on only the values 0 and 1.
Term
Mutex
Definition

Similar to a binary semaphore. 

A key difference between the two is that the process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1).
In contrast, it is possible for one process to lock a binary semaphore and for another to unlock it.

Term

fatal region

 

Definition

The gray-shaded area can be referred to as a __________, applies to paths 3 and 4.

 If an execution path enters this __________, then deadlock is inevitable.

 

Only occurs if joint progress of the two processes creates a path that enters ______.

Term

 

Reusable


 

Definition

can be safely used by only one process at a time and is not depleted by that use.

Such as:
Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores
Deadlock occurs if each process holds one resource and requests the other

Term

 

Consumable

 

Definition

one that can be created (produced) and destroyed (consumed).

 

Such as Interrupts, signals, messages, and information in I/O buffers
Deadlock may occur if a Receive message is blocking
May take a rare combination of events to cause deadlock

Term
Resource Allocation
 Graphs
Definition

 

Directed graph that depicts a state of the system of resources and processes

A graph edge directed from a process to a resource indicates a resource that has been requested by the process but not yet granted.

Within a resource node, a dot is shown for each instance of that resource.

A graph edge directed from a reusable resource node dot to a process indicates a request that has been granted

 

Term
4 conditions for deadlock
Definition

Mutual exclusion
Only one process may use a resource at a time
Hold-and-wait
A process may hold allocated resources while awaiting assignment of others
No pre-emption
No resource can be forcibly removed form 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

Term
2 approaches to deadlock
Definition

1. Process initiation denial - do not start a process if its demands might lead to deadlock

2. Resource allocation denial - do not grant an incremental resource request to a process if this allocation might lead to deadlock

Term
Deadlock prevention
Definition
 strategy simply to design a system in such a way that the possibility of deadlock is excluded
Term
Deadlock avoidance
Definition

A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock
Requires knowledge of future process requests

Term
Process initiation denial
Definition

do not start a process if its demands might lead to deadlock.

A process is only started if the maximum claim of all current processes plus those of the new process can be met.
Not optimal,
Assumes the worst: that all processes will make their maximum claims together.

Term

 

Resource Allocation Denial

 

Definition
Do not grant an incremental resource request to a process if this allocation might lead to deadlock
Referred to as the banker’s algorithm
Consider a system with fixed number of resources
State of the system is the current allocation of resources to process
Safe state is where there is at least one sequence that does not result in deadlock
Unsafe state is a state that is not safe
Term
Safe State
Definition

where there is at least one sequence that does not result in deadlock.

A system consisting of four processes and three resources.
Allocations are made to processors

Term
Deadlock Detection
Definition

Resource requests are granted whenever possible.
Regularly check for deadlock

Term
4 strategies of recovery
Definition

Abort all deadlocked processes
Back up each deadlocked process to some previously defined checkpoint, and restart all process
Risk or deadlock recurring
Successively abort deadlocked processes until deadlock no longer exists
Successively preempt resources until deadlock no longer exists

Term
Integrated deadlock strategy approaches
Definition

1. swappable space - blocks of memory on 2nd storage for use in swapping processes.

2. process resources (tape drive or files)

3. main memory - assignable to processes in pages or segments

4. Internal resources (I/O channels)

Term
Relocation
Definition

The programmer does not know where the program will be placed in memory when it is executed,
it may be swapped to disk and return to main memory at a different location (relocated)
Memory references must be translated to the actual physical memory address

Term
Protection
Definition

Processes should not be able to reference memory locations in another process without permission
Impossible to check absolute addresses at compile time
Must be checked at run time

Term
Sharing
Definition

Allow several processes to access the same portion of memory
Better to allow each process access to the same copy of the program rather than have their own separate copy

Term
Logical Organization
Definition

Memory is organized linearly (usually)
Programs are written in modules
Modules can be written and compiled independently
Different degrees of protection given to modules (read-only, execute-only)
Share modules among processes
Segmentation helps here

Term
Physical Organization
Definition

Cannot leave the programmer with the responsibility to manage memory
Memory available for a program plus its data may be insufficient
Overlaying allows various modules to be assigned the same region of memory but is time consuming to program
Programmer does not know how much space will be available

Term
Fixed Partitioning
Definition

Equal-size partitions 
Any process whose size is less than or equal to the partition size can be loaded into an available partition
The operating system can swap a process out of a partition
If none are in a ready or running state

Term
Internal Fragmentation
Definition
When there is wasted space internal to a partition due to the fact that the block of data loaded is smaller than the partition
Term
The Placement Algorithm
Definition

Equal-size
Placement is trivial (no options)
Unequal-size
Can assign each process to the smallest partition within which it will fit
Queue for each partition
Processes are assigned in such a way as to minimize wasted memory within a partition

Term
Dynamic Partitioning
Definition

Partitions are of variable length and number
Process is allocated exactly as much memory as required

Term

 

External Fragmentation

 

 

Definition
As time goes on, memory becomes more and more fragmented, and memory utilization declines.
Memory external to all processes is fragmented

Can resolve using

Term

compaction

Definition
OS moves processes so that they are contiguous
Time consuming and wastes CPU time
Term

Best-fit algorithm

Definition
Chooses the block that is closest in size to the request
Worst performer overall
Since smallest block is found for process, the smallest amount of fragmentation is left
Memory compaction must be done more often
Term

First-fit algorithm

Definition
Scans memory from the beginning and chooses the first available block that is large enough
Fastest

May have many process loaded in the front end of memory that must be searched over when trying to find a free block

Term

Logical

Definition
Reference to a memory location independent of the current assignment of data to memory.
Term

Physical address

Definition
The absolute address or actual location in main memory
Term

Relative Address

Definition
Address expressed as a location relative to some known point.
Term
Paging
Definition

Partition memory into small equal fixed-size chunks and divide each process into the same size chunks

Term
Page
Definition
The chunks of a process
Term
Frame
Definition
The chunks of memory
Term
Page Table
Definition

Operating system maintains a _________ for each process
Contains the frame location for each page in the process
Memory address consist of a page number and offset within the page

Term
Segmentation
Definition

A program can be subdivided into segments
Segments may vary in length
There is a maximum segment length
Addressing consist of two parts
a segment number and
an offset
Segmentation is similar to dynamic partitioning

Term
Buffer overflow attacks
Definition

A condition at an interface under which more input can be placed into a buffer or data holding area than the capacity allocated, overwriting other info.  Attackers exploit such a condition to crash a system or to insert specially crafted code that allows them to gain control of the system.

Can occur as a result of a programming error when a process attempts to store data beyond the limits of a fixed-sized buffer and consequently overwrites adjacent memory locations

Term
Two characteristics of paging and segmentation are the keys to this breakthrough in memory management:
Definition

1) Memory references are logical addresses dynamically translated into physical addresses at run time

A process may be swapped in and out of main memory occupying different regions at different times during execution

2) A process may be broken up into pieces that do not need to located contiguously in main memory

Supporting users have an ad free experience!