David E. Goldschmidt, Ph.D.

assignments

Both homeworks and projects are detailed below.

Assignments are to be completed individually, as specified in the assignment description. Projects are to be completed either individually or in teams of up to three students. Teamwork is not required for any assignments.

Unless otherwise noted, assignments are due by midnight on the specified due date and are to be submitted via this link. Log in using either your RCS ID and password or your CS ID and password.

Unix environments

With multiple versions of Unix available, please be sure to use BSD Unix for homeworks and projects detailed below. CS Department machines include ashley.cs.rpi.edu, mary-kate.cs.rpi.edu, and monica.cs.rpi.edu.

Compilation

Use gcc to compile your code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment).

» show details

« hide details

Our first homework assignment is to be completed individually. Do not share code or review anyone else's code. Work on this homework assignment is to be your own.

Submit your homework via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name at the top of each file submitted.

Part I:
On campus BSD Unix systems, write a program in C to mimic the ls command by displaying the contents of the current working directory. In addition to displaying files, also display subdirectories and recursively show each subdirectory's contents. For each subdirectory encountered, indent the output as shown in the example output below.

For each file, show the file's name and size (in bytes). Skip . and .., as these refer to the current directory and its parent directory.

Your output must be formatted as follows:

hw1.c (780 bytes)
a.out (18288 bytes)
stuff (subdirectory)
    old.c (424 bytes)
    hw2.c (1727 bytes)
    Sudoku.java (16200 bytes)
course (subdirectory)
    sample.txt (142 bytes)
    spring2009 (subdirectory)
        hw1.c (19 bytes)
        ghij.txt (28 bytes)
    spring2008 (subdirectory)
        b.txt (29 bytes)
        c.txt (998 bytes)
        d.txt (1228 bytes)

HINT: make use of the opendir(), readdir(), and stat() system calls, which are described on their respective man pages. Further, use a recursive helper function for each subdirectory encountered, including the current working directory, but be sure to stop the recursion when opendir() returns NULL.

Part II:
Extend your program to support an optional command-line argument (i.e. argv[1]). If present, your program should show files with names matching the command-line argument (using strcmp(), much like C++). All subdirectories should be shown, regardless.

From the example above, if the user specified hw1.c as the command-line argument, output would appear as follows:

hw1.c (780 bytes)
stuff (subdirectory)
course (subdirectory)
    spring2009 (subdirectory)
        hw1.c (19 bytes)
    spring2008 (subdirectory)

EXTRA CREDIT: modify to not show subdirectories that do not contain a file matching the command-line argument (or a subdirectory chain that ultimately contains it). Output would appear as follows:

hw1.c (780 bytes)
course (subdirectory)
    spring2009 (subdirectory)
        hw1.c (19 bytes)

Compiler:
Use gcc to compile your code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). With multiple versions of Unix available, please be sure to use BSD Unix.

Clarifications:

1. You need only handle files and subdirectories; skip anything else you encounter (e.g. symbolic links).
2. For Part II, only match the command-line argument against file names (i.e. not subdirectories).
3. If you decide to implement the extra credit, replace your existing Part II functionality. In other words, either implement as shown in Part II or as shown in the extra credit example; otherwise, you'll lose points.
4. The order in which files and subdirectories are displayed does not matter; however, be sure files and subdirectories are correctly shown in relation to one another (i.e. files within subdirectories).
5. For Part II, if the command-line argument does not match any files, display only the subdirectories; or, if you do the extra credit, display nothing. No error message is required.
6. If more than one command-line argument is specified, either display a usage message or ignore the extraneous arguments.
7. Use either a fixed number of spaces or a single TAB character to show the subdirectory indentation for Part II; whatever you choose, be consistent.

Grading Criteria:

1. Compiles without errors or warnings (use -Wall with gcc): 30 points
2. (Penalty) Warnings during compilation: -5 points per warning
3. (Part I) Prints the correct files in the current directory: 20 points
4. (Part I) Prints the correct subdirectories: 20 points
5. (Part II) Prints the correct files in the current directory: 10 points
6. (Part II) Prints the correct subdirectories: 10 points
7. Well-commented and well-designed solution: 5 points
8. Handles error conditions gracefully: 5 points
9. (Extra Credit) Prints correct subset of files and subdirectories: 10 points
10. (Late) -10 points per "business" day, up to 5 days maximum

» show details

« hide details

This homework assignment is to be completed individually. Do not share code or review anyone else's code. Work on this homework assignment is to be your own.

Submit your homework via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name at the top of each file submitted.

Part I:
On campus BSD Unix systems, write a C program to implement an interactive shell in which users can execute commands. Call this program myshell.

Create an infinite loop that repeatedly prompts the user to enter a command (see example output and input below). Before executing the command entered by the user, the command must be found using the path specified by environment variable MYPATH. If found, the command is executed via fork() and exec().

The MYPATH environment variable consists of a series of paths delimited by the ! character. If MYPATH is not set, use /bin!. as default.

Commands may optionally have arguments. You may assume that no more than four arguments will be used on the command line.

If the user types exit or quit, your shell should terminate.

Required output and input shown in bold follows:

welcome to myshell
($MYPATH is /usr/local/bin!/usr/local/sbin!/usr/bin!/usr/sbin!/bin!/sbin!.)
==> ls -l
total 44
-rwxrwxr-x  1 goldsd  grads  4928 Jan 24 23:13 getbacktowork
-rw-rw-r--  1 goldsd  grads  1100 Jan 20 16:13 hello.c
-rw-rw-r--  1 goldsd  grads   143 Jan 20 10:18 hello3.c
-rw-rw-r--  1 goldsd  grads   561 Jan 20 16:15 malloc.c
-rw-rw-r--  1 goldsd  grads   539 Jan 23 10:37 readfile.c
-rw-rw-r--  1 goldsd  grads   150 Jan 23 11:19 repeat.c
-rw-rw-r--  1 goldsd  grads   189 Jan 23 10:20 strings.c
-rw-rw-r--  1 goldsd  grads   542 Jan 20 16:15 struct.c
-rw-rw-r--  1 goldsd  grads    85 Jan 24 23:02 textfile.txt
==> cat textfile.txt
This is the contents of this text file.
The quick brown fox jumps over the lazy dog.
==> wc repeat.c
      13      26     150 repeat.c
==> blahblahblah
ERROR: command 'blahblahblah' not found.
==> exit
goodbye

Part II:
Extend myshell to execute processes in the background if the user enters & at the end of a command. When the child process is created, the parent does not wait for the child to terminate before prompting the user for the next command.

Further, add pipe and redirect functionality. If a user enters a | character, output from one process is fed as input to the next. You may assume that no more than two pipes will be used on a given command line.

For redirect functionality, add support for < and > characters, which redirect files to stdin and stdout, respectively.

Required output and input shown in bold follows:

welcome to myshell
($MYPATH is /usr/local/bin!/usr/local/sbin!/usr/bin!/usr/sbin!/bin!/sbin!.)
==> getbacktowork &
[process running in background with pid 36910]
HEY!  Get back to work.
HEY!  Get back to work.
==> mail goldschd@strose.edu < textfile.txt
==> wc repeat.c
      13      26     150 repeat.c
HEY!  Get back to work.
HEY!  Get back to work.
==> tar cf - hello.c hello3.c | gzip -9 > source.tar.gz
==> ls -l
total 48
-rwxrwxr-x  1 goldsd  grads  4928 Jan 24 23:13 getbacktowork
-rw-rw-r--  1 goldsd  grads  1100 Jan 20 16:13 hello.c
-rw-rw-r--  1 goldsd  grads   143 Jan 20 10:18 hello3.c
HEY!  Get back to work.
-rw-rw-r--  1 goldsd  grads   561 Jan 20 16:15 malloc.c
-rw-rw-r--  1 goldsd  grads   539 Jan 23 10:37 readfile.c
-rw-rw-r--  1 goldsd  grads   150 Jan 23 11:19 repeat.c
-rw-rw-r--  1 goldsd  grads   753 Jan 24 23:22 source.tar.gz
-rw-rw-r--  1 goldsd  grads   189 Jan 23 10:20 strings.c
-rw-rw-r--  1 goldsd  grads   542 Jan 20 16:15 struct.c
-rw-rw-r--  1 goldsd  grads    85 Jan 24 23:02 textfile.txt
==> exit
goodbye

EXTRA CREDIT: extend your shell to support the * wildcard when specifying file names. Given the example output above, the command cat *t.c would be expanded to cat repeat.c struct.c by the shell. As another example, the shell would expand cat s*c to cat strings.c struct.c. Test your program using these and other similar examples (e.g. *llo*.c).

Compiler:
Use gcc to compile your code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). With multiple versions of Unix available, please be sure to use BSD Unix.

Clarifications and Hints:

1. In the above specification, "four command-line arguments" refer to argv[1], argv[2], argv[3], and argv[4]. Also note that when multiple commands are combined using a pipe, each command must support a minimum of four arguments (e.g. cat a.txt b.txt c.txt d.txt | wc -c -l -m -w > output.txt)
2. Feel free to use the GNU readline() function; check out man readline for more information.
3. To parse MYPATH, consider using the strtok() function.
4. Arguments within myshell must not contain spaces. In other words, don't worry about parsing out quoted strings in your argument list (e.g. cat a.txt "some file.txt")
5. For the cd command, your myshell will execute the command via fork(), but your program's current working directory will not change. This is fine -- i.e. the cd command doesn't have to work for full credit. In a typical shell, the cd command is handled separately such that the parent process (the shell) changes the current working directory.
6. You may ignore the ~ character in this assignment -- i.e. you do not need to support ls ~/OS.
7. You may ignore relative and absolute paths on the command line.
8. There can be at most two redirects for a given command -- i.e. use of both < and >, as in mail goldschd@strose.edu < f.txt > output.txt.
9. Pipes may be combined with redirects, as in wc < a.txt | mail goldschd@strose.edu > output.txt. In this example, the a.txt file is redirected as input to the wc program; further, the output produced by mail is redirected to output.txt.
10. The & symbol can only be included at the end of a full command line; otherwise, this is an error. Pipes and redirection may precede the & symbol, as in wc < a.txt | mail goldschd@strose.edu > output.txt &. When the & symbol is used, all processes on the command line are to be executed in the background.

Grading Criteria:

1. Compiles without errors or warnings (use -Wall with gcc): 30 points
2. (Penalty) Warnings during compilation: -5 points per warning
3. (Part I) Run system commands correctly, with and without parameters (e.g. ps, ls -l, etc): 15 points
4. (Part I) Run local directory commands correctly, when . is in MYPATH (e.g. a.out, print_hello_world, etc): 15 points
5. (Part II) Implement background processes using & correctly: 10 points
6. (Part II) Implement use of pipe | correctly: 10 points
7. (Part II) Implement redirection using < and > correctly: 10 points
8. Well-commented and well-designed solution: 5 points
9. Handles error conditions gracefully: 5 points
10. (Extra Credit) Expands *x correctly: 5 points
11. (Extra Credit) Expands *x* correctly: 5 points
12. (Late) -10 points per "business" day, up to 5 days maximum

» show details

« hide details

This homework assignment is to be completed individually. Do not share code or review anyone else's code. Work on this homework assignment is to be your own.

Submit your homework via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name at the top of each file submitted.

Part I:
On campus BSD Unix systems, write a C program to implement a backup utility. Call this program mybak.

Your backup utility will create backup copies of all regular files in the current working directory. All subdirectories and other file types (e.g. symlinks) are to be ignored.

Backup files are stored in a hidden directory called .backup, which your program creates, if necessary. To create a directory, use the mkdir() function (click here for details), but be sure to check whether the directory already exists (using stat() or checking for EEXIST).

From main(), allocate a thread for each file to be copied. Each of the threads is responsible for copying a single file (using the read() and write() system calls).

Backup file names are created by appending .bak to the end of the original file name (e.g. program1.c.bak is the backup file for program1.c). If a backup file already exists, the corresponding thread simply overwrites the backup file.

The main thread must wait for all threads to terminate, then display the total number of files and bytes copied.

Required output follows in the example bash session below (with sample input shown in bold):

bash-3.2$ ls
pipe.c  repeat.c
bash-3.2$ mybak
(thread 134558720) Backing up repeat.c...
(thread 134559232) Backing up pipe.c...
Copied 150 bytes from repeat.c to repeat.c.bak
Copied 703 bytes from pipe.c to pipe.c.bak
Successfully copied 2 files (853 bytes)
bash-3.2$ ls .backup/
pipe.c.bak         repeat.c.bak

EXTRA CREDIT: modify mybak to only copy files if the backup file is not up-to-date. In other words, compare last modification times to determine whether creating a backup is required. Output displaying the total files and bytes copied must be updated accordingly (i.e. if a file is not copied, do not add it to any counts).

Required output follows in the example bash session below (with sample input shown in bold):

bash-3.2$ ls
pipe.c             repeat.c           struct.c
bash-3.2$ mybak
(thread 134558720) Backing up repeat.c...
(thread 134559232) Backup copy of pipe.c is already up-to-date
(thread 134559744) Backing up struct.c...
Copied 150 bytes from repeat.c to repeat.c.bak
Copied 491 bytes from struct.c to struct.c.bak
Successfully copied 2 files (641 bytes)
bash-3.2$ ls .backup/
pipe.c.bak         repeat.c.bak       struct.c.bak

Compiler:
Use gcc to compile your code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). With multiple versions of Unix available, please be sure to use BSD Unix.

Grading Criteria:

1. Compiles without errors or warnings (use -Wall with gcc): 40 points
2. (Penalty) Warnings during compilation: -5 points per warning
3. (Part I) Back up regular files in the .backup directory correctly: 30 points
4. (Part I) Display thread information correctly (mimicking the output format above): 10 points
5. (Part I) Display statistics of files copied correctly (as shown above): 10 points
6. Well-commented and well-designed solution: 5 points
7. Handles error conditions gracefully: 5 points
8. (Extra Credit) Back up only modified files correctly: 10 points
9. (Extra Credit) Display statistics of only modified files correctly: 5 points
10. (Late) -10 points per "business" day, up to 5 days maximum

» show details

« hide details

This project is to be completed individually or in teams of up to three students. Beyond your team, do not share code or review anyone else's code.

Submit your project via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name(s) at the top of each file submitted.

Part I:
On campus BSD Unix systems, using C, C++, Java, or Python (contact the instructor if you'd like to use another language), design and implement a simulation program for process management in an operating system, in particular short-term (CPU) scheduling.

A process is a program in execution. For this project, processes are ready to use the CPU or actively using the CPU. Ignore I/O. There is only one CPU available.

Build a configurable program that simulates the creation and execution of n processes numbered 1-n. Each process requires a random amount of CPU time, from 500-10,000 milliseconds, to complete its operation and terminate.

Before the simulation starts, ask the user to select one of the following scheduling algorithms:

• Round-Robin (RR), with configurable time slice t initially set to 100 milliseconds
• First-Come, First-Served (FCFS), with no time slice
• Shortest-Job-First (SJF), with no time slice
• Priority, with random priority levels 0-4 assigned to processes at the onset (low numbers indicate high priority); processes with the same priority are processed in FCFS order with no time slice

Each process starts in the ready queue at time 0, though you may assume they are ordered by process ID. The CPU scheduler dispatches a ready process as designated by the given scheduling algorithm, and the process runs. When a context switch occurs, add t_cs, the overhead for performing the context switch. Set t_cs to 7 milliseconds.

Display a line of output for each of the following events:

• Process creation (display the process ID, required CPU time, and priority)
• Context switch (display the two process IDs)
• Process's first CPU usage (display the process ID and wait time)
• Process termination (display the process ID and the turnaround time)

For each line of output, begin with the current elapsed time, as in:

[time 0ms] Process 1 created (requires 788ms CPU time, priority 2)
...
[time 4279ms] Context switch (swap out process 4 for process 18)
...
[time 4890ms] Process 5 accessed CPU for the first time (wait time 4890ms)
...
[time 5288ms] Process 3 terminated (turnaround time 5288ms)
...

Simulate the above operating system, running your simulation until all processes terminate. Upon completion, display the following data:

• Minimum, average, and maximum turnaround time
• Minimum, average, and maximum waiting time
• Throughput

Calculate the above values and show to three decimal places.

Part II:
Extend your simulation such that 20% of the n processes begin at time 0, the other 80% entering the system at random times in the range 100-5000 milliseconds.

As in Part I, simulate the operating system, running your simulation until all processes terminate. Note that there may be periods of time where no processes are in the system.

Compiler:
Use gcc/g++to compile your C/C++ code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). For Java programs, use javac to compile your code and java to execute it. For Python programs, use python (version 2.5.2) to execute your code. With multiple versions of Unix available, please be sure to use BSD Unix.

Clarifications and Hints:

1. Be sure to account for times when there are no processes in the system.
2. For the Priority scheduling algorithm, use Preemptive Priority scheduling. So, higher-priority processes entering the system may interrupt and preempt a running process.
3. Set n to 20, though be sure this is a configurable value (and test using other values of n).
4. Be sure your code is purely a simulation -- nothing more. There is no need to use fork() or other process-related system calls. All of the above should be simulated.
5. Further, do not use real-time measurements for this project. Simulate time using a (global) variable.
6. Be sure your program runs with no interactive user input, except for the selection of a scheduling algorithm.
7. Command-line arguments may be used to specify simulation parameters, but all such arguments must be optional (use given default values).
8. You may skip the very first context switch for the very first process. In other words, at time 0, your first process starts using the CPU.
9. When a process terminates, a context switch occurs to swap out the terminated process and swap in the next ready process. If there is no ready process, wait until one becomes available and simulate the context switch at that time.

Grading Criteria (OUT OF 120 POINTS):

1. Compiles and runs without errors, crashes, or warnings: 30 points
2. (Part I) Successfully simulates each of the four scheduling algorithms: 40 points
3. (Part I) Displays lines of output for each case (mimicking the output format above): 10 points
4. (Part I) Displays correct statistics at end of simulation (as shown above): 15 points
5. (Part I) Statistics shown to three decimal places, as specified above: 5 points
6. (Part II) Successfully simulates each of the four scheduling algorithms given 80% of processes have non-zero arrival times: 20 points
7. (Late) -10 points per "business" day, up to 5 days maximum

» show details

« hide details

This homework assignment is to be completed individually. Do not share code or review anyone else's code. Work on this homework assignment is to be your own.

Submit your homework via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name at the top of each file submitted.

On campus BSD Unix systems, write a sockets-based system using C to create a cache-server for integers. The server (written in C) maintains a list or array of integers. At most, the server stores 1000 integers.

To start your cache-server, use the port number specified on the command-line. In general, use a port number in the range 8000-9000 for your server; if you run into a bind error, choose another port number.

When you start your server, your output must appear as follows (no other server output is required):

bash-3.2$ cache-server 8128
Started cache-server
Listening on port 8128

Clients connect to the server and either add or remove elements from the end of the list, so the list actually acts as a stack.

Clients communicate with the server using strings (i.e. streams of bytes). Implement the following protocol:

Client commands:

A <integer>  -- add <integer> to the end of list (HINT: use atoi() function)
S            -- server returns the size of (i.e. number of elements in) the list
G            -- get: server returns the last element from the array and also
                     removes it from the list

In your client code, create a test case that generates 100 random integers (in the range 1-6) and sends them to the cache-server. Display the integers in the client as you send them to the server.

To confirm on the server side, use the client to obtain and display the number of elements in the list. Next, remove and display ten elements.

To start your cache-client, specify the cache-server's hostname and port number on the command-line. Your client output must be formatted as follows:

bash-3.2$ cache-client monica.cs.rpi.edu 8128
Started cache-client
Server is monica.cs.rpi.edu:8128
Adding 5
Adding 3
Adding 3
Adding 6
Adding 1
...
Adding 2
Adding 3
Adding 5
Cache-server has 100 integers
Removed 5
Removed 3
Removed 2
...

As a further test, run your cache-client again (without restarting your cache-server). This time, you should see a total of 190 integers, as shown in the following sample output:

bash-3.2$ cache-client monica.cs.rpi.edu 8128
Started cache-client
Server is monica.cs.rpi.edu:8128
Adding 2
Adding 5
Adding 3
Adding 6
Adding 6
...
Adding 3
Adding 4
Adding 1
Cache-server has 190 integers
Removed 1
Removed 4
Removed 3
...

EXTRA CREDIT: implement the protocol and repeat the tests above by creating a Java cache-client that successfully interacts with the C cache-server.

EXTRA CREDIT: implement the protocol and repeat the tests above by creating a Java cache-server that successfully interacts with both the C cache-client and the Java cache-client.

Compiler:
Use gcc to compile your C code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). Use javac to compile your Java code; and use the java virtual machine to execute your Java code. With multiple versions of Unix available, please be sure to use BSD Unix.

Grading Criteria:

1. Compiles without errors or warnings (use -Wall with gcc): 40 points
2. (Penalty) Warnings during compilation: -5 points per warning
3. Correct communication between client and server: 20 points
4. Client code executes required test case and displays output correctly (as shown above): 20 points
5. Client code executes second test case and displays output correctly without restarting the server (as shown above): 10 points
6. Well-commented and well-designed solution: 5 points
7. Handles error conditions gracefully: 5 points
8. (Extra Credit) Java cache-client works properly (both test cases) with C cache-server: 10 points
9. (Extra Credit) C cache-client works properly (both test cases) with Java cache-server: 10 points
10. (Late) -10 points per "business" day, up to 5 days maximum

» show details

« hide details

This project is to be completed individually or in teams of up to three students. Beyond your team, do not share code or review anyone else's code.

Submit your project via this link as a single compressed and zipped file (using tar and gzip); include only source code and documentation files. Log into the submission site using either your RCS ID and password or your CS ID and password.

Be sure to comment your code and include your name(s) at the top of each file submitted.

Initialialization:
On campus BSD Unix systems, using C, C++, Java, or Python (contact the instructor if you'd like to use another language), design and implement a simulation program for memory management in an operating system.

Use a 1-dimensional character array of size 2400 to represent main memory. Each cell of the array represents an equally sized chunk of memory. The resident operating system processes are fixed in size and loaded into memory at array locations 0-79.

Using continguous memory allocation, assign 20 user processes to memory, each process requiring a random amount (in the range 10-100) of memory cells. Use the following character mappings:

• A '.' character represents a free memory cell.
• A '#' character represents an operating system process memory cell.
• An ASCII character in the range 'A'-'Z' and 'a'-'z' (i.e. uppercase and lowercase letters) represents a user process memory cell. Feel free to use the character sequence A-Z[\]^_`a-z if it makes implementation easier.

Cycle through the character set to uniquely identify each process, looping back to 'A' after process 'z' has been allocated. Be sure no duplicates are used (i.e. to reuse 'A', first be sure memory is not still allocated to 'A').

In general, as your simulation attempts to place processes in memory, it's possible you will not be able to allocate a contiguous block of memory. If this occurs, display an error message (e.g. OUT-OF-MEMORY) and exit the simulation.

Once your simulation has been set up, show the memory allocation by displaying your array 80 characters to a line, as in:

################################################################################
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFF
FFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGHHHHHHHHHHHHHHHHHHHHHHHHHHH
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJJJJJJKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLMMMMMMMMMMMMMMMMMMMMMMMMM
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPQQQQQQQQQQQQQQQQQQQ
QQQQQQQQRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTTTT
TTTT............................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................

Simulation:
Use a command-line argument to specify the type of memory allocation algorithm to use. Your program must be called memsim and follow these usage specifications:

bash-3.2$ memsim
USAGE: memsim  { first | best | next | worst }  <new-proc-prob>
bash-3.2$ memsim first 40
...
bash-3.2$ memsim best 30
...
bash-3.2$ memsim next 40
...
bash-3.2$ memsim worst 60
...

Create a loop controlled by the user (see below); at each iteration, two types of events occur in the given order:

1. Processes exit the system: each process has a 20% probability of terminating, in which case its memory is marked as free;
2. A new process enters the system: a new process enters the system with probability <new-proc-prob> (as specified on the command-line), requiring a random amount (10-100) of memory cells.

At each iteration of the loop, display your memory, then prompt the user to press ENTER to continue.

Use the memory allocation algorithm specified on the command-line (i.e. first-fit, best-fit, next-fit, and worst-fit).

EXTRA CREDIT: if your program reaches an OUT-OF-MEMORY condition, perform defragmentation or compaction and continue running. Display the memory once defragmentation has completed.

Compiler:
Use gcc/g++to compile your C/C++ code (and specify -Wall to ensure all compiler warnings are addressed before submitting your assignment). For Java programs, use javac to compile your code and java to execute it. For Python programs, use python (version 2.5.2) to execute your code. With multiple versions of Unix available, please be sure to use BSD Unix.