Paging Experiments

Overview

These comprise a series of experiments in the virtual memory system of your computer. The homework is described for the linux operating system. You can use the AWS account if you wish. You should turn in at least one program per experiment. The programs will build off of each other, so they will be alike, but turn each one in separately.

You also should hand in written answers to the questions, with reference to the code you wrote and supporting transcript of the run. Please also you makefiles. The way that you build your code, although simple enough, is a part of your code. We are no more responsible for (essentially) writing your build as we are for writing your program.

As you are not root, there might be things you can't do, which you should do for these experiments. Please let us know. We will arrange a sudo line for you.

First experiment: mapping the memory.

You will locate the sections in memory of:

1. The text section which holds your program text.
2. The bss section, block started by symbol, which holds the static data.
3. The heap section which holds your dynamic memory variables, and grows up.
4. The stack section which holds your stack, and grows down.

The assignment is to write a program that defines variables in each of these sections, and gets the addresses of those variables, and prints them out.

Test the readability and writability of each segment.

For this exercise you will need to remember:

• C's pointer notation,
• the address-of operator &,
• pointer-to-function notation,
• casting, e.g. (char *), and (void *) (review void *, it's tricky!),
• and also read about sbrk() and mmap() functions.

Second experiment: stake your (virtual memory) claims!

Starting with your previous program, use sbrk/mmap to allocate different amounts of memory on the heap, and write to the allocated memory. Predict where the heap will end and write one byte beyond that location. What happens?

Explain this in terms of the kernel having knowledge of segments of virtual memory. What does sbrk/mmap do? Does the kernel find pages immediately? Does it fill out the page tables immediately? Think of an experiment that you can do to answer this question.

Do a calculation that get the number of pages between the top of heap and the bottom of the stack (this is the number of free pages). Using sbrk/mmap, allocate a lot of pages. How many pages can you allocate?

Use malloc to allocate memory. What is the difference between malloc and sbrk/mmap?

Third experiment: using top to examine memory allocations.

Read about linking and loading file formats,

• a.out,
• coff,
• Portable Execution (PE),
• elf,
• and mach-O.

See Wiki Object file article.

Read about the tools for viewing these file formats,

• objdump, a binutils tool,
• readelf, and how is it different than objdump,
• otools, which is for OSX, and why OSX can't use readelf.

As well as top, especially how to change the fields that top shows.

Use readelf to look at the binary files you had created in previous experiments. From the sections, find the text and bss segments. What does it claim are the addresses of these segments, and does this agree with what you have found by printing out addresses?

Run top on your program. Do do this you will probably have to put your program into a loop, and open two terminal windows, one to run your program, another to run top. Show the appropriate fields in top. You want to know about,

• physical memory,
• virtual memory,
• swap space (non-resident pages),
• and paging behavior.

What what happens in top as your program allocates memory? Can you have your program allocate and free virtual space and see the virtual memory amounts change in top? When is physical memory allocated? Can you have your program write to the allocated memory in stages, and watch the physical memory allocate in stages? What percent of memory does it show? Why does this make sense?

Fourth experiment: virtual memory performance, single process.

You should now have programs that allocate virtual memory, and write to that memory, causing it to be covered by physical memory. We now do some timings. There are three situations to test:

1. touch the same byte repeatedly,
2. touch bytes consecutively in memory,
3. touch each page consecutively in turn.

   for N trials
      for M accesses
         write byte 

For the third case, there might be a different time the first time you access the 30,000 pages and the following times. Investigate this. You can use the timing calls clock() and time() to get the CPU time (time actually charged to the process for being on the CPU) and the wall clock time (from start to finish, time according to a "clock on the wall"). You might investigate different time calls and how they account for time.

Fifth experiment: virtual memory performance, multiple processes.

In this experiment you will run multiple copies of your program, attempting to over commit physical memory. You will plot the run time of the programs as they compete for time, and possibly memory. You will for paging behavior, most obviously, the NFLT field of top.

You will also need to lear how to use & to background your program. If before you ran your program myprog but typing it's name (or more typically ./myprog since for security reasons the current directory is often not in the search path), you type ./myprog & and the parent (shell) does not wait for the child (myprog) before returning to the user for commands.

Along with that, you will need to learn ps. You will find that variations on unix will make for variations on the arguments to common utilities. For linux, I think ps auwx works well on the Linux we are using. Certian System V unix derivatives need the options edalf for this sort of "full" listing.

Since you are stating programs in the background, you have to learn how to stop them from the foreground. Use ps to get their PID and then send a "kill 9" signal to time: kill -9 PID. It might be helpful to know if the system has a killall the-prog-name command, which means you dont' have to look up PID's, and you can kill all programs of a given name at once.

So the experiment is to launch top, properly configured, in one window, and then more and more copies of your test program in another window. Make a graph of number of copies versus time to run one experiment (i.e. to sweep N times through all M locations, either fixed location, consecutive locations, or one-per-page location).

Watch the swap space, the committed physical memory, and the fault rates. Does run time vary inverse to the number of processes? That should be about true for a simple memory model. Variations from that curve should be observed under high loads from a program that uses paging extensively, and certainly when the fault rate rises, and you see the free swap space decline.

Predict how many processes you can start before sbrk/mmap returns an out-of-memory condition. Report on the numbers for swap space as you work your way to that condition.

Sixth experiment: virtual memory performance, the x-games version.

In the last experiment, we had got to a place where we could allocate no further memory on any process. We will ask why is this, and add swap space so we can continue adding processes. We will make estimates of how the additional swap space will be used, and look at system behavior on this overly-loaded systems.

Add a 1G swap file. Figure out how many processes you can have before an out-of-memory condition. Your collective programs have now claimed well beyond the physical memory of the machine. How does it react? How is it satisfying the various programs' needs for memory? What is the fault rate? How fast are the processes progressing? What is happening to the other processes? Did you crash our class machine?

For additional swap space, see the Red Hat documentation, the part about a file based swap space. You need to be root to run swapon and swapoff. Sudo is a program that grants superuser-powers according to instructions in the /etc/sudoers file. For this reason, you will run the commands as:

	[pikachu@ip-10-251-43-16 ~]$ PATH=/sbin:$PATH
	[pikachu@ip-10-251-43-16 ~]$ swapon -s
	Filename				Type		Size	Used	Priority
	/dev/sda3                               partition	917496	0	-5
	[pikachu@ip-10-251-43-16 ~]$ sudo swapon ./swapfile
	[pikachu@ip-10-251-43-16 ~]$ swapon -s
	Filename				Type		Size	Used	Priority
	/dev/sda3                               partition	917496	0	-5
	/opt/home/pikachu/swapfile              file		248	0	-6
	[pikachu@ip-10-251-43-16 ~]$ sudo swapoff ./swapfile
	[pikachu@ip-10-251-43-16 ~]$ swapon -s
	Filename				Type		Size	Used	Priority
	/dev/sda3                               partition	917496	0	-5
	[pikachu@ip-10-251-43-16 ~]$ 

Avoid accidentally removing the /dev/sda3 swap partition. You can put it back, if you do, by sudo swapon -s.