使用Linux的Mutex，实现一个FCFS Error-Checking的读写锁。

Requirement

In this lab, you are asked to implement a First-Come-First-Serve (FCFS) Error-Checking Read/Write Lock using pthread mutexes and condition variables.

Overview

An RW lock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.

By a First-Come First-Server (FCFS) Read/Write lock, we mean that when a writer thread (a thread who wants a write lock) is blocked because one or more threads currently hold read locks, new requests for read locks should also be blocked and be served only after the writer thread has obtained and released the write lock.

By an Error-Checking Read/Write lock, we mean that your implementation should return an error code when a thread who tries to obtain a lock already has read or write lock, and a thread who calls read or write unlock does not hold the corresponding type of lock. When such an error situation occurs, your thread should return without having to wait for any other thread calling unlock.

In your implementation, you are only allowed to use pthread mutexes and pthread condition variables for synchronization primitives. Usage of semaphores, read/write locks, and other synchronization primitives is not allowed.

Goal

You should implement the following C++ class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class RWLock {

Public:
  static const int ERROR_ALREADY_HOLDING_READ_LOCK = 1;
  static const int ERROR_ALREADY_HOLDING_WRITE_LOCK = 2;
  static const int ERROR_NOT_HOLDING_READ_LOCK = 3;
  static const int ERROR_NOT_HOLDING_WRITE_LOCK = 4;
  static const int LOCK_BUSY = 5;

  /* Initialize the RWLock object. */
  RWLock();

  /* The calling thread acquires the read lock if a writer does not
     hold the lock and there is no thread blocked on the lock.
     Return 0 when the calling thread has obtained a read lock.
     If the calling thread already holds read (resp., write) lock on
     this RWLock, it should indicate this error by returning 1
     (resp., 2).  In the error case, the calling thread should not be
     blocked to wait for other threads calling lock unlock.  */
  int read_lock();

  /* If read_lock would have succeeded, obtain the read lock and
     return 0. Otherwise, if read_lock would have returned an error
     code, return the same error code.  If read_lock() would have
     been blocked to wait for some other thread to call unlock,
     return 5.  */
  int try_read_lock();

  /* If the calling thread does not hold read lock, return 3.
     Otherwise, release the read lock and return 0. */
  int read_unlock();

  /* If the calling thread already holds read (or write) lock,
     return 1 (or 2) without waiting for other threads to call
     unlock.  Otherwise, if no other thread holds either read or
     write lock, acquire the write lock and return 0. Otherwise, the
     thread shall be blocked until it can acquire the lock.  */
  int write_lock();

  /* Behave as write_lock() if write_lock() would have returned
     without being blocked to wait for another thread to call unlock.
     Otherwise, return 5 to show that the lock is busy. */
  int try_write_lock();

  /* If the calling thread does not hold write lock, return 4.
     Otherwise, release the write lock and return 0. */
  int write_unlock();

  /* If the calling thread does not hold write lock, return 4.
     Otherwise, release the write lock and obtain a read lock for the
     current thread, and return 0. */
  int write_to_read();
}

Grading

Ten test cases are provided with the lab. Expected output are also provided. Your implementation should generate identical output as the given output on corresponding test cases. Your submission receives 10% of lab 4 grade for each test case that your implementation is able to provide identical output. No new test cases will be used in grading.

Provided Files.

You are provided with the following files:

• src/Makefile Do not edit.
• src/TestRWLock.cc Do not edit. Code for testing implementation of RWLock.
• src/script.h Do not edit. Script of last test case.
• src/RWLock.h Edit to add private fields and methods.
• src/RWLock.cc Edit to replace the current trivial implementation.
• test/out01.txt to test/out10.txt Expected output for the 10 test cases, generated by running TestRWLock against the reference implementation.

Generate executable lab4. Run lab4 n > tmp.txt, where n is from 1 to 10. Then run diff tmp.txt outn.txt to see whether your output is identical as desired output.

APIs to Use

You are allowed to use pthread_mutex and pthread_cond_var. No other synchronization primitives are allowed. If you want to use add any header files other than the ones already included in the source file, please check with the instructor first.

Recommended Steps to Take

Understand the implementation and the questions. This implementation of RWLock there uses two mutexes m1, m2, and a semaphore sem. The mutex m2 ensures that accessing internal data of the lock is atomic. The mutex m1 is used to enable a waiting writer thread to block all later reader threads (so as to achieve FCFS). The semaphore is used to block out writers when readers are holding the lock. Note that this implementation uses a semaphore (which is not allowed in this lab), is not error checking, and does not support all required functions.

Second, implement your RWLock using the code. This should suffice to pass test cases 1 to 4. After this is done, replace the use of semaphore with a condition variable, and make sure that you can pass test cases 1 to 4.

Third, add the logic to handle error checking. To do this, you need to use the following pthread APIs.

1

pthread_t pthread_self(void);

returns the ID of the calling thread.

1

int pthread_equal(pthread_t t1, pthread_t t2);

If the two thread IDs are equal, pthread_equal() returns anonzero value; otherwise, it returns 0.

You need to remember which thread(s) are holding the lock, and perform checks inside each function. Note that you should always use pthread_equal to compare two thread ids. It is required that if an error occurs, the function should return without waiting for another thread to call unlock. This means that while it is okay to block on the mutex m2 while performing error checks, your implementation should not block on m1 or the condition variable (semaphore in the sample implementation). Whenever m2 is not available, it means that another thread is in critical section, and given a little bit more time, m2 will become available. However, waiting on m1 or the condition variable (or semaphore) means waiting for some other threads call certain unlock methods, which may never happen.

Hint. It is okay to separate the logic for error checking and the logic to obtain a lock so that other threads get interleaved between the two steps. The error status depends only on the current thread and cannot be changed by other threads actions.

After adding error checking logic, you should be able to pass test case 5 and 6.

Fourth, add the logic for handling try_read_lock(), try_write_lock(), and write_to_read().