CMSC 412 Project 3

1. Overview

This project has two parts.

CPU Scheduling.  As you might have already noticed, the default CPU scheduling algorithm in GeekOS is priority-based preemptive round-robin. You will add your own CPU scheduling algrorithm. You will add a system call to choose between them. To see the difference between them, you will add a system call to get the system's current time.

Semaphores.  You will implement semaphores, a simple synchronization construct for threads. You will provide system calls to create, use and terminate semaphores.

Notes

• Grading Criteria
• Discussion slides

• Relevant user programs for testing in src/user/ (should already be there): sem-p1.c, sem-p2.c, sem-p3.c, sched1.c, sched2.c, sched3.c, schedtest.c, semtest.c, semtest1.c, semtest2.c, sem-ping.c, sem-pong.c, workload.c

2. Scheduling

The choice of scheduler should be implemented within the function Get_Next_Runnable() (see kthread.c). The choice should not show up in the arguments of this function. A call to Get_Next_Runnable() should return without indicating the scheduling algorithm being used; the caller should learn only that some thread has been selected.

You are free to create a new scheduling algorithm that is optimized for anything you want. However, there are two constraints. First, you need to explain its goals, i.e., what it is intended to optimize. When you turn in your code, put your explanation (justified with measured elasped times) in a REAME.scheduler file in the top level of the class project directory. Second, make sure that your algorithm is no worse than the default algorithm in the time it takes to complete user programs. Otherwise the tester may timeout and give up on your submission.

You will provide the following two system calls so that you can run user programs to compare your scheduler against the default.

Set_Scheduling_Policy(policy)

int Set_Scheduling_Policy(int policy): If parameter policy is 0, the system should switch to its built-in round robin scheduling. If parameter policy is 1, the system should switch to your scheduler. For other values of this parameter, return EINVALID.

Get_System_Time

unsigned long Get_Time_Of_Day(): Return g_numTicks

You can obtain the elapsed time of a user program's execution by invoking the system call at the beginning and at the end of the program (in the user code). Use such measurements to compare your scheduler versus the default scheduler; include them in your justification in README.scheduler.

Note:  This elapsed time is known as wall clock time. It includes the time when the system is not doing anything on behalf of the program's process, e.g., when the process is switched out but runnable, when the process is waiting on an IO device that is serving another process. The time during which the process is executing on the CPU is referred to as process time (or sometimes virtual time); this project is not concerned with obtaining that.

Additional Reading

3. Semaphores

You will augment GeekOS with semaphores so that user programs can open them, use them for thread synchronization, and close them.

For specification purposes, it is convenient to view each semaphore as having the following attributes while it exists. ("For specification purposes" means that these attributes need not be explicitly present in your implementation.)

• name: at most 25 characters.
• semaphore id (or SID): integer.
• value: non-negative integer.
• open users: set of user threads that currently have the semaphore "open".

The name is supplied by user programs. The SID is supplied by the kernel; it points to a particular semaphore data structure (which you will implement) in the kernel. The SIDs come from a fixed pool of 20 SIDs, initially all available.

You will add the following four system calls to manipulate semaphores. Each is described in more detail below.

int Open_Semaphore(const char *name, int ival)
int P(int sem)
int V(int sem)
int Close_Semaphore(int sem)

Open_Semaphore(name,ival)

int Open_Semaphore(const char *name, int ival): If a semaphore of the given name does not currently exist and there is an available SID, the kernel should return an available SID and initialize the value of the associated semaphore data structure to ival. The caller now has the semaphore open. The SID is now not available. If a semaphore of the given name does not currently exist and there is no available SID, the kernel should return ENOSPACE. No semaphore is created. If a semaphore with the given name currently exists, the kernel should return the SID of the semaphore. The caller now has the semaphore open. (The ival is ignored.) If name is longer than 25 characters, the kernel should return ENAMETOOLONG. No semaphore is created.

Close_Semaphore(sem)

int Close_Semaphore(int sem): Returns EINVALID if sem is not an SID or if the caller does not have semaphore (with SID) sem open. (The latter also covers the case where semaphore sem does not currently exist.) Otherwise returns 0. The caller no longer has the semaphore open. If the semaphore now has no open users, it is terminated and SID sem becomes available.

P(sem) and V(sem)

int P(int sem): Returns EINVALID if sem is not an SID or if the caller does not have the semaphore sem open. If the caller has the semaphore open: Returns 0 only when the semaphore's value is greater than zero and simultaneously decreases the semaphore's value by 1. Blocks otherwise.

int V(int sem): Returns EINVALID if sem is not an SID or if the caller does not have the semaphore with SID sem open. If the caller has the semaphore open: returns 0 and simultaneously increases the semaphore's value by 1.

Each semaphore data structure should contain a thread queue for its blocked threads. To block a thread (in a "P" operation), you can use the Wait function in the kernel. To wake up a thread (in a "V" operation), you can use the Wake_Up_One function. (If you want to wake up all the threads in a thread queue, you can use the Wake_Up function. Look at kthread.h and kthread.c to see how these functions are declared and used.

You have some options regarding the implementation of V(sem) when processes are blocked on semaphore sem. One option is to select one or more blocked processes and restore each to redo the P(sem) in which it was blocked. Another option is to select one (and only one) blocked process and restore it to just after the P(sem) in which it was blocked. (Here, the V operation is also simultaneously executing the blocked thread's P operation. Think about how the semaphore's value should be updated.)

Thread termination

If a thread exits while it has one or more semaphores open, the kernel should close this thread from every such semaphore. (So it makes sense to have a semaphore-closing function in the kernel which can be invoked by both the Sys_Close_Semaphore() function and some function involved in terminating user threads.)

Notes

In order not to clobber syscall.c with too much functionality, put your semaphore implementation in sem.h and sem.c. Semaphore operations must be executed atomically, i.e., implemented within a critical section.

Since you need to have multiple processes running concurrently to test the functionality you will implement, your shell should be able to launch processes in the background.

In this and other projects, you will rely heavily upon a list data structure. An implementation has been provided to you in list.h file. Familiarize yourself with its syntax and functionality. It can be a little tricky to understand the syntax because functions are written using #define. Naturally you are always free to extend, modify, or write your own implementation that would better suit your needs.

Additional Reading

4. Summary: New System Calls

5. Testing your code

The files we provided can be used to test your semaphores or scheduling algorithm:

• workload.c is used for testing spawn with arguments and the scheduling algorithm:

  % /c/workload.exe [algorithm]
  where algorithm can take any of the values rr or mys .

• sem-ping.c and sem-pong.c create a nice effect when you launch them concurrently:

  % /c/sem-ping.exe &
  % /c/sem-pong.exe