Operating Systems Concepts Assignment Two
CMPT 332 CMPT 332 Operating Systems Concepts Assignment Two Due: Friday October 22nd, 8:00 pm – late submissions will not be accepted General Instructions: This assignment consists of three parts. It is to be done in self-selected groups of at most two students, with each group member contributing approximately equally to the solution for each part. Solutions must in be in C, and should work on the Department’s Linux machines. You must use –Wall, and revise your code as needed to remove all warnings. Submission Instructions: All assignment submissions must use the Moodle online submission system. Only one team member should submit the assignment solutions, with both team members clearly identified in the submission documentation. The other team member should simply submit a file called “partner.txt” that gives the name and NSID of the partner who submitted the solutions. The submission for each of the three assignment parts should be a single tar file that has been created using “tar –cvf” on one of the Department’s Linux machines. Each of the three tar files should include the contents of a directory into which all of the relevant (and no irrelevant (!)) files for that part have been placed. In particular, the directory for each part should include: source file(s), a single makefile, and a single separate documentation file (plain text or PDF format – no other formats). Note that there should be no .o files or executable files, for example. Make sure that you try unpacking your submitted tar file and testing what you submitted, so as to ensure that nothing went wrong when preparing your submission. With respect to the documentation file for each part – think carefully about what the marker needs to know to evaluate what you have done. For each of the xv6 parts (i.e., Parts A and B), the marker will need to know exactly what your changes were to xv6. More generally, you should always give an outline of what you have done, and carefully describe any limitations that your solution has. If the markers discover limitations that you have not described in your documentation, the markers will conclude that your testing was insufficient and you will be docked marks accordingly. Finally, note the additional requirements described below for the documentation file for Part B. PART A: Instrumenting xv6 (10 marks) In this part you will add some instrumentation to xv6 that will allow measurements of performance with different processor scheduling policies. Extend the proc structure in proc.h with the following fields: created, ended, and running, which will be used to record (in ticks) the time at which the process was created, the time at which the process terminated, and an estimate of the running time of the process, respectively. The created field should be filled in when a process is created, and the ended field when a process terminates (note that a process may stay in the “zombie” state for some period of time after termination, which should not have any effect on ended). (A complication: when accessing the ticks variable you should use an instruction sequence like that used in sys_uptime() in sysproc.c.) The running field for any currently running processes should be incremented by 1 whenever ticks is incremented. So that this information can be retrieved from the OS, add a new system call waitstat. Your new system call should operate the same as wait, except that it should take three arguments instead of just one argument, with the additional arguments, each of type uint*, used to provide the turnaround time of the waited-for process (from ended – created) and an estimate of its running time (from running). Finally, write a userspace program test.c that you can use to test your instrumentation and your new system call. Your program test.c should take four positive integers K, L, M, and N as parameters. Your program should fork 45 child processes in total. Each of the first 15 of these should perform the following calculation, and then call exit(): ∑(∑(? − ?) ? ?=1 ) ? ?=1 Each of the next 15 child processes that your program forks should perform the same calculation except using M rather than N. Each of last 15 child processes should perform the same calculation except using L rather than N. After forking all 45 children, your program should wait for them all to finish, using waitstat. Your program should then calculate the sum of the turnaround times and the sum of the estimated running times for each group of 15 child processes separately, print these values (clearly indicating which group of child processes each of the sums is for), and then exit(). Note that your program will need to save the process IDs returned by the fork operations, so that you can determine which group each child belongs to when your waitstat calls return. PART B: A new xv6 scheduler (30 marks) In this part you will implement a variant of MLFQ scheduling. Each process will have an associated current priority which can be “high”, “medium”, or “low”. New processes are initially given high priority. A medium-priority process should be selected to run next only if there are no runnable high- priority processes, and similarly a low-priority process should be selected to run next only if there are no runnable high-priority or medium-priority processes. After a high-priority process has been selected to run once, its priority should be changed to medium. After a medium-priority process has been selected to run mtimes (more) times, its priority should be changed to low. Add a line to param.h in which the value of mtimes is defined. After every moveup times that a scheduling decision is made, selecting a process to run, all medium and low priority processes should have their priority set to high. Add a line to param.h in which the value of moveup is defined. To make things simpler, rather than implement a queue of runnable processes of each priority, you can simply keep track of the current priority of each process in its proc structure. When a scheduler thread is swtch’d to and begins looking for a new process to run, look for the first (starting after the proc structure of the process that had been running, as in the existing scheduler) runnable high priority process. If none is found after looking at all NPROC proc structures, then look for a runnable high or medium priority process. If none is found, then look for the first runnable process of any priority. Your documentation file should include a discussion, supported by example test cases using test.c, of the performance comparison between your new scheduler and the existing xv6 scheduler. This discussion should also address the impact of the values chosen for mtimes and moveup. What are the strengths and weaknesses of your new xv6 scheduler? What improvements do you think you could make to it, without excessive implementation difficulty? PART C: A memory allocator (30 marks) In this part you will implement a memory allocator. Specifically, you should implement the following routines and provide a makefile that compiles them as a library archive (i.e., .a file). Your allocator must use the doubly-linked free list approach that was discussed in class, with each chunk having both a 16-byte header and a 16-byte footer. int M_Init(int size): The purpose of M_Init() is to initialize your memory allocator. The calling program should invoke it only once. It takes as its argument the size of the memory space (in bytes) that your allocator should manage. Round this up to the nearest multiple of 16 bytes. You must then use mmap() to request this space from the OS. The function should return 0 on success and -1 for a failure return. void *M_Alloc(int size): M_Alloc() is used to allocate a chunk; its argument is the requested size in bytes. The function should return a pointer to the start of the allocated chunk, or NULL if the request fails, e.g. satisfying the request is not possible owing to there not being enough contiguous free space. The actual size of the allocated chunk should be size rounded up to the nearest multiple of 16 bytes. Allocation should use the next fit policy. int M_Free(void *p): This function is used to free the chunk with address p. It should return 0 on success and -1 for failure. You must coalesce free space using the method described in class. void M_Display(): This function should print the addresses and sizes of the free chunks to stdout. Some tips: - Read Chapter 17 of the text, as well as the Moodle lecture notes for Friday September 24th. - Start simple (e.g. without coalescing), get it working, and then add more complexity incrementally, testing each new addition as it is made. - Think about scenarios that should trigger a graceful failure return (such as, program calls M_Init twice, or M_Free with an invalid pointer), and about special cases (e.g., the only chunk in the free list is deleted from the list) http://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf