Your cart is currently empty!
Priority Queue of Processes (100 points) Overall Goal The goal of this assignment is to help you review C/C++ data structures and familiarize you with Unix/Linux programming. You should carefully read the programming policies and submission guidelines before start. Overview In this assignment you need to implement some commonly…
Priority Queue of Processes (100 points)
Overall Goal
The goal of this assignment is to help you review C/C++ data structures and familiarize you with Unix/Linux programming.
You should carefully read the programming policies and submission guidelines before start.
Overview
In this assignment you need to implement some commonly used data structures in operating systems, including:
PCB : Process control block (PCB) is a data structure representing a process in the system. A process should have at least an ID and a state (i.e. NEW, READY, RUNNING, WAITING or TERMINATED). It may also have other attributes, such as Program Counter, CPU Registers, scheduling information (e.g. priority), Memory-management information and I/O status information etc.
PCB Table: An array(list) of PCB elements. It contains all processes currently in the system.
ReadyQueue: This is a queue of processes that are in the READY state to be scheduled to run. It needs to be a priority queue such that the process with the highest priority can be selected next. It should support at least following operations:
insertProc: add the PCB of a process into the ready queue.
removeHighestProc : remove and return the PCB with the highest priority from the queue
size : return the number of elements in the queue
displayQueue : Display the IDs and priorities of processes in the queue.
You have the freedom of choosing the data structure, for example linked-list, array, binary tree or heap, used for implementing the Ready_Queue. However, you cannot directly use any exsiting priority queue data structure, for example the one from STL. The choice of your implementation is critical for the performance of your program. In the report you should discuss your choice of data structure, the time complexity of your implementation, and how the timing results match with your expectations.
Required Output
Read and follow the programming policies and submission guidelines.
You need to write a driver(main) program to test your data structures as follows. As a good program structure, the main program should be in a separate le from the classes. Your program should rst print your name when it starts.
1
Measure the total time of running the 1,000,000 iterations and print out the nal content of the ReadyQueue (don’t print in each of the iteration). Hint: You may use the UNIX gettimeofday function to measure the time. type man gettimeofday in a Unix shell to get more information or look it up online.
The timing results of your program should be measured on the class server. You may run your program a few times and take the average. In the report, you should present and discuss your timing results.
Useful Things to Start
You must provide your source code and Make le so that I can compile you program with the make command. I provide you a dummy test.c le and a Make le for students who haven’t used Make le before. You can download them as a zip le from the class website or copy them form directory /cs433/example on the cs433.cs.csusm.edu server. You should modify the make le for your own project. Read the Unix programming tools doc and links to additional resources for more information. Use -g compilation ag for g++ when debugging your program and -O or -O2 to generate optimized code for timing test 2. The group that implements test2 correctly and has the fastest time will get 10 points extra credit.
2