Project 03. Semaphore and Readers Writer Lock

Definition

Semaphore / Readers-writer Lock

• Semaphore is kind of locking which allows sharing with processes as many as the certain variable
• Readers-writer Lock is kind of locking which allows sharing with reading processes but it doesn't allow sharing with writing processes

POSIX semaphore

• sem_t : semaphore type
• int sem_init(sem_t *sem, int pshared, unsigned int value)
  • sem : semaphore object to be initialized
  • pshared : if its value is 0, then share it with processes, otherwise, only one process
  • value : a number of processes to be used concurrently
• int sem_wait(sem_t *sem)
  • sem : semaphore object to run
  • After decreasing value of sem, If it is bigger or equal to 0, then return immediately, otherwise, sleep sem until the value is not negative
• int sem_post(sem_t *sem)
  • sem : semaphore object to be released
  • After increasing value of sem, If it is begger or equal to 0, then wake a process

POSIX reader-writer lock

• pthread_rwlock_t : readers-writer lock type
• int pthread_rwlock_init(pthread_rwlock_t* lock, const pthread_rwlock attr_t* attr)
  • lock : readers-writer lock object to be initalized
  • attr :
• int pthread_rwlock_rdlock(pthread_rwlock_t* lock)
  • lock : readers-writer lock object to be read
  • If lock is first reading process, then acquire write lock for preventing from writing processes
  • Increase a number of reader
• int pthread_rwlock_wrlock(pthread_rwlock_t* lock)
  • lock : readers-writer lock object to be written
  • It doesn't allow to access any process after holding write lock
• int pthread_rwlock_unlock(pthread_rwlock_t* lock)
  • lock : readers-writer lock object to be released
  • If lock is last reading process, then release write lock for allow to access from any process
  • Decrease a number of reader

Implement the Basic Semaphore

// proc.c
struct _xem_t {
  struct spinlock lock;
  int value;
};

int
xem_init(xem_t *semaphore)
{
  semaphore->value = 1;
  return 0;
}

int
xem_wait(xem_t *semaphore)
{
  acquire(&semaphore->lock);
  semaphore->value--;
  while(semaphore->value < 0)
	sleep((void *)semaphore, &semaphore->lock);
  release(&semaphore->lock);
  return 0;
}

int xem_unlock(xem_t *semaphore)
{
  acquire(&semaphore->lock);
  semaphore->value++;
  if(semaphore->value <= 0)
	wakeup((void *)semaphore);
  release(&semaphore->lock);
  return 0;
}

• xem_t : structure of semaphore has member lock and value which is mentioned above as certain variable
• xem_init : initialize xem_t variable to have value with 1 so that it can be used as binary semaphore
• xem_wait : guarantee mutual exclusion with processes using current semaphore
• xem_unlock : if there is any sleeping process, then wake up

Implement the Readers-writer Lock using Semaphores

struct _rwlock_t {
  xem_t lock;
  xem_t writelock;
  int readers;
};

int
rwlock_init(rwlock_t *rwlock)
{
  xem_init(&rwlock->lock);
  xem_init(&rwlock->writelock);
  rwlock->readers = 0;
  return 0;
}

int
rwlock_acquire_readlock(rwlock_t *rwlock)
{
  xem_wait(&rwlock->lock);
  rwlock->readers++;
  if(rwlock->readers == 1)
	xem_wait(&rwlock->writelock);
  xem_unlock(&rwlock->lock);
  return 0;
}

int
rwlock_release_readlock(rwlock_t *rwlock)
{
  xem_wait(&rwlock->lock);
  rwlock->readers--;
  if(rwlock->readers == 0)
	xem_unlock(&rwlock->writelock);
  xem_unlock(&rwlock->lock);
  return 0;
}

int
rwlock_acquire_writelock(rwlock_t *rwlock)
{
  xem_wait(&rwlock->writelock);
  return 0;
}

int
rwlock_release_writelock(rwlock_t *rwlock)
{
  xem_unlock(&rwlock->writelock);
  return 0;
}

• rwlock_t : structure of rwlock has member lock, writelock and readers
• rwlock_init : initialize rwlock_t variable about lock, writelock and readers
• rwlock_acquire_readlock : allow sharing with reading processes but block writing processes if reading process is using
• rwlock_release_readlock : if readers is 0, then allow access from any process which wants to acquire
• rwlock_acquire_writelock : guarantee mutual exclusion so that no other process can use it
• rwlock_release_writelock : allow access from any process which wants to acquire