Research the synchronize mechanism implement in Linux
- [
include/linux
]
In mutex.h
line 53
struct mutex {
atomic_long_t owner;
spinlock_t wait_lock;
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
struct optimistic_spin_queue osq; /* Spinner MCS lock */
#endif
struct list_head wait_list;
#ifdef CONFIG_DEBUG_MUTEXES
void *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
};
Acquire the mutex (in mutex.c
line 252)
void __sched mutex_lock(struct mutex *lock)
{
might_sleep();
if (!__mutex_trylock_fast(lock))
__mutex_lock_slowpath(lock);
}
static int __sched
__mutex_lock(struct mutex *lock, long state, unsigned int subclass,
struct lockdep_map *nest_lock, unsigned long ip)
{
return __mutex_lock_common(lock, state, subclass, nest_lock, ip, NULL, false);
}
static int __sched
__ww_mutex_lock(struct mutex *lock, long state, unsigned int subclass,
struct lockdep_map *nest_lock, unsigned long ip,
struct ww_acquire_ctx *ww_ctx)
{
return __mutex_lock_common(lock, state, subclass, nest_lock, ip, ww_ctx, true);
}
Every called the __mutex_lock_common
function (in mutex.c
line 899)
- rwlock
- Condition
- spinlock
- Hardware related lock...
Linux made a lots of different locks for its kernel. Typically, it classified into software and hardware usage.
But for user/programmer, I found in the most case they use Pthread library.
Read the following code, understand current Nachos synchronize mechanism
code/threads/synch.h
code/threads/synch.cc
code/threads/synchlist.h
code/threads/synchlist.cc
Nachos has implemented Semaphore in threads/synch.h
class Semaphore {
public:
void P(); // these are the only operations on a semaphore
void V(); // they are both *atomic*
private:
int value; // semaphore value, always >= 0
List *queue; // threads waiting in P() for the value to be > 0
};
Parameter
int value
: thresholdList *queue
: threads which are waiting for this semaphore
(Atomic) Operation
P()
- When
value
== 0- Put current Thread into waiting queue
- Sleep current Thread and switch to other Thread
- When
value
> 0value--
- When
V()
- If there is a Thread waiting for this semaphore
- Pick one up and set to READY state
value++
- If there is a Thread waiting for this semaphore
Either use primitive sleep and wakeup (notice to disable the system interrupt), or use Semaphore as the only primitive (then you won't need to handle interrupt by yourself)
Disable interrupt in the beginning and re-enable it in the end to make the routine atomic or make it become primitive.
// Any implementation of a synchronization routine needs some
// primitive atomic operation. We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts. While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
Pthreads offers two synchronization mechanism: mutex and condition variable
- POSIX Threads Programming
Some of the Pthreads calls relating to mutexes
Pthread_mutex_init
: Create a mutexPthread_mutex_destroy
: Destroy an existing mutexPthread_mutex_lock
: Acquire a lock or blockPthread_mutex_trylock
: Acquire a lock or failPthread_mutex_unlock
: Release a lock
Some of the Pthreads calls relating to condition variables
Pthread_cond_init
: Create a condition variablePthread_cond_destroy
: Destroy a condition variablePthread_cond_wait
(primary): Block waiting for a signal- Using a WHILE loop instead of an IF statement to check the waited for condition can help deal with several potential problems
- If several threads are waiting for the same wake up signal, they will take turns acquiring the mutex, and any one of them can then modify the condition they all waited for.
- If the thread received the signal in error due to a program bug.
- The Pthreads library is permitted to issue spurious wake ups to a waiting thread without violating the standard.
- Using a WHILE loop instead of an IF statement to check the waited for condition can help deal with several potential problems
Pthread_cond_signal
(primary): Signal another thread and wake it upPthread_cond_broadcast
: Signal multiple threads and wake all of them- Called when there are multiple threads potentially all blocked and waiting for the same signal
Example
The Binary Semaphore with Ownership Concept!
Nachos has a initial template for Lock. And I use Semaphore
to implement it.
It will be much easier because I don't have to handle interrupt and sleeping thread problem.
I was tried to implement Lock from scratch. But I found I was making "spinlock" which may lead deadlock or starvation maybe. So I'm using semaphore to avoid sleepgin thread problem...
I've created two private variable.
class Lock {
private:
Thread* holderThread; // Thread which is holding this lock
Semaphore* semaphore; // Use semaphore to implement lock
};
And the most important thing is implementing Lock using Semaphore with the value of 1! (binary semaphore)
//----------------------------------------------------------------------
// Lock::Lock
// Initialize a lock, so that it can be used for synchronization.
//
// "debugName" is an arbitrary name, useful for debugging.
//----------------------------------------------------------------------
Lock::Lock(char* debugName)
{
name = debugName;
semaphore = new Semaphore("Lock", 1);
}
Assign the holderThread
to currentThread
when the currentThread
has got the Lock successfully.
//----------------------------------------------------------------------
// Lock::Acquire
// Acquire Mutex Lock.
// * When lock is BUSY, enter SLEEP state. (if loop and wait => spinlock)
// * When lock is FREE, current Thread get lock and keep running.
//----------------------------------------------------------------------
void
Lock::Acquire()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
DEBUG('s', "Lock \"%s\" Acquired by Thread \"%s\"\n", name, currentThread->getName());
semaphore->P();
holderThread = currentThread;
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
Release the Lock only when the currentThread
is the owner itself.
This is the biggest difference between a mutex lock and a binary semaphore! Because lock has ownership concept.
(Note: Ownership means that mutex can only be "incremented" back (set to 1) by the same process that "decremented" it (set to 0), and all other tasks wait until mutex is available for decrement (effectively meaning that resource is available), which ensures mutual exclusivity and avoids deadlock.)
//----------------------------------------------------------------------
// Lock::Release
// Release Mutex Lock.
// (Note: Only the Thread which own this lock can release lock)
// Set lock status to FREE. If any other Thread is waiting this lock,
// wake one of them up, enter READY state.
//----------------------------------------------------------------------
void
Lock::Release()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
DEBUG('s', "Lock \"%s\" Released by Thread \"%s\"\n", name, currentThread->getName());
// make sure the owner of this lock is currentThread
ASSERT(this->isHeldByCurrentThread());
holderThread = NULL;
semaphore->V();
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
Other trivial code implementation just checkout threads/synch.cc
.
And the test of Lock
I'll using Exercise 4 as an example.
Condition variables should be used as a place to wait and be notified. They are not the condition itself and they are not events. The condition is contained in the surrounding programming logic.
Nachos has a initial template for Condition. And I use Lock
(Exercise 3-1) to implement it.
I've create a waiting queue as a private variable.
class Condition {
private:
List* waitQueue; // Waiting queue for the Thread blocked by this condition
};
Notes that all the condition operation has a input of conditionLock
. That's because the Thread which is using the condition must have held the lock.
In addition, when calling Condition::Wait()
, the lock must be locked. And wait must be wrapped with a loop.
BUT in Nachos, warp wait in a loop will CAUSE SERIOUS PROBLEM that
Condition::Wait()
will sleep/block the threads again right after they have been waken up. So don't do that (i.e. in Barrier).
//----------------------------------------------------------------------
// Condition::Wait
// Wait blocks the calling thread until the specified condition is signalled.
// This routine should be called while mutex is locked, and it will
// automatically release the mutex while it waits.
// After signal is received and thread is awakened,
// mutex will be automatically locked for use by the thread.
// The programmer is then responsible for unlocking mutex when the thread
// is finished with it.
//
// "conditionLock" is the lock protecting the use of this condition
//----------------------------------------------------------------------
void
Condition::Wait(Lock* conditionLock)
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
// conditionLock must be held by the currentThread
ASSERT(conditionLock->isHeldByCurrentThread())
// conditionLock must be locked
ASSERT(conditionLock->isLocked());
// 1. Release the lock while it waits
conditionLock->Release();
// 2. Append into waitQueue and sleep
waitQueue->Append(currentThread);
currentThread->Sleep();
// Awake by Signal...
// 3. Reclaim lock while awake
conditionLock->Acquire();
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
We have two operation that can wake up the Thread which is waiting for this condition. Condition::Signal()
to wakeup single Thread; Condition::Broadcast
to wakeup all the Thread (in waitQueue)
//----------------------------------------------------------------------
// Condition::Signal
// Signal is used to signal (or wake up) another thread which is waiting
// on the condition variable. It should be called after mutex is locked,
// and must unlock mutex in order for Condition::Wait() routine to complete.
//
// "conditionLock" is the lock protecting the use of this condition
//----------------------------------------------------------------------
void
Condition::Signal(Lock* conditionLock)
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
// conditionLock must be held by the current Thread
ASSERT(conditionLock->isHeldByCurrentThread())
if (!waitQueue->IsEmpty()) {
// Putting thread from the front of waitQueue onto ready list
Thread* thread = (Thread*) waitQueue->Remove();
scheduler->ReadyToRun(thread);
}
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
//----------------------------------------------------------------------
// Condition::Broadcast
// Wakeup all the threads waiting on this condition.
// Brodcast should be used instead of Condition::Signal() if more than
// one thread is in a blocking wait state.
//
// "conditionLock" is the lock protecting the use of this condition
//----------------------------------------------------------------------
void
Condition::Broadcast(Lock* conditionLock)
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
// conditionLock must be held by the current Thread
ASSERT(conditionLock->isHeldByCurrentThread())
DEBUG('b', "Condition \"%s\" Broadcasting: ", name);
while (!waitQueue->IsEmpty()) {
// Putting all the threads on ready list
Thread* thread = (Thread*) waitQueue->Remove();
DEBUG('b', "Thread \"%s\", ", thread->getName());
scheduler->ReadyToRun(thread);
}
DEBUG('b', "\n");
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
Other trivial code implementation just checkout threads/synch.cc
.
And the test of Lock
I'll using Challenge 1 as an example.
Based on Semaphore, (Mutex) Lock and Condition Variable. Use two different ways to implement synchronization and mutual mechanism application (one of them must using Condition Variable).
Candidate list: (or any other classic concurrency problem)
Basically followed the pseudocode in Wikipedia.
The shared memory between Threads, the buffer class object called shared_buffer
.
//----------------------------------------------------------------------
// Bounded buffer
// Condumer must wait if the buffer is empty,
// and the producer must wait if the buffer is full
// (no malloc in Nachos?! so use define)
//----------------------------------------------------------------------
#define BUFFER_SIZE 10
class buffer {
public:
buffer() {
fillCount = new Semaphore("Fill Count", 0);
emptyCount = new Semaphore("Empty Count", BUFFER_SIZE);
buffer_mutex = new Lock("Buffer mutex");
count = 0;
};
~buffer() {
delete list;
}
void putItemIntoBuffer(product* item) {
emptyCount->P(); // down
buffer_mutex->Acquire();
/* Critical Section */
list[count++] = *item;
/********************/
buffer_mutex->Release();
fillCount->V(); // up
};
product* removeItemFromBuffer() {
fillCount->P(); // down
buffer_mutex->Acquire();
/* Critical Section */
product* item = &list[count-- -1];
/********************/
buffer_mutex->Release();
emptyCount->V(); // up
return item;
};
void printBuffer() {
printf("Buffer: [", BUFFER_SIZE, count);
int i;
for (i = 0; i < count; i++) {
printf("%d, ", list[i].value);
}
for (; i < BUFFER_SIZE; i++) {
printf("__, ");
}
printf("]\n");
}
private:
int count;
Lock* buffer_mutex;
Semaphore* fillCount;
Semaphore* emptyCount;
product list[BUFFER_SIZE];
} *shared_buffer;
Product is simply a struct with a value.
//----------------------------------------------------------------------
// Product
// Product with value
//----------------------------------------------------------------------
typedef struct PRODUCT {
int value;
} product;
I've invoked interrupt->OneTick()
to make system time moving forward.
So the random context switch (-rs
) will work.
//----------------------------------------------------------------------
// Produce Item
// Generate prodoct with value
//----------------------------------------------------------------------
product*
produceItem(int value)
{
printf("Producing item with value %d!!\n", value);
product item;
item.value = value;
return &item;
}
//----------------------------------------------------------------------
// Consume Item
// Delete product
//----------------------------------------------------------------------
void
consumeItem(product* item)
{
printf("Consuming item with value %d!!\n", item->value);
}
//----------------------------------------------------------------------
// Producer
// generate data, put it into the buffer, and start again.
//----------------------------------------------------------------------
void
ProducerThread(int iterNum)
{
for (int i = 0; i < iterNum; i++) {
printf("## %s ##: ", currentThread->getName());
product* item = produceItem(i);
shared_buffer->putItemIntoBuffer(item);
interrupt->OneTick();
}
}
//----------------------------------------------------------------------
// Consumer
// consuming the data, one piece at a time.
//----------------------------------------------------------------------
void
ConsumerThread(int iterNum)
{
for (int i = 0; i < iterNum; i++) {
printf("$$ %s $$: ", currentThread->getName());
product* item = shared_buffer->removeItemFromBuffer();
consumeItem(item);
interrupt->OneTick();
}
}
Notes:
- Because the mutex and semaphore is built in buffer. So
printBuffer()
may be interrupt and make the result much mess.- Only delete item when using linked list.
I've create 2 producer and 2 consumer. Each has will produce/consume the following amount of items.
Producer 1
: 8Producer 2
: 7Consumer 1
: 6Consumer 2
: 9
And the calling order is Producer 1
-> Consumer 1
-> Consumer 2
-> Producer 2
Add the following test in threads/threadtest.cc
and as case 8.
//----------------------------------------------------------------------
// Lab3 Exercise 4 Producer-consumer problem (Bounded-buffer problem)
// The problem describes two processes, the producer and the consumer,
// who share a common, fixed-size buffer used as a queue.
// The producer's job is to generate data, put it into the buffer,
// and start again.
// At the same time, the consumer is consuming the data
// (i.e., removing it from the buffer), one piece at a time.
// The problem is to make sure that the producer won't try to add data
// into the buffer if it's full and that the consumer won't try to
// remove data from an empty buffer.
//----------------------------------------------------------------------
void
Lab3ProducerConsumer()
{
DEBUG('t', "Entering Lab3ProducerConsumer");
shared_buffer = new buffer();
Thread *producer1 = new Thread("Producer 1");
Thread *producer2 = new Thread("Producer 2");
Thread *consumer1 = new Thread("Consumer 1");
Thread *consumer2 = new Thread("Consumer 2");
producer1->Fork(ProducerThread, (void*)8);
consumer1->Fork(ConsumerThread, (void*)6);
consumer2->Fork(ConsumerThread, (void*)9);
producer2->Fork(ProducerThread, (void*)7);
currentThread->Yield(); // Yield the main thread
}
Without random context switch
threads/nachos -q 8
Lab3 Exercise4: Producer-consumer problem (Bounded-buffer problem)
(add `-d c -rs` argument to show "Context Switch" and activate random timer
## Producer 1 ##: Producing item with value 0!!
## Producer 1 ##: Producing item with value 1!!
## Producer 1 ##: Producing item with value 2!!
## Producer 1 ##: Producing item with value 3!!
## Producer 1 ##: Producing item with value 4!!
## Producer 1 ##: Producing item with value 5!!
## Producer 1 ##: Producing item with value 6!!
## Producer 1 ##: Producing item with value 7!!
$$ Consumer 1 $$: Consuming item with value 7!!
$$ Consumer 1 $$: Consuming item with value 6!!
$$ Consumer 1 $$: Consuming item with value 5!!
$$ Consumer 1 $$: Consuming item with value 4!!
$$ Consumer 1 $$: Consuming item with value 3!!
$$ Consumer 1 $$: Consuming item with value 2!!
$$ Consumer 2 $$: Consuming item with value 1!!
$$ Consumer 2 $$: Consuming item with value 0!!
$$ Consumer 2 $$: ## Producer 2 ##: Producing item with value 0!!
## Producer 2 ##: Producing item with value 1!!
## Producer 2 ##: Producing item with value 2!!
## Producer 2 ##: Producing item with value 3!!
## Producer 2 ##: Producing item with value 4!!
## Producer 2 ##: Producing item with value 5!!
## Producer 2 ##: Producing item with value 6!!
Consuming item with value 6!!
$$ Consumer 2 $$: Consuming item with value 5!!
$$ Consumer 2 $$: Consuming item with value 4!!
$$ Consumer 2 $$: Consuming item with value 3!!
$$ Consumer 2 $$: Consuming item with value 2!!
$$ Consumer 2 $$: Consuming item with value 1!!
$$ Consumer 2 $$: Consuming item with value 0!!
With random context switch
I've add the debug message in
threads/system.cc
theTimerInterruptHandler
. So you can use-d c
to show the debug message.DEBUG('c', " << random Context Switch (stats->totalTicks = %d) >>\n", stats->totalTicks);
threads/nachos -d c -rs -q 8
Lab3 Exercise4: Producer-consumer problem (Bounded-buffer problem)
(add `-d c -rs` argument to show "Context Switch" and activate random timer)
## Producer 1 ##: Producing item with value 0!!
## Producer 1 ##: Producing item with value 1!!
## Producer 1 ##: Producing item with value 2!!
<< random Context Switch (stats->totalTicks = 190) >>
$$ Consumer 1 $$: Consuming item with value 2!!
$$ Consumer 1 $$: << random Context Switch (stats->totalTicks = 280) >>
$$ Consumer 2 $$: ## Producer 2 ##: Producing item with value 0!!
## Producer 2 ##: Producing item with value 1!!
## Producer 2 ##: Producing item with value 2!!
## Producer 2 ##: Producing item with value 3!!
<< random Context Switch (stats->totalTicks = 460) >>
## Producer 1 ##: Producing item with value 3!!
## Producer 1 ##: Producing item with value 4!!
<< random Context Switch (stats->totalTicks = 580) >>
Consuming item with value 0!!
$$ Consumer 1 $$: Consuming item with value 4!!
$$ Consumer 1 $$: Consuming item with value 3!!
$$ Consumer 1 $$: Consuming item with value 2!!
$$ Consumer 1 $$: << random Context Switch (stats->totalTicks = 780) >>
## Producer 1 ##: Producing item with value 5!!
Consuming item with value 1!!
Consuming item with value 0!!
<< random Context Switch (stats->totalTicks = 920) >>
## Producer 2 ##: Producing item with value 4!!
## Producer 2 ##: Producing item with value 5!!
## Producer 2 ##: Producing item with value 6!!
<< random Context Switch (stats->totalTicks = 1110) >>
$$ Consumer 2 $$: Consuming item with value 6!!
$$ Consumer 2 $$: << random Context Switch (stats->totalTicks = 1210) >>
## Producer 1 ##: Producing item with value 6!!
<< random Context Switch (stats->totalTicks = 1260) >>
Consuming item with value 5!!
<< random Context Switch (stats->totalTicks = 1290) >>
## Producer 1 ##: Producing item with value 7!!
$$ Consumer 2 $$: Consuming item with value 7!!
$$ Consumer 2 $$: << random Context Switch (stats->totalTicks = 1460) >>
<< random Context Switch (stats->totalTicks = 1490) >>
Consuming item with value 6!!
$$ Consumer 2 $$: Consuming item with value 5!!
$$ Consumer 2 $$: << random Context Switch (stats->totalTicks = 1590) >>
Consuming item with value 4!!
$$ Consumer 2 $$: << random Context Switch (stats->totalTicks = 1650) >>
Consuming item with value 3!!
$$ Consumer 2 $$: Consuming item with value 0!!
You can use synchronization mechanism offered by Nachos (e.g. condition variable) to implement barrier. Such that the program can continue if and only if a certain amount of thread reach the same point.
- Wiki - Barrier (computer science)
- Latches And Barriers
- Stackoverflow - What is the best way to realize a synchronization barrier between threads
Pthreads
- Pthreads barriers (with prefix
pthread_barrier_
)pthread_barrier_destroy
pthread_barrier_init
pthread_barrier_wait
pthread_barrierattr_destroy
pthread_barrierattr_getpshared
pthread_barrierattr_init
pthread_barrierattr_setpshared
C++ Standard Library
std::latch
- Unlike
std::barrier
can be decremented by a participating thread more than once.
- Unlike
std::barrier
std::flex_barrier
Example using Pthread mutex and condition varialbe
Example using Pthread barrier
I've imitiate the arrive_and_wait
of std::barrier
and build a Barrier class
class Barrier {
public:
Barrier(char* debugName, int num); // initialize barrier
~Barrier(); // deallocate the barrier
char* getName() { return (name); } // debugging assist
void ArrivedAndWait(); // Sleep the Thread until all the Threads arrived
private:
char* name; // useful for debugging
int remain; // How many Threads have not arrived
int num_threads; // Total Threads
Lock* mutex; // Lock for "remain"
Condition* condition; // Used to sleep the Thread and wake them up
};
The idea is simple.
If there is anyone haven't reach the barrier (remain > 0). Sleep the current Thread (using Condition)
Else broadcast to wake everyone up (who sleeping in the Condition). (And reset the barrier).
//----------------------------------------------------------------------
// Barrier::ArrivedAndWait
// Allows a single thread to indicate that it has arrived at a synchronization point.
// The thread will block until the synchronization condition has been reached.
// May be called repeatedly by a given thread.
//----------------------------------------------------------------------
void
Barrier::ArrivedAndWait()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
// Use mutex to ensure that only one thread modifies remain at a time
mutex->Acquire();
remain--;
DEBUG('b', "Thread %s enter barrier %s with remain=%d\n", currentThread->getName(), name, remain);
if (remain == 0) {
DEBUG('b', "Everyone reached the Barrier!!\n");
condition->Broadcast(mutex);
// Reset barrier
remain = num_threads;
} else {
// while (remain != 0) // While will sleep the waken Thread sleep again!
condition->Wait(mutex);
}
mutex->Release();
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
Other trivial code implementation just checkout threads/synch.cc
.
I've made the following scenario
- Shared memory:
matrix[24][10]
- 4 Threads. Each thread manipulate 6 rows (24/4).
There are three parts of calculation. Each of them will wait at the barrier until every body complete.
- Threads do first calculation
matrix[x][y] += (x+1)*(y+1)
- Barrier!
- Threads do second calculation
matrix[x][y] /= startRow+1
- Barrier!
- Threads do third calculation
matrix[x][y] -= startRow/N_ROWS
Because the code is quite long.
Checkout Lab3Barrier()
and CalcThread
in threads/threadtest.cc
.
(And it's as case 9)
-d b
for debugging message related to barrier
$ threads/nachos -d b -q 9
Lab3 Challenge1: Barrier
main() is ready.
Thread "Calc 1" finish First Calculation
Thread Calc 1 enter barrier Matrix Calc with remain=4
Thread "Calc 2" finish First Calculation
Thread Calc 2 enter barrier Matrix Calc with remain=3
Thread "Calc 3" finish First Calculation
Thread Calc 3 enter barrier Matrix Calc with remain=2
Thread "Calc 4" finish First Calculation
Thread Calc 4 enter barrier Matrix Calc with remain=1
Thread main enter barrier Matrix Calc with remain=0
Everyone reached the Barrier!!
Condition "Barrier Condition" Broadcasting: Thread "Calc 1", Thread "Calc 2", Thread "Calc 3", Thread "Calc 4",
main() is going!
Thread "Calc 1" finish Second Calculation
Thread Calc 1 enter barrier Matrix Calc with remain=4
Thread "Calc 2" finish Second Calculation
Thread Calc 2 enter barrier Matrix Calc with remain=3
Thread "Calc 3" finish Second Calculation
Thread Calc 3 enter barrier Matrix Calc with remain=2
Thread "Calc 4" finish Second Calculation
Thread Calc 4 enter barrier Matrix Calc with remain=1
Thread main enter barrier Matrix Calc with remain=0
Everyone reached the Barrier!!
Condition "Barrier Condition" Broadcasting: Thread "Calc 1", Thread "Calc 2", Thread "Calc 3", Thread "Calc 4",
main() is going again!
Thread "Calc 1" finish Third Calculation
Thread "Calc 2" finish Third Calculation
Thread "Calc 3" finish Third Calculation
Thread "Calc 4" finish Third Calculation
Result of data:
1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00 10.00
2.00 4.00 6.00 8.00 10.00 12.00 14.00 16.00 18.00 20.00
3.00 6.00 9.00 12.00 15.00 18.00 21.00 24.00 27.00 30.00
4.00 8.00 12.00 16.00 20.00 24.00 28.00 32.00 36.00 40.00
5.00 10.00 15.00 20.00 25.00 30.00 35.00 40.00 45.00 50.00
6.00 12.00 18.00 24.00 30.00 36.00 42.00 48.00 54.00 60.00
0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00
0.14 1.29 2.43 3.57 4.71 5.86 7.00 8.14 9.29 10.43
0.29 1.57 2.86 4.14 5.43 6.71 8.00 9.29 10.57 11.86
0.43 1.86 3.29 4.71 6.14 7.57 9.00 10.43 11.86 13.29
0.57 2.14 3.71 5.29 6.86 8.43 10.00 11.57 13.14 14.71
0.71 2.43 4.14 5.86 7.57 9.29 11.00 12.71 14.43 16.14
-1.00 0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00
-0.92 0.15 1.23 2.31 3.38 4.46 5.54 6.62 7.69 8.77
-0.85 0.31 1.46 2.62 3.77 4.92 6.08 7.23 8.38 9.54
-0.77 0.46 1.69 2.92 4.15 5.38 6.62 7.85 9.08 10.31
-0.69 0.62 1.92 3.23 4.54 5.85 7.15 8.46 9.77 11.08
-0.62 0.77 2.15 3.54 4.92 6.31 7.69 9.08 10.46 11.85
-2.00 -1.00 0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00
-1.95 -0.89 0.16 1.21 2.26 3.32 4.37 5.42 6.47 7.53
-1.89 -0.79 0.32 1.42 2.53 3.63 4.74 5.84 6.95 8.05
-1.84 -0.68 0.47 1.63 2.79 3.95 5.11 6.26 7.42 8.58
-1.79 -0.58 0.63 1.84 3.05 4.26 5.47 6.68 7.89 9.11
-1.74 -0.47 0.79 2.05 3.32 4.58 5.84 7.11 8.37 9.63
Based on lock (
synch.h
andsynch.cc
) made by Nachos. Implement read/write lock, such that a certain amount of thread can read the shared data at the same time. But can only be a single thread writing the shared data at a moment.
The Reader-writer lock is a solution for readers-writers problem. And it has been generalized as a special lock on some system.
- Synchronization, Part 7: The Reader Writer Problem
- Wiki - Readers–writer lock - I've followed the pseudocode of first implementation (Using two mutexes)
- Wiki - Readers–writers problem
Pthreads
pthread_rwlock
pthread_rwlock_init
pthread_rwlock_destroy
pthread_rwlock_tryrdlock
pthread_rwlock_timedrdlock
pthread_rwlock_rdlock
pthread_rwlock_timedrdlock
pthread_rwlock_tryrdlock
pthread_rwlock_trywrlock
pthread_rwlock_timedwrlock
pthread_rwlock_wrlock
pthread_rwlock_unlock
There are some different readers-writers problem
- The first readers-writers problem (simplest)
- Requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object.
- i.e. No reader should wait for other readers to finish simply because a writer is waiting.
- The second readers-writers problem
- Requires that once a writer is ready, that writer perform its write as soon as possible.
- i.e. If a writer is waiting to access the object, no new readers may start reading.
A soluiton to either problem may result in starvation
- Writers may starve (read-preferring solution)
- Readers may starve (write-preferring solution)
In application
- It's easy to identify which processes only read shared data and which processes only write shared data.
- Usually have more readers than writers.
Acquiring a reader-writer lock requires specifying the mode of the lock: either read or write access.
I'm using two mutexes to implemet this.
Note that, one of the mutex is only used by readers. The other one is a "global" mutual exclusion of writer. This requires that a mutex acquired by one thread can be released by another. (So I'll use binary simaphore here)
class ReaderWriterLock {
public:
ReaderWriterLock(char* debugName); // initialize barrier
~ReaderWriterLock(); // deallocate the barrier
char* getName() { return (name); } // debugging assist/
// For Reader
void ReaderAcquire();
void ReaderRelease();
// For Writer
void WriterAcquire();
void WriterRelease();
private:
char* name; // useful for debugging
int blockingReader; // counts for blocking readers
// "Global" mutex lock for writer that can be release by other
// Alias g in comment
Semaphore* binary_semaphore_writer;
// Lock used by reader to protect number "blockingReader"
// Alias r in comment
Lock* mutex_reader;
};
//----------------------------------------------------------------------
// ReaderWriterLock::ReaderAcquire
//----------------------------------------------------------------------
void
ReaderWriterLock::ReaderAcquire()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
mutex_reader->Acquire(); // Lock r
blockingReader++;
DEBUG('w', "Reader \"%s\" comming in \t(blockingReader=%d)\n", currentThread->getName(), blockingReader);
if (blockingReader == 1) {
binary_semaphore_writer->P(); // Lock g
}
mutex_reader->Release(); // Unlock r
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
//----------------------------------------------------------------------
// ReaderWriterLock::ReaderRelease
//----------------------------------------------------------------------
void ReaderWriterLock::ReaderRelease()
{
IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
mutex_reader->Acquire(); // Lock r
blockingReader--;
DEBUG('w', "Reader \"%s\" getting out \t(blockingReader=%d)\n", currentThread->getName(), blockingReader);
if (blockingReader == 0) {
binary_semaphore_writer->V(); // Unlock g
}
mutex_reader->Release(); // Unlock r
(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
//----------------------------------------------------------------------
// ReaderWriterLock::WriterAcquire
//----------------------------------------------------------------------
void ReaderWriterLock::WriterAcquire()
{
DEBUG('w', "Writer \"%s\" comming in \t(blockingReader=%d)\n", currentThread->getName(), blockingReader);
binary_semaphore_writer->P(); // Lock g
}
//----------------------------------------------------------------------
// ReaderWriterLock::WriterRelease
//----------------------------------------------------------------------
void ReaderWriterLock::WriterRelease()
{
DEBUG('w', "Writer \"%s\" getting out \t(blockingReader=%d)\n", currentThread->getName(), blockingReader);
binary_semaphore_writer->V(); // Unlock g
}
Other trivial code implementation just checkout threads/synch.cc
.
I've made the problem, that
- The Writer is going to write the quote of Albert Einstein into
char quote[SENTENCE_LENGTH][MAX_CHAR]
.- Insanity: doing the same thing over and over again and expecting different results
- The Readers are going to read the quote repeatedly until writer has finish the quote.
The problem is written in threads/threadtest.cc
as case 10.
//----------------------------------------------------------------------
// Reader Thread
// Keeping trying to read the quote. Until writer has finished the
// quote. (i.e. the words is match the SENTENCE_LENGTH)
//----------------------------------------------------------------------
void
ReaderThread(int reader_id)
{
do {
RWLock->ReaderAcquire();
printf("Reader %d is reading: ", reader_id);
for (int i = 0; i < words; i++) {
printf("%s ", quote[i]);
}
printf("\n");
RWLock->ReaderRelease();
} while (words < SENTENCE_LENGTH);
}
//----------------------------------------------------------------------
// Writer Thread
// Trying hard to write the quote...
//----------------------------------------------------------------------
void
WriterThread(int dummy)
{
while (words < SENTENCE_LENGTH) {
RWLock->WriterAcquire();
strcpy(quote[words], AlbertEinstein[words]); // composing...
words++;
printf("Writer is writting: ");
for (int i = 0; i < words; i++) {
printf("%s ", quote[i]);
}
printf("\n");
RWLock->WriterRelease();
}
}
-d w
for reader-writer lock;-d c
for context switch;-rs
for random context switch timer interrupt
This is the result with 3 readers.
We need some luck to see the "phenomenon". Threre are some possible scenario during random context switch
- The thread has done its job.
- Writer is still writing
- Readers are still reading
If you got lots of readers, you may take a long time for writer to finsh composing. But sometime writer is just happen to writting...
$ threads/nachos -d c -rs -q 10
Lab3 Challenge2: Reader-Writer
(add `-d wc -rs` argument to show "Context Switch", RWLock message and activate random timer)
Writer is writting: Insanity:
Writer is writting: Insanity: doing
Writer is writting: Insanity: doing the
Writer is writting: Insanity: doing the same
Writer is writting: Insanity: doing the same thing
Writer is writting: Insanity: doing the same thing over
Writer is writting: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 190) >>
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 280) >>
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 460) >>
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 580) >>
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 780) >>
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
Reader 1 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 920) >>
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
Reader 2 is reading: Insanity: doing the same thing over and
<< random Context Switch (stats->totalTicks = 1110) >>
Writer is writting: Insanity: doing the same thing over and over
Writer is writting: Insanity: doing the same thing over and over again
Writer is writting: Insanity: doing the same thing over and over again and
Writer is writting: Insanity: doing the same thing over and over again and expecting
Writer is writting: Insanity: doing the same thing over and over again and expecting different
<< random Context Switch (stats->totalTicks = 1210) >>
Reader 1 is reading: Insanity: doing the same thing over and over again and expecting different
Reader 1 is reading: Insanity: doing the same thing over and over again and expecting different
<< random Context Switch (stats->totalTicks = 1260) >>
Reader 2 is reading: Insanity: doing the same thing over and over again and expecting different
<< random Context Switch (stats->totalTicks = 1290) >>
Writer is writting: Insanity: doing the same thing over and over again and expecting different results.
The
quote
is taken control continuously by Reader 1 and 2...
$ threads/nachos -d wc -rs -q 10
Lab3 Challenge2: Reader-Writer
(add `-d wc -rs` argument to show "Context Switch", RWLock message and activate random timer)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity:
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity: doing
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity: doing the
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity: doing the same
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity: doing the same thing
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
Writer is writting: Insanity: doing the same thing over
Writer "Writer" getting out (blockingReader=0)
Writer "Writer" comming in (blockingReader=0)
<< random Context Switch (stats->totalTicks = 190) >>
Reader "Reader 1" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and over
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
<< random Context Switch (stats->totalTicks = 280) >>
Writer is writting: Insanity: doing the same thing over and over again
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and over again and
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and over again and expecting
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and over again and expecting different
Writer "Writer" getting out (blockingReader=1)
Writer "Writer" comming in (blockingReader=1)
Writer is writting: Insanity: doing the same thing over and over again and expecting different results.
Writer "Writer" getting out (blockingReader=1)
Reader 1 is reading: Insanity: doing the same thing over and over again and expecting different results.
Reader "Reader 1" getting out (blockingReader=0)
Reader "Reader 2" comming in (blockingReader=1)
Reader 2 is reading: Insanity: doing the same thing over and over again and expecting different results.
Reader "Reader 2" getting out (blockingReader=0)
Reader "Reader 3" comming in (blockingReader=1)
Reader 3 is reading: Insanity: doing the same thing over and over again and expecting different results.
Reader "Reader 3" getting out (blockingReader=0)
The
quote
is luckly taken control by Writer...
Research if Linux's kfifo module can be merge into Nachos as a new module.
- Stackoverflow - typedef struct vs struct definitions
- Stackoverflow - Why should we typedef a struct so often in C?
Struct
- programmertech - Resolve C++ cross initialization error in switch case
- Stackoverflow - Getting a bunch of crosses initialization error
In C++ when we declare & initialize variable in switch case directly except first case then c++ compiler throws jump to case label crosses initialization error; because cases considered as jump & c++ does not create scope for switch cases except first switch case; to resolve this error we have two options.
- Declare & initialize variable before switch and reassign value to that variable inside switch case.
- Declare & initialize variable inside curley braces {} or block and used within that block in switch case. this block of code is now create scope within switch cases i.e. variable scope is inside that block only when block completes then scope of variable finished.
struct PRODUCT item;
// X
case 8:
struct PRODUCT *new_item = &item;
// O
case 8:
struct PRODUCT *new_item
new_item = &item;
Segmentation Fault!
It may caused by you declare a struct pointer and then you access it. You should declare a struct normally. And pass it with
&
if you wan't to pass in address.
Common mistakes:
- dereferencing NULL
- dereferencing an uninitialized pointer
- dereferencing a pointer that has been freed (or deleted, in C++) or that has gone out of scope (in the case of arrays declared in functions)
- writing off the end of an array.
So many warning message makes me feel annoying..
- Passing
-Wno-write-strings
to gcc and g++I've add it in
Makefile.common
in CFLAGS - Use
char const *
as the type instead ofchar*
char string[STRING_SIZE] = "text "
char buffer[BUFFER_SIZE];
sprintf(buffer, "%d", number);
strcat(string, buffer)
char * strncpy(char * dst, const char * src, size_t len));
char str[80];
strcpy (str,"these ");
strcat (str,"strings ");
strcat (str,"are ");
strcat (str,"concatenated.");
puts (str);
char * strndup(const char *s1, size_t n);
- Wiki - Concurrency (computer science)
- Wiki - Monitor (synchronization) - Condition variables
- Stackoverflow - When to use pthread condition variables?
- C++ Core Guidelines: Be Aware of the Traps of Condition Variables
- GeeksforGeeks - Array of Strings in C++ (3 Different Ways to Create)
Bold the chapter with more reference.
Operating System Concept 9ed.
- Ch3 Processes
- Ch3.4 Interprocess Communication
- Ch3.4.1 Shared-Memory Systems => Producer-consumer bounded buffer
- Ch3.4 Interprocess Communication
- Ch5 Process Synchronization
- Ch5.1 Background => Producer-consumer
- Ch5.2 The Critical-Section Problem
- Ch5.3 Peterson's Solution
- Ch5.4 Synchronization Hardware
- Ch5.5 Mutex Locks 互斥鎖(鎖)
- Ch5.6 Semaphores 號誌(信號量)
- Ch5.7 Classic Problems of Synchronization
- Ch5.7.1 The Bounded-Buffer Problem => Producer-consumer semaphore
- Ch5.7.2 The Readers-Writers Problem
- Ch5.7.3 The Dining-Philosophers Problem
- Ch5.8 Monitors
- Ch5.9 Synchronization Examples
- Ch5.9.2 Synchronization in Linux
Modern Operating Systems 4ed.
- Ch2.3 Interprocess Communication
- Ch2.3.4 Sleep and Wakeup
- Ch2.3.5 Semaphores
- Ch2.3.6 Mutexes
- Ch2.3.7 Monitors
- Ch2.3.8 Message Passing
- Ch2.3.9 Barriers