Comp111 Assignment 4
Paging

Overview

In the case of limited physical memory, processes must contend for pages. A common strategy for dealing with paging is "lookahead", in which one tries to predict what a process will do from its pattern of references.

In this assignment, you will write a paging strategy for a simulator. The simulator assumes that there are several processors sharing a pool of memory. You must assign which pages to assign to what processes, and when. You are graded on the latency of your solution, compared to that of others, i.e., how long your processes have to block. While paging in memory that it needs, a process is blocked; paging and processing for other processes occur concurrently while paging is occurring.

Objective

Your objective is to write a pager that will optimally swap in and out pages of memory so that a small pool of processes completes as quickly as possible. Your pager has the following form:
 
#define MAXPROCPAGES 20   /* max pages per individual process */ 
#define MAXPROCESSES 20   /* max number of processes in runqueue */ 
#define PAGESIZE 128 	  /* size of an individual page */ 
#define PAGEWAIT 100 	  /* wait for paging in */ 
#define PHYSICALPAGES 100 /* number of available physical pages */ 

typedef struct pentry { 
   int active; 
   int pc; 
   int npages; 
   int pages[MAXPROCPAGES]; /* 0 if not allocated, 1 if allocated */ 
} Pentry ; 

// you write this: 
void pageit(Pentry processes[MAXPROCESSES]); /* your routine */ 
// you use these simulated "system calls": 
extern int pageout(int process, int page); /* move a page out */ 
extern int pagein (int process, int page); /* move a page in */ 
You write the routine pageit, which calls my routines pagein and pageout to accomplish paging. Your routine pageit gets a page map for each process as well as the program counter for it. By tracking the program counter, you might be able to figure out which page to page in next. Note: the process is getting nowhere if the program counter points to a page outside memory that has been paged in. This is true if pages[pc/PAGESIZE]==0, and is the initial state of the simulation.

This would be easy if there were an unlimited number of physical frames; in fact there are a small number and you'll have to be clever about how you page processes in and out. There are 100 physical pages and 20 processors, each of which runs one process. So you are extremely memory starved.

Note that your pager has no knowledge of the actual nature of processes, or even which processes are assigned to which processors. Processes are randomly generated, where the randomization determines branching structure and the probability of branching. To make things easier, only instruction memory is considered.

Hints

First, some overall comments:

The following facts may help you:

Strategies you might use for paging:

Several other observations that might help:

  • When a process exits, all of its pages are released instantly. You can use this to gain access to pages.
  • Note that you are resource starved and deadlock is possible. To avoid deadlock, make sure that you release resources from some process to make resources available for others.
  • Note that you cannot tell when processes exit other than by tracking their pid's. These are integers from 0-39.
  • Note that you cannot tell when processes exit other than by observing that the pc is 0 and that the whole page table is clear.

    Helper files

    There are a number of helper files available to you in /comp/111/a/a4. In this assignment I am going to give you the source to the simulator so you'll know exactly what's going on inside it. This is contained in /comp/111/a/a4/t4.c and includes /comp/111/a/a4/t4.h. There is also an example program /comp/111/a/a4/a4.c that does rather badly in performance.

    Grading

    The simulator computes the ratio of paging to useful work. You are graded on the smallness of ratio that you can achieve. The beginning solution is downright awful and there is a lot of room for improvement. Smaller ratios are better; larger ratios are worse. Your solution will be run several times and the average used to compute your grade. The assignment is worth 10 points, including 8 points performance and 2 points style.

    Getting started

    There is a brain-dead solution in /comp/111/a/a4/a4.c. It demonstrates the interface but has terrible performance. To get a copy,
     
    mkdir a4
    cd a4 
    cp /comp/111/a/a4/a4.c a4.c
    

    Testing

    To test your solution, if it is a4.c, type
    ln -s /comp/111/a/a4/Makefile Makefile 
    make
    a.out
    
    This will create symbolic links in your directory for tester files t4.c, t4.h, programs.c, etc.

    The tester in this assignment is a white-box tester; you have source code. Hopefully this will be useful. Please pay attention to the news for bug fixes and enhancements. Some observations may be helpful:

    The tester options

    The tester has several options that can help you debug your program. If you run ./a.out -help it will print the following.
     
      -all       log everything
      -load      log loading of processes
      -unload    log unloading of processes
      -branch    log program branches
      -page      log page in and out
      -seed 512  set random seed to 512
      -procs 4   run only four processors
      -dead      detect deadlocks
      -csv       generate output.csv and pages.csv for graphing
    

    Running see.R

    When you are trying to tune performance (and not when doing basic debugging) it helps to be able to visualize what is happening. The R program see.R takes as input two files output.csv and pages.csv, and makes a visual representation of the performance of your algorithm. To run it:

    In the visualizer

    Submitting assignments

    To submit this assignment, if your program is "a4.c", ssh to one of the comp111 machines and type
     
    provide comp111 a4 a4.c
    
    You will see your results with the command "progress comp111".