![]() If a process tries to acquire a resource that is held by another process, we can make it possible for the new process to steal the resource. In some situations we can make resources preemptable. Mutual exclusion is a good condition to break if you can, but often you can't. printers: can't print two documents simultaneously!). However, many resources are inherently non-shareable (e.g. Using a lock-free data structure is another way to allow multiple threads to access a data structure simultaneously (without blocking). For example, using a reader/writer lock instead of a mutex can make deadlock less likely (since many readers can share the read lock). In some cases, deadlock can be mitigated by making resources more shareable. We can design a system to avoid deadlock by making any of the 4 conditions impossible. Here each philosopher is holding the chopstick on her left, while trying to acquire the chopstick on her right. Vertices represent either threads (drawn as ovals) or resources (drawn as rectangles).Īn edge from a thread to a resource indicates that the thread is waiting to acquire the resourceĪn edge from a resource to a thread indicates that the thread is holding the resource The graph is drawn according to the following rules: ![]() The circular wait condition can be easily explained using a resource allocation graph. , which is currently waiting on the first thread. No preemption: it is impossible to force a thread to relinquish a resource until it has completed its taskĬircular wait: there is a thread that is currently waiting for another thread, which is currently waiting for another thread. Hold and wait: threads can hold one resource while waiting for another The following conditions are necessary and sufficient for a system to be in deadlock: - mutual exclusion: multiple threads cannot simultaneously hold the same resource At that point, all of the philosophers are waiting for a chopstick, but no chopstick is available, so the system is deadlocked. This solution may exhibit deadlock if all threads pick up their left chopstick before any thread picks up the right chopstick. ![]() Pick up right chopstick (blocking if unavailable) Pick up left chopstick (blocking if unavailable) One possible way to write the pseudocode for each philosopher: ![]() Between each pair of philosophers is a single chopstick a philosopher needs two chopsticks to eat. key terms: optimistic concurrency, rollback, livelockĭeadlock occurs when a system is unable to make progress because threads are blocking each other.Ĭonsider the "dining philosophers" problem: n philosophers are sitting around a table, wanting to eat.mutual exclusion, hold and wait, no preemption, cyclic wait. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |