quiz 2

studied byStudied by 37 People

What is a critical region?


Tags & Description

Computer Science


Studying Progress

New cards
Still learning
Almost Done
186 Terms

What is a critical region?

A part of the program where the shared memory is accessed

What characteristics are required of a solution to the critical section problem?

Mutual Exclusion, Progress, Bounded Waiting

Mutual Exclusion for critical section problem

If process Pi is executing in its critical section, then no other processes can be executing in their critical sections

Progress for critical section problem

If no process is executing in its critical section and there are some want to enter their cs, then selection of the process that will enter next can't postpone indefinitely

Bounded Waiting for critical section problem

A bound must exist on # times other processes allowed to enter critical sections after process made request to enter critical section/before that request is granted

Bounded Waiting for critical section problem

Assume that each process executes at a nonzero speed

Bounded Waiting for critical section problem

No assumption concerning relative speed of the N processes

What is a race condition?

outcome of execution depends upon order of access

How does a race condition occur?

2 thread access 1 shared variable

What is the definition of deadlock?

a process indefinitely waits for a resource that is held by another process

What are the four conditions necessary for a deadlock to occur?

Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait

Mutual Exclusion

not required for sharable resources; must hold for nonsharable resources

Hold and Wait

must guarantee that whenever a process requests a resource, it does not hold any other resources

Hold and Wait

Require process to request/be allocated all its resources before starting execution, or allow it to request resource only when process has none

Hold and Wait Disadvantage

Low resource utilization; starvation possible

No Preemption

If process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held release

No Preemption

Preempted resources are added to the list of resources for which the process is waiting

No Preemption

Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting

Mutual Exclusion Disadvantage

unwise to allow user process to this ability (should be privileged) Only works on a single CPU system.

Circular Wait

impose total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

Circular Wait

Invalidating the circular wait condition is most common.

Circular Wait

Simply assign each resource (i.e. mutex locks) a unique number.

Circular Wait

Resources must be acquired in order.

What is a safe sequence?

sequence of processes that not leads to deadlock state and fulfilling requests with available resources

How does a safe sequence prevent deadlock?

If a system is in safe state, no deadlocks

Difference between contiguous and non-contiguous allocation of memory?

contiguous allocate consecutive blocks of memory, non-contiguous allocate separate block of memory to file/process

Advantages of contiguous allocation?

No space need to determine next block location,

Advantages of contiguous allocation?

Sequential access required min head movement,

Advantages of contiguous allocation?

File descriptors are easy 2 implement,

Advantages of contiguous allocation?

Easily implemented

What is the idea behind address translation?

enabling private IP networks using unregistered IP addresses to go online

What is a virtual address?

generated by the CPU and also called logical address

What is a physical address

address seen by the memory unit

What is internal fragmentation?

allocated memory being slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

What is external fragmentation?

total memory space exists to satisfy a request, but it is not contiguous

What is the idea behind paging?

break each process into individual pages

Advantages of Paging

NO external fragmentation, Fast to allocate and free, Simple to swap-out portions of memory to disk

Disadvantages of paging

Internal fragmentation, Assigning different levels of protection to different classes of data items not feasible.

Disadvantages of contiguous allocation?

Finding contiguous space for a new file may be impossible

Disadvantages of contiguous allocation?

Programmer must specify size before hand

Disadvantages of contiguous allocation?

External fragmentation occurs

What are the ways to deal with very large page tables efficiently?

use special fast-lookup hardware cache called translation look-aside buffers (TLBs)

What is Effective Access time?

(weighted) average time it takes to get a value from memory

What is Effective Access Time function?

EAT = (202) * 1-hit ratio + 102 * hit ratio

Briefly explain the Banker's algorithm.

allocate resources to process considering availability of resource and predetermined maximum need of process.

Producer-Consumer Problem

Producer process produces information in buffer that is consumed by a consumer process

Bounded Buffer Solution

many producers and consumers share 1 buffer

critical region

accessing shared memory or file

Race Condition

results when several threads try to access and modify the same data concurrently