Operating Systems II

Instructor - Robert Hochberg 
Office-         STC C-121 
Phone-         328-9685 
Email-         hochberg@cs.ecu.edu		 Text - Operating Systems by Tannenbaum, second edition.
 The Syllabus can be found here


Assignment 1, Due approximately September 19, 2007
There is no group work on this first assignment. Each person must write and submit his or her own program.
The goal of this assignment is to use threads to have the computer win a game.
Modify this program:  game.cpp and game.h, so that the computer is always
finding the optimal move, according to some criterion, in the background.
Here are the requirements:
  1. Whenever it is the user's turn to move, for each possible move that the user could make, the program should spawn a thread which descends the game tree from that position, computing the best move.
  2. The trees should be descended in a breadth-first fashion, and no thread should descend to the k+1st level until all trees have completed their kth level.
  3. At every moment, each thread should be able to answer the question:  "What is the best move to make, now that we know the user made the move that you were supposed to consider?"
  4. As soon as the user makes his move, the threads should all be terminated, and the program should make the move that the appropriate thread has determined to be best.
For grading purposes, I would like you to include some reporting.  If  VERBOSE is defined at compile time (with a #define VERBOSE), then each thread should report:
You may get some hints about how threads and semaphores work from this file:  mutex.cpp.


Assignment 2, Due October 22, 2007
We saw four algorithms for placing processes into holes in memory:  best fit, worst fit, next fit and first fit.  Your job is to write a simulator which will take processes of varying sizes, load them into memory according to each of those rules, and swap processes out as needed to create a larger hole.  Let us make the following assumptions:
  1. Memory is of size 128MB
  2. The size of each process will be some whole number of megabytes in the range 1..128
  3. Memory is initially empty.  (We will ignore the operating system.)
  4. The first line of the input file will specify the algorithm to use for this run.
  5. Processes are scheduled dynamically; requests are sent to the memory manager as a series of requests to make sure processes are in memory, or if not, to swap them in.  The sizes of the processes are given every time.
  6. Requests to kill processes will also arrive, always right after the process has been run.  In this case, its space needs to be deallocated.  See the sample file to the right for the format.
  7. If a process needs to be loaded but there is no hole large enough to accomodate it, then processes should be swapped out, one at a time, until there is a hole large enough to hold the process that needs to be loaded.
  8. If a process needs to be swapped out, then the process which had been last scheduled least recently should be the one to go.  That is, we use the Least Recently Used algorithm.

You can use whatever data structure you wish (eg. linked list, bitmap) to simulate memory usage, but please make sure that the comments in the file clearly indicate what data structure you are using and how it is implemented. 

Each time a process is requested to be in memory, print a line such as:
  Load F, #proc=5, #holes=3, %mem=41, Avg%mem=40
Thus one line should be printed for each line in the file except for the first line and the "kill" lines.

#proc is the number of processes in memory
#holes is the number of holes
%mem refers to the percent of memory that is currently occupied by processes
Avg%mem gives the average of all the %mems up until and including the current process load.

When the last process has been killed, which will also be the first time since the start that memory becomes empty, summary stats should be printed:
  #swaps=33, avg #proc=14.4, avg #holes=6.3, Avg%mem = 62
where #swaps is the number of times a process had to be swapped out of memory to make room for an incoming process. For example, if you have to remove 4 processes from memory to make room for one large incoming process, that counts as 4 swaps.

This program should be called holes.c, and should take a single commandline argument as indicated above:  a.out testfile1
Sample Input File



ff
A 30
B 20
C 75
A 30
D 80
C 75
A 30
D 80
A 30
C 75
B 20
A 30
C 75
B 20
E 55
B 20
kill B
E 55
D 80
A 30
kill A
E 55
kill E
D 80
C 75
D 80
C 75
kill C
D 80
kill D
Sample Run
Notes

The first line in the file will be either ff, wf, bf nf or ma (see below)

For extra credit, design your own algorithm, including alternatives to LRU, if you wish, and see if you can consistently beat any or all of the four algorithms.  The better your algorithm does, the more extra credit, up to 10 points, you will get.  That's what the "ma" means up above.

To make it easier on me, if you elect not to implement your own algorithm for the extra credit, then please have your program print a message such as "Not implemented," and then gracefully exit, whenever a file starting with "ma" is encountered.


Assignment 3, Due November 22, 2007

There is no group work on this third assignment. Each person must write and submit his or her own program.

Your assignment is to write a program which will make two Assignment 1-type games play against each other. 

Requirements:
  • Your program should be called compete.cpp, and your makefile should compile an executable called "comp"
  • A commandline should look like "comp game1 game2 time1 time2", where game1 and game2 are the names of the executables from assignment 1, and time1 and time2 are integers, with time1 specifying how long game1 may compute before making its move, and time2 specifying how long game2 may compute before making its move.  Times are in seconds.  A sample run is shown to the right.
  • Your program should detect the size of the board on which the two games are playing.
  • game1 makes the first move
  • After each move, a line should be printed that says something analogous to "game1 moved to a1", and a copy of the resulting board should be printed.  The output should use the names of the game executables.
  • When the game is over, the program should print a line saying how many points each game had, and who the winner was.
  • The programs should use Unix pipes to communicate.
  • The games from Assignment 1 read from standard input and write to standard output.  You may not assume otherwise as you write your Assignment 3 program.
  • Please write a one page summary of how your program works.

Assumptions:
  • You may assume that the games written in Assignment 1 output a line at the start of the game that says "Playing on a 5x5 board", except, of course, that the actual dimensions of the board will be printed. 
  • You may assume that the board is no larger than 50x50.
  • You may assume that when the Assignment 1 game makes a move, it's output is exactly in the form:  "My move is to a1", with "a1" replaced by the actual move.

Helpful Links and Files:
  • Sample program from Monday
  • Sample program from Wednesday
  • prettyls from Wednesday
  • fork(), dup() and pipe() are described on this page
  • sleep() is described here, and can be used to give a game time to compute
 Sample Transcript

$ comp smart2-5-10 smart2-5-7 1 1

Playing on a 5x5 board
smart2-5-10 moved to a1
  12345
 +-----+
a|X    |
b|     |
c|     |
d|     |
e|     |
 +-----+

smart2-5-7 moved to c3
  12345
 +-----+
a|X    |
b|     |
c|  O  |
d|     |
e|     |
 +-----+

smart2-5-10 moved to b3
  12345
 +-----+
a|X    |
b|  X  |
c|  O  |
d|     |
e|     |
 +-----+

smart2-5-7 moved to c2
  12345
 +-----+
a|X    |
b|  X  |
c| OO  |
d|     |
e|     |
 +-----+

smart2-5-10 moved to c4
  12345
 +-----+
a|X    |
b|  X  |
c| OOX |
d|     |
e|     |
 +-----+

smart2-5-7 moved to c1
  12345
 +-----+
a|X    |
b|  X  |
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-10 moved to b4
  12345
 +-----+
a|X    |
b|  XX |
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-7 moved to b2
  12345
 +-----+
a|X    |
b| OXX |
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-10 moved to a2
  12345
 +-----+
a|XX   |
b| OXX |
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-7 moved to a3
  12345
 +-----+
a|XXO  |
b| OXX |
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-10 moved to b5
  12345
 +-----+
a|XXO  |
b| OXXX|
c|OOOX |
d|     |
e|     |
 +-----+

smart2-5-7 moved to d2
  12345
 +-----+
a|XXO  |
b| OXXX|
c|OOOX |
d| O   |
e|     |
 +-----+

smart2-5-10 moved to d4
  12345
 +-----+
a|XXO  |
b| OXXX|
c|OOOX |
d| O X |
e|     |
 +-----+

smart2-5-7 moved to e3
  12345
 +-----+
a|XXO  |
b| OXXX|
c|OOOX |
d| O X |
e|  O  |
 +-----+

smart2-5-10 moved to d3
  12345
 +-----+
a|XXO  |
b| OXXX|
c|OOOX |
d| OXX |
e|  O  |
 +-----+

smart2-5-7 moved to a4
  12345
 +-----+
a|XXOO |
b| OXXX|
c|OOOX |
d| OXX |
e|  O  |
 +-----+

smart2-5-10 moved to a5
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOX |
d| OXX |
e|  O  |
 +-----+

smart2-5-7 moved to e2
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOX |
d| OXX |
e| OO  |
 +-----+

smart2-5-10 moved to c5
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOXX|
d| OXX |
e| OO  |
 +-----+

smart2-5-7 moved to d1
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOXX|
d|OOXX |
e| OO  |
 +-----+

smart2-5-10 moved to d5
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOXX|
d|OOXXX|
e| OO  |
 +-----+

smart2-5-7 moved to e4
  12345
 +-----+
a|XXOOX|
b| OXXX|
c|OOOXX|
d|OOXXX|
e| OOO |
 +-----+

smart2-5-10 moved to b1
  12345
 +-----+
a|XXOOX|
b|XOXXX|
c|OOOXX|
d|OOXXX|
e| OOO |
 +-----+

smart2-5-7 moved to e1
  12345
 +-----+
a|XXOOX|
b|XOXXX|
c|OOOXX|
d|OOXXX|
e|OOOO |
 +-----+

smart2-5-10 moved to e5
  12345
 +-----+
a|XXOOX|
b|XOXXX|
c|OOOXX|
d|OOXXX|
e|OOOOX|
 +-----+

smart2-5-10 (X) had 6 points and smart2-5-7 (O) had 6 points.
*** DRAW ***
Assignment 4, Due December 10, 2007, before the final.

There is no group work on this third assignment. Each person must write and submit his or her own program.

Your job is to write the UNIX "pwd" command using inode information.

How UNIX pwd works:
At a shell command prompt, when the user types "pwd," the current absolute path is returned.
% pwd
/export/fac/hochberg
% 

Hints for your implementation:
Here are some hints on how you can write this program.  Note:  A well-commented program should be less than two printed pages.

  • The stat command can be used to obtain inode information about a particular file or directory.   You use a statstructure to hold the return information. 
  • The opendir and readdir commands can be used to read directory information.  You use dirent structures to hold the information returned from a readdir operation.  See the readdir entry on the Sun site for an example.
  • Here is one way to find the name of the current directory: Find the inode of ".", and then compare this with the inodes of all the files contained in the directory "..".
  • The root directory is its own "parent," in the sense that "." = ".." for the directory "/".
You can read about the commands indicated above here (for stat) and here (for the 'dir' commands.)
 
 Notes:

When files are stored across a network, you may need to take into account the device id.  This is because on separate disks you may find the same inode number, even though the files are different.

Here is a sample program to gather the stat information:  stat.cpp

Here is the one that does not make us of an intermediate file descriptor.  stat2.cpp

Also note that if "../" points to the parent directory, then "../../" will point to the parent of the parent.

Question:
I'm not seeing what you mean by using the devic ID, I'm not finding anything to match with.  As you said my program finds the path up until the last two correctly.  My path is

/home/crw0620/OS/Assignment_4/testDir/testDir2

and I can get here:

OS/Assignment_4/testDir/testDir2

    From here on the device ID's are not the same, so crw0620 has a different device ID than OS and so on but not sure how you want us to use the device id to go from here on. I'm not seeing how to match things up from here on.
Answer:
When you search a directory for the correct file, compare both the inode number and the device id number.  So, for example, I have a line such as
   if(dotstat.st_ino == buf.st_ino && dotstat.st_dev == buf.st_dev) ...