Fichas
Sin título
Fichas del conjunto (125)
- 1cooperating processone that can affect or be affected by other processes
executing in the system, and can either directly share a
logical address space (that is, both code and data) or be allowed to share data
only through files or messages. - 2race conditionwhere
several processes access and manipulate the same data concurrently and the
outcome of the execution depends on the particular order in which the access
takes place - 3To guard against the race conditionwe need to ensure that only one process at a time can be manipulating
the variable counter. - 4critical sectionwhich the process may be changing common variables, updating a table,
writing a file, and so on. - 5The critical-section problemIt is to design a
protocol that the processes can use to cooperate. - 6The section of code (critical-section) implementing this request is the______-entry section
- 7The critical section may be followed by an (a)_____Exit section
- 8The remaining code is the___remainder section
- 9A solution to the critical-section problem must satisfy the following three requirements:Mutual exclusion
Progress
Bounded waiting - 10Mutual exclusionIf process Pi is executing in its critical section, then no
other processes can be executing in their critical sections - 11Progress.If no process is executing in its critical section and some
processes wish to enter their critical sections, then only those processes
that are not executing in their remainder sections can participate in
deciding which will enter its critical section next, and this selection cannot
be postponed indefinitely. - 12Bounded waiting.There exists a bound, or limit, on the number of times
that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that
request is granted. - 13Two general approaches are used to handle critical sections in operating systems:preemptive kernels and nonpreemptive kernels
- 14preemptive kernelallows a process to be preempted while it is running in kernel mode
- 15nonpreemptive kerneldoes not allow a process running in kernel mode to be
preempted; - 16Peterson’s solution requires the two processes to share two data items:int turn;
boolean flag[2]; - 17variable turn indicates...whose turn it is to enter its critical section. Then, process Pi is allowed to execute in its critical section.
- 18The flag array is used...to indicate if a process is ready to enter its critical section.
- 19lockingprotecting critical regions through
the use of locks. As we shall see, the designs of such locks can be quite
sophisticated. - 20mutex lockto protect critical regions and thus prevent race conditions.
- 21The two functions of a mutex lockacquire() and release()
- 22The definition of acquire() is as follows:acquire() {
while (!available)
; /* busy wait */
available = false;;
} - 23definition of release() is as follows:release() {
available = true;
} - 24definition of the test and set()boolean test and set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
} - 25the compare and swap()int compare and swap(int *value, int expected, int new value) {
int temp = *value;
if (*value == expected)
*value = new value;
return temp;
} - 26Bounded-waiting mutual exclusion with test and set()do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test and set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
} while (true); - 27Distinguish the difference between counting and binary semaphoresThe value of a counting semaphore can range over an unrestricted domain.
The value of a binary semaphore can range only between 0 and 1. - 28Does binary semaphores behave similarly to mutex locks?Yes.
- 29What is the alternative to mutual exclusion on systems that do not provide mutex locksbinary semaphore
- 30A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations:wait() and signal().
- 31definition of wait()wait(S) {
while (S <= 0)
; // busy wait
S--;
} - 32The definition of signal() is as follows:signal(S) {
S++;
} - 33block() operationsuspends the process that invokes it.
- 34wakeup()resumes the execution of a blocked process
- 35deadlockedThe implementation of a semaphore with a waiting queue may result in a
situation where two or more processes are waiting indefinitely for an event
that can be caused only by one of the waiting processes. - 36Another problem related to deadlocks is____or____indefinite blocking, starvation
- 37The structure of the producer processdo {
. . .
/* produce an item in next produced */
. . .
wait(empty);
wait(mutex);
. . .
/* add next produced to the buffer */
. . .
signal(mutex);
signal(full);
} while (true); - 38The structure of the consumer process.do {
wait(full);
wait(mutex);
. . .
/* remove an item from buffer to next consumed */
. . .
signal(mutex);
signal(empty);
. . .
/* consume the item in next consumed */
. . .
} while (true); - 39readers–writers problemensure that these difficulties do not arise, we require that the writers
have exclusive access to the shared database while writing to the database. - 40The structure of a reader processdo {
wait(mutex);
read count++;
if (read count == 1)
wait(rw mutex);
signal(mutex);
. . .
/* reading is performed */
. . .
wait(mutex);
read count--;
if (read count == 0)
signal(rw mutex);
signal(mutex);
} while (true); - 41The structure of a writer process.do {
wait(rw mutex);
. . .
/* writing is performed */
. . .
signal(rw mutex);
} while (true); - 42dining-philosophers problemconsidered a classic synchronization
problem neither because of its practical importance nor because computer
scientists dislike philosophers but because it is an example of a large class
of concurrency-control problems. - 43The structure of philosopherdo {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
. . .
/* eat for awhile */
. . .
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
. . .
/* think for awhile */
. . .
} while (true); - 44abstract data type (ADT)encapsulates data with a set of functions
to operate on that data that are independent of any specific implementation
of the ADT. - 45monitor typean ADT that includes a set of programmerdefined
operations that are provided with mutual exclusion within the monitor. - 46The monitor typedeclares the variables whose values define the state
of an instance of that type, along with the bodies of functions that operate
on those variables. - 47Syntax of a monitor.monitor monitor name
{
/* shared variable declarations */
function P1 ( . . . ) {
. . .
}
function P2 ( . . . ) {
. . .
}
.
.
.
function Pn ( . . . ) {
. . .
}
initialization code ( . . . ) {
. . .
}
} - 48The only operations that can be invoked on a condition variablewait()
and signal() - 49Signal and waitP either waits until Q leaves the monitor or waits for
another condition. - 50Signal and continueQ either waits until P leaves the monitor or waits
for another condition. - 51deadlocka
waiting process is never again able to change state, because the resources it
has requested are held by other waiting processes - 52A processes never finish executing, and system resources are tied up, preventing other jobs fromstartingdeadlock
- 53A deadlock situation can arise if the following four conditions hold simultaneously in a system:Mutual exclusion.
Hold and wait.
No preemption.
Circular wait. - 54Mutual exclusion(deadlock)At least one resource must be held in a nonsharable
mode; that is, only one process at a time can use the resource. If another
process requests that resource, the requesting process must be delayed
until the resource has been released. - 55Hold and wait(deadlock)A process must be holding at least one resource and
waiting to acquire additional resources that are currently being held by
other processes. - 56No preemption(deadlock)Resources cannot be preempted; that is, a resource can
be released only voluntarily by the process holding it, after that process
has completed its task. - 57Circular wait(deadlock)A set {P0, P1, ..., Pn} of waiting processes must exist such
that P0 is waiting for a resource held by P1, P1 is waiting for a resource
held by P2, ..., Pn−1 is waiting for a resource held by Pn, and Pn is waiting
for a resource held by P0. - 58system resource-allocation graph.directed graph that consists of a set of vertices V
and a set of edges E. The set of vertices V is partitioned into two different types
of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the
system, and R = {R1, R2, ..., Rm}, the set consisting of all resource types in the
system. - 59Deadlock Prevention(Mutual Exclusion)– not required for sharable resources; must hold for non-sharable resources
- 60Can a mutex lock be simultaneously shared by several processes.No, mutex lock cannot
be simultaneously shared by several processes. - 61Deadlock Prevention (Hold and Wait)must guarantee that whenever a process requests a resource, it does not hold any other resources.
Low resource utilization; starvation possible. - 62Deadlock Prevention(No Preemption)If a process is holding
some resources and requests another resource that cannot be immediately
allocated to it (that is, the process must wait), then all resources the process is
currently holding are preempted. In otherwords, these resources are implicitly
released. - 63Deadlock Prevention (Circular Wait)One
way to ensure that this condition never holds is to impose a total ordering of
all resource types and to require that each process requests resources in an
increasing order of enumeration. - 64Safe Statethe system can allocate resources to each process (up to its
maximum) in some order and still avoid a deadlock. - 65Is a safe state a deadlocked state?No, deadlocked state is
an unsafe state. - 66Un safe state may lead to a _____deadlcok
- 67claim edgeA claim edge Pi → Rj indicates that process Pi may request resource Rj at
some time in the future. This edge resembles a request edge in direction but is
represented in the graph by a dashed line. - 68banker’s algorithmThe deadlockavoidance
algorithm that we describe next is applicable to such a system but
is less efficient than the resource-allocation graph scheme. - 69We need the following (Banker'sAlgorithm) data structures, where n is the number of processes in the system and m is the number of resource types:Available
Max
Allocation
Need - 70Banker's Algorithm (Available)Avector of lengthmindicates the number of available resources
of each type. If Available[j] equals k, then k instances of resource type Rj
are available. - 71Banker's Algorithm (Max)An n × m matrix defines the maximum demand of each process.
If Max[i][j] equals k, then process Pi may request at most k instances of
resource type Rj . - 72Banker's Algorithm(Allocation)An n × m matrix defines the number of resources of each type
currently allocated to each process. If Allocation[i][j] equals k, then process
Pi is currently allocated k instances of resource type Rj . - 73Banker's Algorithm( Need)An n × m matrix indicates the remaining resource need of each
process. If Need[i][j] equals k, then process Pi may need k more instances
of resource type Rj to complete its task. Note that Need[i][j] equalsMax[i][j]
− Allocation[i][j]. - 74Resource-Request AlgorithmAvailable = Available–Requesti ;
Allocationi = Allocationi + Requesti ;
Needi = Needi –Requesti ; - 75Process TerminationTo eliminate deadlocks by aborting a process, we use one of two methods. In
both methods, the system reclaims all resources allocated to the terminated
processes. - 76Avoidance Algorithms for Single instance of a resource type:Use a resource-allocation graph
- 77Avoidance Algorithms for Multiple instances of a resource type:Use the banker’s algorithm
- 78Resource-Allocation GraphClaim edge Pi Rj indicated that process Pj may request resource Rj; represented by a dashed line.
Resources must be claimed a priori in the system. - 79Claim edge converts to request edge when a process requests a resource. Request edge converted to an assignment edge when the resource is allocated to the process.Resource-Allocation
- 80Ensure that the system will never enter a deadlock stateDeadlock prevention
Deadlock avoidance - 81Methods for Handling DeadlocksEnsure that the system will never enter a deadlock state.
Allow the system to enter a deadlock state and then recover.
Ignore the problem and pretend that deadlocks never occur in the system; used by most current operating systems, including UNIX. - 82Recovery from Deadlock: Resource PreemptionSelecting a victim- minimize cost
Rollback-return to some safe state, restart process for that state.
Starvation- same process may always be picked as victim, include number of rollback in cost factor. - 83Compile timeIf memory location known a priori, absolute code can be generated; must recompile code if starting location changes
- 84Load timecompiler must generate relocatable code if memory location is not known at compile time.
- 85Execution time: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 (e.g., base and limit registers)
- 86logical address spaceThe set of all
logical addresses generated by a program - 87physical address space.The set
of all physical addresses corresponding to particular logical addresses - 88memory-management unit (MMU).The run-time mapping from virtual to physical addresses is done by a
hardware device - 89Dynamically linked librariesystem libraries that are linked to user
programs when the programs are run - 90static linkingsystem libraries are treated
like any other object module and are combined by the loader into the binary
program image. - 91Do Logical and physical addresses have the same compile-time and load-time address-binding schemes?Yes
- 92Do Logical (virtual) and physical addresses same execution-time address-binding schemeNo, Logical (virtual) and physical addresses differ in execution-time address-binding scheme
- 93Does the user program deals with logical addresses?Yes.
- 94user program deals with real physical addressesNo, it never sees the real physical addresses
- 95With dynamic loading, Routine is not loaded until it is calledBetter memory-space utilization; unused routine is never loaded.
Useful when large amounts of code are needed to handle infrequently occurring cases.
No special support from the operating system is required. Implemented through program design. - 96Backing store– fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
- 97Major part of swap time is ____Transfer Time
- 98Transfer timedirectly proportional to the amount of memory swapped.
- 99Does the swapped out process need to swap back in to same physical addresses?Yes
Depends on address binding method
Plus consider pending I/O to / from process memory space - 100Does Android terminates apps if low free memory?Yes, but first writes application state to flash for fast restart
- 101Not typically supported Swapping on Mobile Systems-Flash memory based
-Small amount of space
-Limited number of write cycles
-Poor throughput between flash memory and CPU on mobile platform - 102In Contiguous Allocation, Main memory usually into two partitionsResident operating system, usually held in low memory with interrupt vector
User processes then held in high memory - 103in Contiguous Allocation, relocation registers used to protect user processes from each other, and from changing operating-system code and dataBase register contains value of smallest physical address
Limit register contains range of logical addresses – each logical address must be less than the limit register
MMU maps logical address dynamically - 104Given what we currently know about memory, what must we do during a context switch?Allocate memory to the switching process
- 105Dynamic Storage-Allocation ProblemWhen a process arrives, search for a hole big enough for it. If none available, the process must wait.
When a process terminates, memory is freed, creating a hole.
This new hole may join with other contiguous holes to create a bigger - 106How to satisfy a request of size n from a list of free holes?First-fit
Best-fit
Worst-fit - 107First-fitAllocate the first hole that is big enough
- 108Best-fit:Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
- 109Worst-fit:Allocate the largest hole; must also search entire list
Produces the largest leftover hole - 110dynamic storageallocation problemconcerns how to satisfy a request of size n from a
list of free holes. - 111Both the first-fit and best-fit strategies for memory allocation suffer fromexternal fragmentation
- 112Statistical analysis of first fit, for instance, reveals that, even with some optimization, given N allocated blocks, another 0.5 N blocks will be lost to fragmentation50-percent rule
- 113External Fragmentationtotal memory space exists to satisfy a request, but it is not contiguous
- 114One can reduce external fragmentation bycompaction
- 115Compaction is possibleonly if relocation is dynamic, and is done at execution time.
- 116Internal FragmentationThe memory allocated may be slightly larger than the size needed by the process.
- 117Virtual memoryinvolves the separation of logical memory as perceived
by users from physical memory - 118virtual address spacethe logical (or virtual) view
of how a process is stored in memory - 119sparseVirtual address spaces that include holes
- 120demand pagingLoading the entire
program into memory results in loading the executable code for all options,
regardless of whether or not an option is ultimately selected by the user. An
alternative strategy is to load pages only as they are needed. - 121what happens if the process tries to access a page that was not brought into memory?page fault
- 122Global replacementprocess selects a replacement frame from the set of all frames; one process can take a frame from another
- 123Local replacementeach process selects from only its own set of allocated frames
- 124LRU:approximation of optimal but difficult to implement
- 125FIFOeasy to implement but suffers from Belady’s anomaly
Información
- Descripción
- Fichas sobre Sin título, creado por wward246 el 08/05/2015.
- Creado por
- wward246
- Visitas
- 0
- Valoración