Weekly Note 6 - Week 11

06 March 2019

Lecture - Tuesday, March 12th.

16-19 in U82

We will cover chapter 8 on deadlocks, and study how to detect and handle them. This chapter will be the primary material for exam topic 5: "Deadlocks".

We will have a small review of the previous lecture, so this time it will be chapters 6 and 7, and we probably sneak in a Kahoot.

I will bring some feedback and review of project 2, and we will do the mid-term evaluation.

Tutorial session

Thursday March 14th. 14-16 in U156 or Friday March 15th. 8-10 in U82

Preparation:

Make a list of 10-15 keywords for a 10 min. presentation with the topic: "Deadlocks"

Prepare at home to discuss:

  1. Consider the trafic deadlock depicted the Figure below
    ex 7.1

    1. Show that the four necessary conditions for deadlock hold in this example.

    2. State a simple rule for avoiding deadlocks in this system.

  2. Assume a multithreaded application uses only reader–writer locks for synchronization. Applying the four necessary conditions for deadlock, is deadlock still possible if multiple reader–writer locks are used?

  3. The program example shown below doesn’t always lead to deadlock. Describe what role the CPU scheduler plays and how it can contribute to deadlock in this program.

/* thread one runs in this function */
void *do_work_one(void *param) {
    pthread_mutex_lock(&first mutex);
    pthread_mutex_lock(&second mutex);
    /**
     * Do some work
     */
    pthread_mutex_unlock(&second mutex);
    pthread_mutex_unlock(&first mutex);
    pthread_exit(0);
}

/* thread two runs in this function */
void *do work two(void *param) {
    pthread_mutex_lock(&second mutex);
    pthread_mutex_lock(&first mutex);
    /**
     * Do some work
     */
    pthread_mutex_unlock(&first mutex);
    pthread_mutex_unlock(&second mutex);
    pthread_exit(0);
}

  1. Compare the circular-wait scheme with the various deadlock-avoidance schemes (like the banker’s algorithm) with respect to the following issues:

    1. Runtime overheads

    2. System throughput

  2. Consider the version of the dining-philosophers problem in which the chopsticks are placed at the center of the table and any two of them can be used by a philosopher. Assume that requests for chopsticks are made one at a time. Describe a simple rule for determining whether a particular request can be satisfied without causing deadlock given the current allocation of chopsticks to philosophers.

  3. Consider again the setting in the preceding question. Assume now that each philosopher requires three chopsticks to eat. Resource requests are still issued one at a time. Describe some simple rules for determining whether a particular request can be satisfied without causing deadlock given the current allocation of chopsticks to philosophers.

  4. Consider the following snapshot of a system:
    ex 7.12
    Using the banker’s algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the processes may complete. Otherwise, illustrate why the state is unsafe.

    1. Available = (0, 3, 0, 1)

    2. Available = (1, 0, 0, 2)

  5. A single-lane bridge connects the two Vermont villages of North Tunbridge and South Tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if both a northbound and a southbound farmer get on the bridge at the same time (Vermont farmers are stubborn and are unable to back up). Using semaphores, design an algorithm that prevents dead- lock. Initially, do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge, and vice versa).

  6. Modify your solution to the previous, so that it is starvation-free.

In class:

Use the first 30 minutes to work on those exercises:

  1. In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?

    1. Increase Available (new resources added)

    2. Decrease Available (resource permanently removed from system)

    3. Increase Max for one process (the process needs or wants more resources than allowed).

    4. Decrease Max for one process (the process decides it does not need that many resources)

    5. Increase the number of processes

    6. Decrease the number of processes

  2. Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

  3. Consider a system consisting of m resources of the same type being shared by n processes. A process can request or release only one resource at a time. Show that the system is deadlock free if the following two conditions hold: i.) The maximum need of each process is between 1 and m resources, and ii.) The sum of all maximum needs is less than m + n

  4. Consider the following snapshot of a system:
    ex 7.13
    Assume the Available vector being (A,B,C,D)=(3,3,2,1). Answer the following questions using the banker’s algorithm:

    1. Illustrate that the system is in a safe state by demonstrating an order in which the processes may complete.

    2. If a request from process P1 arrives for (1, 1, 0, 0), can the request be granted immediately?

    3. If a request from process P4 arrives for (0, 0, 2, 0), can the request be granted immediately?

Then spend the remaining time discussing your list of keywords, and the excercises prepared at home and in class.

  • Chapter 8 in Operating System Concepts, Enhanced eText, 10th Edition

Material (Slides, etc.)