Serializability

The idea that no matter what is occuring internally the external behavior appears to be sequentially allowing an observer to explain the process with a series of transitions

Atomicity

Atomicity is the concept of designing each action to be indivisible, meaning we want each action to be small enough to where we could not make it smaller without losing utility. This is used to inforce isolation and allows more efficient locking and unlocking of critical sections.

Bank Example of Actions

Simple Actions:

• deposit/withdraw
• transfer
• audit

Auditing is expensive for locking since it is a composition of non atomic actions internally. One way to attempt to avoid this is by locking to quickly take a snapshot of the current state, and then audit the snapshot. This decreases the time we need to lock down the accounts since we now just audit on the snapshot

Running Example Pipes

We can implement this in two different ways. The first way is Lazy Evaluation, for this we run B as much as possible until we absolutely need data from a. One major benefit is that we may never even have to execute A. The second is Eager Evaluation which is essentially the opposite, we would run A as much as possible until we needed to run B.

Unix uses a combination of the two previous types of evaluation of pipes, it runs the two in parallel.

A pipe is abounded buffer. The buffer is bounded to avoid space exhaustion which gives us flow control. There are two ways to impement, the first is by polling. Polling is and ugly way to implement this since it is CPU intensive, since it constantly checks to see if the process is ready. The alternative is blocking which disables the process until the process tells us it is ready, then it renables the blocked process.

Read/Write Coherence

  T1:	movl foo, %eax
  
  T2:	movl %eax, foo

In this example if we were to initialize eax to 1, and foo to 0, we would get the correct values at the end, but if we were trying to do the same thing with a larger object such as a char buffer, we would get incorrect behavior. This occurs because loads and stores are not atomic, and we are not locking the critical sections.

Another Example

  struct foo{
	unsigned int b1 : 1;
	unsigned int b2 : 1;
  }
  
  struct foo g = {0};
  T1:	g.b1 = 1;
  
  T2:	g.b2 = 1;

In this example we want both bits to be set, but this will not be the case all the time, since we can only store/load words not bits, so the same type of problem can occur where one will over write the other.

Multi-thread Memory access

  struct pipe {
	char buff[N];
	size_t r,w;
  }
  
  void writec (struct pipe* p, char c) {
	p->buff[p->w++%N] = c;
  }
  
  char readc (struct pipe* p){
	return p->buff[p->r++%N];
  }

In the above code we need to use a cicular buffer for the pipe, and we assume N is a power of 2 to accomplish circular buffer. This code should handle reading and writing a character into and from a pipe, but there is still a problem with the above implementation, we do not take into account flow control to prevent over writing characters and reading too far. To add flow control we simple insert a while loop before our code giving us the following.

  struct pipe {
	char buff[N];
	size_t r,w;
  }
  
  void writec (struct pipe* p, char c) {
	while(p->w - p->r == N){
		yeild();
	}
	p->buff[p->w++%N] = c;
  }
  
  char readc (struct pipe* p){
	while(p->w - p->r == 0){
		yeild();
	}
	return p->buff[p->r++%N];
  }

Now that we have added flow control we are left with only one problem remaining, if we have two writers we will have data inconsistencies. This issue will be addressed by locking the critical sections.

Critical Sections

A critical section is a set of instructions executed by a thread such that atomicity is preserved if at most one thread's instuction pointer is in that set at any given time.

We need a way to enforce this, and handle two subproblems that occur from critical sections, mutual exclusion and bounded wait. Mutual exclusion is the idea that if one process is executing the critical section then all other processes must wait for the process to finish, and bounded wait is that anyone running this section cannot run it indefinitely, it must leave the critical section quickly.

Uniprocessor Critical Sections

If we assume no interrupts this is easy since we us cooperative multitasking and that will accomplish our two main goals. If we assume there are interrupts we are using preemptive multitasking. In this case we would need to make readc and writec syscalls atomic, and mask out intterupts.

Multiprocessor Critical Sections

We handle the mutual excultion problem mention before using locks, but the bounded wait problem is the responsibility of the programmer. A lock blocks other processes from the critical section that the process that has obtained the lock is currently in, when finished we must make sure to release the lock so the waiting processes can then subsequently obtain the lock. To create a lock and unlock we use the following functions.

  typeof int mutex_t;
  void lock (mutext_t*);
  void unlock (mutext_t*);

The lock function checks the passed in mutex to see if some else owns that lock, if someone does we wait for the lock otherwise the process grabs the lock. There is a precondition to locking though which is that we do not already own the lock if we already own the lock calling lock again will lead to an unbounded wait and locking the entire process. The unlock function releases the passed mutext. This two has a similar precondition which is we can only do this if we have the lock.

Coarse Grained Locking

Coarse grained locking is where a single lock controls many objects and actions. This approach to locking is not good since it can slow down performance since the lock is bigger and more processes may need to run the lock.

Example Of Coarse Grained Locking

  static mutext_t mutex;
  void writec (struct pipe* p, char c) {
	for(;;){
		lock(&mutex);
		if(p->w - p->r != N){
			p->buff[p->w++%N] = c;
			unlock(&mutex);
			return;
		}
		unlock(&mutex);
	}
  }

Fine Grained Locking

Fine grained locking is where there are many locks each controlling a small piece of the system. This technique leads to fewer collisions which allows for more parallelism. The goal is to control as few objects as possible. To make the above example of Coarse Grained Locking into a Fine Grained Locking scheme we could instead of a global lock have the pipe struct have its own mutex and have locks and unlocks use &(p->m). To improve this even more we could have a lock for both reading and writing.

Heuristic for Designing Critical Sections

We want our critical sections to be as small as possible, but we must also make sure that they arent so small that we have bugs. Below are two steps to make sure we have an optimal critical section.

• Look for writes to a shared state
• Expand the view to include all dependant reads(reads that affect the writes behavior).

Implementation of lock and unlock

  typeof int mutex_t;
  void lock (mutext_t *m) {
	while (*m) {
		continue;
	}
	*m=1;
  }
  void unlock (mutex_t *m) {
	*m = 0;
  }

While the above implementation of lock looks like there is a race condition during the while statement, because two processes might obtain the same lock, there is an added instruction in the x86 architecture xchg which is atomic and essentially switches the values of two registers. From this we can create a new lock implementation using a new function as follows

  int tas(int *p, int new) {
	int old = *p;
	*p = new;
	return old;
  }
  void lock (mutex_t *m){
	while (tas(m,1) == 1)
		continue;
  }

Generic Example: Multiple Readers, One Writer

Assuming we have an object p that contains a mutex_t field and an integer for the number of readers, the pseudo code for locking for reads and writes are as follows

  locking for read
	lock(&p->m);
	p->readers++;
	unlock(&p->m);
  locking for writer
	for(;;){
		lock(&p->m);
		if(!p->readers)
			return;
		unlock(&p->m);
	}

Blocking Mutexes

The implementations we have seen thus far are all using the polling method to grab the lock. To implement a blocking method instead of the less efficient polling method we can use the following mutex struct and implementation pseudo code.

  struct bmutex {
	mutex_t m;
	bool locked;
	proc_t* blocked_list;
  }
  
  void acquire (struct bmutex *b){
	lock(&b->m);
	for(;;){
		Set process descriptor to BLOCKED;
		add us to b->blocked_list;
		if(!b->blocked)
			break;
		unlock(&b->m);
		yeild();
	}
	b->locked = true;
	Set process descriptor to RUNNABLE;
	remove ourselves from blocked_list
	unlock(&b->m);
  }
  
  To release
	lock(&b->m);
	change all in the blocked list to runnable;
	set locked to false;
	unlock(&b->m);