CSE 2431/5431 LAB 3: A Mini Operating System
CSE 2431/5431 LAB 3
1. Goal
Create a simulation of an operating system that uses Shortest Job First and Round robin CPU scheduling with paging and two page replacement algorithms.
2. Introduction
This lab assignment asks you to build a simple simulation of an operating system using the C Programming Language that assigns the CPU to a process, loads instructions into a program counter, and uses paging to load the appropriate virtual memory locations into physical memory using execution time binding. The operating system simulation uses a struct representing the process control block and a file per process that contains the “instructions” for that process. Template code is provided that includes all required data structures and loads the provided files into locations in structure “memory” once a frame location is chosen.
Output is given to demonstrate when a page fault occurs and show the instructions each process “executes.”
3. A Mini Operating System
A C program that provides all required data structures and limited additional functionality can be found in the assignment where these instructions are linked. This template code initializes a free frame list as well as an array of memory structs that functions as a series of frames. The template code initializes process control blocks for each process, including an empty page table per process and a random number of instructions that represents the CPU burst for each process.
For your Lab 3, there are four functions that must be completed for full credit, in addition to two lines in a fifth function that must be completed to finish the process of translating from virtual address to physical address. These two lines complete the separation of a single virtual address into a page number and byte offset. In addition to this, you will implement two CPU scheduling algorithms and two Page replacement algorithms.
The FIFO CPU scheduling algorithm has already been implemented to give an illustration of how to use the functions provided. You will instead implement Shortest Job First and Round Robin. To simplify this task, no arrival times are provided. You can instead assume that all processes are present in the system and they arrived in numerical order of process ID. The CPU scheduling functions do not return a value.
The Page replacement algorithms take in the process that is currently suffering from a page fault, and returns the frame number that will be chosen for replacement. For simplicity, we are assuming local page replacement rather than global page replacement, and we are assuming that no process may be allocated more than the number of total frames divided by the number of processes in system. For this lab assignment, you will implement one (1) Least Recently Used approximation algorithm, but you may choose which implementation. Data structures are already in place to support a timestamp per frame or a boolean replacement bit.
The second page replacement algorithm you choose to implement may be a second LRU approximation method, FIFO, or a counting algorithm like LFU or MFU. Data structures are already in place to support a count of the number of accesses since being brought into memory. Memory metadata structs have already been set up as a form of linked list to make it easier to implement FIFO or the second chance algorithm.
Bonus point available: If you decide to use either the stack method, you will need to build the data structure to support this.
4. Test cases
A list of defined values are provided at the beginning of the template code assignment that you may use to test your miniature operating system. These include toggles such as debug, quantum, and page size.
General Instructions
Write your own Makefile. The output file should be lab3.
Pack all your file in a zip file and submit it on Carmen.
Any program that does not compile will receive a zero. The TA will not spend any time to fix your code due to simple errors you introduce at the last minute. It is your responsibility to leave yourself enough time to ensure that your code can be compiled, run, and tested well before the due date.
