This is not the current version of the class.

Problem set 6 hints

This page has some hints about completing Problem Set 6.

Thread IDs and recursive mutexes

Each thread in a process has an ID that’s distinct from all other threads’ IDs. Thread IDs have type std::thread::id, which is usually, but not always, a synonym for a kind of integer; you can compare thread IDs for equality, and you can obtain the current thread’s ID by calling std::this_thread::get_id().

Thread IDs are very useful when implementing recursive mutexes, and can be useful for this pset.

EXERCISE. Implement the try_lock, lock, and unlock functions for this recursive mutex implementation.

struct my_recursive_mutex {
    std::mutex m;            // mutex protecting my_recursive_mutex’s state
    unsigned locked = 0;     // 0 means unlocked, >0 means locked by `owner`
    std::thread::id owner;   // if `locked>0`, ID of owning thread
    std::condition_variable_any cv;  // used to wake up waiting threads

    bool try_lock() {
        ???
    }
    void lock() {
        ???
    }
    void unlock() {
        ???
    }
};

Given my_recursive_mutex rm:

  • If rm.locked == 0, then rm is not locked by any thread.
  • If rm.locked > 0, then rm has been locked that number of times by the thread with ID rm.owner.
    • So if rm.locked > 0 && rm.owner == std::this_thread::get_id(), then the mutex is locked by the current thread.
  • One must lock the internal mutex rm.m before examining rm.locked or rm.owner.

First try to write try_lock. If you get stuck, peek below.

Once you understand try_lock, go for lock and unlock.

may_overlap_with_other_lock

Phase 2 of the problem set asks you to implement finer-grained locking for file range locks. There are many ways to program this, but consider implementing a predicate function called may_overlap_with_other_lock:

// Return true if some other thread (not `std::this_thread::get_id()`)
// has a lock on a range of `f`, and that range might overlap with the
// range [start, start + len).
//
// This function may return true when another thread has a range lock on
// `f` that *doesn’t* overlap with [start, start + len). That is, it can
// be conservative, rather than precise. However, it *must return false*
// if all range locks on `f` are held by *this* thread.
//
// The caller must have locked all mutexes required to examine `f`’s
// range lock state.

bool may_overlap_with_other_lock(io61_file* f, off_t start, off_t len) {
    ...
}

This predicate will let you separate two concerns. You can write versions of may_overlap_with_other_lock for many lock granularities and data structure designs, ranging from coarse-grained locking to the finest-grained locking possible; and you can make the result work with an io61_file containing just one mutex and one condition variable (though you may use more).

For instance, this definition of may_overlap_with_other_lock implements coarse-grained locking.

struct io61_file { ...
    std::mutex m;
    std::condition_variable_any cv;
    unsigned locked = 0;
    std::thread::id owner;
};

bool may_overlap_with_other_lock(io61_file* f, off_t /*start*/, off_t /*len*/) {
    return f->locked > 0 && f->owner != std::this_thread::get_id();
}

This definition of may_overlap_with_other_lock is a bit more fine-grained. It divides the file into three regions—offsets [0, 48), offsets [48, 1024), and offsets [1024, ∞)—that can be locked separately.

struct io61_file { ...
    std::mutex m;
    std::condition_variable_any cv;
    struct region_lock {
        unsigned locked = 0;
        std::thread::id owner;
    } reg[3];
};

static int file_region(off_t off) {
    if (off < 48) {
        return 0;
    } else if (off < 1024) {
        return 1;
    } else {
        return 2;
    }
}

bool may_overlap_with_other_lock(io61_file* f, off_t start, off_t len) {
    int rstart = file_region(start), rend = file_region(start + len - 1);
    for (int ri = rstart; ri <= rend; ++ri) {
        if (f->reg[ri].locked > 0 && f->reg[ri].owner != std::this_thread::get_id()) {
            return true;
        }
    }
    return false;
}

Thanks to Lucas Szwarcberg for noticing a bug!

The code for io61_try_lock, io61_lock, and io61_unlock will look pretty similar for any version of may_overlap_with_other_lock!

int io61_try_lock(io61_file* f, off_t start, off_t len, int locktype) {
    if (len == 0) {
        return 0;
    }
    std::unique_lock guard(f->m);
    if (may_overlap_with_other_lock(f, start, len)) {
        return -1;
    }
    /* YOUR CODE HERE: account for new lock (depends on lock design) */
    return 0;
}

int io61_lock(io61_file* f, off_t start, off_t len, int locktype) {
    if (len == 0) {
        return 0;
    }
    std::unique_lock guard(f->m);
    while (may_overlap_with_other_lock(f, start, len)) {
        f->cv.wait(guard);
    }
    /* YOUR CODE HERE: account for new lock (depends on lock design) */
    return 0;
}

int io61_unlock(io61_file* f, off_t start, off_t len) {
    if (len == 0) {
        return 0;
    }
    std::unique_lock guard(f->m);
    /* YOUR CODE HERE: account for unlock (depends on lock design) */
    f->cv.notify_all(); // spurious wakeup possible, prob no big deal
    return 0;
}

EXERCISE. How would you implement /* account for new lock */ (in io61_try_lock and io61_lock) and /* account for unlock */ (in io61_unlock) for the coarse-grained version?

EXERCISE. How would you implement /* account for new lock */ and /* account for unlock */ for the three-region version?