This project consists of two separate parts. The first part is on Inter-Process Communication (IPC) with Messages, and the second is on CPU Scheduling.
1. Inter-Process Communication with Messages (40 points)
One of the Inter-Process Communication (IPC) mechanisms we have discussed is message passing; processes can communicate with each other by sending messages to
and receiving messages from the same mailbox.
2. CPU Scheduling (60 points)
The basic DLXOS right now only has round-robin preemptive scheduling. In
this lab, we will add a lottery scheduler into DLXOS.
In this assignment you are to implement a lottery scheduler. A lottery scheduler assigns each process some number of tickets, then randomly draws a ticket among those allocated to ready processes to decide which process to run. That process is allowed to run for a set time quantum, after which it is interrupted by a timer interrupt and the process is repeated.
The number of tickets assigned to each process determines both the likelihood that it will run at each scheduling decision as well as the relative amount of time that it will get to execute. Processes that are more likely to get chosen each time will get chosen more often, and thus will get more CPU time.
Note that we don't have to dole out actual tickets. We can just keep a count of how many tickets each process has {n1, n2, ..., nm} (assuming m processes), how many tickets have been doled out altogether (N), and the fraction of the total each process has {f1, f2, ..., fm} = {n1/N, n2/N, ..., nm/N}. Then, to decide which process we should run at each scheduling decision, we can compute a random number p between 0 and 1. If 0 < p < f1 then we run process 1. Else if f1 < p < f1+f2, we run process 2. Else if f1+f2 < p < f1+f2+f3, we run process 3. Etc.
One goal of best-effort scheduling is to give I/O-bound processes both faster service and a larger percentage of the CPU when they are ready to run. Both of these things lead to better responsiveness, which is one subjective measure of computer performance for interactive applications. CPU-bound processes, on the other hand, can get by with slower service and a relatively lower percentage of the CPU when there are I/O-bound processes that want to run. Of course, CPU-bound processes need lots of CPU, but they can get most of it when there are no ready I/O-bound processes. One fairly easy way to accomplish this in a lottery scheduler is to give I/O-bound processes more tickets - when they are ready they will get service relatively fast, and they will get relatively more CPU than other non-I/O-bound processes.
The key question is how to determine which processes are I/O-bound and which are CPU-bound. One way to do this is to look at whether or not processes block before using up their time quantum. Processes that block before using up their time quantum are doing I/O and are therefore more I/O-bound than those that do not. On the other hand, processes that do not block before using up a time quantum are more CPU-bound than those that do. So, one way to do this is to start with every process with some specified number of tickets. If a process blocks before using up its time quantum, give it another ticket (up to some set maximum, say 19). If it does not block before using up its time quantum, take a ticket away (down to some set minimum, say 1). In this way, processes that tend to do relatively little processing after each I/O completes will have relatively high numbers of tickets and processes that tend to run for a long time will have relatively low numbers of tickets. Those that are in the middle will have medium numbers of tickets.
This system has several important parameters: time quantum, minimum and maximum numbers of tickets, speed at which tickets are given and taken away, etc.
In this project, you will modify the scheduler for DLXOS.
The prototype of create_process has been changed to facilitate passing in parameters p_nice and p_info . The new prototype is
void process_create(int p_nice, int p_info, char * args...);
For lottery scheduling, p_nice corresponds to the number of tickets given to the process. It can range from -20 to 19, but for all processes, specifying a negative value or zero will be ignored and default to 1. Each time the scheduler is called, it should randomly select a ticket (by number) and run the process holding that ticket. Clearly, the random number must be between 0 and nTickets-1, where nTickets is the sum of all the outstanding tickets. You may use the random() call to generate random numbers and the srandom() call to initialize the random number generator (these calls function the same way they do in Unix).
For dynamic priority assignment, you should modify lottery scheduling to decrease a process's priority by 1 each time it receives a full quantum, and increase its priority by 1 each time it blocks without exhausting its quantum. A process's priority should never drop below 1 and should never exceed 19.
Copy /home/shay/g/ee469/labs/common/lab3.tar to your lab directory. After you untar it (tar xvf), it will becomes lab3 which contains 2 directories, lab3_1 and lab3_2. Do question 1 and 2 in lab3_1 and 3-5 in lab3_2. A makefile is provided for you. Typing "make" will create all the executables for you. Do not modify the makefile. We will test your program with a different makefile. You should not need to generate any new file to complete your work.
You will have to implement 6 functions, of which the first one is an internal routine and the remaining five are system calls.
Note the user interface and prototype of these functions has been defined for you. The corresponding system calls are void mbox_open(int id), int mbox_close(int id), int mbox_send(int id, int len, char* mesg), int mbox_recv(int id, int * len,char* mesg) and int mbox_stat(id). Look at usertraps.s and traps.c to see how they are used. In this lab, we assume that we have 16 mailboxes and that each has a buffer size of 50 bytes. The constants MAX_MBOXES and BUFFER_SIZE have been defined for you in mbox.h. Do not change any of the predefined constants. Put your solution in mbox.h and mbox.c.
You are to create 5 producer processes, each sending a message "hello world!" one word at a time to the same mailbox. Also, each message sent should be appended with the process number (a value to be passed in, not the pid). So process 0 will send out 2 messages, "hello 0" and "world!0". Another 5 processes(5-9) will each receive 2 messages, prepend each message with its process number, and print them out in strings ended with an "\n". It will print each message immediately after it receives one. So if process 5 receives both messages from process 0 it will print out "5hello 0" and "5world!0" on 2 separate lines. Put your solution in userprog2.c. If you need additional files for your producer and consumer, use q2_producer.c and q2_consummer.c.
Start by implementing a lottery scheduler where every process starts with the number of tickets given by p_nice. The number of tickets does not change.
The variable p_info is passed in during process_create() Every time a process gets context switched out, check the the value of p_info for that process. If it equals 1, the scheduler should print out how much CPU time it has consumed so far. DLXOS does not have a timer so you will not be able to get exact timing info. So implement it in the following way. Each time quantum is 0.1 s. So if a context switch happens by a timer interrupt when a process uses up a time quantum, add 0.1 s to the time the process has run so far. For other types of context switch, do not add any time to the process run time. It should print the messages "Process pid has run for x.xxx s","Process pid 's priority is #". 3 format strings (TIMESTRING1, 2, and 3)are provided in process.c.
Modify your scheduler to have dynamic priorities, as discussed above. Also implement yield(). A process calling yield() will cause an immediate context switch and its priority should be upgraded. Implement the system call yield() (Yes, you need to write the traps for this problem. Use the trap vector 0x433. It is already defined in traps.h . ).
Hint: See where ProcessSchedule() gets called to figure out what caused the context switch (traps.c). Then you can adjust priorities, as discussed above.
Make
five versions of your codes if necessary and call it lab3_q1, lab3_q2, lab3_q3,
lab3_q4, and lab3_q5.
All your modifications have to be saved in the these directories and only these
directories should be turned in by
turnin -c ee469 -p labX-Y lab3_q1 lab3_q2 lab3_q3 lab3_q4 lab3_q5
lab3_q1: your dlxos/ directory containing solutions for question 1
lab3_q2: another version of the dlxos/
containing solutions for question 2
lab3_q3: another version of the dlxos/
containing solutions for question 3
lab3_q4: another version of the dlxos/ containing
solutions for question 4
lab3_q5: another version of the dlxos/
directory containing solutions for question 5
Please include all of the files you used to build your project: source code, Makefiles, and any other scripts you may have used.
In addition, please include a README
file in each directory lab3_1 and lab3_2 to explain anything unusual to the TA
- testing procedures, etc.
Your solution should only print out what was specified
in the assignment. i.e. it should not contain any
debug printf statements. Not following this rule will
results in points deduction by the TA.
Note : The same person who turn in assignment for their group in lab 2 should do the turnin in lab 3. Only those accounts will be graded.
Make sure that each of the directories that you turn in contains an appropriate Makefile. The Makefile should be written in such a way that after typing make in the problem directory, all the executables will automatically be produced. So the Makefile for q2 should be written in such a way that after typing make in the directory q2, it should make all the executables (including os.dlx.obj, q2.dlx.obj, and any other programs you might have) and move the executables to the directory ../execs.
The same also holds for other directories. This is the preferred way for this assignment. If for some reason you cannot write such a Makefile, you may put detailed instructions about how to make various programs and how to run them in your README. But in that case you may loose some points depending on the complexity of the instructions. Try to stick to the preferred way so that you will not loose any points. If you do not know how to write a makefile, do man make. If you still do not understand, ask your TA.
IMPORTANT: do NOT submit object files or other files generated by the DLX compiler or assembler. Every file in the handin directory that could be generated automatically by the DLX compiler or assembler will result in a warning from your TA of a 5-point deduction from your project grade. To do so, you should do 'make clean' before you turn in.