GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Untitled

wward246 English 125 cards

Cards in this deck (125)

  1. 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.
  2. 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
  3. 3To guard against the race conditionwe need to ensure that only one process at a time can be manipulating
    the variable counter.
  4. 4critical sectionwhich the process may be changing common variables, updating a table,
    writing a file, and so on.
  5. 5The critical-section problemIt is to design a
    protocol that the processes can use to cooperate.
  6. 6The section of code (critical-section) implementing this request is the______-entry section
  7. 7The critical section may be followed by an (a)_____Exit section
  8. 8The remaining code is the___remainder section
  9. 9A solution to the critical-section problem must satisfy the following three requirements:Mutual exclusion
    Progress
    Bounded waiting
  10. 10Mutual exclusionIf process Pi is executing in its critical section, then no
    other processes can be executing in their critical sections
  11. 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.
  12. 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.
  13. 13Two general approaches are used to handle critical sections in operating systems:preemptive kernels and nonpreemptive kernels
  14. 14preemptive kernelallows a process to be preempted while it is running in kernel mode
  15. 15nonpreemptive kerneldoes not allow a process running in kernel mode to be
    preempted;
  16. 16Peterson’s solution requires the two processes to share two data items:int turn;
    boolean flag[2];
  17. 17variable turn indicates...whose turn it is to enter its critical section. Then, process Pi is allowed to execute in its critical section.
  18. 18The flag array is used...to indicate if a process is ready to enter its critical section.
  19. 19lockingprotecting critical regions through
    the use of locks. As we shall see, the designs of such locks can be quite
    sophisticated.
  20. 20mutex lockto protect critical regions and thus prevent race conditions.
  21. 21The two functions of a mutex lockacquire() and release()
  22. 22The definition of acquire() is as follows:acquire() {
    while (!available)
    ; /* busy wait */
    available = false;;
    }
  23. 23definition of release() is as follows:release() {
    available = true;
    }
  24. 24definition of the test and set()boolean test and set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
    }
  25. 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;
    }
  26. 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);
  27. 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.
  28. 28Does binary semaphores behave similarly to mutex locks?Yes.
  29. 29What is the alternative to mutual exclusion on systems that do not provide mutex locksbinary semaphore
  30. 30A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations:wait() and signal().
  31. 31definition of wait()wait(S) {
    while (S <= 0)
    ; // busy wait
    S--;
    }
  32. 32The definition of signal() is as follows:signal(S) {
    S++;
    }
  33. 33block() operationsuspends the process that invokes it.
  34. 34wakeup()resumes the execution of a blocked process
  35. 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.
  36. 36Another problem related to deadlocks is____or____indefinite blocking, starvation
  37. 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);
  38. 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);
  39. 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.
  40. 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);
  41. 41The structure of a writer process.do {
    wait(rw mutex);
    . . .
    /* writing is performed */
    . . .
    signal(rw mutex);
    } while (true);
  42. 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.
  43. 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);
  44. 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.
  45. 45monitor typean ADT that includes a set of programmerdefined
    operations that are provided with mutual exclusion within the monitor.
  46. 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.
  47. 47Syntax of a monitor.monitor monitor name
    {
    /* shared variable declarations */
    function P1 ( . . . ) {
    . . .
    }
    function P2 ( . . . ) {
    . . .
    }
    .
    .
    .
    function Pn ( . . . ) {
    . . .
    }
    initialization code ( . . . ) {
    . . .
    }
    }
  48. 48The only operations that can be invoked on a condition variablewait()
    and signal()
  49. 49Signal and waitP either waits until Q leaves the monitor or waits for
    another condition.
  50. 50Signal and continueQ either waits until P leaves the monitor or waits
    for another condition.
  51. 51deadlocka
    waiting process is never again able to change state, because the resources it
    has requested are held by other waiting processes
  52. 52A processes never finish executing, and system resources are tied up, preventing other jobs fromstartingdeadlock
  53. 53A deadlock situation can arise if the following four conditions hold simultaneously in a system:Mutual exclusion.
    Hold and wait.
    No preemption.
    Circular wait.
  54. 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.
  55. 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.
  56. 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.
  57. 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.
  58. 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.
  59. 59Deadlock Prevention(Mutual Exclusion)– not required for sharable resources; must hold for non-sharable resources
  60. 60Can a mutex lock be simultaneously shared by several processes.No, mutex lock cannot
    be simultaneously shared by several processes.
  61. 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.
  62. 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.
  63. 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.
  64. 64Safe Statethe system can allocate resources to each process (up to its
    maximum) in some order and still avoid a deadlock.
  65. 65Is a safe state a deadlocked state?No, deadlocked state is
    an unsafe state.
  66. 66Un safe state may lead to a _____deadlcok
  67. 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.
  68. 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.
  69. 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
  70. 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.
  71. 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 .
  72. 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 .
  73. 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].
  74. 74Resource-Request AlgorithmAvailable = Available–Requesti ;
    Allocationi = Allocationi + Requesti ;
    Needi = Needi –Requesti ;
  75. 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.
  76. 76Avoidance Algorithms for Single instance of a resource type:Use a resource-allocation graph
  77. 77Avoidance Algorithms for Multiple instances of a resource type:Use the banker’s algorithm
  78. 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.
  79. 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
  80. 80Ensure that the system will never enter a deadlock stateDeadlock prevention
    Deadlock avoidance
  81. 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.
  82. 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.
  83. 83Compile timeIf memory location known a priori, absolute code can be generated; must recompile code if starting location changes
  84. 84Load timecompiler must generate relocatable code if memory location is not known at compile time.
  85. 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)
  86. 86logical address spaceThe set of all
    logical addresses generated by a program
  87. 87physical address space.The set
    of all physical addresses corresponding to particular logical addresses
  88. 88memory-management unit (MMU).The run-time mapping from virtual to physical addresses is done by a
    hardware device
  89. 89Dynamically linked librariesystem libraries that are linked to user
    programs when the programs are run
  90. 90static linkingsystem libraries are treated
    like any other object module and are combined by the loader into the binary
    program image.
  91. 91Do Logical and physical addresses have the same compile-time and load-time address-binding schemes?Yes
  92. 92Do Logical (virtual) and physical addresses same execution-time address-binding schemeNo, Logical (virtual) and physical addresses differ in execution-time address-binding scheme
  93. 93Does the user program deals with logical addresses?Yes.
  94. 94user program deals with real physical addressesNo, it never sees the real physical addresses
  95. 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.
  96. 96Backing store– fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
  97. 97Major part of swap time is ____Transfer Time
  98. 98Transfer timedirectly proportional to the amount of memory swapped.
  99. 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
  100. 100Does Android terminates apps if low free memory?Yes, but first writes application state to flash for fast restart
  101. 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
  102. 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
  103. 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
  104. 104Given what we currently know about memory, what must we do during a context switch?Allocate memory to the switching process
  105. 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
  106. 106How to satisfy a request of size n from a list of free holes?First-fit
    Best-fit
    Worst-fit
  107. 107First-fitAllocate the first hole that is big enough
  108. 108Best-fit:Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
  109. 109Worst-fit:Allocate the largest hole; must also search entire list
    Produces the largest leftover hole
  110. 110dynamic storageallocation problemconcerns how to satisfy a request of size n from a
    list of free holes.
  111. 111Both the first-fit and best-fit strategies for memory allocation suffer fromexternal fragmentation
  112. 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
  113. 113External Fragmentationtotal memory space exists to satisfy a request, but it is not contiguous
  114. 114One can reduce external fragmentation bycompaction
  115. 115Compaction is possibleonly if relocation is dynamic, and is done at execution time.
  116. 116Internal FragmentationThe memory allocated may be slightly larger than the size needed by the process.
  117. 117Virtual memoryinvolves the separation of logical memory as perceived
    by users from physical memory
  118. 118virtual address spacethe logical (or virtual) view
    of how a process is stored in memory
  119. 119sparseVirtual address spaces that include holes
  120. 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.
  121. 121what happens if the process tries to access a page that was not brought into memory?page fault
  122. 122Global replacementprocess selects a replacement frame from the set of all frames; one process can take a frame from another
  123. 123Local replacementeach process selects from only its own set of allocated frames
  124. 124LRU:approximation of optimal but difficult to implement
  125. 125FIFOeasy to implement but suffers from Belady’s anomaly

Information

Description
Flashcards on Untitled, created by wward246 on 08/05/2015.
Created by
wward246
Views
0
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?