What Is a Circular Buffer?

A file is a collection of related information identified by a file name stored on an external storage medium. Due to speed mismatch between CPU and I / O devices. To mitigate the speed mismatch between the CPU and I / O devices. The file buffer is a certain space reserved in the memory area for temporarily storing file data during reading and writing. Using a file buffer reduces the number of times the hard disk is read.

The file buffer is a certain space reserved in the memory area for temporarily storing file data during reading and writing. by

In device management, the main reasons for introducing buffers can be attributed to the following:

(1) Alleviate the contradiction of speed mismatch between CPU and I / O devices. In fact, where the data arrives at a rate different from its departure rate, a buffer can be set to alleviate the contradiction in rate mismatch between them. As we all know, the CPU's operation speed is much higher than the I / O device's speed. If there is no buffer, the CPU will stop and wait because the printer's speed cannot keep up when outputting data. It's idle. Obviously, if a buffer is set in the printer or controller to quickly store the output data of the program, the printer will "fetch" the data from it and print it later, so that the work efficiency of the CPU can be improved. Similarly, setting a buffer between the input device and the CPU can also improve the efficiency of the CPU.

(2) Reduce the interrupt frequency to the CPU, and relax the restriction on the CPU interrupt response time. In the remote communication system, if the data sent from the remote terminal is received with only one bit buffer, as shown in Figure 5-10 (a), the CPU must be interrupted once every bit of data is received. For data communication at a speed of 9.6 Kb / s, it means that the frequency of interrupting the CPU is also 9.6 Kb / s, that is, the CPU must be interrupted every 100 s, and the CPU must respond within 100 s, otherwise The data in the buffer will be flushed. If an 8-bit buffer (shift) register is set, as shown in Figure 5-10 (b), the frequency of the CPU interrupt can be reduced to 1/8 of the original; if an 8-bit register is set, such as As shown in the figure, the response time of the CPU to the interrupt can be relaxed to 800 s.

(3) Improve

According to the application's access to the file, that is, whether there is a buffer, access to the file can be divided into buffered operations and non-buffered file operations:

a) Buffered file operations: Advanced standard file I / O operations will automatically open up memory buffers for user-used files in user space.

b) Non-buffer file operations: low-level file I / O operations. When reading and writing files, the buffer for file operations will not be opened, and the disk operations (read, write, etc.) are directly performed through system calls. Set a buffer for each file in your own program.

Explanation and comparison of two file operations

1. Unbuffered file operation access mode. Each time a file is read or written, a read and write system call is required to handle this operation. That is, a system call needs to be performed. Executing a system call will involve CPU status. Switching, that is, switching from user space to kernel space, to realize the switching of process context, which will consume a certain amount of CPU time, and frequent disk access will have a great impact on the execution efficiency of the program.

2. The ANSI standard C library function is built on the underlying system call, that is, the implementation of the C function library file access function uses low-level file I / O system calls. The file processing functions in the ANSI standard C library are used to reduce the use of the system The number of calls, to improve efficiency, using a buffer mechanism, so that when the disk file is operated, a large amount of data can be read from the file into the buffer at one time, and future access to this part does not require the use of system calls. That is, a small amount of CPU state switching is required, which improves efficiency.

Single buffer

In the case of single buffering, whenever a user process issues an I / O request, the operating system allocates a buffer for it in main memory, as shown in the figure. in

When inputting a block device, it is assumed that the time to input a piece of data from the disk to the buffer is T, the time for the operating system to transfer the data in the buffer to the user area is M, and the time for the CPU to process (calculate) this piece of data Is C. Because T and C can be parallel (see figure), when T> C, the system processing time for each block of data is M + T, otherwise it is M + C, so the system processing time for each block of data can be Expressed as Max (C, T) + M.

During character device input, the buffer is used to temporarily store a line of data entered by the user. During the input, the user process is suspended to wait for data input to complete. During output, the user process enters a line of data into the buffer and continues. deal with. When the user process has the second line of data output, if the first line of data has not been extracted, the user process should block at this time ^[1] .

Double buffer

In order to speed up the input and output speeds and improve the utilization of equipment, people have also introduced a double buffer mechanism, also known as buffer swapping (Buffer Swapping). When the device is input, the data is first sent to the first buffer, and then it is transferred to the second buffer when it is full. At this point, the operating system can

The data is removed from the red zone and sent to the user process (see figure). The CPU then calculates the data. In double buffering, the time it takes for the system to process a block of data can be roughly thought of as Max (C, T). If C <T, the block device can be continuously input; if C> T, the CPU does not have to wait for the device input. For character devices, if the line input method is used, double buffering can usually eliminate the user's waiting time, that is, after the user enters the first line and the CPU executes the command in the first line, the user can continue to the second buffer Enter the next line of data.

Circular buffer

When the input and output or the speed of the producer and the consumer are basically matched, the double buffering can achieve better results, and the producer and consumer can basically operate in parallel. However, if the speeds of the two are very different, the effect of double buffering is not ideal, but the situation can be improved with the increase of the number of buffers. Therefore, a multi-buffering mechanism was introduced. Multiple buffers can be organized into circular buffers. For the circular buffer used as input, it is usually provided to the input process or calculation process. The input process continuously inputs data into the empty buffer, and the calculation process extracts data from it for calculation.

Composition of circular buffer

(1) Multiple buffers. Include multiple buffers in the circular buffer, each of which is the same size. Multiple buffers as input can be divided into three types

Type: An empty buffer R for the input data, a buffer G full of data, and the current working buffer C being used by the calculation process, as shown in the figure.

(2) Multiple pointers. Three pointers can be set as the input buffer: used to indicate the next available buffer of the calculation process

Pointer Nextg for area G, Nexti indicating the empty buffer R available to the input process next time, and pointers for calculations

A pointer to buffer C that the process is using, Current.

Use of circular buffers

The calculation process and the input process can use the following two procedures to use the circular buffer.

(1) Getbuf process. When the calculation process wants to use the data in the buffer, the Getbuf procedure can be called. This process provides the buffer indicated by the pointer Nextg to the process. Correspondingly, it must be changed to the current working buffer, and the Current pointer points to the first unit of the buffer, and Nextg is moved to the next G at the same time. Buffer. Similarly, whenever the input process wants to use an empty buffer to load data, the Getbuf process is also called, which provides the buffer indicated by the pointer Nexti to the input process and moves the Nexti pointer to the next R buffer Area.

(2) Releasebuf process. When the calculation process has finished extracting the data in the C buffer, it calls the Releasebuf process to release the buffer C. At this time, the buffer is changed from the current (active) working buffer C to the empty buffer R. Similarly, when the input process fills the buffer, the Releasebuf procedure should be called to release the buffer and change it to G buffer.

Process synchronization

Using input circular buffering enables input processes and computation processes to execute in parallel. Correspondingly, the pointers Nexti and Nextg will continue to move clockwise, so that the following two situations may occur:

(1) The Nexti pointer catches up with the Nextg pointer. This means that the input process's input data is faster than the calculation process can process the data, and all available empty buffers have been filled, and no more buffers are available. At this point, the input process should block until the calculation process has completely extracted the data in a certain buffer, making it an empty buffer R, and calling the Releasebuf process to release it, then the input process wakes up. This situation is called the system is computationally limited.

(2) The Nextg pointer catches up with the Nexti pointer. This means that the speed of input data is slower than the processing speed of the calculation process, so that all buffers containing input data are evacuated, and there is no buffer with data for the calculation process to extract data. At this time, the calculation process can only block until the input process fills up a certain buffer again and calls the Releasebuf procedure to release it, then it does not wake up the calculation process. This situation is referred to as the system being I / O-bound.

Buffer pool

The above buffers are only suitable for a specific I / O process and calculation process, so they are dedicated buffers. When the system is large, there will be many such circular buffers, which will not only consume a lot of memory space, but also its utilization is not high. In order to improve the utilization rate of the buffer, the current common buffer pool (Buffer Pool) is widely used, and multiple buffers are set in the pool that can be shared by several processes.

Composition of the buffer pool

For a common buffer pool that can be used for both input and output, there should be at least the following three types of buffers:

empty (free) buffer area;

Fill the buffer of input data;

Fill the buffer of output data.

For management convenience, the same type of buffers can be chained into a queue, so the following three queues can be formed:

(1) The empty buffer queue emq. This is a queue linked by an empty buffer. Its head pointer F (emq) and tail pointer L (emq) point to the head buffer and tail buffer of the queue, respectively.

(2) The input queue inq. This is a queue formed by a buffer filled with input data. The head pointer F (inq) and the tail pointer L (inq) point to the head buffer and tail buffer of the queue, respectively.

(3) The output queue outq. This is a queue linked by a buffer filled with output data. The head pointer F (outq) and the tail pointer L (outq) point to the head buffer and tail buffer of the queue, respectively.

In addition to the above three queues, there should be four kinds of working buffers: a working buffer for holding input data; a working buffer for extracting input data; a working buffer for containing output data; Working buffer for extracting output data.