------------------------------------------------------------------------------- ------------------------------------------------------------------------------- Sample sequence of operations that the simulator should perform for objective 3 ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------- Quick summary of function call sequence ------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- The following is the sequence of important function calls for one iteration in main's while loop to process a LOGON event. ------------------------------------------------------------------------------- main->Interrupt ->Interrupt_Handler->Logon_Service->Get_Script ->Next_pgm->Get_Memory->Alloc_seg ->Loader->Get_Instr ->Display_pgm ------------------------------------------------------------------------------- The following is the sequence of important function calls for one iteration in main's while loop to process an END event. ------------------------------------------------------------------------------- main->Interrupt ->Interrupt_Handler->End_Service->Get_Script ->Next_pgm->Dealloc_pgm->Dealloc_seg->Merg_seg ->Get_Memory->Alloc_seg ->Compact_mem ->Loader->Get_Instr ->Display_pgm ------------------------------------------------------------------------------- --------------- Sample sequence of operations with explanation --------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- Assume the following for this example. ------------------------------------------------------------------------------- logon.dat: LOGON U1 0 END U1 10 LOGON U2 25 END U1 30 END U2 50 new_events: ---------- ---------- ---------- ---------- ---------- |LOGON U1| -> |END U1| -> |LOGON U2| -> |END U1| -> |END U2| ---------- ---------- ---------- ---------- ---------- script.dat: EDITOR COMPILER LOGOFF LINKER LOGOFF ------------------------------------------------------------------------------- What happens? The first event on the new_events list is processed. ------------------------------------------------------------------------------- ---------- Interrupt() removes |LOGON U1| from new_events, sets EVENT=LOGON, and AGENT=U1. ---------- Interrupt_Handler() calls Logon_Service() since EVENT==LOGON. Logon_Service() allocates a new process context block (pcb) and saves it in termtable. Logon_Service() calls Get_Script() to read U1's list of programs. Get_Script() reads script.dat (via scriptfp) to get U1's program list. U1's programs consist of the current program in the script file up to (and including) the LOGOFF program. Hence, pcb->script[0] = EDITOR pcb->script[1] = COMPILER pcb->script[2] = LOGOFF Note: Do not open or close script.dat; just read from scriptfp. Logon_Service() calls Next_pgm() to allocate the first program in U1's list. Next_pgm() calls Get_memory() to allocate space for the first program. Get_memory() does the following: --reads the editor.dat script by reading from the (already open) file pointer PROGM_FILE[p] where p = pcb->script[ pcb->pgmid ], --reads the number of segments for U1's EDITOR program --stores the segment table information in pcb->segtable (the setup is the same as MEMMAP from objective 2, e.g., the fields accbits, seglen, membase must be set) --calls Alloc_seg(), once for each segment, to allocate space for the segments and set the membase field of each segment. Alloc_seg() searches the list of free memory blocks, FreeMem, to find space for U1's program. Once a block large enough to hold the program is found, the index to get to it in MEM is returned. For the first program for U1, the index pointer returned will be the next index after the kernel instructions set by Boot() (e.g., 17 if boot.dat had 17 instructions like in objective 2). Next_pgm() then calls Loader() to actually store the instructions for the EDITOR in the memory space that was just allocated for it. Loader() looks very similar to Boot(). For each segment and each instruction, Get_Instr() is called to read the next instruction from the file editor.dat. Again, editor.dat will already be open-- pcb->script[pcb->pgmid] should be passed to Get_Instr(), so it can read the proper file (in objective 2, you should have passed BOOT to Get_Instr(), not hard-coded it into Get_Instr()). Like in Boot(), call Display_pgm() for each segment you created--pass it pcb's segment table (not MEMMAP). ------------------------------------------------------------------------------- That's all for U1's first program, EDITOR. ------------------------------------------------------------------------------- ---------- Interrupt() removes |END U1| from new_events, sets EVENT=END, and AGENT=U1. ---------- Interrupt_Service() then calls End_Service() to handle the END instruction. The corresponding pcb is retrieved from termtable by retrieving the element at index AGENT - 1. Next_pgm() is then called to load the next program for the pcb. Note: An END event for a user will always follow a LOGON event (and not come before), so we are guaranteed that a pcb exists in termtable at that location. In Next_pgm(), since this is not the first program to be ran for user U1, the memory for the previous program (EDITOR) is returned to the system. This is done by calling Dealloc_pgm() for the pcb. For each segment, Dealloc_pgm() calls Dealloc_seg() to free the space allocated for each segment. The segtable stored by the pcb is then freed. Delloc_seg() is given a segment's base index and length into MEM and frees this space. Free memory is managed by the global variables TotalFree and FreeMem, which should also have been set properly in objective 2 (despite not being used). TotalFree simply keeps a count of the available free memory cells, so it can just be incremented by the length of the segment being returned to the memory pool. FreeMem maintains a linked list of free memory blocks, so it must be traversed to find the correct point to insert a free block. The list is ordered by base address (the segptr field), so given two nodes, the node with the smaller base address will appear before the one with the larger. Free blocks are then merged by calling Merge_seg() to attempt to combine adjacent blocks of memory. Merge_seg() combines two adjacent free blocks into one larger block to reduce memory fragmentation. It does this by scanning the FreeMem list, and for each node, if the next node's memory base field is equal to the current node's base field + the segment length, then the two segments represent adjacent free space. The length of the current node's segment can be incremented by the next node's length, and the next node can be deleted. For example, suppose MEM looked like this with hash marks (#) representing allocated space and vertical bars (|) representing the start of each segment: ------------------------------ | | |#####|#####| |... ------------------------------ The first free memory block has a size of 4 (it's 4 since we count the first '|', all the spaces, but not the second '|') and can be merged with the second free memory block of size 7 to form one block of size 11: ------------------------------ | |#####|#####| |... ------------------------------ The last free block, of course, cannot be merged since it is adjacent to no other free blocks. Note: Even though we show the contents of MEM in the example, we are only inspecting FreeMem since that it is what maintains the list of free memory blocks (i.e., we scan FreeMem, not MEM, to determine which blocks to combine). Control then returns back to Next_pgm(). The next steps of Next_pgm() are the same as those used for the first program, EDITOR. Get_memory() is called to allocate space for the new program, and Loader() is called to load the contents of memory with the instructions for the COMPILER program. Note: The memory that was previously deallocated may or may not be used for the next program. If the free block is two small, then another block will have to be used. Also, theoretically, space may not be available for a program even if the program's length is less than TotalFree since the blocks may all be spread apart. You do not have to handle this last situation in your code, though; assume space is available if the program's length is less than TotalFree as the directions state. However, your code must search FreeMem to find an appropriately sized block; look at Alloc_seg() above. ------------------------------------------------------------------------------- Now, U1's COMPILER program has been loaded into memory, so get the next event from the front of new_events. ------------------------------------------------------------------------------- ---------- Interrupt() removes |LOGON U2| from new_events, sets EVENT=LOGON, and AGENT=U2. ---------- The steps are almost identical to U1's LOGON event: Interrupt_Handler() calls Logon_Service(). A new pcb is created by Logon_Service() and saved in termtable. U2's program list is read by Get_Script(), which is called by Logon_Service(). The following are set for U2's pcb: pcb->script[0] = LINKER pcb->script[1] = LOGOFF Logon_Service() calls Next_pgm() to allocate the first program in U2's list. Next_pgm() calls Get_memory() to allocate space for the first program. Next_pgm() then calls Loader() to actually store the instructions for the LINKER in the memory space that was just allocated for it and display the new segments created. ------------------------------------------------------------------------------- The fourth event is then handled. ------------------------------------------------------------------------------- ---------- Interrupt() removes |END U1| from new_events, sets EVENT=END, and AGENT=U1. ---------- Again, the steps above for the previous END event are repeated--U1's pcb is retrieved and the previous program's space is deallocated by a call to Dealloc_pgm(). However, this is the last program since it is LOGOFF, so the pcb is terminated--no new space is created nor a program loaded into memory. ------------------------------------------------------------------------------- The last event is then handled. ------------------------------------------------------------------------------- ---------- Interrupt() removes |END U2| from new_events, sets EVENT=END, and AGENT=U2. ---------- The steps are the same for the previous LOGOFF/END event, except that U2's pcb is used to free the last program in memory and terminate the process. ------------------------------------------------------------------------------- The simulation has completed. -------------------------------------------------------------------------------