Project 5: Semaphore

Due: Nov. 17, 2022, 2:30 pm (submission: by email)
Submit a report to TA: SeungWon Yoo ( email: swyoo98@kaist.ac.kr )
Name your file with “hw5_[your studentid]”. ex: hw5_20201234.zip

Semaphore allows you to specify the maximum number of threads that can access the critical section simultaneously. In addition, semaphore does not spend CPU time while waiting for other threads to finish. If you use semaphore and set the maximum thread to 1, then it works the same as sleeplock. That is, semaphore can cover larger range of the usage for user.

Read/Write semaphore provides two types of lock; exclusive and shared lock. The user can decide the one of them according to the task of thread. For example, Writer thread, that updates the data, use “write (exclusive) lock”. It blocks all of threads not to occur conflicts. Reader thread, that reads the data, use “read (shared) lock” to block writer threads and share the data with other reader threads. Therefore, user can avoid the useless serialized behavior and increase the parallelism.

Unfortunately, the semaphore and read/write semaphore are not implemented in xv6. In this project, we will create these types of lock and develop the xv6 programs.

Part One : Add new system calls to test semaphore

First, we will check whether sleeplock of xv6 guarantees ordering of waiters. We have to add new system call to use new type of locks, since these are kernel data structure. We will add new system call, sematest and rwsematest. Add Appendix A. code to sysfile.c.

Please refer to the sleeplock homework for next step of adding new system call. You don`t need to submit files that have been updated to do this.

Part Two : Create the semaphore

Before you start to evaluate your semaphore, make sure that CPUS=1 which makes the numbef of cpus of virtual machine 1.
That’s because user library printf() locks the console for each character.

Create semaphore.h and declare struct semaphore in semaphore.h. Then, define and implement following functions in semaphore.c.

# 1. Set the maximum threads to count and initialize anything you need.
void initsema(struct semaphore *lk, int count)

# 2. Similar with acquiring the lock, but need to check how many threads are in there.
# Return the number of remained threads that can access the section.
int downsema(struct semaphore *lk)

# 3. Similar with releasing the lock. Return the number of remained threads that can access the section.
int upsema(struct semaphore *lk)

Lastly, you need to add predefined functions in def.h to use at the sysfile.c.

Part Three : Create read/write semaphore

Create rwsemaphore.h and declare struct rwsemaphore in rwsemaphore.h. Then, define and implement following functions in rwsemaphore.c.

Download Resource : homework-07

# 1. Initialize anything you need.
void initrwsema(struct rwsemaphore *lk)

# 2. Acquire the shared lock.
void downreadsema(struct rwsemaphore *lk)

# 3. Release the shared lock.
void upreadsema(struct rwsemaphore *lk)

# 4. Acquire the exclusive lock.
void downwritesema(struct rwsemaphore *lk)

# 5. Release the exclusive lock.
void upwritesema(struct rwsemaphore *lk)

Lastly, you need to add predefined functions in def.h to use at the sysfile.c. In this part, you need to consider two types of ordering. Let`s see the following example.

R-W-R contention : While writer thread is a sleep because some reader threads are already holding the lock, another reader thread can acquire the lock repeatedly. In this situation, writer thread cannot get the opportunity to update the data. That is, thread might be scheduled unfairly because of read/write semaphore. Therefore, you need to block the reader thread, if there is writer thread waiting.
W-W contention : FIFO (first-in first-out) ordering is guaranteed between write (exclusive) locks. By doing this, the probability that write thread will not wakeup forever is eliminated.

There are no ordering policies for other situation, so you can implement the ordering policy as whatever you want.

Part Four : Explain result of your test

We upload the test program; sematest.c & rwsematest.c. You can get full credit by explaining result of provided test program. Please, write the reason of result clearly and submit your report as pdf file. Appendix B is our result of tests.

Submit : semaphore.h, semaphore.c, rwsemaphore.h, rwsemaphore.c and pdf file.

We will test the proc.c file that already contains the struct proc *next in struct proc. You don`t need to submit the proc.c file if you only change the struct proc *next.
You can submit other files, but you need to write the reason why you submit these files in pdf file. One or two sentences for each file is enough.

Appendix A : modified codes for sysfile.c

#include "fcntl.h"
#include "semaphore.h"
#include "rwsemaphore.h"
… <bottom of file>
int 
sys_sematest(void)
{
	static struct semaphore lk;
	int cmd,ret = 0;

	if (argint(0, &cmd) < 0)
		return -1;

	switch (cmd) {
		case 0 : initsema(&lk,5); ret = 5; break;
		case 1 : ret = downsema(&lk); break;
		case 2 : ret = upsema(&lk); break;
	}

	return ret;
}

int 
sys_rwsematest(void)
{
	static struct rwsemaphore lk;
	int cmd;

	if (argint(0, &cmd) < 0)
		return -1;

	switch (cmd) {
		case 0 : initrwsema(&lk); break;
		case 1 : downreadsema(&lk); break;
		case 2 :   upreadsema(&lk); break;
		case 3 : downwritesema(&lk); break;
		case 4 :   upwritesema(&lk); break;
	}

	return 0;
}

Appendix B : Our test result of rwsematest

There is no ordering policy about semaphore, so we don`t upload our result. Just explain the result in pdf file.