Design of an user level thread package

Background reading

1. Read from the OS books the sections that deal with: CPU scheduling, threads, FIFO, FCFS, critical sections. Read Stevens for IPC.
2. demo.c. Try it. This C code gives an example of context switching (user-level) and round-robin scheduling of two processes. Read the necessary man pages and figure out how it works.

Build your own scheduler and threads package

1. Implement a round-robin pre-emptive scheduler and context switching. You may use the hack of demo.c.
2. Design data structures for thread entities.
3. Implement the following functions:
   • int CreateThread(void (*f)(void)) - this function creates a new thread with f() being its entry point. The function returns the created thread id (>= 0) or (-1) to indicate failure. It is assumed that f() never returns. A thread can create other threads! The created thread is appended to the end of the ready list (state = READY). Thread ids are consecutive and unique, starting with 0.
   • void Go() - This function is called by the main process to start the scheduling of threads. It is assumed that at least one thread is created before Go() is called. This function is called exactly once and it never returns.
   • int GetMyId() - This function is called within a running thread. The function returns the thread id of the calling thread.
   • int DeleteThread(int thread_id) - deletes a thread. The function returns 0 if successful and -1 otherwise. A thread can delete itself, in which case the function doesn't return.
   • void Dispatch(int sig) - the thread scheduler. This function is called by the interval clock interrupt and it schedules threads using FIFO order. It is assumed that at least one thread exists all the time - therefore there is a stack in any time. It is not assumed that the thread is in ready state.
   • void YieldCPU() - this function is called by the running thread. The function transfers control to the next thread. The next thread will have a complete time quantum to run.
   • int SuspendThread(int thread_id) - this function suspends a thread until the thread is resumed. The calling thread can suspend itself, in which case the thread will YieldCPU as well. The function returns id on success and -1 otherwise. Suspending a suspended thread has no effect and is not considered an error. Suspend time is not considered waiting time.
   • int ResumeThread(int thread_id) resumes a suspended process. The process is resumed by appending it to the end of the ready list. Returns id on success and -1 on failure. Resuming a ready process has no effect and is not considered an error.
   • int GetStatus(int thread_id, status *stat) - this call fills the status structure with thread data. Returns id on success and -1 on failure.
   • void SleepThread(int sec) - the calling process will sleep until (current-time + sec). The sleeping time is not considered wait time.
   • void CleanUp() - shuts down scheduling, prints the following statistics, deletes all threads and exits the program.

1. int CreateThreadWithArgs(void *(*f)(void *), void *arg) f is a ptr to a function which takes (void *) and returns (void *). Unlike the threads so far, this thread takes arguments, and instead of uselessly looping forever, returns a value in a (void *). This function returns the id of the thread created.
2. void *GetThreadResult(int tid) waits till a thread created with the above function returns, and returns the return value of that thread. tid is the id of thread. This function, obviously, waits until that thread is done with.

Hints:

1. The C calling convention says that params are pushed on the stack. So, to pass an argument to the function, put the argument (the void ptr) at the top 4 bytes of the stack (make sure it's in little endian order!), and then decrement the stack ptr.
2. Where does a function (thread) return to? To the return address. Where is the return address? On the stack (surprise!). It comes after the params. So after pushing the param, push the return address, and again decrement the stack ptr by 4.
3. But where to return to? To a procedure which does some wrapping up, like setting the state of the thread to FINISHED, so that the dispatcher doesn't try to schedule it again, and storing the return value somewhere.
4. Finally, where is the return value. On Intel machines, at least, it's returned in the eax register. That's part of the C calling convention : return values are in eax. So all you have to do is get the contents of eax. There are two ways to do that:
   1. inline assembly
   2. Write a three line assembly routine, and call it like any normal function from your program:

                ------ geteax.asm -----
                  .text
                  .align 4
      
                  .globl geteax
                  geteax : ret
      
                ------ end of geteax.asm ----
               

      To call this, declare a prototype in your C program : extern void * geteax(); and then link in geteax.o like any other normal program.
   3. GetThreadResult will have to wait till the thread is over. Use semaphores.

Statistics:

1. Total number of thread that were created.
2. Total number of thread that were deleted.
3. Number of threads at shutdown time (Do not use (1) - (2) !! why?)
4. Elapsed time between Go() and CleanUp() in msec.
5. For each of the still exiisting threads:
   1. thread id.
   2. state (running, ready, sleeping, suspended).
   3. number of bursts (none if the thread never ran).
   4. total execution time in msec(N/A if thread never ran).
   5. total requested sleeping time in msec (N/A if thread never slept).
   6. average execution time quantum in msec (N/A if thread never ran).
   7. average waiting time (status = READY) (N/A if thread never ran).

Constant test values:

STACK_SIZE 4096

TIME_QUANTUM 1*SECOND