Stage 17 : Program Loader (6 Hours)

In this stage, you will be working on the implementation of the exec system call. Exec is the "program loader" of eXpOS. Exec takes as input a filename. It first checks whether the file is a valid eXpOS executable stored in the XSM disk, adhering to the XEXE format. If so, Exec destroys the invoking process, loads the executable file from the disk, and sets up the program for execution as a process. A successful exec operation results in the termination of the invoking process and hence never returns to it.

Name of the executable file is the only input to the exec system call. This file should be present in the disk before starting the machine. The inode index of this file can be obtained by going through the memory copy of the inode table.

Exec first deallocates all pages the invoking process is using. These include two heap pages, two user stack pages, code pages occupied by the process and the user area page. It also invalidates the entries of the page table of the invoking process. Note that the newly scheduled process will have the same PID as that of the invoking process. Hence the same process table entry and page table of the invoking process will be used by the newly loaded process. Exec calls the Exit Process function in the process manager module(module 1) to deallocate the pages and to terminate the current process.

As mentioned earlier, Exit Process function releases the user area page of the current process. Since Exec system call runs in kernel mode and needs a kernel stack for its own execution, after coming back from Exit process function, exec reclaims the same user area page for the new process. Further, exec acquires two heap, two stack and the required number of code pages (number of disk blocks in the inode entry of the file in the inode table) for the new process. New pages will be acquired by invoking the Get Free Page function present in the memory manager module(module 2). Page table is updated according to the new pages acquired. Code blocks for the new process are loaded from the disk to the memory pages obtained. For loading blocks into the memory pages, we use immediate load (loadi statement in SPL). Finally, exec initializes the IP value of new process on top of its user stack and initiates execution of the newly loaded process in the user mode.

eXpOS maintains a data structure called memory free list in page 57 of the memory. Each Page can be shared by zero or more processes. There are 128 entries in the memory free list corresponding to each page of memory. For each page, the corresponding entry in the list stores the number of processes sharing the page. The constant MEMORY_FREE_LIST gives the starting address of the memory free list.

Now we will understand the working of the module functions that exec uses during its execution. Before proceeding further have a careful look of the diagram to understand the overall working of the exec system call.

1. Exit Process (function number = 3,process manager module)¶

The first function invoked in the exec system call is the Exit Processfunction. Exit Process function takes PID of a process as an argument (In this stage, PID of the current process is passed). Exit process deallocates all the pages of the invoked process. It deallocates the pages present in the page table by invoking another function called Free Page Table present in the same module. Further, The Exit Process deallocates the user area page by invoking Free User Area Page in the same module. The state of the process (corresponding to the given PID) is set to TERMINATED. This is not the final Exit process function. There will be minor modifications to this function in the later stages.

2. Free Page Table (function number = 4, process manager module)¶

The Free Page Table function takes PID of a process as an argument (In this stage, PID of the current process is passed). In the function Free Page Table , for every valid entry in the page table of the process, the corresponding page is freed by invoking the Release Page function present in the memory manager module. Since the library pages are shared by all the processes, do not invoke the Release Page function for the library pages. Free Page Table function invalidates all the page table entries of the process with given PID. The part of the Free Page Table function involving updates to the Disk Map Table will be taken care in subsequent stages.

3. Free User Area Page (function number = 2,process manager module)¶

The function Free User Area Page takes PID of a process (In this stage, PID of the current process is passed) as an argument. The user area page number of the process is obtained from the process table entry corresponding to the PID. This user area page is freed by invoking the Release Page function from the memory manager module. However, since we are using Free User Area Page to release the user area page of the current process one needs to be careful here. The user area page holds the kernel stack of the current process. Hence, releasing this page means that the page holding the return address for the call to Free User Area Page function itself has been released! Neverthless the return address and the saved context of the calling process will not be lost. This is because Release Page function is non blocking and hence the page will never be allocated to another process before control transfers back to the caller. (Free User Area Page function also releases the resourses like files and semaphores acquired by the process. We will look into it in later stages.)

4. Release Page (function number = 2,memory manager module)¶

The Release Page function takes the page number to be released as an argument. The Release Page function decrements the value in the memory free list corresponding to the page number given as an argument. Note that we don't tamper with the content of the page as the page may be shared by other processes. The system status table keeps track of number of free memory pages available to use in the MEM_FREE_COUNT field. When the memory free list entry of the page becomes zero, no process is currently using the page. In this case, increment the value of MEM_FREE_COUNT in the system status table indicating that the page has become free for fresh allocation. Finally, Release page function must check whether there are processes in WAIT_MEM state (these are processes blocked, waiting for memory to become available). If so, these processes have to be set to READY state as memory has become available now. At present, the OS does not set any process to WAIT_MEM state and this check is superfluous. However, in later stages, the OS will set processes to WAIT_MEM state when memory is temporarily unavailable, and hence when memory is released by some process, the waiting processes have to be set to READY state.

5. Get Free Page (function number = 1,memory manager module)¶

To acquire the pages for the new process, exec calls the module function Get Free Page. The function returns the page number of the page allocated. Fundamentally, Get Free page searches through the memory free list to find a free page for the allocation. If a free page is found, memory free list entry corresponding to that page is incremented and number of the page found is returned.

If no memory page is free (MEM_FREE_COUNT in the system status table is 0), then state of the process is changed to WAIT_MEM and the scheduler is invoked. This process is scheduled again, when the memory is available (state of this process is changed to READY by some other process). The field WAIT_MEM_COUNT in the system status table stores the number of processes waiting to acquire a memory page. The Get Free Page function increments the WAIT_MEM_COUNT before changing state to WAIT_MEM. The process waits in the WAIT_MEM state until any memory page is available for use. Upon waking up, the Get Free Page function allocates the free memory page and updates the WAIT_MEM_COUNT and MEM_FREE_COUNT in the system status table.

Implementation of Exec system call¶

Exec has system call number as 9 and it is implemented in interrupt routine 9. Follow steps below to implement interrupt routine 9.

1. Save user stack value for later use, set up the kernel stack.(see kernel stack management during system calls.)
2. Set the MODE FLAG in the process table to system call number of exec.
3. Get the argument (name of the file) from user stack.
4. Search the memory copy of the inode table for the file, If the file is not present or file is not in XEXE format return to user mode with return value -1 indicating failure (after setting up MODE FLAG and the user stack).
5. If the file is present, save the inode index of the file into a register for future use.
6. Call the Exit Process function in process manager module to deallocate the resources and pages of the current process.
7. Get the user area page number from the process table of the current process. This page has been deallocated by the Exit Process function. Reclaim the same page by incrementing the memory free list entry of user area page and decrementing the MEM_FREE_COUNT field in the system status table. (same user area page is reclaimed - why?)
8. Set the SP to the start of the user area page to intialize the kernel stack of the new process.
9. New process uses the PID of the terminated process. Update the STATE field to RUNNING and store inode index obtained above in the inode index field in the process table.
10. Allocate new pages and set the page table entries for the new process.
    1. Set the library page entries in the page table. (must be set to read only-why? Note that library page need not be allocated.)
    2. Invoke the Get Free Page function to allocate 2 stack and 2 heap pages. Also validate the corresponding entries in page table.
    3. Find out the number of blocks occupied by the file from inode table. Allocate same number of code pages by invoking the GetFree Page function and update the page table entries.
11. Load the code blocks from the disk to the memory pages using loadi statement.(We will change this step in the next stage.)
12. Store the entry point IP (present in the header of first code page) value on top of the user stack.
13. Change SP to user stack, change the MODE FLAG back to user mode and return to user mode.

Implementation of Process Manager Module (Module 1)¶

1. According to the function number value present in R1, implement different functions in module 1.
2. If the function number corresponds to Free User Area Page, follow steps below
3. Obtain the user area page number from the process tableentry corresponding to the PID given as an argument.
4. Free the user area page by invoking the Release Page function.
5. Return to the caller.
6. If the function number corresponds to Exit Process, follow steps below
7. Extract PID of the invoking process from the corresponding register.
8. Invoke the Free Page Table function with same PID to deallocate the page table entries.
9. Invoke the Free user Area Page function with the same PID to free the user area page.
10. Set the state of the process as TERMINATED and return to the caller.
11. If the function number corresponds to Free Page Table, follow steps below
12. Invalidate the page table entries for the library pages by setting page number as -1 and auxiliary data as "0000" for each entry.
13. For each valid entry in the page table, release the page by invoking the Release Page function and invalidate the entry.
14. Return to the Caller.

Implementation of Memory Manager Module (Module 2)¶

1. According to the function number value present in R1, implement different functions in module 2.
2. If the function number corresponds to Get Free Page, follow steps below
3. Increment WAIT_MEM_COUNT field in the system status table. //Do not increment the WAIT_MEM_COUNT in busy loop (an important step )
4. While memory is full (MEM_FREE_COUNT will be 0), do following.
   1. Set the state of the invoked process as WAIT_MEM.
   2. Schedule other process by invoking the context switch module. // blocking the process
5. Decrement the WAIT_MEM_COUNT field and MEM_FREE_COUNT field in the system status table. Note the sequence - increment WAIT_MEM_COUNT, waiting for the memory, decrement WAIT_MEM_COUNT.
6. Find a free page using memory free list and set the corresponding entry as 1. Make sure to store the obtained free page number in R0 as return value.
7. Return to the caller.
8. If the function number corresponds to Release Page, follow steps below
9. The Page number to be released is present in R2. Decrement the corresponding entry in the memory free list.
10. If that entry in the memory free list becomes zero, then the page is free. So increment the MEM_FREE_COUNT in the system status table.
11. Update the STATUS to READY for all processes (with valid PID) which have STATUS as WAIT_MEM.
12. Return to the caller.

Modifications to the Boot Module.¶

1. Load interrupt routine 9, module 1, module 2 and inode table from the disk to the memory. Refer to disk and memory organization here.
2. Initialize the memory free list with value 1 for pages used and 0 for free pages.
3. Initialize the fields WAIT_MEM_COUNT to 0 and MEM_FREE_COUNT to number of free pages in the system status table.

Making things work¶

1. Compile and load interrupt routine 9, module 1 and module 2 using XFS-interface.
2. Run the machine.