CS 134

Updating Repository and General Setup

You no longer need your code from Homework 5, as you'll be working with your cloned Homework 6 repository.

Cloning the Repository

After accepting the assignment on GitHub Classroom, you'll need to clone the repository to your CS 134 server account. Here's how you do it:

  1. Go to your repository on GitHub.
  2. Click the green button that says <> Code.
  3. You'll see a URL; copy that URL (the easiest way is to click the button that looks like two overlapping rectangles (i.e., select_window_2)).
  4. Open VS Code.
  5. Click on the >< button in the lower-left corner. In the pop-up menu, select Remote-SSH: Connect to Host... and enter username@cs134.cs.hmc.edu for the host (where username is replaced by your CS 134 server username from Homework 1). When prompted, enter your server password.
  6. On the sidebar of your VS Code window, click the “Explorer” icon (looks like two overlapping pieces of paper) or the “Source Control” icon (looks like three circles connected by two lines).
  7. Click Clone Repository.
  8. In the text box at the top of the window, paste the URL you copied from GitHub.
  9. Now edit the path to choose a place to save the cloned repo. We recommend using the cs134 directory that is already in your home directory.
  10. VS Code will download the repository and ask if you want to open the repository. Say yes!

Selecting OS/161 Mode in VS Code

In the bottom right corner of your VS Code window (directly to the left of the bell icon notifications ) there is a “C/C++ Configuration” button, which will probably say “Linux”. Click that button, and a drop-down menu from the Command Palette will allow you to select a configuration. Choose “OS/161”, and the C/C++ Configuration button should change to read “OS/161”. VS Code's “IntelliSense” should now work properly with the OS/161 code.

Building the OS/161 User-Space Tools

As you did with HW 5, you'll need to build OS/161's user-space tools and kernel.

Run

./setup

to build the user-space tools.

Running ./setup can take a few moments depending on how busy the server is. Remember that you can skip ahead to do some of the reading parts of the assignment while you are waiting for some code to compile.

The build process should finish with a message like

Base system installed in /home/username/cs134/repo-name/root
Now you need to configure and build the kernel.

where username is your username and repo-name is the name of the repository you cloned. (If you don't see this message, something went wrong. Please ask for help.)

Building the OS/161 Kernel

For this assignment, there are actually four configurations you can build with:

  • VM-CLOCK-RTLB: A clock algorithm with page aging and random TLB replacement.
  • VM-CLOCK-STLB: A clock algorithm with page aging and sequential TLB replacement.
  • VM-RAND-RTLB: A random page replacement algorithm with random TLB replacement.
  • VM-RAND-STLB: A random page replacement algorithm with sequential TLB replacement.

(In theory, currently the code that is supposed to implement the clock algorithm uses FIFO for page replacement.)

For now, configure and build using the VM-CLOCK-RTLB configuration file. Make sure that your current directory is ~/cs134/repo-name, and then run

cd src/kern/conf
./config VM-CLOCK-RTLB
cd ../compile/VM-CLOCK-RTLB
bmake depend

and then build the kernel with

cd ../../../../root
cd - ; bmake && bmake install ; cd -

Testing the Kernel

Once it's built, you can test it by changing your directory to your virtual root directory and run the kernel with

sys161 kernel

(You can also do cd ~/cs134/repo-name/root (where repo-name is the name of the repository you cloned), and run the kernel from there.)

Checking in with the Kernel

Here's a sample session, which shows us running

  • hw4test (our test program from homework 4)
  • forktest (another test program from homework 4—now we can run it multiple times without running out of memory!)
  • maze (a new program that generates and solves a maze of a given size, using memory allocated with sbrk)

It also shows a new menu command, vm, that gives us stats from the VM system:

sys161: System/161 release 2.0.3, compiled Jul 25 2024 16:47:30

OS/161 base system version 2.0.3
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
   President and Fellows of Harvard College.  All rights reserved.

Our work-in-progress OS/161 system version 0 (VM-CLOCK-RTLB #1)

760k physical memory available
vm: Page replacement: LRU
vm: TLB replacement: random
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lhd0 at lamebus0
lhd1 at lamebus0
lser0 at lamebus0
con0 at lser0

vfs: Swap attached to lhd0
swap: swapping to lhd0: (50331648 bytes; 12288 pages)
cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]: s
/bin/sh: Timing enabled.
OS/161$ hw4test >hw4test.out
**********
* write() works for stderr
/bin/sh: subprocess user time: 0.060067 seconds, system time: 0.234814 seconds, real time: 2.388477 seconds
OS/161$ forktest
forktest: Starting. Expect this many:
|----------------------------|
AABBBBCCCCCCCCDDDDDDDDDDDDDDDD
forktest: Complete.
/bin/sh: subprocess user time: 0.252231 seconds, system time: 0.412306 seconds, real time: 1.082280 seconds
OS/161$ forktest
forktest: Starting. Expect this many:
|----------------------------|
AABBBBCCCCCCCCDDDDDDDDDDDDDDDD
forktest: Complete.
/bin/sh: subprocess user time: 0.252230 seconds, system time: 0.411823 seconds, real time: 1.082337 seconds
OS/161$ maze 15
Allocating 673 bytes for 15 x 15 maze...

Generating maze...

###############
....#...#.#.#.#
#.#####.#.#.#.#
#.....#.......#
#.#.#####.###.#
#.#.....#...#.#
###.#.###.###.#
#.#.#...#...#.#
#.###.###.###.#
#.......#...#.#
###.#.###.###.#
#...#.#.....#.#
###.###.#####.#
#.........#....
###############

Solving maze...

###############
oo..#...#.#.#.#
#o#####.#.#.#.#
#ooo..#..ooooo#
#.#o#####o###o#
#.#ooo..#o..#o#
###.#o###o###o#
#.#.#o..#o..#o#
#.###o###o###o#
#..ooo..#o..#o#
###o#.###o###o#
#..o#.#ooo..#o#
###o###o#####o#
#..ooooo..#..oo
###############

/bin/sh: subprocess user time: 0.007836 seconds, system time: 0.117525 seconds, real time: 1.267696 seconds
OS/161$ exit
Program exited with status 0.
Operation took 44.697409432 seconds
OS/161 kernel [? for menu]: vm
vm: 29 zerofills 770 minorfaults 0 majorfaults
vm: 0 evictions (0 discarding, 0 writes)
vm: shootdowns: 0 sent, 0 done (0 interrupts)
vm: coremap: 8 kernel, 0 user, 181 free, 189 total
vm: swap: 12287 free, 0 reserved, 12288 total
Operation took 0.415953560 seconds
OS/161 kernel [? for menu]: q
Shutting down.
The system is halted.
sys161: 1724780514 cycles (198625797 run, 1526154717 global-idle)
sys161:   cpu0: 69515624 kern, 1184384 user, 0 idle; 111991 ll, 111991/0 sc, 469435 sync
sys161: 3234 irqs 55648 exns 0r/0w disk 63r/2595w console 49r/373w/17m emufs 0r/0w net
sys161: Elapsed real time: 62.763921 seconds (27.4804 mhz)
sys161: Elapsed virtual time: 68.995520448 seconds (25 mhz)

Exploring Paging

None of the programs we ran above caused any evictions (i.e., no pages were swapped out to disk), which you can see this in the vm output. But if we run a larger version of the maze program, we can see some evictions:

  • L-Chippy speaking

    We'll run the maze program with the -s flag to set the random seed to 271828, and a maze size of 800. By using the -s flag, we can get the same maze each time we run the program, for doing comparisons.

cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]: s
/bin/sh: Timing enabled.
OS/161$ maze -s 271828 800
Allocating 1915203 bytes for 799 x 799 maze...

Generating maze...
Maze too large to print
Solving maze...
Maze too large to print
Solution path length: 65011
/bin/sh: subprocess user time: 4.015395 seconds, system time: 2.225252 seconds, real time: 59.277609 seconds
OS/161$ exit
Program exited with status 0.
Operation took 69.799031681 seconds
OS/161 kernel [? for menu]: vm
vm: 234 zerofills 5926 minorfaults 571 majorfaults
vm: 624 evictions (7 discarding, 617 writes)
vm: shootdowns: 0 sent, 0 done (0 interrupts)
vm: coremap: 8 kernel, 0 user, 180 free, 188 total
vm: swap: 12287 free, 0 reserved, 12288 total
Operation took 0.477953560 seconds

We can see that the maze program needs almost 2 MB of memory for the maze itself, but the machine only has 1 MB of RAM, so it seem likely that some pages will be evicted. In fact, we see that there were 624 pages that were evicted as the program ran, of which 617 were written to disk. The vm command also shows that there were 5926 minor faults and 571 major faults, but what these stats mean is something you'll determine in the next part(s) of the assignment.

When you have implemented the full clock algorithm, you should see that the number of evictions is lower than we get with the FIFO algorithm. For example,

cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]: s
/bin/sh: Timing enabled.
OS/161$ maze -s 271828 800
Allocating 1915203 bytes for 799 x 799 maze...

Generating maze...
Maze too large to print
Solving maze...
Maze too large to print
Solution path length: 65011
/bin/sh: subprocess user time: 4.013554 seconds, system time: 1.934548 seconds, real time: 48.905545 seconds
OS/161$ exit
Program exited with status 0.
Operation took 68.783087137 seconds
OS/161 kernel [? for menu]: vm
vm: 234 zerofills 5840 minorfaults 472 majorfaults
vm: 525 evictions (25 discarding, 500 writes)
vm: shootdowns: 0 sent, 0 done (0 interrupts)
vm: coremap: 8 kernel, 0 user, 180 free, 188 total
vm: swap: 12287 free, 0 reserved, 12288 total
Operation took 0.433953560 seconds

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)