Thread Library and CPU Scheduling

Project Overview

This assignment is designed to help you gain a better understanding of several operating systems concepts including thread implementation and cpu scheduling. The project consists of two parts. In the first part, you will write a simple thread library. In the second part, you will implement preemptive multi-level feedback queue scheduling. This is intended to be a group project; each team will consist of two students. Write your thread library and cpu scheduler in C (not C++) on Solaris. We use C in this project because it is the language most commonly used to write operating system code.

Use gcc (/usr/um/gnu/bin/gcc) to compile your programs. You should not use any libraries (other than the standard C library libc, which is included automatically). Your thread library must be in a single file (e.g. thread.c).

---

Part I: Thread Library (65%)

I.1. Thread Library Interface

You are to write a library to support multiple threads within a single process. Here are the functions you will implement:

void threadInit(voidFunctionPtr funcPtr, int threadPriority, void *argPtr)

threadInit is called to initialize the thread library. After initializing the thread library, threadInit forks and runs the first thread. This first thread is labeled with the name "main" and is initialized to call the function pointed to by funcPtr with the single argument argPtr. Note that threadInit does not return to the calling function (the function that calls threadInit will never execute again).

void threadFork(char *threadName, int threadPriority, voidFunctionPtr funcPtr, void *argPtr)

threadFork is used to fork a new thread, labeled with the string pointed to by threadName. The function that calls threadFork does not yield the CPU. That is, the newly forked thread is put on the ready queue but is not executed right away. When the newly newly forked thread starts, it will call the function pointed to by funcPtr and pass it the single argument argPtr. threadPriority is not used in part I; it is an integer that specifies initial thread priority (and its value ranges from 0 to 2)

void threadYield()

threadYield causes the current thread to yield the CPU to the next runnable thread.

void threadLock(int lockNum)
void threadUnlock(int lockNum)
void threadWait(int lockNum, int conditionNum)
void threadSignal(int lockNum, int conditionNum)

threadLock, threadUnlock, threadWait, and threadSignal implement monitors in your thread library. Implement Mesa monitors (i.e. the signaling thread keeps the CPU; the signaled thread gets put on the ready queue). Locks are numbered from 0 to (LOCK-1). Each lock has several condition variables, numbered from 0 to (CONDITIONS_PER_LOCK-1).

Here is the file "thread.h". DO NOT MODIFY IT OR RENAME IT. thread.h will be included in your thread library (thread.c), as well as any program that wants to link with your library. Solaris also has /usr/include/thread.h, so make sure you use #include "thread.h", NOT #include . The design of the threadState structure is your responsibility. You need to define your threadState struct in an include file that you include before thread.h so that the compiler will be able to process thread.h without errors.

---

#include   #define STACK_SIZE (256*1024)  #define THREAD_NAME_LENGTH 100  #define LOCKS 10  #define CONDITIONS_PER_LOCK 10   typedef struct threadStruct {    ucontext_t ucontext;    char name[THREAD_NAME_LENGTH];    struct threadStruct *nextPtr; /* pointer to the next thread on the                                    linked list.  This only allows a thread                                    to be part of one linked list. */    struct threadState *statePtr; /* pointer to a structure containing                                    any additional thread state                                    information that you may need. */ } thread;   typedef (*voidFunctionPtr) (void *);   extern void threadInit(voidFunctionPtr funcPtr, int threadPriority, void *argPtr);  extern void threadFork(char *threadName, int threadPriority,                        voidFunctionPtr funcPtr, void *argPtr);  extern void threadYield();  extern void threadLock(int lockNum);  extern void threadUnlock(int lockNum);  extern void threadWait(int lockNum, int conditionNum);  extern void threadSignal(int lockNum, int conditionNum);   extern int interruptsAreDisabled;   

---

I.2. Creating and Swapping Threads

You will be implementing your thread library on Sun workstations running the Solaris operating system. Solaris provides some library calls (getcontext, makecontext, swapcontext) to help implement user-level thread libraries. Here's how to use these calls to create a new thread:

    /*       * Initialize a context structure by copying the current thread's context.       */      getcontext(&threadPtr->ucontext);       /*       * Direct the new thread to use a different stack.       */      threadPtr->ucontext.uc_stack.ss_sp =                      (char *) malloc(STACK_SIZE) + STACK_SIZE;       /*       * Direct the new thread to start by calling threadStart(funcPtr, argPtr).       */      makecontext(&threadPtr->ucontext, (void (*)()) threadStart, 3, funcPtr, argPtr);   

Use swapcontext to save the context of the current thread and switch to the context of another thread. Read the Solaris manual pages for more details. I'm not sure swapcontext saves or restores the floating point registers, so don't use floating point numbers in your program.

I.3. Deleting a Thread and Exiting the Program

A thread finishes when it returns from the function that was specified in threadFork. When there are no runnable threads in the system, your thread library should call exit(0). Don't worry about deallocating the thread context or stack space (it's tricky to deallocate a thread's stack, because it's still running on that stack when you'd like to deallocate it).

I.4 Ensuring Atomicity

To ensure atomicity of multiple operations, your thread library will enable and disable interrupts. Since you are writing a user-level thread library, we can't manipulate the hardware interrupt status. Instead, use the following functions to disable and enable software interrupts (include this code in thread.c).

/*   * Disable/enable interrupts to avoid preemption.  Interrupts will be generated   * as periodic SIGALRM signals that call threadYield if !interruptsAreDisabled.   * interruptDisable and interruptEnable should only be called by the thread   * library.   *   * Interrupts are implemented with a variable instead of using sigprocmask,   * because the signal mask is saved/restored as part of ucontext, and it's   * confusing to have sigprocmasks change as a result of swapcontext.   */  int interruptsAreDisabled = 0;   static void interruptDisable() {      assert(!interruptsAreDisabled);      interruptsAreDisabled = 1;  }   static void interruptEnable() {      assert(interruptsAreDisabled);      interruptsAreDisabled = 0;  }   

Note that interrupts should be disabled only when executing in your thread library's code. The code outside your thread library should never execute with interrupts disabled. E.g. the body of a monitor must run with interrupts enabled and use other mechanisms to implement mutual exclusion.

I.5. Scheduling Order

In part I, the thread scheduler is non-preemptive. Furthermore, all scheduling queues should be FIFO. This includes the ready queue, the queue of threads waiting for a monitor lock, and the queue of threads waiting for a signal.

Here is a short sample program that uses the above thread library, along with the output generated by the program. Make sure you understand how the CPU is switching between two threads (both in function loop). "i" is on the stack and so is private to each thread. "g" is a global variable and so is shared among the two threads.

---

#include  #include "thread.h"   int g=0;   loop(void *id)  {      int i;       printf("loop called with id %s\n", (char *) id);       for (i=0; i<5;> 


parent called with parentThread

loop called with id parent thread 

parent thread:  0       0

loop called with id child thread

child  thread:   0       0

parent thread:  1       1

child thread:   1       2 

parent thread:  2       3

child thread:   2       4

parent thread:   3       5

child thread:   3       6

parent thread:  4       7

child  thread:   4       8  
  
A Few Tips for Part I:  
We suggest you start by implementing threadInit, threadFork, and threadYield.  Don't worry at first about disabling and enabling interrupts.  After you get  that system working, implement the monitors functions.  Finally, add calls to  interruptDisable/interruptEnable to ensure your library works with arbitrary  yield points.  A correct concurrent program must work for any instruction  interleaving.  In other words, we should be able to insert a call to threadYield  anywhere in your code that interrupts are enabled.  
Use assertion statements copiously in your thread library to check for  unexpected conditions.  These error checks are essential in debugging concurrent  programs, because they help flag error conditions early.

---

Part II: Preemptive Multilevel Feedback Queue Scheduling (35%)

The objective of part II is to extend the above thread library so that it supports preemptive multilevel feedback scheduling. Your scheduler must support the concept of time slice or time quantum.

Implement your multilevel feedback scheduler with three ready queues: RQ0, RQ1, and RQ2. The second parameter (threadPriority) in the threadFork library call is an integer (0, 1, or 2) that specifies the initial priority queue for the thread. When a process P first enters the system, suppose that it is put in RQ0. When P is eventually placed in the Running State, if it executes until the end of its assigned time slice, it is placed in RQ1 (back in the Ready State). P is demoted to RQ2 if once again it executes for the duration of the next time slice assigned to it. A process that is blocked OR that yields before it consumes its entire time slice is NOT demoted, i.e., it is returned to the same ready queue.

Scheduling is done on a preemptive basis. RQ0 is the highest priority queue; RQ1 is the next highest; RQ2 is the lowest priority queue. Within each priority queue, preemptive round-robin scheduling is used.

To implement a time slice, you will need to use the UNIX interval timer which allows you to set periodic alarms. (The use of interval timers will be covered in the discussion sections.) The time slice for RQ0 should last several timer interrupts. Design your system such that the time slice for RQ1 is twice as long as the time slice for RQ0, and the time slice for RQ2 is twice as long as the time slice for RQ1.

Finally, extend your multilevel feedback scheduler to support aging. The goal is to promote a process to a higher-priority queue if it spends a certain amount of time waiting in its current queue for service. Aging is an effective technique for dealing with possible starvation associated with multilevel priority queues.

Notes on Project Logistics

Write your thread library and cpu scheduler in C (not C++) on Solaris. We use C in this course because it is the language most commonly used to write operating system code.

Declare all internal variables and functions "static" to prevent naming conflicts with programs that link with your thread library. The variable "interruptsAreDisabled" is not declared static so that our testing programs can detect when interrupts are disabled (and hence not call threadYield).

Use gcc (/usr/um/gnu/bin/gcc) to compile your programs. You should not use any libraries (other than the standard C library libc, which is included automatically). Your thread library must be in a single file (e.g. thread.c).

Reminder on the collaboration policy: You are allowed to consult with others during the conceptualization of a problem, but whatever you turn in for grading must be entirely the original work of just the members of your group.