All non-programming and programming problems in this assignment are to be done by yourself. Group collaboration is not permitted for this assignment. All homework submissions are to be made via the submit programs. Documentation regarding these programs can be found at:

http://www.cs.columbia.edu/~nieh/teaching/w4118/homeworks.

Non-Programming Problems:

1. What are the three main purposes of an operating system?

2. Definte the essential properties of the following four types of operating systems: batch, interactive, time-sharing, and real-time.

3. Which of the following instructions should be privileged?
   1. Set value of timer.
   2. Clear memory.
   3. Turn on interrupts.
   4. Switch from user to monitor mode.
   5. Write the clock.

4. Exercise 1.8

5. Exercise 1.11

6. Exercise 2.3

7. Exercise 2.6

8. Exercise 2.8

Programming Problems:

1. Timing Methodologies (20 Pts.) The x86 PCs in the CLIC lab have a tsc hardware register that counts processor cycles. The register can be read using the rdtsc instruction, which can be used to provide very accurate timing measurements. A detailed Intel document is available about this instruction for those who are interested. There are several macros used to read this register, as described in the include file asm/msr.h. These macros can be wrapped through a function like getcycles below, which takes a pointer to a long long and packs it with the number of cpu cycles used since the system was last booted. inline void getcycles (long long int * cycles){ unsigned long low; long high; rdtsc(low,high); *cycles = high; *cycles <<= 32; *cycles |= low; }
   1. Write a function in C called gethosttime that takes a long long cycles value as an argument and returns the equivalent long long in nanoseconds. Your function should be portable across machines, so it will need to determine the CPU speed of the machine on which it is being called. One way to do this in Linux is to parse the data contained in the file /proc/cpuinfo. The /proc filesystem (where /proc/cpuinfo resides), is a virtual filesystem that presents a way for userspace to communicate with the kernel and vice-versa. Various statistics can be read from the files in the /proc filesystem and /proc/cpuinfo, as its name suggests, contains information regarding the CPU.
   2. Figure out how long it takes to execute the getcycles function. In addition, time the gettimeofday system call. You should be careful to do the measurement in such a way that minimizes the overhead of doing the measurement.
   3. Use both getcycles and gettimeofday system calls to time the inner for-loop of the following bit of code: for (i=0; i<100; i++) { for (j=0; j<100000; j++) { /* inner loop starts here */ k = i + j; } /* inner loop ends here */ } Your writeup should include the mean and standard deviation of loop iterations. In addition, you should consider which timing method is more accurate.

2. Shell Utility (20 Pts.)
   1. Using system calls to handle all file operations, write a program in C that copies a file from one location to another, and deletes the original version. The program should take two file names as its arguments, the first one being the file to move and the second being the new location. The program should check for bad inputs and should work for files of arbitrary size. In addition, your program should gracefully handle all error conditions while copying the file.
   2. Write a program in C to create files of 1, 10 and 100 megabytes in size, and then time how long it takes to move these files. Are the results what you imagine they would be?

3. Trivial Shell (20 Pts.)
   1. Write a trivial shell that reads a line from the standard input, splits the line into program name and arguments, and invokes the command after forking, with the arguments passed in the normal C manner. The shell waits until the program completes. You should write this in C. You can make reasonable assumptions about the maximum number of command line arguments, and your shell will exit upon the user typing exit. Please note that it is not acceptable for your shell to utilize the system function, as your shell must operate through the use of forking.
   2. Most shell contain a history of commands that have been launched in the past. Usually typing the word history at the shell prompt will display this list of commands in chronological order, along with a number indicating the command. In addition, typing !n, where n is a number, will launch the nth command in the history list. The history command works as follows: [me@myhost /home/me]$ history [1] vi foo [2] netscape [3] ls ... [79] quake [80] telnet cunix [me@myhost /home/me]$ !3 myfile1 myfile2 myfile3 Augment your shell to utilize a linked list in order to contain the history of the last 100 commands launched. Once 100 commands have been launched, the list should remove the first command in the list whenever it needs to accomodate more commands. Your shell should support the history command, and print out the list of past commands whenever history is typed. In the case where !n is typed, the nth command should be launched. In addition, be sure to free any memory allocated to support the linked list and to support file executions.

Additional Requirements

1. Check the return values of all functions utilizing system resources. Do not blithely assume all requests for memory will succeed and all writes to a file will occur correctly. Typically, a system call will return -1 in the case of an error (malloc will return NULL). As far as system calls are concerned, you will want to use one of the mechanisms described in Reporting Errors or Error Reporting.
2. When using gcc to compile your code, use the -Wall switch to ensure that all warnings are displayed. Do not be satisfied with code that merely compiles; it should compile with no warnings.
3. Use a makefile to control the compilation of your code.
4. All code (including test programs) must be written in C.

Tips

1. For this assignment, your primary reference will be Programming in C. You might also find the Glibc Manual useful.
2. Many questions about functions and system behaviour can be found in the system manual pages; type in man function to get more information about function. If function is a system call, man 2 function can ensure that you receive the correct man page, rather than one for a system utility of the same name.
3. If you are having trouble with basic Unix/Linux behavior, you might want to check out the resources section of the class webpage.
4. A lot of your problems have happened to other people. If you have a strange error message, you might want to try searching for the message on Google.