/*================================================================= ============================= sim.c ============================== =================================================================*/ #include #include #include "sim_startup.h" /*================================================================= ********************** IORequest/IOComplete *********************** =================================================================*/ /* Functions that determine when processes block and complete based on a random number generator. */ Boolean IORequest() { if ( rand() % CHANCE_OF_IO_REQUEST == 0 ) return True; else return False; } Boolean IOComplete() { if ( rand() % CHANCE_OF_IO_COMPLETE == 0 ) return True; else return False; } /*================================================================= ************************** SetDirtyBit **************************** =================================================================*/ /* This function returns true when the memory reference is considered to be a write. */ Boolean SetDirtyBit() { if ( rand() % CHANCE_OF_WRITING == 0 ) return True; else return False; } /*================================================================= *********************** GetNumMemRequests ************************* =================================================================*/ /* This function returns the number of memory references a process makes during one clock cycle. */ int GetNumMemRefs() { return rand()%MAX_NUMBER_OF_REFERENCES; } /*================================================================= ************************** RandMemAccess ************************** =================================================================*/ /* This function returns a value to be added or subtracted from the next memory reference. */ int RandMemAccess(last_ref, data_size, locality_counter) int last_ref, data_size, locality_counter; { static int sign = 1; /* Flip the sign. */ sign = (sign == 1) ? -1 : 1; /* Long jump if we have made LOCALITY_JUMP number of references. */ if ( locality_counter % LOCALITY_JUMP == 0 ) last_ref += sign*(rand()%data_size); /* Else Remain in the locality of the last reference. */ else last_ref += sign*(rand()%(data_size/50)); /* Make negative references positive. */ if ( last_ref < 0 ) last_ref *=-1; /* Chance of core dump. */ if ( last_ref > data_size ) last_ref %= (data_size + 10); return last_ref; } /*================================================================= ***************************** AddPCBQ ***************************** =================================================================*/ /* This function adds the pcb parameter to the end (if normal is True) or front (if false) of the queue given as a parameter. */ AddPCBQ(queue_ptr, pcb1, normal) PCBQueue *queue_ptr; struct PCB *pcb1; Boolean normal; { struct PCB *pcb2; /* Dont try to add a NULL PCB to a queue. */ if ( pcb1 == NULL ) { printf("AddPCBQ(): ERROR: NULL pcb !\n" ); fflush(stdout); return; } /* If the queue pointer is not NULL, add the new PCB to the front or end of the ready queue. */ if ( *queue_ptr != NULL ) { /* Find the end of the list. */ pcb2 = *queue_ptr; if ( normal == True ) { while (pcb2->next != NULL) pcb2 = pcb2->next; /* Assign the last PCB next field to point to the PCB to be added. */ pcb2->next = pcb1; } else { *queue_ptr = pcb1; pcb1->next = pcb2; } } /* Queue is empty - assign PCB to header. */ else *queue_ptr = pcb1; /* The last element's next pointer MUST be NULL. */ if ( normal == True ) pcb1->next = NULL; } /*================================================================= ************************** RemovePCBQ ***************************** =================================================================*/ /* This function removes an element from the front of the queue, if ele is NULL, otherwise it removes ele from the queue. */ struct PCB *RemovePCBQ(queue_ptr, ele) PCBQueue *queue_ptr; struct PCB *ele; { struct PCB *pcb1, *pcb2 = NULL; /* If queue is NULL, return NULL and print error. */ if ( *queue_ptr == NULL ) { printf("RemovePCBQ(): ERROR: NULL queue !\n" ); return NULL; } /* If ele is NULL, grab the PCB on the front of the queue. */ if ( ele == NULL ) { pcb1 = *queue_ptr; *queue_ptr = pcb1->next; } /* Else find the PCB in the list and remove it. */ else { for ( pcb1 = *queue_ptr; pcb1 != NULL; pcb1 = pcb1->next ) { if ( ele == pcb1 ) break; pcb2 = pcb1; } /* If we executed the above loop successfully at least once, then update the previous PCB pointer's next field. */ if ( pcb2 != NULL ) pcb2->next = pcb1->next; else *queue_ptr = pcb1->next; } pcb1->next = NULL; return pcb1; } /*================================================================= *************************** QsHavePCBs **************************** =================================================================*/ /* Check all the queues to determine if any are nonempty. This function will be used to terminate the simulation. */ Boolean QsHavePCBs(readyQ, blockedQ, suspendQ) PCBQueue readyQ, blockedQ, suspendQ; { int i; if ( readyQ != NULL ) return True; if ( blockedQ != NULL ) return True; if ( suspendQ != NULL ) return True; return False; } /*================================================================= ************************* AddNewProcesses ************************* =================================================================*/ /* This function moves PCBs from the list created from the input file (and sorted by arrival time) to the suspend queue. It moves all processes with arrival time equal to the value of clock to the suspend queue and updates the pcb_list_ptr. */ AddNewProcesses(pcb_list_ptr, Q_ptr, clock) struct PCB **pcb_list_ptr; PCBQueue *Q_ptr; int clock; { struct PCB *pcb1; /* Add processes that match the current value of clock to the ready queue. Since the list is sorted by arrival time, we continue until the list is NULL or the arrival time is greater than the value of clock. */ while ( *pcb_list_ptr != NULL && (*pcb_list_ptr)->arr_time == clock ) { /* Get the item from the front of *pcb_list_ptr and then move the pointer forward. This MUST be done before calling AddPCBQ since AddPCBQ will set the pcb1 next field to NULL ! */ pcb1 = *pcb_list_ptr; *pcb_list_ptr = (*pcb_list_ptr)->next; pcb1->status = Suspended; pcb1->suspend_start_clock = clock; AddPCBQ(Q_ptr, pcb1, True); /* Queue up the initial memory allocation request of the process - to be processed by the MST. */ AddMemRequest( pcb1->pid, Create, pcb1->data_size, -1, -1 ); } } /*================================================================= **************************** ChoosePCB **************************** =================================================================*/ /* This function chooses the next process to run from the ready queue. The PCB of a running process is removed from the ready queue. If cur_job is non-NULL, it is inserted on the end of the ready queue. */ struct PCB *ChoosePCB(cur_job, readyQ_ptr, sleep) struct PCB *cur_job; PCBQueue *readyQ_ptr; int sleep; { /* Put the cur_job back on a queue if non-NULL. */ if ( cur_job != NULL ) { /* This should already be NULL but no sense taking any chances. */ cur_job->next = NULL; AddPCBQ(readyQ_ptr, cur_job, True); } /* Check the global MEM_REQUESTS queue. If memory requests are pending, make the MST the next job to run. */ if ( MEM_REQUESTS != NULL && sleep == 0 ) return NULL; /* No PCBs on the ready queue. */ if ( *readyQ_ptr == NULL ) return NULL; /* Remove and return the PCB on the front of the queue. */ return(RemovePCBQ(readyQ_ptr, NULL)); } /*================================================================= ************************ AddIOCompletePCBs ************************ =================================================================*/ /* This function removes processes from the blocked queue and puts them back on the ready queue. It also computes several statistics. */ AddIOCompletePCBs(readyQ_ptr, blockedQ_ptr, clock) PCBQueue *readyQ_ptr, *blockedQ_ptr; int clock; { struct PCB *pcb1, *pcb2 = NULL; /* If no processes are blocked, return. */ if ( *blockedQ_ptr == NULL ) return; /* Check all PCBs on the blocked queue. Call IOComplete to determine if the current process is to be woke up. */ for ( pcb1 = *blockedQ_ptr; pcb1 != NULL; ) if ( IOComplete() == True ) { /* If the current PCB has unblocked, update its status to Ready and compute the amount of time it was on the blocked queue. The assumption that I've used is that if a process runs for any part of the clock, it is considered to have run for the whole slice. Therefore, if the process blocked on the current clock, blocked_start_clock is set to clock + 1. */ pcb1->status = Ready; pcb1->wait_start_clock = clock; if ( pcb1->blocked_start_clock != INVALID ) pcb1->blocked_clocks += clock - pcb1->blocked_start_clock; pcb1->blocked_start_clock = INVALID; /* This MUST precede the call to RemovePCBQ since RemovePCBQ will remove this PCB from the list and set its next pointer to NULL. */ pcb2 = pcb1; pcb1 = pcb1->next; /* Note that RemovePCBQ will update the blockedQ to point to the next element. */ AddPCBQ(readyQ_ptr, RemovePCBQ(blockedQ_ptr, pcb2), True); } else pcb1 = pcb1->next; } /*================================================================= ************************** CheckIORequest ************************* =================================================================*/ /* This function checks if the current job request IO by calling the random function. If it does, then its status is updated and it is added to the blocked queue. */ CheckIORequest(cur_job, clock) struct PCB *cur_job; int clock; { /* Check IO request. */ if ( IORequest() == False ) return; /* If the current job blocks for IO, update its status. */ cur_job->status = Blocked; cur_job->blocked_start_clock = clock; } /*================================================================= *************************** UpdateStats *************************** =================================================================*/ /* Update the statistics of the currently running process. */ UpdateStats(cur_job, clock) struct PCB *cur_job; int clock; { if ( cur_job == NULL ) { printf("UpdateStats(): ERROR: NULL cur_job !\n"); return; } cur_job->run_clocks += 1; /* If this job's time slice expired, record the time it goes onto the ready queue. */ if ( cur_job->status == Ready ) cur_job->wait_start_clock = clock; else cur_job->wait_start_clock = INVALID; } /*================================================================= ************************** PrintVerbose *************************** =================================================================*/ PrintVerbose(cur_job, clock) struct PCB *cur_job; int clock; { int i; if ( cur_job != NULL ) printf("%d:%d:%d:", clock-1, cur_job->pid, cur_job->ser_time-cur_job->run_clocks ); else printf("%d:idle:???:", clock-1); if ( cur_job != NULL ) { if ( cur_job->status == Blocked ) printf("true:"); else printf("false:"); } else printf("false:"); if ( cur_job != NULL ) { switch(cur_job->status) { case Running: printf("Running");break; case Ready: printf("Time Slice Expired");break; case Blocked: printf("Blocked");break; case Suspended: printf("Suspended");break; case Completed: printf("Completed");break; case Crashed: printf("Crashed");break; default: printf("UNKNOWN"); } printf("\n"); } else printf("IDLE\n"); } /*================================================================= ******************************* main ****************************** =================================================================*/ /* THIS IS NOT COMPLETE, YOU WILL HAVE TO ADD CODE TO main. */ main(argc, argv) int argc; char **argv; { struct PCB *pcb_start_list, *pcb1 = NULL, *cur_job = NULL; int shortest, longest, average, job_completion_clocks; PCBQueue readyQ = NULL, blockedQ = NULL, suspendQ = NULL; SegmentBaseEle seg_base_table[MAX_NUM_PROCESSES]; PageFrameEle page_frame_table[NUM_PAGE_FRAMES]; struct PCB *pcb_finished_list = NULL; int cnt = 0, i, j, clock = 0, sleep = 0; int tl_pnum, sl_pnum; int num_mem_refs = 0; /* Check command line args and do other initializations. */ ... /* Seed the random number generator. */ srand(1); /* Read the input from standard in. */ ReadDataFile(&pcb_start_list, &cnt); /* Bubble sort by arrival time. */ BubbleSort(&pcb_start_list, cnt, 2); /* Begin simulator. Add processes arriving at time 0. */ AddNewProcesses(&pcb_start_list, &suspendQ, clock); clock++; /* ========================= */ /* OUTER WHILE - loop until all processes have terminated. */ /* ========================= */ while ( QsHavePCBs(readyQ, blockedQ, suspendQ) == True || cur_job != NULL || MEM_REQUESTS != NULL ) { /* Choose the next job. If no jobs exist on the readyQ, then NULL is returned. The same is true when there are memory requests on the MEM_REQUESTS queue and the MST is not sleeping. I distinguish these below. */ cur_job = ChoosePCB(cur_job, &readyQ, sleep); /* Either run MST or the idle process. */ if ( cur_job == NULL ) { /* Run MST if the MEM_REQUESTS queue is non-NULL. */ if ( MEM_REQUESTS != NULL && sleep == 0 ) MST(...); else if ( sleep > 0 ) sleep--; /* Idle processes take up processor time (clock ticks). Therefore, we must add new processes to the ready queue and check for IO completion of blocked processes. */ AddNewProcesses(&pcb_start_list, &suspendQ, clock); AddIOCompletePCBs(&readyQ, &blockedQ, clock); if ( 1 ) PrintVerbose(cur_job, clock); clock++; continue; } /* Set the state of the selected job to running. Note that clock is always set to the following clock cycle. */ cur_job->status = Running; cur_job->start_slice = clock-1; /* Update the amount of time this process has spent on the wait queue. wait_start_clock is always set to the following clock cycle when it blocks (the clock cycle it begins to wait). However, clock is always set to the following clock and the current process is running (not waiting) on the previous clock, therefore I need to subtract 1 to get the number of wait cycles. */ if ( cur_job->wait_start_clock != INVALID ) cur_job->wait_clocks += clock - cur_job->wait_start_clock - 1; /* ========================= */ /* INNER WHILE - run the current process until its time slice expires, it blocks, it terminates or it suspends. */ /* ========================= */ while (1) { /* Add new processes arriving at the current value of clock (which is the beginning of the next clock cycle). */ AddNewProcesses(&pcb_start_list, &suspendQ, clock); /* Check for jobs that have completed their IO. Remove them from the blocked queue and add them to the appropriate ready queue. */ AddIOCompletePCBs(&readyQ, &blockedQ, clock); /* Check if the current job has completed - if its time remaining is equal to 1. */ if ( cur_job->run_clocks == cur_job->ser_time - 1 ) { cur_job->status = Completed; cur_job->finish_clock = clock; /* Request that the page tables be freed up. */ AddMemRequest(...); } /* If cur_job is Running, or not completed. */ if ( cur_job->status == Running ) { /* Get the number of memory requests using random number generator. */ num_mem_refs = GetNumMemRefs(); /* Process each of the requests. */ for ( i = 0; i < num_mem_refs; i++ ) { if ( cur_job->page_fault == False ) cur_job->last_ref = RandMemAccess(cur_job->last_ref, cur_job->data_size, cur_job->locality_counter++); else cur_job->page_fault = False; if ( PagePresent(...) == False ) { /* Check reference out of bounds - kill process. */ if ( out of bounds ) { cur_job->status = Crashed; cur_job->finish_clock = clock; /* Request that the page tables be freed up. */ AddMemRequest( ... ); } /* Page fault - Page table or page not present. */ else { AddMemRequest( ... ); cur_job->page_fault = True; } /* Break in either case. */ break; } } /* If page fault occurs, put cur_job on suspended queue and mark suspended. Do NOT put crashed processes back on the suspend queue. */ if ( i != num_mem_refs && cur_job->status == Running ) { cur_job->status = Suspended; cur_job->suspend_start_clock = clock; } } /* Check if the current job blocks for IO. If so, update status to blocked. Note that it is also added to the blocked queue so cur_job needs to be set to NULL. */ if ( cur_job->status == Running ) CheckIORequest(cur_job, clock); /* Decrement the value of sleep for MST if its greater than 0. */ if ( sleep > 0 ) sleep--; /* Check for time slice expiration. */ if ( cur_job->status == Running ) { if ( cur_job->start_slice + TIME_SLICE == clock ) cur_job->status = Ready; if ( MEM_REQUESTS != NULL && sleep == 0 ) cur_job->status = Ready; } /* Update statistics for current job only. */ UpdateStats(cur_job, clock); /* Print out verbose output. */ if ( 1 ) PrintVerbose(cur_job, clock); /* Update the clock. */ clock++; /* Break out of inner loop if one of a number of conditions hold. */ if ( cur_job->status != Running ) { if ( cur_job->status == Completed || cur_job->status == Crashed ) AddPCBQ(&pcb_finished_list, cur_job, True); if ( cur_job->status == Suspended ) AddPCBQ(&suspendQ, cur_job, True); if ( cur_job->status == Blocked ) AddPCBQ(&blockedQ, cur_job, True); /* Don't put this job back on the ready queue if it is blocked (on the blocked queue) or finished (on the finished list) or suspended (on the suspended queue). */ if ( cur_job->status != Ready ) cur_job = NULL; break; } } } /* Print out the results. */ }