CISC 3320 3.0 17279 EW6 ; Operating Systems

HW# 2 (due by 4th class): There is a Project at the end of chapter2 (or chapter3 in new edition) of your book. ``Adding a System Call to the Linux Kernel'' (or google for how to do it; e.g. How to Build and Modify an Ubuntu 3.13 Kernel). This homework is about following that guide (or the linked one) and... actually doing it. It involves building your own linux kernel, adding the system call, and then actually using that system call from your program. All that is explained in the book project (and linked page); if you have any questions, feel free to email me. Email all the source files you've created (the system call, and your program to test it). You can use virtualbox to host ubuntu for this homework. Note that some small details have changed in the later versions of Linux, so use google to figure out how to compile the module with the latest kernel.

Note that apparently the assignment at the end of chapter2 is slightly different for 9th edition of the book. If your book is different, follow this guide: How to Build and Modify an Ubuntu 3.13 Kernel (or feel free to find another guide---there are plenty of them online).

HW# 3 (due by 4th class): Data structures: Implement an auto-growing (same way vectors grow) array based list with constant time insert and remove from either the front or the back of the list. Note that this is different from how Vectors (e.g. in Java) work, they only support constant time insert/remove from end of the list, not beginning. Your implementation needs to work for both. Also, implement a heap based priority queue on top of your array based list (your code should work similarly to PriorityQueue in Java, except use your own array based list). Use whatever language you are comfortable with.

HW# 4 (due by 5th class): This is mostly a status update homework. Start working on project1. Submit the program to generate input data (along with instructions on how to compile/run it). This does count as a "homework", so please submit it.

HW# 5 (due by 6th class): Write a program to estimate PI using the monte carlo algorithm, using N threads (have N=100). Individual threads will update a shared estimate values of PI, using the Bakery algorithm (notes 0006) to synchronize. This homework is about implementing the Bakery algorithm---do not use other synchronization methods.

You will have 2 variables: CNT, INARC. These variables MUST be shared between threads. These are your PI estimate. Each thread will: loop forever, at each iteration, get two random values (0..1) x,y. Each iteration will increment CNT. If x*x + y*y <= 1, then the thread will also increment INARC. You will have N threads doing this at the same time. Access to CNT++ and INARC++ will be controlled via the Bakery algorithm.

Every 100th iteration of each thread will display the current PI estimate, which is just: INARC/CNT*4. Note that the simulation will be very very very slow. (e.g. you have 100 processes waiting for 100 other processes and you'd be displaying a value every 100th iteration)

Submit the program, and first 100 lines of output from your program (your PI estimates).

HW# 6 (right after spring break): Write a program to calculate average seek time for a few disk scheduling algorithms: FCFS (first come first served), SSF (shortest seek first), Elevator, CSCAN. Your program will accept a parameter N (number of requests in buffer; how many requests are being compared to determine which one to do next). The input into your program is a stream of numbers indicating where to seek to. The output is just a an average seek time (or 4 averages if you decide to do all 4 algorithms in a single program).

HW# 7: In any language of your choice, write an NTP client. NTP is Network Time Protocol. Your program sends a UDP packet to the server. The server responds with a similarly formatted UDP packet with the current time. A public ntp server is: pool.ntp.org. This homework is part research part programming. Research part: Find the NTP specification, and determine what the UDP packet format is. Programming Part: Write a program to send the packet AND recieve a response. When your program is executed, it will output the current time (recieved from NTP server) to standard output, in ``Wed Sep 24 07:29:23 EDT 2008'' format, (Note that since you're using UDP, not all packets will get through---so you might need to run the program a few times in order to get the correct time). You can lookup the format for the to/from message in NTP RFC (google for it)---the format is pretty simple. Your program should work similar to the unix utility ``ntptime''; [hw7 hint]

HW# 8: In the not-so-distant future, flying cars are commonplace---everyone's on the planet got one. Yes, there are ~10 billion flying cars all over the globe. Each one logs its coordinates every 10 milliseconds (assume x,y,z), with z being altitude, and x,y, some cartesian equivalent of gps. To avoid accidents, regulation states that no car can be next to any other car by more than 10 feet while in the air (z > 0). Cars can go really fast, ~500mph. YOUR TASK: write an algorithm & program to find all violators. Assume input is a HUGE file (10 billion cars logging VIN,time,x,y,z every 10 milliseconds all-the-time).

What is the running time of your algorithm? If it's O(N^2), can you make it run in O(N log N) time? (note that with this much data, N^2 is not practical, even N log N is a bit long). Use Apache Hadoop (hadoop.apache.org) MapReduce to distribute the algorithm. Is the running time still O(N log N)?

Good Hadoop installation guide.

HW# 9: In this homework, you'll write a few utilities. These should be flexible enough to run on schedule (cron, etc.). I highly recommend you use GPG for this (generate public/private key pair; do not keep private key anywhere near these programs), and command line email/ssh utilities, etc., don't recreate stuff if you can just use other programs/libraries. (I don't expect each of these to be longer than 10-20 lines of code).

Write a utility that accepts an "outbox" folder, "encrypted" folder, and "publickey" file. When a FILENAME.comp shows up in the "outbox" folder, your utility will encrypt the FILENAME using the public key and place it into the "encrypted" folder. Your utility then verifies that the encrypted file was created successfully (length is not zero, and there were no errors such as running out of disk space, etc.), your utility creates FILENAME.comp file in the "encrypted" folder, and erases the FILENAME.comp and FILENAME from the "outbox" folder. You then loop thorugh the "outbox" folder and erase all files (those without the .comp) with create date older than 30 days.

Note that you can create "encrypted" folder under your Dropbox folder.

Write another utility that nightly compresses your IMPORTANT_PROJECTS folder, into say IMPORTANT_PROJECTS.20150429120101.tar.gz, and places the file in the "outbox" folder. Verifies that compression completed successfuly (perhaps by uncompressing and checking; making sure size is not zero, etc.), and then also creates a IMPORTANT_PROJECTS.20131204062800.tar.gz.comp file. (note that this will *cause* your other utility to encrypt the archieve).

Write another utility called "cleanup", that accepts a folder, sorts files by create date, keeps the last 10, and erases the rest. (you can run this utility on the encrypted folder, so it doesn't grow beyond bound).

Note, it is a very good idea to ensure you only have 1 instance of each such program running at any given time. You can accomplish that by specifying another parameter such as "lockfile". Your program would then open the file and aquire an exclusive lock on it. (google for "flock" command). If it can't aquire the lock, your program would exit (meaning another copy of your program is already running). This eliminates a lot of the race conditions that might cause corruption.

In this homework, you are writing 3 scripts (3 programs). For homework submission, email the three programs you've created. You can use any lange you please, I highly recommend bash/perl/python. If you're doing this on Windows, it might be a bit cumbersome, but not impossible.

HW# 10: In this homework, you'll implement a simple Chat Server. Your server will start listening for connections (on whatever port you choose). When a connection arrives, it will create a new thread to handle that connection (maintain a list of connections). When a line arrives on any connection, the server will forward that line to all other connections. Pseudo code might look something like this:

List clients;
ServerSocket server = createserversocket;
for(;;){
   Socket client = server.acceptconnection();
   addclienttolist(client);
   createthread(client);
}

//place that handles the thread
void run(){
   while(;;){
      String line = readlinefromclient();
      sendlinetoeveryone(line);
   }
}

//some other function
void sendlinetoeveryone(string line){
   forall(clients){
      sendtothatclient(line);
   }
}

The code isn't much longer than the pseudo code, but I'd like you all to figure it out on your own. Now, when you run the server, you should be able to telnet into that server. If more than one person telnets into that server, then everything one person types will be seen by everyone else. You can test it by running multiple Telnet instances (in different terminals), and seeing whether everything you type in one window appears in the other window. Submit the source code.

If you're feeling creative, think of how you'd handle user names and nicknames in such a system. How would one person find out who is connected? How would they find out information about other users?