(Some parts of this section have been borrowed or summarized from the Wikipedia page on Asynchronous I/O)
Asynchronous I/O, or non-blocking I/O, is a form of input/output processing that permits other processing to continue before the transmission has finished.
Input and output (i.e., I/O) operations on a computer can be extremely slow compared to the processing of data. An I/O device can incorporate mechanical devices which must physically move, such as a hard drive seeking a track to read or write; extremely slow compared to other CPU (non-I/O) operations. For example, during a disk operation that takes ten milliseconds to perform, a processor that is clocked at one gigahertz could have performed ten million instruction-processing cycles.
A simple approach to I/O, that is commonly used, is to start the access and then wait for it to complete. This approach (called synchronous I/O or blocking I/O) blocks the progress of a program while the communications is in progress, leaving system resources idle. When a program makes many I/O operations, this means that the processor can spend almost all of its time idle waiting for I/O operations to complete.
Alternatively, it is possible to start the communication and then perform processing that does not require that the I/O has completed. This approach is called asynchronous I/O. Any task that actually depends on the I/O having completed (this includes both using the input values and critical operations that claim to assure that a write operation has been completed) still needs to wait for the I/O operation to complete, and thus is still blocked, but other processing which does not have a dependency on the I/O operation can continue.
One common way OSs typically implement asynchronous I/O is to provide a set of system calls that immediately return to the program. For example, aio_read() is the asynchronous read system call. When returning, there are two possible cases for aio_read(). First, the system call may return with the data (if the requested data was in the OS's buffer cache). Second, the system call may return notifying the process that the data is not ready. In this case, the actual I/O read from the disk is performed asynchronously, and when it is complete a signal (interrupt) is generated for the process. To handle these signals, programs must implement and register special asynchronous I/O handlers (an aio read handler in this example).
Extend the xv6 kernel to add support for the aio_read() (asynchronous read) system call. This call will work as in the following example:
int done = 0;
void
io_handler(void) {
done = 1;
}
int
main(int argc, char **argc) {
int fd;
char buf[256];
signal(IO, io_handler);
fd = open("testfile", O_RDRW);
n = aio_read(fd, buf, 256);
while(!done);
}
The aio_read() works similarly to read() except that aio_read() returns immediately and a signal will be posted to the process when the read operation completes.
A process may issue multiple asynchronous read operations. Each aio_read() may read multiple blocks depending on its size, some of which could be cached in the buffer cache.
Here are the steps you will need to complete for this exam:
#define NAIO 1024 // Number of outstanding aios allowed without blocking
#define NAIOOP 1024 // Number of block operations per aio
struct aio { // One per AIO read
struct proc *p; // Process that issued the AIO read
int count; // Number of pending AIO blocks to be read from disk
struct aio_bop { // One per AIO block operation scheduled
char *dst; // User buffer destination
uint n; // Total size of block read
uint boff; // Offset in block to start reading
} aioops[NAIOOP];
} aiolist[NAIO];
A struct aio will be initialized in readi() for each AIO read operation and discarded when the operation completes. A struct aio_bop will be initialized in bread() for each asynchronous block operation scheduled. aio.count tracks the outstanding blocks to be read for the aio, will be incremented each time bread() passes a request to the driver and decremented in ide_intr() where the block data is copied to the user-space buffer. When aio.count == 0 the AIO signal should be issued to the process from ide_intr() to notify the process of AIO read completion.
The buffer control structure passed to the driver will also need pointers added that point to the corresponding element in the struct aio and struct aio_bop data structures to be able to discover them in the ide_intr() when the operation completes.
struct buf {
...
int aio_index;
int op_index;
};
In the asynchronous case ide_rw() will not put the process to sleep after placing the request in the ide request queue. Instead, in the asynchronous case, the ide_intr() should: (i) copy the data back to the user-space buffer (using struct aio), (ii) decrement aio.count, and (iii) signal the process when all of the requested data has been copied to the buffer (when aio.count == 0).
Run "make qemu". Then inside the xv6 shell:
$ echo "1" > testfile
Then quit out of QEMU to flush the buffer cache. Run "make qemu". Then inside the xv6 shell:
$ mytest
AIO signal!
n: 0 - buf: "1"
read n: 0
NOTE 1: XV6 SOURCE CODE: The source code for the xv6 kernel can be downloaded from here.
NOTE 2: You may download our signals implementation if you would rather start with our code. The patch file for this code is here. To use this you first untar a fresh copy of xv6 (tar -zxvf xv6-rev2.tar.gz) and copy the patch file into the xv6 directory (cp xv6-signals-thexam.patch xv6). Then you change directory into the xv6 directory (cd xv6) and issue the patch command (patch < xv6-signals-thexam.patch). You should see the following messages if it patches the sources correctly:
[steve@archangel temp]$ tar -zxvf xv6-rev2.tar.gz
[steve@archangel temp]$ cp xv6-signals-thexam.patch xv6
[steve@archangel temp]$ cd xv6
[steve@archangel xv6]$ patch < xv6-signals-thexam.patch
patching file Makefile
patching file defs.h
patching file mytest.c
patching file proc.c
patching file proc.h
patching file syscall.c
patching file syscall.h
patching file sysproc.c
patching file user.h
patching file usys.S
If you see anything else, then there is an error and you must delete the sources and try again. This method only works on Linux. If you are not using Linux, then you can download a version of the sources with the patch applied from here.
NOTE 3: You may reuse any portion of your signal/kill_signal implementation from HW#3. Specifically you should use the signal() system call for a process to register an AIO read handler, and you should use the in kernel signal posting mechanism to issue the AIO read signal to the process when all of the requested data has been copied into the user provided buffer.
NOTE 4: There is a possible race condition that may occur. It is possible for the AIO read to return from the disk before the aio_read() system call has completed and returned to the program. This is unlikely to happen in a typical system, but in the Qemu emulated environment, since the disk is emulated, it is likely to occur.
Email the tar file to Prof. Iftode and Steve Smaldone prior to the deadline. The subject of the email should read "[CS416-S08 TAKE HOME EXAM]". Please ensure that you submit the files before the deadline. To be safe, hand it in as early as possible. If you are close to the due date/time and are not completed, you can submit one version with whatever you have done earlier, and then submit a later version by sending a new tarfile before the deadline. We will consider the submitted version to be the last version received, prior to the deadline. Partial credit will be granted, and so you should at least submit what you were able to complete.
If you need any help during the 24 hours of the take home exam period, please email Steve Smaldone (smaldone AT cs DOT rutgers DOT edu). He will be available as a proctor for the take home exam. When you email for assistance, specify the form of communication you are requesting: email answer, phone call, chat session, in-person meeting, etc., and he will do his best to accommodate your request. Keep in mind that if you make the request very late in the night/early in the morning, there may be a lag in response time.