CanesOS Semaphores

The operating system supplies system calls used by threads to solve problems of concurrency.

If there is a necessary time ordering between statement, statement blocks, functions, or processes, then those element are synchronized. Else if there is no imposed order, they are concurrent. The word concurrent tends to connotate a necessary concurrency — that two things run at the same time. This is not the case in our definition.

Statics, defines and datastructures

#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<unistd.h>


/*
 * semaphore 
 * for the hypothetical cane OS 85 op sys, a.k.a. caos85
 * author: burt rosenberg
 * created: october 11, 2019
 * last update: 11 oct 2019 
 *
 */


typedef enum { 
	THREAD_INIT, THREAD_READY, THREAD_RUNNING, THREAD_WAITING, THREAD_ZOMBIE  } 
	ThreadState ;


struct TCB {
	struct TCB * wait_next ;
	int tid ;
	ThreadState  thread_state ;
	int priority ;
	int cpu ;
	int sleeps ;
	int wakeups ;
} ;

struct PVSema {
	int lock ;
	int count ;
	struct TCB head_queue ;	
} ;

#define N_SEMAPHORES 8

struct PVSema sema_table[N_SEMAPHORES] ;
struct TCB * current ;

Core Semaphore Code

int sys_sema_queue_empty( struct PVSema * s) {
	return ( s->head_queue.wait_next==NULL ) ;
}

struct TCB * sys_sema_queue_remove_head( struct PVSema * s) {
	struct TCB * t ;
	t = s->head_queue.wait_next ;
	if (t==NULL) return NULL ;
	s->head_queue.wait_next = t->wait_next ;
	return t ;
}

int sys_sema_queue_priority_insert( struct PVSema * s, struct TCB * tcb ) {
	struct TCB * t = &(s->head_queue) ;
	while (t->wait_next) {
		if (t->wait_next->priority>tcb->priority) {
			tcb->wait_next = t->wait_next ;
			t->wait_next = tcb ;
			return 0 ;
		}
		t = t->wait_next ;
	}
	t->wait_next = tcb ;
	return 0 ;
}

#define ATOMIC /* atomic section */

int testandset(int * m, int val) {
	ATOMIC { 
		int old_val = *m ;
		*m = val ;
		return old_val ; 	
	}
}

void sys_sema_spinlock(struct PVSema * pvs) {
	int l = testandset(&(pvs->lock),1) ;
	while (l){
		l = testandset(&(pvs->lock),1) ;
	}
	return ;
}

void sys_sema_unlock(struct PVSema * pvs) {
	testandset(&(pvs->lock),0) ;
	return ;
}

int sys_sema_P(int sid) {
	struct PVSema * pvs ;
	if (sid<0 || sid>=N_SEMAPHORES) return -1;
	pvs = &(sema_table[sid]) ;
	
	sys_sema_spinlock(pvs) ;
	pvs->count-- ;
	if (pvs->count<0) {
		sys_sema_queue_priority_insert(pvs,current) ;
		current->thread_state = THREAD_WAITING ;
	}
	sys_sema_unlock(pvs) ;
	return (pvs->count<0)?0; pvs->count ;
	 // return will take us through the scheduler
}

int sys_sema_V(int sid) {
	struct PVSema * pvs ;
	if (sid<0 || sid>=N_SEMAPHORES) return -1 ;
	pvs = &(sema_table[sid]) ;
	sys_sema_spinlock(pvs) ;
	pvs->count++ ;
	if (!sys_sema_queue_empty(pvs)) {
		struct TCB * t ;
		t = sys_sema_queue_remove_head(pvs) ;
		t->thread_state = THREAD_READY ;
	}
	sys_sema_unlock(pvs) ;
	return (pvs->count>0)?0; -pvs->count ;
	// return will take us through the scheduler
}

Typical Concurrency Problems

Notation: A good way to reason about concurrency is to mark non-concurrent events, A and B, with their mandatory time ordering. For instance, A < B means A will come before B (if they both do occur). Concurrency is then an application of a non-excluded middle: neither A < B nor B < A are required. Solving a problem in concurrency is using (for instance) semaphores to achieve the ordering relationship required.

### Signal/waits:

# Enforce A1 < B1

s = Semaphore(0)

Thread A:
	statement A1
	Sema_V(s)
	
	
Thread B:
	Sema_P(s)
	statement B1

*Proof:

   given A1 < Sema_V, Sema_P < B1. 
   the semaphore promise is Sema_V ≶ Sema_P.
   
   if Sema_V < Sema_P, then
       A1 < Sema_V < Sema_P < B1, 
   and we have the result
   
   if Sema_P < Sema_V, Sema_P occurs when the count is 0, 
   and therefore thread B does not go on until Sema_V, so 
       Sema_V < B1, 
   and we have the result from A1 < Sema_V < B1
    
   note that in this second case we have established no relationship
   between A1 and Sema_P. They remain concurrent: A1 ∏ Sema_P.



### Rendez-vous:

# Enforce A1 < B2 and B1 < A2

sA = Semaphore(0)
sB = Semaphore(0)

Thread A:

	statement A1
	Sema_V(sB)
	Sema_P(sA)
	statement A2
	
Thread B:

	statement B1
	Sema_V(sA)
	Sema_P(sB)
	statement B2

*Proof:

   we have the usual relations between statements in A and statements in B.
   the semaphore promise is Sema_V(sB) ≶ Sema_P(sB). 
   
   If Sema_V(sB) < Sema_P(sB), then A1 < B2 follows by the logic,
      A1 < Sema_V(sB) < Sema_P(sB) < B2
   Else if Sema_P(sB) < Sema_V(sB) then B2 does not begin until Sema_V(sB),
      Sema_V(sB) < B2,
   then A1 < B2 follows by the logic,
      A1 < Sema_V(sB) < B2
      
   The same argument establishes B1 < A2.



### Mutex:

# Enforce for all Threads _A_, _B_, either _A_n < _B_1 or _B_n < _A_1

M = Semaphore(1)

Thread _X_:

	Sema_P(M)
	statement _X_1
	...
	statement _X_n
	Sema_V(M)

CanesOS Semaphores: from spin locks to wait/notify

by: burt rosenberg
at: university of miami
date: oct 2019

Overview

Statics, defines and datastructures

Core Semaphore Code

Typical Concurrency Problems

CanesOS Semaphores: from spin locks to wait/notify

by: burt rosenbergat: university of miami date: oct 2019

Overview

Statics, defines and datastructures

Core Semaphore Code

Typical Concurrency Problems

by: burt rosenberg
at: university of miami
date: oct 2019