Homeworks

You should EMAIL me homeworks, alex at theparticle dot com. Start your email subject with "CIS25".

CIS25 HW# 1 (due by 2nd class; not accepted after (20090212): Email me your name, prefered email address, IM account (if any), major, and year.

CIS25 HW# 2 (due by 3nd class; not accepted after (20090219): 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''. This homework is about following that guide 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; 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.

CIS25 HW# 3 (due by 5nd class; not accepted after (20090305): Write a scheduler program. Your program will accept a file with 3 columns, like:

P1 CPU 10
P2 CPU 20
P1 IO 100
P2 IO 50
P1 CPU 50
P2 CPU 10

(your program should be capable of reading thousands of lines, etc.) The first column is a Process id, second column is the type of "burst", and third column is the duration.

Your program will read this file and output 3 numbers, the average waiting time for: FCFS, RR, and SJF scheduling algorithms. You can use any language you like (I highly recommend Java/C#/Perl, as those have queues already implemented in the libraries). If you have questions, email.

CIS25 HW# 4 (due by 6th class; not accepted after (20090312): 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 to synchronize.

You will have 2 variables: CNT, INARC. 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 10000th iteration of each thread will display the current PI estimate, which is just: INARC/CNT*4.

CIS25 HW# 5 (due by 8th class): Write a program to calculate number of page faults given three different algorithms: FIFO, LRU, and Optimal page replacement. Your program must accept a command line parameter of: number of available frames. The output of the program is just a number (or 3 numbers, if you decide to make it all 1 program, instead of 3 separate programs).

CIS25 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).

CIS25 HW# 7: Given N objects, with x,y,z coordinates and radius, write an algorithm to find all touching (overlapping) objects. 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? Use Apache Hadoop (hadoop.apache.org) MapReduce to distribute the algorithm. Is the running time still O(N log N)?

© 2006, Particle