C++ Programming Homework

Your name: S number: Programming Assignment 2

CSCI 4300/6150 Operating Systems October 5, 2019

1 Submission Instruction

Zip your codes and screenshots of the output in a single file. Your submission should be only one zip file which looks like:

s num first last name.zip

problem-1

problem-1.1

main.cpp

screenshots.jpg

...

problem-2

problem-2.1

main.cpp

screenshots.jpg

...

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

2 Problem 1 - Scheduling (60 Points)

2.1 Complete “fifo.cpp” for a FIFO scheduling algorithm. Instruc- tion:

1. Function “RunProcess()” is to simulate the the run time of a process. It changes the state from ’W’ (waiting) to ’R’ and record the start time and the finish time.

2. Function “Schedule()” has a while loop. It retrieves a process from the head and runs it. Note that the head process always has a earlier arriving time than the remaining processes.

3. You need to complete the missing part of function “CreateProcess”:

• 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 sched-

ule based on the arriving time.

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

1

Your name: S number: Programming Assignment 2

CSCI 4300/6150 Operating Systems October 5, 2019

Figure 1: Sample output

2.2 Copy “pcb.h”, “fifo.h” and “fifo.cpp” to another folder. Rewrite function “Schedule()” and “RunProcess()” to use Round Robin scheduling algorithm. Note that you should use the same “CreateProcess()” function that you created in Problem 2.1. Requirement:

1. Assume that the time slice for execution in Round Robin is 2.

2. In the “RunProcess()” function, print out the process name, start time, finish time, remaining time of the current job.

3. You should get a similar output as Figure 2.

Figure 2: Sample output

3 Problem 2 - Cache (40 Points)

3.1 Complete the “LFUCache::get()” and “LFUCache::set()” func- tions in lfu.cpp, to implement a last-frequently-used based cache replacement algorithm. Not that you shouldn’t change other functions. Instruction:

1. Hashmap “cache” is to record the visit frequency and last visit time of a cache entry.

2

Your name: S number: Programming Assignment 2

CSCI 4300/6150 Operating Systems October 5, 2019

2. 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.

3. Function “getMin()” is to get the least frequently used entry.

4. Function “compare()” is to compare two records in hashmap “cache” based on the frequency and then last visit time.

5. You should get a similar output as Figure 3.

Figure 3: Sample output

3.2 Implement the Least Recently Used (LRU) cache replacement algorithm using linked list in C/C++. You can use Prob- lem 3.1 as a reference. Requirement and hints:

1. 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.

2. You should have a get function, which retrieve a value from an entry. You need to move the current entry to the tail because it is the most recently used entry.

3. You should get a similar output as Figure 4 (using the same test data as it is in Problem 3.1.

Figure 4: Sample output

3