Fichas
Threads, sync and deadlock
Fichas del conjunto (37)
- 1What is the difference between processes and threads?Threads (of the same process) run in a shared memory space, while processes run in separate memory spaces.
Thread is a path of execution within a process. - 2Why is it "more expensive" to create a new process compared to creating a new thread?For a process you have to copy the PCB, create memory space etc.
Threads dont require a separate adress space, share recourses with the process they belong to - 3Why do concurrent accesses to shared memory need to be synchronized?To stop race condition. Memory could be overwritten in an unwanted way, corrupting data
- 4What is meant by a race condition (aka data race)?When one parallell running threads needs data from another. It becomes a bug when these uncontrolled events do not happen in the order the programmering intended.
- 5What are the problems with Petersson's solution?1. Not guaranteed to work on modern day architecture
2. Only works for 2 concurrent task - 6Name two atomic instructions that can be used to implement mutex locks.TestAndSet()
Swap() - 7What is meant by busy waiting?Looping in the entry code, waiting to enter the critical section
- 8How can spin locks be constructed using swap()?In swap you have a lock (shared) and one local key. If we have the key, test the lock by
Swap(&lock, &key). If lock == FALSE
(CS not locked) we’re allowed to enter
CS and key is set to FALSE and lock
is set to TRUE locking the CS. - 9What is a semaphore?A counter manipulated by operations like signal and wait to control access to a common resource by multiple processes.
- 10What is a mutex lock?Binary semaphore. Restricted to the values 0 and 1 (or locked/unlocked)
- 11What operations can be performed on a semaphore and how do these operations work?Signal() - increments the counter
Wait() - if counter > 0, decrement it! Else wait until it is > 0, then decrement. - 12What is the difference between a mutex lock and a semaphore?Mutex - one key to a toilet. One person can have it at a time, one can use the toilet.
Semaphore - Number of free identical keys to the toilet. Used to restrict the amount of simultaneous users. - 13How can busy waiting be avoided?Each semaphore can have a list of blocked processes where they "sleep" instead of busy wait. They can be woken up by a signal (wakeup())
- 14What is a monitor?A thread safe class, object etc. that uses mutual exclusion to safely allow access to a method or variable by more than one thread.
Important: its methods are executed with mutual exclusion - 15What problem with monitors is addressed by condition variables?Threads may need to wait until some condition holds true. This condition cannot happen if the thread is occupying the monitor.
Solution: If thread is waiting for a condition to become true it can enter a queue of threads (CV) -> leaving the monitor, not occupying it -> other threads may enter and execute and signal when the condition has become true - 16What is meant by starvation?When a process is permanently denied necessary resources to process its work
Bounded buffer - 17How can semaphores be used to synchronize access to a bounded buffer?By making three semaphores, one the empty and one for the filled slots, we can keep track of how
many slots are used and whether we're trying to remove from en empty buffer, or insert into a full
buffer. One to keep track of the indexes - 18When solving the Dining philosophers problem, how can deadlocks be avoided?1. Monitor solution - by monitoring the states and ensuring that no two neighbors are eating simultaneously
2. If a philosopher takes one chopstick, but not the other -> put both back! - 19Starvation be avoided?For example by associating every thread with a priority that increases the longer it waits.
- 20What is meant by a deadlock?When each member of a group of actions, is waiting for some other member to release a lock
- 21What are the four necessary conditions for deadlocks to occur?i. Mutual exclusion - only one task at a time can use a resource
ii. Hold and wait - a task holding at least one resource is waiting to acquire additional resources held by other tasks
iii. No preemption - a resource can be released only voluntarily by the task holding it, after that task has completed its task.
iv. Circular wait - The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list - 22What is the difference between deadlock prevention and deadlock avoidance?i. Prevention - ensure that at least one of the four necessary conditions for deadlock can never hold
ii. Avoidence - The system dynamically considers every request and decides whether it is safe to grant it at this point - 23Define a-priori information and describe how it is used in deadlock avoidance.i. Latin for "from the earlier"
ii. Knowledge independent of experience - information given to us before we start
iii. Each process declares a maximum number of resources that it may need (e.g memory/disk pages) - 24What are the benefits of threads?Responsiveness: Allows a program to run even if a part of it is blocking of performing a lengthy operation
Resource sharing: Several threads in the same adress space
Economy: allocation memory & resources is costly! - 25Advantages of Kernel threads- The kernel has knowledge of all threads
- Scheduler may decide to give more CPU time to a process having a large nr of threads - 26Disadvantages of Kernel threads- Significant overhead
- Slow and inefficient compared to user-level threads - 27User-level threadsAre managed by a user-level library. There is a lack of cooperation between user level threads and the kernel, it is a known disadvantage. In this case, the kernel may not favor a process that has many threads. User level threads are typically fast. Creating threads, switching between threads and synchronizing threads only needs a procedure call. They are a good choice for non blocking tasks otherwise the entire process will block if any of the threads blocks.
- 28Advantage of User-level thread- typically fast & efficient
- Creating threads, switching between threads and synchronizing threads only needs a procedure call.
- They are a good choice for non blocking tasks otherwise the entire process will block if any of the threads blocks. - 29Disadvantage of user-level threads- Can make poor decisions;
✓ blocking a process due to a blocking thread even though the process
has other threads that can run
✓ A process as a whole gets one time slice irrespective of whether the process has 1 or 1000 threads
-> to overcome this it might need communication with the kernel - 30Many-To-One Thread ModelUser level threads follow this model. This means multiple threads managed by a library in user space but the kernel is only aware of a single thread of the process owning these threads. For example, If the currently running thread blocks for input then all other threads are blocked. For the same reason, the kernel is not going to be able to distribute the other threads on other CPUs if the system has more than one.
- 31One-To-One ModelKernel level threads
follow the one to one model. Process threads are managed by the kernel so there are separate kernel threads for each process thread. Since the kernel is aware of all threads, if one thread blocks it does not affect the others - 32Give an example of a Deadlock due to circular waitPhilosophers problem: If all philosophers holds their right chopstick and all waits for their left chopstick to become available
- 33Give example of resources a process might need• CPU cycles
• Memory space • I/O devices
• Semaphores - 34Deadlock PreventionNo preemption; If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released:
- Make circular wait impossible by impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration. - 35Deadlock avoidanceRequires some
additional a priori information.
-> Simplest model: each process declare the maximum number of resources of each type that it may need.
-> The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. - 36What is meant by "safe state" in deadlock avoidance?* If a system is in safe state ⇒ no deadlocks. When a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state.
* System is in safe state if there exists a sequence of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < i. - 37In the Banker´s algorithm, what a priori information must be given for the algorithm to work?-The number of available
instances of each resource.
-Each process must a priori claim
maximum use of each resource.
-Also give one point for number of
processes.
Información
- Descripción
- Operating systems Fichas sobre Threads, sync and deadlock, creado por Emma Tysk el 12/03/2017.
- Creado por
- Emma Tysk · mar 2017
- Actualizado
- 14 mar 2017
- Visitas
- 69
- Valoración