Studied by 37 PeopleWhat is a critical region?
Tags & Description
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