quiz 2

0.0(0)
studied byStudied by 1 person
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/138

flashcard set

Earn XP

Description and Tags

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

139 Terms

1
New cards
What is a critical region?
A part of the program where the shared memory is accessed
2
New cards
What characteristics are required of a solution to the critical section problem?
Mutual Exclusion, Progress, Bounded Waiting
3
New cards
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
4
New cards
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
5
New cards
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
6
New cards
Bounded Waiting for critical section problem
Assume that each process executes at a nonzero speed
7
New cards
Bounded Waiting for critical section problem
No assumption concerning relative speed of the N processes
8
New cards
What is a race condition?
outcome of execution depends upon order of access
9
New cards
How does a race condition occur?
2 thread access 1 shared variable
10
New cards
What is the definition of deadlock?
a process indefinitely waits for a resource that is held by another process
11
New cards
What are the four conditions necessary for a deadlock to occur?
Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
12
New cards
Mutual Exclusion
not required for sharable resources; must hold for nonsharable resources
13
New cards
Hold and Wait
must guarantee that whenever a process requests a resource, it does not hold any other resources
14
New cards
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
15
New cards
Hold and Wait Disadvantage
Low resource utilization; starvation possible
16
New cards
No Preemption
If process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held release
17
New cards
No Preemption
Preempted resources are added to the list of resources for which the process is waiting
18
New cards
No Preemption
Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
19
New cards
Mutual Exclusion Disadvantage
unwise to allow user process to this ability (should be privileged) Only works on a single CPU system.
20
New cards
Circular Wait
impose total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
21
New cards
Circular Wait
Invalidating the circular wait condition is most common.
22
New cards
Circular Wait
Simply assign each resource (i.e. mutex locks) a unique number.
23
New cards
Circular Wait
Resources must be acquired in order.
24
New cards
What is a safe sequence?
sequence of processes that not leads to deadlock state and fulfilling requests with available resources
25
New cards
How does a safe sequence prevent deadlock?
If a system is in safe state, no deadlocks
26
New cards
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
27
New cards
Advantages of contiguous allocation?
No space need to determine next block location,
28
New cards
Advantages of contiguous allocation?
Sequential access required min head movement,
29
New cards
Advantages of contiguous allocation?
File descriptors are easy 2 implement,
30
New cards
Advantages of contiguous allocation?
Easily implemented
31
New cards
What is the idea behind address translation?
enabling private IP networks using unregistered IP addresses to go online
32
New cards
What is a virtual address?
generated by the CPU and also called logical address
33
New cards
What is a physical address
address seen by the memory unit
34
New cards
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
35
New cards
What is external fragmentation?
total memory space exists to satisfy a request, but it is not contiguous
36
New cards
What is the idea behind paging?
break each process into individual pages
37
New cards
Advantages of Paging
NO external fragmentation, Fast to allocate and free, Simple to swap-out portions of memory to disk
38
New cards
Disadvantages of paging
Internal fragmentation, Assigning different levels of protection to different classes of data items not feasible.
39
New cards
Disadvantages of contiguous allocation?
Finding contiguous space for a new file may be impossible
40
New cards
Disadvantages of contiguous allocation?
Programmer must specify size before hand
41
New cards
Disadvantages of contiguous allocation?
External fragmentation occurs
42
New cards
What are the ways to deal with very large page tables efficiently?
use special fast-lookup hardware cache called translation look-aside buffers (TLBs)
43
New cards
What is Effective Access time?
(weighted) average time it takes to get a value from memory
44
New cards
What is Effective Access Time function?
EAT = (202) * 1-hit ratio + 102 * hit ratio
45
New cards
Briefly explain the Banker's algorithm.
allocate resources to process considering availability of resource and predetermined maximum need of process.
46
New cards
Producer-Consumer Problem
Producer process produces information in buffer that is consumed by a consumer process
47
New cards
Bounded Buffer Solution
many producers and consumers share 1 buffer
48
New cards
critical region
accessing shared memory or file
49
New cards
Race Condition
results when several threads try to access and modify the same data concurrently
50
New cards
how a race condition occurs
when two threads access a shared variable at the same time
51
New cards
nonpreemptive kernels
process cannot be preempted while in kernel/supervisor mode. Must wait until return to user mode or yields CPU
52
New cards
preemptive kernel
process can be preempted while in kernel mode
53
New cards
preemptive kernel example
Linux starting with version 2.6, Solaris, Windows 7/8/10
54
New cards
preemptive kernel advantage
sys-calls do not block the entire system
55
New cards
preemptive kernel disadvantage
introduces more complexity to the kernel code
56
New cards
non-preemptive kernel advantage
less difficult to design
57
New cards
non-preemptive kernel disadvantage
It can lead to starvation especially for those real-time tasks
58
New cards
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
59
New cards
atomic instruction
allow us to either test-and-modify the content of a word, or two swap the contents of two words atomically/uninterruptibly
60
New cards
Test and Set (atomic instruction)
test memory word and set value
61
New cards
Swap (atomic instruction)
swap contents of two memory words
62
New cards
Semaphores
Synchronization tool that provides more sophisticated ways for process to synchronize their activities.
63
New cards
Wait() (semaphore)
wait function has an argument called S, while S is less or equal to 0, S decreases by 1.
64
New cards
signal() (semaphore)
signal function has an argument called S. S increments by 1.
65
New cards
How wait() is used
blocks the calling process until one of its child processes exits or a signal is received
66
New cards
How signal() is used
call the func function if the process receives a signal signum
67
New cards
Counting semaphore
integer value can range over an unrestricted domain
68
New cards
Binary semaphore
aka mutex lock, integer value can range only between 0 and 1; can be simpler to implement
69
New cards
Semaphore as General Synchronization Tool can...
implement a counting semaphore S as a binary semaphore
70
New cards
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().
71
New cards
busy-waiting advantage
thread has the processor and can resume immediately after the wait is finished
72
New cards
busy-waiting disadvantage
waste of resource
73
New cards
spinlocks
Mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability.
74
New cards
spinlock advantage
threads get the chance to take advantage of their full runtime quantum
75
New cards
spinlock disadvantage
while waiting to acquire a lock, it wastes time that might be productively spent elsewhere
76
New cards
mutex locks
Protect a critical section by first acquire() a lock then release() the lock
77
New cards
how binary semaphore is used
control access to a single resource and can implement as counting semaphore
78
New cards
how counting semaphore is used
coordinate access to resources and can implement as binary semaphore
79
New cards
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.
80
New cards
When binary semaphore is used
when users are controlling access to shared device, like using a printer
81
New cards
Resource-Allocation Graph
A graph representing processes and resource instances in a system. Directed edges represent resource requests and allocations.
82
New cards
monitor
high-level abstraction that provides a convenient and effective mechanism for process synchronization
83
New cards
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
84
New cards
condition variable
enables a thread to efficiently wait for a change to shared state protected by a lock
85
New cards
Bounded buffer solution using semaphores (producer)
produces item, has others wait for semaphore, then puts item in buffer, then locks the semaphore
86
New cards
Bounded buffer solution using semaphores (consumer)
has others wait for semaphore, move item to consumed, then locks semaphore before consuming it
87
New cards
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
88
New cards
Reader/Writer solution using semaphores (writer)
wait for semaphore then writes the thing, then locks it
89
New cards
Dining Philosophers solution using monitor
imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available
90
New cards
How resource allocation graph has deadlock
when its in cycle and processes wait forever
91
New cards
Ignoring deadlocks
Reboot the system when there's a deadlock. E.g. Ostrich
92
New cards
Preventing deadlocks
Invalidate one of the four necessary conditions for deadlock.
93
New cards
Preventing deadlock example
safe sequence
94
New cards
Avoiding deadlock
requires that each process declare the maximum number of resources of each type that it may need, banker algorithm/resource allocation graph.
95
New cards
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
96
New cards
advantages of ignoring deadlock
simple and straightforward, easy to implement
97
New cards
disadvantage of ignoring deadlock
reboot = breaks other programs
98
New cards
advantage of preventing deadlock
easy to understand
99
New cards
disadvantage of preventing deadlock
Low resource utilization; starvation possible
100
New cards
advantage of avoiding deadlock
eliminates deadlocks