Description
This programming assignment (PA2) has three main goals. First, you will use the source
code offered by us to understand how one may implement user-level threads. Second,
you will implement the following CPU scheduling algorithms for these user-level threads:
(i) Round Robin (RR) and (ii) Lottery (LOT). You will validate the correctness of your
implementation using some test cases that we will provide. Finally, you will design simple experiments to measure and compare the efficacy of user-level threads as a ”vehicle
of concurrency” vs. kernel-level threads along the following axes: (i) context switching
overheads, (ii) handling of blocking IO, and (iii) using multi-processors.
2 Understanding the Provided Code-Base
After accepting the invitational link to PA2 (please use the account for one of the members
of your team and be sure to indiate the names of both members in all your files), you will
be given to access to your own private repository. Clone the repository for PA2 to obtain
a collection of files containing our code and test cases. If needed, read the Git manual in
files section on canvas as well as in the repository, to clone the repository. You will find
the following files:
• The user-level threads implementation: thread.c, thread.h, my scheduler.c
available in the User Level Thread directory.
• Four parallel programs (”test cases”) based on user-level threads (each contained
within a separate file with a name such as TestFile*.c) for you to test your
scheduler implementation. These files have definitions for functions that you will
pass to the CreateThread() function of the user-level threads implementation.
Each of these files has a main() function which calls the CreateThread() function multiple times to create a certain number of threads, and then call the Go()
function to start scheduling and executing them. You can find these files also in
the User Level Thread directory. Section 2 offers details on CreateThread(),
Go(), and other associated functions.
1
• Two functions that threads comprising your parallel programs will run called (i)
counter() and sleeping(). You will find the prototypes and definitions of these
functions in functions.h and functions.c, respectively which you can find
them in the Kernel Level Thread directory. Both of these functions increment a
counter variable for 10 seconds of real time. Whereas the counter function increments the counter continuously, the sleeping() function sleeps for a short period
of time (less than 10 seconds) before resuming counting. To use these functions, we
have provided a program called kt test.c which you can find it in the same directory. This file uses kernel threads (created using the pthreads library) that run
these functions. By running the program, you can tell each thread to run either the
counter function or the sleeping function by passing an argument to the program. All of these are source codes, which can be compiled using the makefile
included in the Kernel Level Thread directory.
User-level threads implementation: You must develop a clear understanding of how the
provided user-level threads implementation works. Towards this, you will go over the
code and combine this with material covered in class on context switching and user-level
threads (Lectures 4-8). Among other things, you will use this to augment our discussion
in class (Lectures 7-8) on how user-level threads differ from kernel-level threads. The
main functions comprising our user-level threads implementation are:
• int CreateThread(void (*f) (void), int cpuweight): this function creates a new thread with f() 1 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.
The second argument (cpuweight) specifies the weight for a thread when creating
it. For FCFS and RR schedulers this argument is meaningless. For LOT, it represents
the CPU weight of the thread as employed by this scheduling algorithm.
• void Go(): This function is called by your 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
does not return.
• void Dispatch(int sig): The signal handler for alarm signals. The CPU scheduler will be invoked by this function. In our code, the scheduling algorithm is FCFS.
It is assumed that at least one thread exists at all times – therefore there is a stack at
any time. It is not assumed that the thread is in ready state.
1Use this opportunity to learn about function pointers if you are not already familiar with them.
2
• void YieldCPU(): This function is called by the running thread. The function
transfers control to the next thread (in the scheduling order). 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 thread. The thread
is resumed by appending it to the end of the ready list. Returns thread id on success
and -1 on failure. Resuming a ready thread 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 thread id on success and -1 on failure.
• void SleepThread(int sec): The calling thread will sleep until current time
plus sec). The sleeping time is not considered wait time.
• void CleanUp(): Shuts down scheduling, prints relevant statistics, deletes all
threads and exits the program.
Make sure you understand how these functions are implemented. Make sure you understand the data structures used by this code (e.g., what are status t and thread t
and how they relate to the data structures we discussed as part of context switching and
CPU scheduling?) – these are contained in the file threads.h. Make sure you understand the role of various macros that the code defines (e.g., what is x86 64?) Many
macros are important constants:
• MAX NO OF THREADS 100 /* in any state */
• STACK SIZE 4096
• SECOND 1000000
• TIME QUANTUM 1*SECOND
Our code in the User Level Thread folder implements FCFS scheduling. You will be
implementing RR and LOT as described below.
3 Description of Tasks
3.1 Task 1: implement and test schedulers
3.1.1 Implement RR and LOT
You are now ready to implement the RR and LOT algorithms (both covered in class in
Lecture 9). Your scheduler should implement the following interface:
3
• thread t *scheduler(): Returns the thread (from the ready queue) which should
run next.
• void thread enqueue(thread t *t, thread queue t *q): Adds a thread
t to the queue q.
• void InsertWrapper(thread t *t, thread queue t *q): When a thread’s
state changes from SLEEPING to READY or from RUNNING to READY, you have to
add it to the appropriate queue accordingly.
Again, your code will be written in the file my scheduler.c. By now, it should be
clear to you that the (already implemented) FCFS scheduler always returns the thread
at the head of the ready list. Your code for RR or LOT will choose a thread from the
ready list differently based on how these scheduling algorithms work. Note that you
may implement other functions based on your needs as well.
3.1.2 Test the correctness of your RR and LOT implementations
The makefile in User Level Thread directory creates a static library named libutl.a
which contains threads.c, threads.h and my scheduler.c. You must link your
Testfile1.c,Testfile2.c,Testfile3.c, and Testfile4.c against this library to
compile and create the project2 object file. An example of how to do this is already
included in the makefile. After writing the code for LOT and RR scheduler you should
be able to run all 4 test cases for LOT and RR ( $./project2 LOT, $ ./project2
RR). These test cases are given just for illustrative purposes to test your code. As you will
see, each test case consists of creating one or more threads which run specified functions.
When LOT is to be used, certain weights are supplied. For example, CreateThread
(clean up thread, 1) creates a thread which runs the clean up thread function
and has a CPU weight of 1. This function prints the thread id within a loop and when
the condition j=10 occurs, it shuts down scheduling, deletes all the threads and exits. The
following statistics are printed for each thread after clean up:
• num runs: shows the number of runs for each thread for all calls of Dispatch(.),
• total exec time: shows the total execution time for the thread,
• total sleep time: shows the total sleeping time,
• total wait time: shows the total waiting time,
• avg exec time: shows the average execution time,
• avg wait time: shows the average execution time.
NOTE: You are NOT supposed to modify any of the test cases. You should consider
creating more extensive test cases for further testing. The TAs will test your code with
other test cases during grading and your code should still work correctly.
4
3.1.3 Understand given parallel programs and re-implement them using user-level
threads
As mentioned earlier, you have been given two functions, counter() and sleeping(),
implemented using pthreads. Go over these functions, and make your own improvised
counter() and sleeping() functions for use with user-level threads.
3.2 Task 2: evaluate pros and cons of user-level threads
You will conduct the following experiments to compare parallel programs implemented
using kernel-level threads provided by us vs. the same programs implemented using
user-level threads with the RR scheduler.
3.2.1 Context switch time
Use the lmbench benchmark to measure the context switching time for kernel threads
on the lab machine you have chosen to work on. (Among the various measurements
listed under context switching, you should report the time mentioned under the heading
2p/0K. Make sure you understand what this heading means and what the other values
are for.) Use this link to download the latest version of lmbench: http://www.bitmover.
com/lmbench/lmbench3.tar.gz. Make sure you take several measurements for statistical
significance and report the empirical average and variance across these. (Take the time to
read up on these basic statistical concepts if you have forgotten them).
First, you will implement functionality to measure the context switching time within
the user-level threads code. Hint: you could introduce calls to a C library function like
clock gettime() (that has a microsecond or nanosecond resolution) within threads.c
for this.
Launch 2 threads each running this improvised counter() function for 10 seconds
and measure:
1. Total number of context switches.
2. Time taken for each context switch in microseconds. Report the empirical average
and variance across all context switches during your experiment.
3.2.2 Effect of a blocking call
As described earlier, the sleeping() function sleeps for a short period of time (less
than 10 seconds) before resuming counting. Execute the sleeping() function using
kt test.c and compare the work done with the improvised sleeping() function to be
used with User Level Threads. Report your observation with a brief description. You can
use any plotting tool of your choice. To use the plotting script provided in the repository,
type,
$ python plot script.py
5
3.2.3 Using multiple processors
Vary the number of parallel threads within a program where each thread runs the counter()
function. The number of threads should vary as {1,2,4,8,16,32}. Call the summation of
the counter values reported by all threads the work done by the program. Plot how the
work done by a program varies with the number of threads when the program is based
on kernel-level threads vs. user-level threads. Relate observed behavior to the number of
processors on the machine on which you perform this experiment.
4 Submission and Grading
PA2 will be done in groups of 2. A group may choose either member’s repository as their
workplace. Do remember to list both members’ names in all files you submit (including
your report). Just like in PA1, you will submit all your source files, Makefiles, READMEs
(to convey something non-trivial we may need to know to use your code), and a report
containing the results as described earlier. Check out the updated Git Manual, included
in your repository, especially Section 4.
PA2 is worth 10 points (amounting to 10% of your overall grade). The TAs will evaluate your submission based on (i) the quality and correctness of your report and code and
(ii) running your code on some test cases different from the ones you are being given. The
distribution of points will be as follows:
• RR implementation and testing: 2
• LOT implementation and testing): 3
• Context switch time for kernel-level threads using lmbench: 1
• Context switch time for user-level threads: 2
• Effect of I/O blocking: 1
• Multiple processors: 1
Appendix
We offer miscellaneous tips here.
• While using ssh to log into a department Linux machine, please use the port forwarding option by passing the -X option like so:
$ ssh
where xx is some machine number.
6
