PART 1
Write answers to the following questions in a text file:

1. Consider a computer that uses swapping for memory management and that currently has holes in memory of the following sizes (in order): 10MB, 4MB, 20MB, 18MB, 7MB, 9MB, 12MB, and 15MB. Which holes will be used if the computer swaps in a process needing 12MB, then one needing 10MB, then one needing 9MB. Give answers for each of the following algorithms: first fit, best fit, and worst fit.

2. For each of the following virtual addresses (written as decimal numbers), compute the virtual page number and offset if 4KB pages are being used: 20000, 32768, 60000.

3. Suppose that a computer with 32-bit addresses uses a two-level page table such that the first 9 bits of a virtual address specify a top-level page table field, then next 11 bits specify a second-level page table field, and the remainder is an offset. How large are pages in this computer, and how many pages exist in each process's address space?

4. Suppose that a particular process on a computer accesses memory in such a way that it needs all of the pages from 0 to 511 in order, then some random page, then pages 0 to 511 in order, then some random page, and continues in this way. Why would the LRU, FIFO, and Clock algorithms all perform poorly for this process? Describe a new algorithm of your own invention that would work well for this process.

5. Suppose that a computer that uses paging has four frames and a process running on it has eight pages. Suppose the frames are initially empty, then the process accesses page 0, then 1, then 7, then 2, then 3, then 2, then 7, then 1, then 0, then 3. How many page faults will occur using FIFO? How many using LRU?

6. Suppose that a computer that uses paging has four frames. At the first clock interrupt the R bits are 0111. At the next clock interrupts the R bits are 1011, 1010, 1101, 0010, 1010, 1100, and 0001. If the Aging algorithm is used with an 8-bit counter, what are the values of the aging counters for each frame after the last interrupt?

7. Suppose that a computer uses a bitmap to keep track of the free blocks on disk, and it contains 1000 0000 0000 0000 for a newly-partitioned disk. The computer always uses the first free blocks it can find from the beginning, SO when a file A is created that needs 6 blocks, the bitmap becomes 1111 1110 0000 0000. Show what the bitmap will look after file B is written (5 blocks), file A is deleted, file C is written (8 blocks), and file B is deleted. (That's 4 different answers).

8. What would happen if the list of free blocks on a disk were destroyed? Could it be recovered, and if so, how? Answer for the UNIX and FAT-16 filesystems.

9. Suppose that a UNIX file system has 4KB blocks and each block number takes up 4 bytes. What is the maximum file size if i-nodes contain 10 direct entries and one single-indirect, one double-indirect, and one triple-indirect block each?

10. How many disk operations are needed to fetch the i-node for a file with the path /home/chadhogg/courses/os/hw05.tex Assume that the i-node for the root directory is already in memory but nothing else is, and that all directories fit in a single disk block.

PART 2
One of the standard UNIX commands is ls, which prints information about files and directories. We are going to implement a crippled version of this program, SO read its man page and experiment with it a bit. For names of files, ls simply prints the file name back at you.

For names of directories, ls prints the contents of the directory. In order to find this, you will need the system calls opendir, readdir, and closedir.

3.1 Unsupported Features
The real ls program automatically does a number of things that we will not be doing, because they would require a lot of work and teach us little about the topics of this course:

3.1.1 Coloring
When ls detects that its output is going directly to a terminal (not redirected to a file), it prints the names of files in different colors based on their types. We will not do this.

3.1.2 Columns
When ls detects that its output is going directly to a terminal (not redirected to a file), it prints its output in multiple columns to fit the width of that terminal. We will instead just print one piece of output per line. (One of the problems in the Spring 2013 programming competition at Bucknell was to implement this feature.)

3.1.3 Sorting
By default ls sorts its output alphabetically. (It also has options to sort the output in many other ways.) We will just print our output in whatever order is most convenient for us.

3.2 Supported Options
The real ls program has a great many options that control how it works. In the interests of time, we will support only two of them:

3.2.1 Show All Files
We would like to support the -a option, which is also known as --all. When this option is not used (the default), ls ignores all files whose names begin with a period. These are sort of like hidden files in Windows. With the option turned on, these files are not ignored. To find some of these files to experiment with, look at the top level of your home directory, where you will find lots of automatically-generated configuration files.

3.2.2 Long Listings
We would also like to support the -1 option. Normally ls just prints file names. With this option, however, it prints a large amount of information about each file:

The type of file: regular, directory, block special, character special, symbolic link, other (there are a few other types as well, but we can call all of them "other")

The permissions that the file's owner, group, and everyone else have for reading, writing, and executing the file (this can also show some extra information, but the basic r/w/x/- is fine for us)

The number of hard links to the file
The name of the file's owner
The name of the file's group
The size of the file, in bytes
The date / time when the file was last modified
The file's name

All of this information can be discovered through the stat system call. You will also need to use the getpwuid and getgrgid system calls to turn ID numbers into names. Figuring out modification time is complicated enough that I have written a function to do SO and included it in a .C file with these instructions for you to use.

3.3 Notes
See what happens when you run ls with no non-option arguments, with one non-option argument, and with several non-option arguments. Try having the arguments be names of regular files, but also try having them be names of directories. Try to make your output as identical to the real program as possible.

You should see that when you are using the long listing option and printing directories, before the contents of the directories you get a total XX line. This is printing the number of 1024-byte blocks used by all files in the directory. Strangely, when the stat system call returns a number of blocks used by a file, they are 512-byte blocks. Also, you may find that files take up more blocks than you would expect based on their sizes. This is because the filesystem pre-allocates more blocks than a file needs to prevent file growth from causing lots of fragmentation. Finally, notice that this total changes based on whether or not hidden files are to be included in the output.

You can get somewhat more detail about what is does and how it works by reading the extending manual with the command info coreutils 'ls invocation'

PART 1 Write answers to the following questions in a text file:...