TUD Logo

TUD Home » ... » Teaching » Distributed Operating Systems » Parallel Architectures

Operating Systems

Exercise: Parallel Architectures

In the tutorial, all solutions will be presented by students. Please be prepared for all questions as the exercise will focus on discussion, not on understanding the question and gathering the knowledge. Some challenging questions are usually a lot more difficult and require knowledge that was not presented in the lecture.

1. Lock-free

Implement double-address compare-and-swap with the help of compare-and-swap.

2. Cache-Coherency and Locks

The cache-coherency protocol is sometimes crucial for the scaling of a particular lock implementation. The reason is, that some lock implementations produce too many bus messages and thereby slow down the execution of the processor.

2.1. Test-and-Set Locks

The Test-and-Set locks presented within the lecture do not scale well since they perform exclusive write operations to the lock variable even if the lock is currently taken by a different thread.

A possible implementation of a simple Test-and-Set locks can be done as follows:

class TSLock {
   private:
    unsigned int _lock

   public:
    TSLock() : _lock(0) {}

    void lock() {
        while (test_and_set(_lock) == 1) {}
    }

    void unlock() {
        _lock = 0;
    }
};

Check the scalability problem of the Test-and-Set locks by completing the below-mentioned table.

The first column of the table states which CPU is executing an instruction at the moment. The second column contains the executed operation. The state of the lock variable should be written in column three. The remaining four columns are supposed to contain the state of the cache line containing the lock variable on the corresponding core according to the MESI cache coherency protocol.

CPU Operation Lock P1 P2 P3 P4
0 I I I I
1 lock (T&S) 1 M I I I
2 wait (T&S) 1 I M I I
4 wait (T&S) 1 I I I M
2 wait (T&S)
3 wait (T&S)
4 wait (T&S)
3 wait (T&S)
1 unlock
3 lock (T&S)
2 wait (T&S)
4 wait (T&S)
3 unlock
2 lock (T&S)
4 wait (T&S)
4 wait (T&S)
2 unlock

2.2. Test-Test-and-Set Locks

Within the lecture, an extension of the simple Test-and-Set lock was presented. This new lock implementation contains an additional Test-operation before the actual taking of the lock is performed.

A possible implementation of a Test-Test-and-Set lock could look as follows:

class TTSLock {
   private:
    unsigned int _lock

   public:
    TTSLock() : _lock(0) {}

    void lock() {
        while (true) {
            while (_lock == 1) {}

            if (test_and_set(_lock) == 0)
                break;
         }
    }

    void unlock() {
        _lock = 0;
    }
};

Repeat exercise 2.1 and use a Test-Test-and-Set lock instead of only a Test-and-Set Lock. Keep in mind that the Test-operation of the lock is only a read access and not a write access.

CPU Operation Lock P1 P2 P3 P4
0 I I I I
1 test 0 E I I I
2 test 0 S S I I
1 lock (T&S) 1 M I I I
2 lock (T&S)
3 wait
4 wait
2 wait
3 wait
4 wait
1 unlock
3 test
3 lock (T&S)
2 wait
4 wait
3 unlock
2 test
4 test
2 lock (T&S)
4 lock (T&S)
4 wait
4 wait
2 unlock

2.3. False Sharing

Within the last exercise session there was one exercise about false sharing. Discuss the consequences if two independent lock variables l1 and l2 share the same cache line.

3. Scalable Reader-Writer Locks

Fair reader-writer locks protect a critical section such that multiple readers can enter the critical section concurrently, provided no writer is attempting to enter or holding the lock. Thereby at most one writer may be in the critical section at any point in time, provided no readers are in the critical section.

3.1. Reader-Writer Lock Implementation

Implement a reader writer lock using the atomic read-modify-write instructions presented in the lecture. Make sure the lock is fair, that is, both readers and writers get the lock after a bounded time.

3.2. Fair Fast Scalable Reader-Writer Lock

In their paper "A Fair Fast Scalable Reader-Writer Lock", Krieger et al. present a scalable reader-writer lock implementation based on the MCS lock discussed in the lecture.

  1. Search for typos in the readerUnlock function and correct them. Justify why there is a bug. If you do not spot any errors, justify why the function is correct.
  2. Describe how the readerUnlock function works.
  3. Challenging Question: The reader-writer lock implementation is fair, though inherently unfair spin-lock implementations are used in the readerUnlock function. Why?

Materials

Last modified: 16th Jun 2016, 2.39 PM
Author: Dr.-Ing. Marcus Völp

Contact
Dr.-Ing.
Carsten Weinhold

Phone: 463 38056
Fax: 463 38284
e-mail contact form

Regulations
  • ModuleModules: INF-BI-1, INF-BAS4, INF-VERT4, DSE-E3
  • Credits6 Credit Points
  • 2/1/0 = 3 SWS
Time and Place

This course is not being offered in this term.