Description

Updated
Total: 30 Marks
Key Points:
1. The assignment has to be done individually.
3. We shall use Ubuntu Linux 18.04 to test the assignment. If the assignment does not work, it is the student’s fault.
The assignment has 5 parts.
1 Installing and Testing xv6 [1]: 3 Marks
• xv6 is available at :
• Instructions to build and install xv6 can be found here:
• Check scripts can be downloaded from http://www.cse.iitd.ernet.in/
2 System calls: 7 Marks
In this part, you will be implementing system calls in xv6. These are simple system calls and form the basis for the subsequent parts of the assignment.
• System call trace:
Let us define two states within the kernel: TRACE ON and TRACE OFF. If the state is equal to TRACE OFF, which is the default, then nothing needs to be done. However, it is possible to set the state to TRACE ON with a special system call, which we shall see in the next bullet point. The state can be subsequently reset (set to TRACE OFF) as well.
Whenever the state changes from TRACE OFF to TRACE ON, you need to enable a custom form of system call tracing within the kernel. This will keep a count of the number of times a system call has been invoked since the state changed to TRACE ON.
Let us define a new system call called sys print count. It will print the list of system calls that have been invoked since the last transition to the TRACE ON state with their counts. A representative example is shown below. The format is as follows. There are two columns separated by a single space. The first column contains the name of the system call, and the second column contains the count. There are no additional lines; the system call names are sorted alphabetically in ascending order.
sys_fork 10 sys_read 20 sys_write 0
• Toggling the tracing mode:
Let us now add one more system call, sys toggle() that toggles the state: if the state is TRACE ON sets it to TRACE OFF, and vice versa. A program to toggle the state looks like this:
#include “types.h”
#include “user.h”
int main(int argc, char *argv[])
{
// If you follow the naming convention, the system call
// name will be sys_toggle and you
// call it by calling the function toggle();
toggle(); exit();
}
Add User Programs to xv6:
– Create two files called, “user toggle.c”, and “print count.c” in the root directory.
– Add a line “ user toggle” and “ print count” in the Makefile. The relevant part of your Makefile should look like this:
UPROGS=
_cat
_echo
_forktest
_grep
_init
_kill
_ln
_ls
_mkdir
_rm
_sh
_stressfs
_usertests
_wc
_zombie
_user_toggle
_print_count
The only change in this part is the last two lines.

– Also make changes to the Makefile as follows (the only change is on the second line):
EXTRA= user_toggle.c print_count.c
mkfs.c ulib.c user.h cat.c echo.c forktest.c grep.c kill.c ln.c ls.c mkdir.c rm.c stressfs.c usertests.c wc.c zombie.c printf.c umalloc.c
README dot-bochsrc *.pl toc.* runoff runoff1 runoff.list
.gdbinit.tmpl gdbutil
1
2
3
4
5
6
7
– Now, enter the following commands to build the OS in the xv6 directory.
make clean make
– If you want to test the user program, launch xv6 using the command make qemu-nox
After xv6 has booted in the new terminal, you can type ls
This will show user toggle and print count in the list of available programs.
• Add system call: sys add
In this part, you have to add a new system call to xv6. This system call should take two integer arguments and return their sum. Create a system call, sys add, and then create a user-level program to test it.
• Process List: sys ps
In this part you have to add a new system call, sys ps, to print a list of all the current running processes in the following format:
pid:<Process-Id> name:<Process Name> eg:
pid:1 name:init pid:2 name:sh
Similarly for this part, create a new user program, which should in turn call your sys ps system call.
3 Inter-Process Communication: 10 Marks
In this part, you have to create system calls for communication between the processes. You are not allowed to use sys pipe for this purpose (which is already present in the xv6 code).
3.1 IPC system calls for unicast communication [5 Marks]
You need to implement a system call for this purpose, which should be named sys send. The length of the message is fixed to 8 bytes. The system call will take three arguments, int sys_send(int sender_pid, int rec_pid, void *msg)
• sender pid: pid of the sender process.
• rec pid: pid of the receiver process.
• msg: pointer to the buffer that contains the 8-byte message.
The return type is int: 0 means success and any other value indicates an error.
Similarly we have another function for the receiver.
int sys_recv(void *msg)
• msg: Pointer to the buffer where the message from the sender is stored (after sys recv returns). This is a blocking call.
3.2 Multicast [5 Marks]
In the previous section, you implemented a unicast model of communication. In this section, you need to implement a multicast model of communication. In the basic unicast model, one sender sends to only one receiver. In the multicast model, one sender sends a single message to multiple receivers using a single system call. The signature of the function is:
int sys_send_multi(int sender_pid, int rec_pids[], void *msg)
4 Distributed Algorithm: 5 Marks
In this part, you will compute the sum of the elements in an array in a distributed manner. Modern systems have multiple cores, and applications can benefit from parallelizing their operations so as to use the full capability of the hardware present in the system. Use your unicast and multicast primitives.
The task here is simple. Calculate the sum of an array, subject to the following conditions:
• Total number of elements in the array: 1000.
• Elements are from 0 to 9.
• A sample input dataset can be downloaded from here:
A sample program has been provided. It needs to be completed. The program takes two command line arguments: htypei and hinput file namei. If the type is 0, you use unicast communication, and if it is 1, you use multicast based communication.
Some more points:
1. In the unicast version create (assign) a coordinator process. This will collect the partial sums from the rest of the processes, compute and print the sum. The format of the output is specified in the sample program.
2. In the multicast version, you need to extend the program to compute the variance. Divide your program into two phases. In the first phase, you have the standard unicast version, where all the processes send their partial sums to the coordinator. The coordinator then computes the mean and then multicasts it to all the worker processes. The worker processes then unblock themselves, compute the sum of the squares of the differences about the mean (second phase). Then the worker processes send the partial sums to the coordinator. The coordinator computes and prints the variance.
3. Limit the number of processes to 8. Note that your program should run for 8 processes.
5 Report: 5 Marks
The report should clearly mention the implementation methodology for all the parts of the assignment. Small code snippets are alright, additionally, the pseudocode should also suffice.
• Distributed Algorithm: How exactly does your algorithm work?
• IPC: Explain the implementation of the interrupt handler • Any other details that are relevant to the implementation.
• Submit an OpenOffice presentation.
• Say what you have done that is extra.
6 Submission Instructions
• We will run MOSS on the submissions. We will also include last year’s submissions. Any cheating will result in a zero in the assignment, a penalty as per the course policy and possibly much stricter penalties (including a fail grade and/or a DISCO).
• There will be NO demo for assignment 1. Your code will be evaluated using a check script (check.sh) on hidden test cases and marks will be awarded based on that.
How to submit:
1. Copy your report in the xv6 root directory.
2. Then, in the root directory run
make clean
tar czvf assignment1_<entry_number>.tar.gz *
This will create a tar ball with name, assignment1 h entry numberi.tar.gz in the same directory. Submit this tar ball on moodle.
References