Studied by 1 PersonTags & 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
how a race condition occurs
when two threads access a shared variable at the same time
nonpreemptive kernels
process cannot be preempted while in kernel/supervisor mode. Must wait until return to user mode or yields CPU
preemptive kernel
process can be preempted while in kernel mode
preemptive kernel example
Linux starting with version 2.6, Solaris, Windows 7/8/10
preemptive kernel advantage
sys-calls do not block the entire system
preemptive kernel disadvantage
introduces more complexity to the kernel code
non-preemptive kernel advantage
less difficult to design
non-preemptive kernel disadvantage
It can lead to starvation especially for those real-time tasks
Peterson's Solution
a classic software-based solution to the critical-section problem which has to two processes that alternate execution between critical sections/remainder sections
atomic instruction
allow us to either test-and-modify the content of a word, or two swap the contents of two words atomically/uninterruptibly
Test and Set (atomic instruction)
test memory word and set value
Swap (atomic instruction)
swap contents of two memory words
Semaphores
Synchronization tool that provides more sophisticated ways for process to synchronize their activities.
Wait() (semaphore)
wait function has an argument called S, while S is less or equal to 0, S decreases by 1.
signal() (semaphore)
signal function has an argument called S. S increments by 1.
How wait() is used
blocks the calling process until one of its child processes exits or a signal is received
How signal() is used
call the func function if the process receives a signal signum
Counting semaphore
integer value can range over an unrestricted domain
Binary semaphore
aka mutex lock, integer value can range only between 0 and 1; can be simpler to implement
Semaphore as General Synchronization Tool can...
implement a counting semaphore S as a binary semaphore
Busy-waiting
While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().
busy-waiting advantage
thread has the processor and can resume immediately after the wait is finished
busy-waiting disadvantage
waste of resource
spinlocks
Mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability.
spinlock advantage
threads get the chance to take advantage of their full runtime quantum
spinlock disadvantage
while waiting to acquire a lock, it wastes time that might be productively spent elsewhere
mutex locks
Protect a critical section by first acquire() a lock then release() the lock
how binary semaphore is used
control access to a single resource and can implement as counting semaphore
how counting semaphore is used
coordinate access to resources and can implement as binary semaphore
how mutex lock is used
declare a lock variable of type Mutex, then execute the Lock() method of that lock, then execute the Unlock() method of the lock.
When binary semaphore is used
when users are controlling access to shared device, like using a printer
Resource-Allocation Graph
A graph representing processes and resource instances in a system. Directed edges represent resource requests and allocations.
monitor
high-level abstraction that provides a convenient and effective mechanism for process synchronization
difference between semaphore and monitor
semaphore's signal and wait increase/decrease, monitor's signal and wait doesn't, and m is higher lvl proc sync tool
condition variable
enables a thread to efficiently wait for a change to shared state protected by a lock