CSE 120: Homework #5

Spring 2009

1. This homework question will require you to gather some information on ieng6. Consider the files in the subtree rooted at /usr/include. Produce a table of percentage of disk space lost to (internal) fragmentation as a function of disk block size for all of these files. Compute fragmentation for each file (e.g., a 524 byte file with a 1KB block size has 500 bytes of internal fragmentation), but report fragmentation in the table as an overall percentage across all files: total bytes of fragmentation for all files / total bytes allocated in blocks for all files. Do not consider the directories in your computation. Assume that a file of length b > 0 bytes would be stored in ⌈b/s⌉ blocks for a block size of s bytes. A zero-length file requires no blocks. Let s range from 1K to 32K bytes in increments of 1KB.

   Number of files: ...

   Percentation of disk space lost to internal fragmentation across all files for block sizes ranging from 1-32 KB:

   	1 KB	...	32 KB
   % Internal fragmentation

   You can produce a list of files in this directory with the find command, e.g.:

   find /usr/include -print > ~/files.txt

   will create a file called files.txt that contains the names of the files in /usr/include. You may find it more handy to store the file names in a shell variable. For instance, using the csh or tcsh shells:

   set flist = `find /usr/include -print`

   You can then use wc with the -c switch to find the character lengths of the files, e.g.,

   foreach f ($flist)
   wc -c $f
   end

   And with bash:

   for f in `find /usr/include -print`; do wc -c $f; done

   You may need to write a simple program that computes the percentage of space lost to fragmentation. Or, if you are facile with spreadsheets, you may find them a good tool to perform this computation.

2. (11.8)  In what situations would using memory as a RAM disk be more useful than using it as a disk cache?

3. Consider a UNIX-style inode with 10 direct pointers, one single- indirect pointer, and one double-indirect pointer only. Assume that the block size is 8K bytes, and that the size of a pointer is 4 bytes. How large a file can be indexed using such an inode?

4. Consider a file archival system, like the programs zip or tar. Such systems copy files into a backup file and restore files from the backup. For example, from the zip documentation:

   The zip program puts one or more compressed files into a single zip archive, along with information about the files (name, path, date, time of last modification, protection, and check information to verify file integrity).

   When the file is restored, it is given the same name, time of last modification, protection, and so on. If desired, it can even be put into the same directory in which it was originally located.

   If desired, can the file be restored into the same inode? If you don't know, think about it. Explain your answer.

The following problem is optional (not required, no points). You might find it useful as practice with synchronization for the final.

• [Java Monitors] As additional practice with monitors, the final problem will be solving one of the midterm synchronization problems using Java monitors.

  A group of students are studying for the CSE 120 midterm. The students can study only while eating pizza. If a student finds that the pizza is gone, the student waits until another pizza arrives. The first student to discover that the group is out of pizza phones Leucadia Pizzeria to order another Meat Combo pizza and then waits for the pizza to arrive. Each pizza has S slices.

  Implement GetSlice and DeliverPizza methods to properly synchronize student threads and the pizza delivery thread using Java monitor mechanisms (Wait and Notify/NotifyAll). Your solution should be in the form of a Java class that compiles and runs. Your solution should avoid deadlock and phone Leucaida (i.e., wake up the delivery thread) exactly once each time a pizza is exhausted. No piece of pizza may be consumed by more than one student.

  Below are five Java files to help you with the implementation. Your job is to implement the guts of the monitor in the fourth file, PizzaMonitor.java. The fifth file, BSem.java, is an example program showing how to use notify and wait.

  1. First, here's the top level program, StudyGroup.java. It's the most complex of the lot. When you run it, you supply as arguments the number of slices per pizza and the list of student names, e.g.:

        java StudyGroup 8 Amako Byun Cheyenne Dmitrii Eija
     

     When you test your program, try it both with more slices per pizza than students (like above) and more students than slices per pizza.

  2. Next is the life of a studying student, Student.java. Note that this extends Thread. When the "start" method on an object of this class is invoked, the thread starts running by executing the method "run".
  3. And then the pizzeria, Luecadia.java. It is also a thread.
  4. Here's the monitor that you will implement, PizzaMonitor.java. It has two entry methods; one for students and one for pizzerias. Note that this monitor does nothing; you need to add the variables and the code for the two methods. This file is the one that you will modify to solve the problem.
  5. Finally, here is an example program, BSem.java, that shows the use of notify and wait in Java.