In assignment 1, we assumed that the system had an infinite amount of memory. In this assignment, the operating system has a limited amount of memory and this needs to be managed to meet process demands. You will write a program to simulate a system that uses paging with virtual memory. The characteristics of the system are described below:

• Memory: The system has F frames available in main memory. During execution, the processor will determine if the page required for the currently running process is in main memory.
  1. If the page is in main memory, the processor will access the instruction and continue.
  2. If the page is not in main memory, the processor will issue a page fault and block the process until the page has been transferred to main memory.
  3. Initially no page is in the memory. I.e. the simulation will be strictly demand paging, where pages are only brought into main memory when they are requested.
  4. In fixed allocation scheme frames are equally divided among processes, additional frames remain unused.
• Paging and virtual memory: The system uses paging (with no segmentation).
  1. Each process can have a maximum 50 pages where each page contains a single instruction.
  2. For page replacement you will need to apply least recently used (LRU) and clock
  3. Resident set is managed using Fixed Allocation with Local Replacement Scope strategy. I.e. you can assume, frames allocated to a process do not change over the simulation period and page replacements (if necessary) will occur within the allocated frames.
  4. All pages are read-only, so no page needs to be written back to disk.
• Page fault handling: When a page fault occurs, the interrupt routine will handle the fault by placing an I/O request into a queue, which will later be processed by the I/O controller to bring the page into main memory. This may require replacing a page in main memory using a page replacement policy (LRU or clock). Other processes should be scheduled to run while such an I/O operation is occurring.
  1. Issuing a page fault and blocking a process takes no time. If a page fault occurs then another ready process can run immediately at the same time unit.
  2. Swapping in a page takes 6 units of time (if a page required by a process is not in main memory, the process must be put into its blocked state until the required page is available).

• Scheduling: The system is to use a Round Robin short-term scheduling algorithm with time a quantum of Q.
  1. Executing a single instruction (i.e. a page) takes 1 unit of time.
  2. Switching the processes does not take any time.
  3. If multiple process becomes ready at the same time then they enter the ready queue in the order of their ID.
  4. All the processes start execution at time t=0.
  5. If a process becomes ready at time unit t then execution of that process can occur in the same time unit t without any delay.

You are to compare the performance of the LRU and clock page replacement algorithms for the fixed allocation with local replacement strategy.

Please use the basic versions of the policies introduced in lectures.

Input and Output:

Input to your program should be via command line arguments, where the arguments are system configurations and the names of files that specify the execution trace of different processes. All processes start execution at time 0, and are entered into the system in the order of the command line arguments (with the third argument being the earliest process). For example:

java A3 30 3 process1.txt process2.txt process3.txt

where 30 is the number of frames (F) and 3 is the quantum size (Q) for Round Robin algorithm and the other arguments are text file names containing page references for each process (these are relative filenames, and SHOULD NOT BE HARDCODED in anyway).

Since we assume that each page contains a single instruction, an execution trace is simply a page request sequence.

For example: (process1.txt)

begin 1

3

2

1

4 3 end

This specifies a process that first reads page 1, then page 3, and so on until the end is reached.

For each replacement strategy, the simulation should produce a summary showing, for each process, the total number of page faults, the time the page faults were generated, and the total turnaround time (including I/O time).

Sample inputs/outputs are provided. Working of the first example is presented with details of different levels. Your code will be tested with additional inputs.

Your program should output to standard output. Output should be strictly in the shown output format. If output is not generated in the required format then your program will be considered incorrect.

Programming Language:

The programming language is Java, versioned as per the University Lab Environment (currently a subversion of Java 1.8). You may only use standard Java libraries as part of your submission.

If you wish to use any language other than the preferred programming language, you must first notify (and justify this to) the course demonstrator (Dan).

User Interface:

The output should be printed to the console, and strictly following the output samples shown above (also given in the assignment package as separate files). You will lose marks if your program does not conform with the input/output formats.