Lab: IO Buffering

CSC 213 - Operating Systems and Parallel Algorithms - Weinman

Summary:

You will measure the effects of system calls and buffering on file I/O.

Assigned:

Tuesday 9 December

Due:

5:30 PM Monday 15 December

Objectives:

Appreciate the cost of system calls and the advantages of buffering.
Practice empirical research methods with system behavior benchmarking.
Develop quantitative and analytical writing skills.

Collaboration:

You will complete this lab in teams as assigned by the instructor.

Background

*nix provides two primary ways to do I/O. The usual functions, open(2), read(2), write(2), and close(2) are for input and output to files among other devices. These are system calls that trap to the kernel, and are typically referred to as unbuffered I/O routines because they do only the IO requested by the system call.

The standard C library also provides what are called buffered I/O routines, fopen(3), getc(3), putc(3), fread(3), fwrite(3), and fclose(3) among others, that are a further abstraction of the system calls above. As Stevens (1992) reminds us, "the goal of buffering provided by the standard I/O library is to use the minimum number of read and write calls" (p. 122).* But why would we want to minimize the number of read and write calls? The purpose of this lab is to answer that question.

Before we do so, let's talk a bit more about just what buffering means. Rather than use the raw file descriptor (an integer) provided by the OS for I/O, the standard C I/O library wraps this information into what are called file streams, represented by the data structure FILE. This structure internally manages lots of properties for each open file, including the current file pointer position, as well as a (relatively large) "buffer" (byte array). When a program asks the library to read or write (say via fread(3) or fwrite(3)) through the stream, the library in turn asks the operating system to read or write through the file descriptor (via read(2) or write(2)). When reading, instead of asking only for the bytes wanted by the program, the library asks for more, and caches the excess in its buffer. That way, the next time the program asks for data, the library can read from its buffer, rather than querying the operating system. Conversely, when writing, the library sometimes just stores the data in its buffer, promising to call the operating system when the accumulated data meets certain requirements (i.e., is big enough or contains a new line; see Stevens, pp. 122-123* for a concise summary). This may sound like a lot of bookkeeping overhead, and indeed it is. So again, we'll ask: why bother?

Preliminaries

Do this laboratory on a MathLAN workstation in 3819 or 3815.
Read the man pages for the four system calls open(2), read(2), write(2), and close(2) to gain an understanding of how to use them.
Read the man pages for fopen(3), fread(3), and fclose(3) to gain an understanding of how to use them.
The examples head-1.c and head-2.c demonstrate some of these calls (the former being unbuffered, the latter being buffered). Read over these two examples and be sure you understand how they work.

Materials

Two programs, unbufread and bufread are required for the lab and both may be found on the MathLAN:

: $ cd ~weinman/public_html/courses/CSC213/2014F/labs/code/buffering

The provided program unbufread uses the unbuffered I/O operation read(2) to simply read through all the data in a file. It takes a buffer size count and a filename as arguments, reads the data, and reports

the number of reads made by your unbufread function until the end of file was reached,
the total wall clock time (in seconds)
the user CPU time (in seconds) (cf. getrusage(2)), and
the system CPU time (in seconds).

For example,

: $ ./unbufread 10 /tmp/amt3.log
2415 0.001778 0.000712 0.002383
$ ./unbufread 16 /etc/ssh_host_dsa_key
Unable to open input file: Permission denied
$ ./bufread 16 /blah
Unable to open input file: No such file or directory

The analogous program bufread uses the buffered library call fread(3) to read through an input file using queries of a specified size. The program otherwise functions the same as unbufread. For example,

: $ ./bufread 10 /tmp/amt3.log
2414 0.000202 0.000798 0.001681

Although they are not difficult to implement, I do not provide the source code for these programs because they have been assignments in the past and may be assigned again in the future.

Empirical analysis

To effectively test the performance of these programs, we will need a relatively large file. To avoid swamping the home directory server and testing network effects more than filesystem/kernel effects, you will create this file in the /tmp directory on your workstation's local disk; create a 2²⁷=134,217,728 byte file using the following command:

$ head -c134217728 /dev/urandom > /tmp/$USER-bigfile

Explain how this command works. You will need to do a bit of research on shell commands, environment variables, and Linux pseudo-devices. (Be prepared to cite your sources.)
Run each of the provided programs with buffer sizes of 2^0...20 bytes. That is: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, and 1048576. Collect the output data in a text file or spreadsheet. (Tip: Use a bash loop to simplify the data gathering process.)
Using your favorite graphing program (a spreadsheet, gnuplot, MATLAB, etc.), create graphs of the (three) times per read and times per byte for each method as the buffer size changes. Note that the programs report total times, so you need to calculate these "per X" quantities.
You will need to decide whether to use linear or logarithmic axes. You may decide how to collect the different curves into axes; in doing so, consider the comparisons that are most important. Label your axes (giving units), title your plot, and (if appropriate) provide a legend.
Organize your findings in a complete report that includes the following elements. (Note that each might be composed of more than one paragraph.)

Introduction

State the task, question, or problem and your purpose.

Setup

Physical scientists often call this "materials and methods." Share the details of the input file you used (e.g., how it was generated where it resides, and why on both counts), the provenance of executables, and anything you may have learned about the filesystem on the machine used for the experiments (all "materials"). Describe the experimental process (your "methods").

Report

Present the experimental results in an organized fashion.

Summarize

Give a brief, objective overall picture of the results. Write one or more paragraphs describing what patterns you see.

Infer

Draw conclusions. Write one or more paragraphs explaining what you can conclude about the results. The goal of the conclusions is to try to explain why the patterns appeared. Why do the results for read vary so much? Why do the results for read and fread differ? What can you conclude about how fread works? What does the system time curve for read tell you about the file system?

Recommend

Make recommendations. What advice would you give to a programmer (e.g., your future self) who needs to do I/O efficiently?

Note that devising and performing the experiment and then summarizing the results are three separate steps and all come before you draw conclusions. To present honest and understandable results, we must present the basic data first (so the reader can draw their own conclusions) before we insert our bias.

What to turn in

A single pdf containing your report.

Extra Credit

The following are a few extra credit possibilities.

Measure system call overhead. Write a program that performs the same lightweight system call repeatedly (perhaps 1000 times). Compute the average time to establish a baseline for the time to do a system call. Good system calls include read (from /dev/null so there is no actual I/O), write (to /dev/null), getpid, and gettimeofday; feel free to try others such as synchronization operations. Also provide an option to call a function that does nothing but return, so that you can compare the cost of a system call to the cost of an ordinary function call.
Measure the cost of creating threads vs. forking processes. To isolate this cost, the child should exit immediately; the parent will need to wait until the child exits. You may go on to estimate the incremental cost of calling exec(2) by comparing the cost of forking and immediately exiting with the cost of forking and then calling exec(2).
Reading a file a second time, even using exactly the same code, can give different results due to caching. In the benchmarking world, these are called warm cache vs. cold cache effects. Devise an experiment to determine whether such an effect is happening. If you want to try this, please come talk with me about your ideas.
As an alternative to writing code, find an interesting systems research paper that reports on a benchmarking experiment. First summarize the paper's approach and main findings, and then give your reactions. Do they follow the experimental method? Be sure to cite your source.

Acknowledgment:

This assignment was inspired by Figure 3.1 of Advanced Programming in the UNIX Environment, by W. Richard Stevens (1992, Addison-Wesley). It is based on a version by Jerod Weinman given in a prior offering of CSC 213, with some text in the Exercise from a similar assignment by Janet Davis, which she credits as "adapted from one given by Barton Miller at the University of Wisconsin," Madison, and the extra credit "borrowed from Fred Kuhn at Washington University in St. Louis."

The Background (including head-1.c and head-2.c) , Preliminaries, and Materials are:

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.