Simulator - dverenna/osproj2 GitHub Wiki

There are several main data structures in our simulator, the processors, the processes, and the memory management. Below you will find an explanation of the main data structures in our simulator.

Processor:

  • We have made our processor a Process queue, we did this so we can easily edit the memory that each processor has.

Process:

  • We have made our process into an object. Our process object contains:
  • Integer for ID and Memory requirement
  • A long long integer for our burst time, arrival time, and end time of the process. We did this so, we won't have to worry about a process having requiring more memory to store one of these variables.
  • We made our memory location an integer pointer, so we can easily locate our process in our processors and in our memory.

Memory Management:

  • To manage our memory we decided to use a double linked list of nodes.
  • Within the nodes contained the process ID, memory requirements, arrival time, end time, and burst time.
  • Within our linked list we made our front and tail buffers with the memory ending at 0 and the maximum memory.
  • We also used a map with a key as the process ID (integer) and Boolean to tell if a process has been swapped off once.
  • Once a map key (process ID) resulted in a Boolean that was true, we then told the program to reject the process.

Since we have given a general description of our main data structures, we are going to move onto pieces of functionality.

Simulator:

  • We begin our simulator by clearing the memory in our linked list.
  • Next we initialize all of our necessary variables like, memory size, processor speed, processor counts for all four processors, four memory pointers, etc.
  • We initialize our ready queue and our result queue and set our process count to 0.
  • After this we initialize the seeds for the RNG.
  • After this we initialize our map that will be used to store processes that memory is too fragmented to currently accept.
  • The next step is to initialize our process placeholders which will signify the program when a processor is available.
  • We then set the total memory size in kilobytes so that the rear node of our linked list has the proper value for each scenario.
  • We now start the time.
  • While the 40 processes have not been completed, each of the processors performs the following actions:
    • Checks if the processor is currently set to "dummy" and thus waiting for a process to be put on. If it is set to dummy, if first checks if the process's total amount of memory required is larger than the amount of memory in the system for that scenario. Then, if it has a valid amount of memory it allocates the memory based on which of the scenarios is currently in progress.
    • If it is scenario 1, the memory is allocated using malloc() and the address that was allocated is then saved into the process object so it can print where it was in memory during it's execution.
    • If it is scenario 2, 3, or 4, the memory is allocated via my_malloc, which places it in a double-linked list
    • If there was not room for the process in the linked list due to fragmentation, its id is placed into the fragMap, to denote that it was swapped out once.
    • If the process has already been placed into the fragMap and appears again while the readyQueue is empty, it is decided to be skipped since the memory is currently too fragmented to let the process enter and there is nothing left to swap it out with
    • Once a process is swapped off, it is placed into a storage queue. A new process is taken off of the ready queue and tested if it has space to be allocated currently. This process repeats until a process that can fit is placed into the system. Once a process is found, the processes from the storage queue are placed back into the ready queue
    • Once a process is found that can fit into the linked list, the location where the process is being stored is loaded into the object so it is available for the toString() method
    • Finally, regardless of what allocated the memory the process is loaded into a tuple that also contains burst time so the execution can begin
    • Increments the cycle counter by the processors speed, gets the current remaining time and the process object for the process that is currently on the CPU, and decrements the remaining time by the clock speed of the CPU.
    • If the process is not completed at that point, the tuple is updated with the new remaining time.
    • If the process is completed at that point, the end time is then set to the cycle where the process actually ended, and the clock is rolled back to the final cycle of the process. The process is then put into the result queue, and the processor is set to having a dummy process so it knows it is ready for a new process. Additionally the memory is freed so it can be used by later processes.

my_malloc():

  • Traverses through the double linked lists of nodes until it finds the node where a gap which is large enough between its starting memory location and the previous node's ending memory location.
  • Once this memory block is found, it performs a standard linked list insertion, but it makes sure that the next process starts where the previous process ended and the new process ends after required memory units after it starts.

my_free():

  • This frees the memory by removing the node from the double linked list.