Description
1 Goals
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, youwillimplementthefollowingCPUschedulingalgorithmsfortheseuser-levelthreads: (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
AfteracceptingtheinvitationallinktoPA2(pleaseusetheaccountforoneofthemembers ofyourteamandbesuretoindiatethenamesofbothmembersinallyourfiles),youwill 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()andsleeping(). Youwillfindtheprototypesanddefinitionsofthese 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 incrementsthecountercontinuously,the sleeping() functionsleepsforashortperiod 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-levelthreadsimplementation: Youmustdevelopaclearunderstandingofhowthe provided user-level threads implementation works. Towards this, you will go over the codeandcombinethiswithmaterialcoveredinclassoncontextswitchinganduser-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): thisfunctioncreates 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. Thesecondargument(cpuweight)specifiestheweightforathreadwhencreating it. ForFCFSandRRschedulersthisargumentismeaningless. ForLOT,itrepresents the CPU weight of the thread as employed by this scheduling algorithm. • void Go(): Thisfunctioniscalledbyyourprocesstostarttheschedulingofthreads. 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): Thesignalhandlerforalarmsignals. TheCPUschedulerwillbeinvokedbythisfunction. Inourcode,theschedulingalgorithmisFCFS. 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): Resumesasuspendedthread. Thethread isresumedbyappendingittotheendofthereadylist. Returnsthreadidonsuccess and -1 on failure. Resuming a ready thread has no effect and is not considered an error. • int GetStatus(int thread id, status *stat): Thiscallfillsthestatusstructure 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(): Returnsthethread(fromthereadyqueue)whichshould 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): Whenathread’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 includedinthe makefile. AfterwritingthecodeforLOTandRRscheduleryoushould be able to run all 4 test cases for LOT and RR ( $./project2 LOT, $ ./project2 RR).Thesetestcasesaregivenjustforillustrativepurposestotestyourcode. Asyouwill 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 theconditionj=10occurs,itshutsdownscheduling,deletesallthethreadsandexits. 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 Asmentionedearlier,youhavebeengiventwofunctions,counter()andsleeping(), implementedusingpthreads. Gooverthesefunctions,andmakeyourownimprovised 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 versionof lmbench: https://www.bitmover. com/lmbench/lmbench3.tar.gz. Make sure you take several measurements for statistical significanceandreporttheempiricalaverageandvarianceacrossthese. (Takethetimeto 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()(thathasamicrosecondornanosecondresolution)withinthreads.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.candcomparetheworkdonewiththeimprovisedsleeping()functiontobe usedwithUserLevelThreads. Reportyourobservationwithabriefdescription. Youcan 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 Varythenumberofparallelthreadswithinaprogramwhereeachthreadrunsthecounter() 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 onkernel-levelthreadsvs. user-levelthreads. Relateobservedbehaviortothenumberof processors on the machine on which you perform this experiment.
4 Submission and Grading
PA2willbedoneingroupsof2. Agroupmaychooseeithermember’srepositoryastheir 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. PA2is worth10points(amounting to10%of youroverallgrade). TheTAswillevaluate your submission based on (i) the quality and correctness of your report and code and (ii)runningyourcodeonsometestcasesdifferentfromtheonesyouarebeinggiven. 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 <username@cse-p204instxx -X where xx is some machine number.
