quiz 2

0.0(0) Reviews
Report Flashcard set

Spaced Repetition

Scientifically backed study method

spaced repetition


Review terms and definitions



Study with MC, T/F, and other questions


Practice Test

Take a test on your terms and definitions



186 Terms
😃 Not studied yet (186)
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
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
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
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.
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
Bounded buffer solution using semaphores (producer)
produces item, has others wait for semaphore, then puts item in buffer, then locks the semaphore
Bounded buffer solution using semaphores (consumer)
has others wait for semaphore, move item to consumed, then locks semaphore before consuming it
Reader/Writer solution using semaphores (reader)
has others wait, then go to first line and has writer to stop writing, then reads it, then read count decreases and locks it
Reader/Writer solution using semaphores (writer)
wait for semaphore then writes the thing, then locks it
Dining Philosophers solution using monitor
imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available
How resource allocation graph has deadlock
when its in cycle and processes wait forever
Ignoring deadlocks
Reboot the system when there's a deadlock. E.g. Ostrich
Preventing deadlocks
Invalidate one of the four necessary conditions for deadlock.
Preventing deadlock example
safe sequence
Avoiding deadlock
requires that each process declare the maximum number of resources of each type that it may need, banker algorithm/resource allocation graph.
detecting deadlock
Periodically invoke an algorithm that searches for a cycle in the graph. e.g. resource allocation graph If there is a cycle, there exists a deadlock
advantages of ignoring deadlock
simple and straightforward, easy to implement
disadvantage of ignoring deadlock
reboot = breaks other programs
advantage of preventing deadlock
easy to understand
disadvantage of preventing deadlock
Low resource utilization; starvation possible
advantage of avoiding deadlock
eliminates deadlocks
disadvantage of avoiding deadlock
Processes may have to wait unnecessarily
advantage of detecting deadlock
can take measure to prevent deadlock in advantage
disadvantage of detection deadlock
cycle doesn't necessarily mean there is a deadlock. deadlock no happen = wasting system resources to search cycle
how mutual exclusion doesn't hold
not required for sharable resources; must hold for nonsharable resources
how hold and wait doesn't hold
must guarantee that whenever a process requests a resource, it does not hold any other resources
how no preemption doesn't hold
If a process hold resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
how circular wait doesn't hold
impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
Deadlock Avoidance general idea
to avoid deadlock from happening by creating safe sequence with banker's algorithm
safe state (in deadlock avoidance)
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
safe sequence
A sequence of resource allocation that ensures deadlock-prevention.
safe state algorithm
sequence of ALL processes in systems such that for each Pi, resources that Pi still request can satisfied by currently available resources + resources held by all Pj, w/ j < I
safe sequence algorithm
System is in safe state if there exists a sequence that includes all processes. Such sequence is called safe sequence
Is Banker algorithm in safe state?
termination (recovery algorithm)
Abort all deadlocked processes, one process at a time until the deadlock cycle is eliminated
termination (recovery algorithm) orders
How long process has computed, and how much longer to completion
termination (recovery algorithm) orders
Priority of the process
termination (recovery algorithm) orders
Resources the process has used
termination (recovery algorithm) orders
Resources process needs to complete
termination (recovery algorithm) orders
How many processes will need to be terminated
termination (recovery algorithm) orders
Is process interactive or batch?
resource preemption (recovery algorithm) issues
Selecting a victim - minimize cost
resource preemption (recovery algorithm) issues
Rollback - return to some safe state, restart process for that state
resource preemption (recovery algorithm) issues
Starvation - same process may always be picked as victim, include number of rollback in cost factor
Address binding times
Compile, load, and execution
Compile (address binding)
If memory location known a priori, absolute code can be generated; must recompile code if starting location changes
Load (address binding)
Must generate relocatable code if memory location is not known at compile time
Execution (address binding)
Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps
Dynamic linking
linking postponed until execution time
Dynamic linking step 1
Small piece of code, stub, used to locate the appropriate memory-resident library routine
Dynamic linking step 2
Stub replaces itself with the address of the routine, and executes the routine
Dynamic linking step 3
Operating system checks if routine is in processes' memory address. If not in address space, add to address space
Dynamic linking benefit
Dynamic linking is particularly useful for implementing shared libraries. .dll for Windows and .so for Linux.
Dynamic loading
A program's module isn't loaded until it is used
Dynamic loading benefit
Useful when large amounts of code are needed to handle infrequently occurring cases
Dynamic loading benefit
No special support from the operating system is required. Implemented through program design + OS can help by providing libraries to implement
virtual address
generated by the CPU
Physical address
address seen by the memory unit
Logical and physical addresses are the same in
compile-time and load-time address-binding schemes
Logical (virtual) and physical addresses differ in
execution-time address-binding scheme
Memory management unit, Hardware device that maps virtual to physical address at run time
relocation/base register
The value in the relocation register is added to every address generated by user process at time sent 2 memory. Physical Address = Logical Address + contents of relocation register
A process can be swapped out of memory to backing store, then brought back into memory for continued execution. Total physical memory space of processes can exceed physical memory
Backing store
fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
Roll out, roll in
swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
Major part of swap time
transfer time. it's proportional to the amount of memory swapped
ready queue
has ready-to-run processes which have memory images on disk
Does the swapped out process need to swap back in to same physical addresses?
Depends on address binding method. consider pending I/O to / from process memory space