Operating Systems

CSCI 4300/6150 – Operating Sys. Spring 2020 Programming Assignment 2

Due:

3/29/2020

Name:

Submission Instructions

This programming assignment includes two problems. In both problems you are provided with incomplete programs and you are required to write the missing code. The problem descriptions specify what you need to do.

When you are ready to turn in your work, zip your code and your output screenshots for both problems altogether in a single file. The zipped archive you submit should have the following structure:

OS HW2 LastName FirstName.zip

Problem-1

Problem-1.1

main.cpp

screenshots

…

Problem-1.2

main.cpp

screenshots

…

Problem-2

Problem-2.1

main.cpp

screenshots

…

Note that “main.cpp” and “screenshots ” are just examples. You don’t have to give the same names. You can also attach multiple source files (need an instruction of how to compile) and screenshots.

Problem. 1. (60 points) Scheduling

In this problem you will work with the following files: “fifo.cpp”, “fifo.h”, and “pcb.cpp”. The file “fifo.cpp” defines a class with three functions:

1. Function RunProcess() simulates the execution of a process. It changes the process’s state from W (waiting) to R (ready) and records the start and finish times.
2. Function Schedule() has a while loop which retrieves a process from the queue’s head and runs it.
   Note that the head process always has an earlier arriving time than the
3. Function CreateProcess() creates a new process.

• remaining processes.

You are required to complete the following two tasks:

(a) (30 points) 1 FIFO Scheduling Complete the missing parts of function CreateProcess() by doing the following:

– Suppose that the list is empty at the beginning (head==NULL). – For every “new proc”, you need to insert it into a correct position for FIFO schedule

based on the arriving time.

– The last process‘s next should point to NULL. – You should get a similar output as Figure 1

Figure 1: Sample FIFO scheduler output

(b) (30 points) Round Robin Scheduling

Copy the three files (“fifo.cpp”, “fifo.h”, and “pcb.cpp”) to another folder. Rewrite the functions Schedule() and RunProcess() to use the Round Robin scheduling algo rithm. Note that you should use the same CreateProcess() function that you created in Problem 2(a) above. Here is what you are required to do:

– Assume that the time slice in Round Robin is 2. – In the RunProcess() function, print out the process name, start time, finish time, and

remaining time of the current job.

– The last process’s next should point to NULL. – You should get an output similar to Figure 2

CSCI 4300/6150 – Operating Sys.Programming Assignment 2 – Page 3 of 4

3/29/2020

Figure 2: Sample Round Robin scheduler output

Problem. 2. (60 points) Cache

In this problem you will work with the following files: “lfu.cpp”, and “lfu.h”. The file “lfu.cpp” defines a Least Frequently Used (LFU) cache replacement class with the following two functions: get() retrieves a memory page from cache, and set() stores a memory page in cache

1. (30 points) LFU Cache Replacement You are required to complete the implementation of the two functions, get() and set(), based on the Least Frequently Used cache replacement algorithm (note that you shouldn’t change the other functions in class LFU). Here is what you need to accomplish:
   Hashmap “cache” is to record the visit frequency and last visit time of a cache entry.
   Hashmap “KV” is to store the real cache entry. Key is the index of the entry and value is the data stored in the entry.
   Function “getMin()” is to get the least frequently used entry.
   Function “compare()” is to compare two records in hashmap “cache” based on the rerquency and then last visit time.
   Your output should be similar to Figure 3

Figure 3: Sample LFU cache replacement output

(b) (30 points) Least Recently Used (LRU) cache replacement Implement the Least Recently Used (LRU) cache replacement algorithm using linked list in C/C++. You can use Problem 2(a) above as a reference. Here is what you are required to do:

– You should have a “set()” function which adds new entry to the tail of the linked

list. If the list is full, kick the first entry (the least recently used entry) out.

– You should have a get function which retrieves a value from an entry. You need to

move the current entry to the tail because it is the most recently used entry. – Your output should be similar to Figure 4

Figure 4: Sample LRU cache replacement output