Stage 27 : Pager Module (18 Hours)

In this stage, we will learn how the limited physical memory pages of the XSM machine can be used effectively to run the maximum number of concurrent processes. To achieve this, we will implement the functions Swap Out and Swap In of Pager module (Module 6). Corresponding modifications are done in Timer Interrupt and Context Switch module as well.

eXpOS gives provision to execute 16 processes concurrently in the system and the number of memory pages available for user processes are 52 (from 76 to 127 - See memory organization ). Consider a case, where every process uses four code, two heap, two user stack and one kernel stack pages. Then each process will need 9 memory pages. In this situation, the OS will run out of memory before all 16 processes can be brought into the memory, as the memory required will be 144 pages in total. A solution to this problem is following - when the OS falls short of free memory pages needed for a process, try to identify some inactive process whose memory pages could be swapped out to the disk. The memory pages freed this way can be allocated to the new process. At a later point of time, the OS can swap back the swapped out pages when the inactive process needs to be re-activated. This gives illusion of more memory than actual available memory. (Also see Virtual Memory .)

eXpOS uses an approach for memory management where the system does not wait for all the memory to become completely exhausted before initiating a process swap out. Instead, the OS regularly checks for the status of available memory. At any time if the OS finds that the available (free) memory drops below a critical level, a swap out is initiated. In such case, the OS identifies a relatively inactive process and swaps out some of the pages of the process to make more free memory available. The critical level in eXpOS is denoted by MEM_LOW (MEM_LOW is equal to 4 in present design). When available memory pages are less than MEM_LOW, eXpOS calls Swap Out function of pager module . Swap Out function selects a suitable process to swap out to the disk. The memory pages used by the selected process are moved into the disk blocks and the memory pages (except the memory pages of the library) are released. The code pages are not required to be copied to the disk as the disk already contains a copy of the code pages. The kernel stack page of a process is also not swapped out by eXpOS. However, the heap and the user stack pages are swapped out into the disk. eXpOS has 256 reserved blocks in the disk (256 to 511 - see disk organization ) for swapping purpose. This area is called swap area .

A swapped out process is swapped back into memory, when one of the following events occur:

1) A process has remained in swapped out state for more than a threshold amount of time.
2) The available memory pages exceed certain level denoted by MEM_HIGH (MEM_HIGH is set to 12 in present design).

Each process has an associated TICK value (see process table ) which is reset whenever the process is swapped out. The TICK value is incremented every time the system enters the timer interrupt routine. If the TICK value of a swapped out process exceeds the value MAX_TICK , the OS decides that the process must be swapped in. A second condition when the OS decides that a process can be swapped in is when the available number of free memory pages (see MEM_FREE_COUNT in system status table ) exceeds the value MEM_HIGH.

When does the OS check for MEM_LOW/MEM_HIGH condition? This is done in the timer interrupt handler . Since the system enters the timer routine at regular intervals, this design ensures that regular monitoring of TICK/MEM_FREE_COUNT is achieved.

We will modify the timer interrupt handler in the following way. Whenever it is entered from the context of any process except a special swapper daemon process (to be described later), the handler will inspect the TICK status of the swapped out processes and the memory availability status in the system status table to decide whether a swap-in/swap-out must be initiated. If swap-in/swap-out is needed, the timer will set the PAGING_STATUS field in the system status table to SWAP_IN/SWAP_OUT appropriately to inform the scheduler about the need for a swap-in/swap-out. The timer handler then passes control to the scheduler. Note that the timer does not initiate any swap-in/swap-out now. We will describe the actions performed when the timer interrupt handler is entered from the context of the swapper daemon soon below.

We will modify the eXpOS scheduler to schedule the swapper daemon whenever PAGING_STATUS field in the system status table is set to SWAP_IN/SWAP_OUT. The OS reserves PID=15 for the swapper daemon process. (Thus the swapper daemon joins login, shell and idle processess as special processess initiated by the kernel.) The swapper daemon shares the code of the idle process, and is essentially a duplicate idle process running with a different PID. Its sole purpose is to set up a user context for swapping operations. A consequence of the introduction of the swapper daemon is that only 12 user applications can run concurrently now.

If the timer interrupt handler is entered from the context of the swapper daemon, then it will call the Swap-in/Swap-out functions of the pager module after inspecting the value of PAGING_STATUS in the system status table. Thus, swap-in/swap out will be initiated by the timer interrupt handler only from the context of the swapper daemon.

While swapping is ongoing, the swapper daemon may get blocked when swap-in/swap-out operation waits for a disk-memory transfer. The OS scheduler will run the Idle process in such case. Note that the Idle process will never get blocked, and can always be scheduled whenever no other process is ready to run.

Once a swap-in/swap-out is initiated from the timer, the OS scheduler will not schedule any process other than the swapper daemon or the idle process until the swap-in/swap-out is completed. This policy is taken to avoid unpredicatable conditions that can arise if other processes rapidly acquire/release memory and change the memory availability in the system while a swap operation is ongoing. This design, though not very efficient, is simple to implement and yet achieves the goal of having the full quota of 16 process in concurrent execution. (Note that the size of the process table in the eXpOS implementation outlined here limits the number of concurrent processes to 16).

The algorithms for Swap-in and Swap-out are implemented in the Pager Module (Module 6).

Modifications to Timer Interrupt¶

Control flow for timer interrupt

Timer interrupt handler is modified as follows:

The handler must check whether the current process is the swapper daemon . This condition can happen only when a swap operation is to be initiated. In this case, PAGING_STATUS field of the system status table must be checked and Swap_in/Swap_out function of the pager module must be invoked appropriately (SWAP_OUT = 1 and SWAP_IN = 2).

If the current process is the idle process, there are two possibilities. If swapping is ongoing (check PAGING_STATUS), one can infer that Idle was scheduled because the swapper daemon was blocked. In this case, the timer must invoke the scheduler. (The scheduler will run Idle again if the daemon is not unblocked. Otherwise, the daemon will be scheduled.) The second possibility is that swapping was not on-going. This case is not different from the condition to be checked when timer is entered from any process other than the paging process, and will be descibed next.

Generally, when the timer handler is entered from a process when scheduling was not on, the handler must decide whether normal scheduling shall continue or swap-in/swap-out must be inititiated. Swap-in must be initiated if the value of MEM_FREE COUNT in the system status table is below MEM_LOW. Swap-out must be inititated if either a) memory availability is high (MEM_FREE_COUNT value exceeds MEM_HIGH) or b) some swapped process has TICK value exceeding the threshold MAX_TICK.

Another modification in the Timer interrupt is to increment the TICK field in the process table of every NON-TERMINATED process. When a process is created by the Fork system call, the TICK value of the process is set to 0 in the process table. Each time the system enters the timer interrupt handler, the TICK value of the process is incremented. The TICK value of a process is reset to zero whenever the process is swapped out or swapped in. Thus the tick value of a process that is not swapped out indicates for how long that process had been in memory without being swapped out. Similarly, the tick value of a swapped out process indicates how long the process had been in swapped state. The swap-in/swap-out algorithms will use the value of TICK to determine the process which had been in swapped state (or not swapped state) for the longest time for swapping in (or out).

Modify Timer Interrupt implemented in earlier stages according to the detailed algorithm given here .

Pager Module (Module 6)¶

Pager module is responsible for selecting processes to swap-out/swap-in and also to conduct the swap-out/swap-in operations for effective memory management.

1. Swap Out (function number = 1, Pager module )

Control flow for Swap Out

Swap Out function is invoked from the timer interrupt handler and does not take any arguments. As mentioned earlier, the timer interrupt handler will invoke Swap Out only from the context of the Swapper Daemon .

Swap Out function first chooses a suitable process for swapping out into the disk. The processes which are not running and are in WAIT_PROCESS or WAIT_SEMAPHORE state are considered first for swapping out (why?). When no such process is found, the process which has stayed longest in the memory is selected for swapping out into the disk. To detect the processes which has stayed longest in the memory, the TICK field in the process table is used. Thus the process with the highest TICK is selected for swapping out.

Now that, a process is selected to swap out, the TICK field for the selected process is initialized to 0. (From now on, the TICK field must count for what amount of time the process has been in memory). The code pages for the swapping-out process are released and the page table entries of the code pages are invalidated. The process selected for swapping out, can have shared heap pages. To simplify implementation, shared heap pages are not swapped out into the disk. Again, to simplify implementation, the kernel stack page is also not swapped out. Non-shared heap pages and user stack pages are stored in the swap area in the disk. Get Swap Block function of the memory manager module is invoked to find free blocks in the swap area. These memory pages are stored into the allocated disk blocks by invoking Disk Store function of the device manager module and disk map table is updated with the disk numbers of corresponding pages. Memory pages of the process are released using Release Page function of memory manager module and page table entries for these swapped out pages are invalidated. Also the SWAP FLAG in the process table of the swapped out process is set to 1, indicating that the process is swapped out.

Finally, the PAGING_STATUS in the System Status Table is reset to 0. This step informs the scheduler that the swap operation is complete and normal scheduling can be resumed.

Implement Swap Out function using the detailed algorithm given in the pager module link above.

1. Swap In (function number = 2, Pager module )

Control flow for Swap In

Swap In function is invoked from the timer interrupt handler and does not take any arguments.

The Swap In function selects a swapped out process to be brought back to memory. The process which has stayed for longest time in the disk and is ready to run is selected. That is, the process with the highest TICK among the swapped-out READY processes is selected).

Now that, a process is selected to be swapped back into the memory, the TICK field for the selected process is initialized to 0. Code pages of the process are not loaded into the memory, as these pages can be loaded later when exception occurs during execution of the process. Free memory pages for the heap and user stack are allocated using the Get Free Page function of the memory manager module and disk blocks of the process are loaded into these memory pages using the Disk Load function of the device manager module . The Page table is updated for the new heap and user stack pages. The swap disk blocks used by these pages are released using Release Block function of the memory manager module and Disk map table is invalidated for these pages. Also the SWAP FLAG in the process table of the swapped in process is set to 0, indicating that the process is no longer swapped out.

Finally, the PAGING_STATUS in the System Status Table is reset to 0. This step informs the scheduler that the swap operation is complete and normal scheduling can be resumed.

Implement Swap In function using the detailed algorithm given in the pager module link above.

1. Get Swap Block (function number = 6, Memory Manager Module )

Get Swap Block function does not take any arguments. The function returns a free block from the swap area (disk blocks 256 to 511 - see disk organization ) of the eXpOS. Get Swap Block searches for a free block from DISK_SWAP_AREA (starting of disk swap area) to DISK_SIZE -1 (ending of the eXpOS disk). If a free block is found, the block number is returned. If no free block in swap area is found, -1 is returned to the caller.

Implement Get Swap Block function using the detailed algorithm given in the memory manager module link above.

Modification to Context Switch Module (Module 5)¶

Previously, the Context Switch module (scheduler module) would select a new process to schedule according to the Round Robin scheduling algorithm. The procedure for selecting a process to execute is slightly modified in this stage. If swap-in/swap-out is ongoing (that is, if the PAGING_STATUS field of the system status table is set), the context switch module schedules the Swapper Daemon (PID = 15) whenever it is not blocked . If the swapper daemon is blocked (for some disk operation), then the idle process (PID = 0) must be scheduled. (The OS design disallows scheduling any process except Idle and Swapper daemon when swapping is on-going.) If the PAGING_STATUS is set to 0, swapping is not on-going and hence the next READY/CREATED process which is not swapped out is scheduled in normal Round Robin order. Finally, if no process is in READY or CREATED state, then the idle process is scheduled.

Modify Context Switch module implemented in earlier stages according to the detailed algorithm given here .

Modifications to OS Startup Code¶

Modify OS Startup Code to initialize the process table and page table for the Swapper Daemon (similar to the Idle Process).

The final algorithm is given here .

Modifications to boot module¶

Modify Boot module to add the following steps :

• Load module 6 (Pager Module) form disk to memory. See disk/memory organization .
• Initialize the SWAPPED_COUNT field to 0 and PAGING_STATUS field to 0 in the system status table to 0, as initially there are no swapped out processes.
• Initialize the TICK field to 0 for all the 16 process table entries.
• Update the MEM_FREE_COUNT to 45 in the system status table . (The 2 pages are allocated for the user/kernel stack for Swapper Daemon reducing the number from 47 to 45).