7. Buffer and Multiprocess File 343
7.8 Example 2: Comprehensive Examples of Multiprocess Operating File
Let’s introduce the problems of the buffer block selection and the use of request through a set of cases of multiprocess operating files. The situations of the three processes are as follows. Process A is a write process in order to write characters “ABCDE” in str1[] to the file hello1.txt. The code is as follows:
Process B is a write process in order to write characters “ABCDE” in str1[] to the file hello2.txt. The code is as follows:
void FunA();
void main() {
……
FunA();
……
}
void FunA() {
char str1[] = “ABCDE”;
int i;
//open the file
int fd = open(“/mnt/user/user1/user2/hello1.txt”, O_RDWR,0644));
for(i=0;i<1000000;i++) {
//write the file
write(fd,str1,strlen(str1));
}
//close the file close(fd);
return;
}
void FunB();
void main() {
……
FunB();
……
}
Process C is a read process, and the purpose is read 20,000 bytes to the buffer from hello3. txt. The code is as follows:
The executive order of three processes are as follows:
At first, process A is executed; then process B is executed; process C is in the end. The three processes do not have a parent-child relationship.
The system will write data to the buffer continuously for process A. First, process A starts with performing the function write, assuming that there is nothing in file hello1.txt.
Process A only needs to apply for a buffer block in the buffer and writes the specified data to the buffer block. The premise of applying the new buffer block is that the buffer block is free and not dirty. We assume that the system has all the buffer blocks free and not dirty and filled with data. Figure 7.35 shows the state of a system that is all free and not dirty as
void FunB() {
char str1[]=“ABCDE”;
int i;
//open the file
int fd=open(“/mnt/user/user1/user2/hello2.txt”, O_RDWR,0644));
for(i=0;i<1000000;i++) {
//write the file
write(fd,str1,strlen(str1));
}
//close the file close(fd);
return;
}
void FunC();
void main() {
……
FunC();
……
}
void FunC() {
char buffer[20000];
int i, j;
//open the file
int fd = open(“/mnt/user/user1/user2/hello3.txt”, O_RDWR,0644));
//read the file
read(fd,buffer,sizeof(buffer));
//close the file close(fd);
return;
}
a buffer block filled with data. Next, we will look at what circumstances applying for the new buffer block and writing operations will cause when the buffer is in the state Figure 7.35 shows.
Continuous performance will lead data of the buffer block to be synchronized.
The current process is still process A, and the system is far from completing its request. It should continue to write data to the buffer. This requires the function getblk to find a free buffer block in the buffer, that is the buffer block with b_count as 0.
The executable code is as follows:
But now the situation is that the buffer has no free and not dirty buffer blocks but only a free but dirty buffer block. This means that the next step is to synchronize data from the
rw rw rw rw r r
Process A
Buffer zone
The time slice of process Process A
Request item
“write” request item
“read” request item
Disk
Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item
rw r
Figure 7.35 System continues to write data to process A.
//code path:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) {
……
tmp = free_list;
do {
if (tmp->b_count) //find the free buffer block continue;
if (!bh || BADNESS(tmp)<BADNESS(bh)) {//on the basis of the idle, //weigh BADNESS
bh = tmp;
if (!BADNESS(tmp)) break;
}
/* and repeat until we find something good */
} while ((tmp = tmp->b_next_free) ! = free_list);
……
}
buffer to the hard disk by force in order to hollow out more space in the buffer and provide support for a subsequent write disk. The executable code is as follows:
Synchronize the data from the buffer to the hard disk. At this time, the function sync_dev() is used to synchronize data from the buffer to the hard disk. After entering sync_dev function, the executable code is as follows:
The function sync_dev will traverse the entire buffer, and all the “dirty” blocks in the buffer block will be synchronized to the hard disk. The synchronous step of each “dirty”
buffer block is like this:
First, the buffer block will be bound with free request items that have been applied, and the records in the claims will be used as the unique basis for data synchronization.
Second, if there is no hard disk working at this time, then the command of the writing disk will be issued, and the data will be synchronized. If the hard disk is working, then the request will be inserted in the request queue. When the hard disk has finished the data synchronization and triggered an interrupt, the interrupt service routine will send com- mand to the hard disk continuously in order to make the data correspond to each item in the request queue synchronized to the hard disk one after another.
Function Sync_dev will keep on executing the above work until it can’t apply for a free request.
//code path:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) {
……
if (bh->b_count) goto repeat;
while (bh->b_dirt) { //if all the free buffer blocks are dirty, //it indicates there is too much data needed //to be synchronized to the hard disk sync_dev(bh->b_dev); //synchronize immediately
wait_on_buffer(bh);
if (bh->b_count) goto repeat;
}
……
}
//code path:fs/buffer.c:
int sync_dev(int dev) {
……
bh = start_buffer;
for (i=0 ; i<NR_BUFFERS ; i++,bh++) { //all have to be traversed if (bh->b_dev != dev)
continue;
wait_on_buffer(bh);
if (bh->b_dev == dev && bh->b_dirt) //as long as the device number matches and //it is dirty, then
//synchronization
ll_rw_block(WRITE,bh);
}
……
}
The synchronization process of each buffer block is completed in function ll_rw_
block. In this process, the buffer block will be locked. The lock can only prevent the data interaction between the process and the buffer block and prevent data interaction between the system itself and the buffer block, but it doesn’t stop the data interaction between the buffer block and the hard disk. Before sending sync command, the dirty flag b_dirt of the buffer block that needs to be synchronized will be set to 0, indicating that it is no longer a
“dirty” buffer block.
The specific route of the implementation: After entering function ll_rw_block, it will call function make_request to bind the buffer block with the request. First the buffer block will be locked in function make_request and load request through function add_request.
After the completion of the loading request, the system will send write disk command to the hard disk through calling function do_hd_request. Function do_hd_request is an interactive underlying function between the system and the hard disk, and according to the data in the request, it will write the data of the specified buffer block to the specified hard disk block ultimately. The executable code is as follows:
The performance of synchronizing a buffer block is as shown in Figure 7.36, and this buffer block is locked in make_request, but the dirty flag of the buffer block has been set to 0 in the function add_request. At this time, the buffer block has become a buffer block which is free but not dirty. In contrast with Figure 7.35, pay attention to the state change of the buffer block.
The final result of function sync_dev continuously synchronizes the buffer block as is shown in Figure 7.37. Note that all the request items which have been left to the write operation have been occupied, and at the same time, the status of the buffer block corre- sponds to the write request item, has also been set to the free and not the dirty state. The hard disk is constantly processing the claims.
//code path:kernel/blk drv/ll rw blk.c:
static void make_request(int major,int rw, struct buffer_head * bh) {
……
if (rw! = READ && rw! = WRITE)
panic(“Bad block dev command, must be R/W/RA/WA”);
lock_buffer(bh); //lock the buffer block
if ((rw = = WRITE && !bh->b_dirt) || (rw = = READ && bh->b_uptodate)) { unlock_buffer(bh);
return;
}
……
req->buffer = bh->b_data;
req->waiting = NULL;
req->bh = bh;
req->next = NULL;
add_request(major+blk_dev,req); //load claims }
static void add_request(struct blk_dev_struct * dev, struct request * req) {
……
if (req->bh)
req->bh->b_dirt = 0; //the buffer block is synchronized and it will not be dirty
……
(dev->request_fn)(); //this line of code corresponds to the function do_hd_request ……
}
rw rw rw rw r r
rw r
Process A
Buffer zone
Process A
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item Figure 7.37 Space in the structure of the claims for the write request has run out.
rw rw rw rw r r
rw r
Process A
Buffer zone
Process A
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item Figure 7.36 Writing request is inserted into the requesting queue.
The code for this process is as follows:
//code path:fs/buffer.c:
int sync_dev(int dev) {
int i;
struct buffer_head * bh;
bh = start_buffer;
for (i=0 ; i<NR_BUFFERS ; i++,bh++) { //traverse all buffer //blocks
if (bh->b_dev ! = dev) continue;
wait_on_buffer(bh);
if (bh->b_dev = = dev && bh->b_dirt) ll_rw_block(WRITE,bh);
}
……
}
//code path:kernel/blk_drv/ll_rw_blk.c:
void ll_rw_block(int rw, struct buffer_head * bh) {
unsigned int major;
if ((major = MAJOR(bh->b_dev)) > = NR_BLK_DEV ||
!(blk_dev[major].request_fn)) {
printk(“Trying to read nonexistent block-device\n\r”);
return;
}
make_request(major,rw,bh);
}
static void make_request(int major,int rw, struct buffer_head * bh) {
……
if (rw! = READ && rw! = WRITE)
panic(“Bad block dev command, must be R/W/RA/WA”);
lock_buffer(bh); //it is locked here
……
add_request(major+blk_dev,req);
}
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
……
req->next = NULL;
cli();
if (req->bh)
req->bh->b_dirt = 0; //here the dirty flag is set to 0
……
}
Although there are free request items in the structure of the request, the request items that left to the “write” operation only account for two thirds of the total number of request items. The corresponding code is as follows:
Because two thirds of the request items have all been occupied, now no free request item can serve the “sync.” The write request is as shown in Figure 7.37.
Process A is suspended by the system because of waiting for free request. There is no free request item for write, but function sync_dev() will still continue to be called.
After re-entering the function make_request(), it will execute the following code:
The function of these codes is when suitable free claim can’t be found in the end, the current process will be suspended. After calling the function sleep_on(), process A has become the process of waiting for free request, and it will be suspended. This process is shown in Figure 7.38. The hard disk is still processing the request constantly while process A has been in the suspended state despite its time slice.
//code path:kernel/blk drv/ll rw blk.c:
static void make_request(int major,int rw, struct buffer_head * bh) {
……
if (rw = = READ)
req = request+NR_REQUEST; //all request items can be used //for read operations
else
req = request+((NR_REQUEST*2)/3); //only 2/3 of the claims can be //used for write operations ……
}
//code path:kernel/blk_drv/ll_rw_blk.c:
static void make_request(int major,int rw, struct buffer_head * bh) {
……
while (-- req >= request)
……
if (req < request) { //indicate that there is no free request //item here
……
sleep_on(&wait_for_request);
}
……
}
Start to execute Process B. Process B starts to be executed, which is also a write disk process. The system should also apply for the buffer block for process B so that it can write data. The executable code is as follows:
As can be seen in Figure 7.38, the state of each free buffer block in the buffer is dif- ferent at this time. The system will comprehensively analyze the state of all the free buf- fer blocks in the current case in order to determine which buffer block will be applied for
rw rw rw rw r r
rw r
Process A
Suspend
Suspend
Buffer zone
Process A
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item Figure 7.38 Process A is suspended.
//code path:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) {
……
tmp = free_list;
do {
if (tmp->b_count) continue;
if (!bh || BADNESS(tmp)<BADNESS(bh)) { bh = tmp;
if (!BADNESS(tmp)) break;
}
/* and repeat until we find something good */
} while ((tmp = tmp->b_next_free) != free_list);
……
}
process B. The system uses the BADNESS (tmp) to carry on a comprehensive analysis.
BADNESS (tmp) is defined as follows:
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock).
Through the above analysis. we know that its role is to divide the buffer block in the buffer into four levels according to the principle more favorable for process executing.
From favorable to unfavorable in order are
Level 1: There is a not “dirty” and not “locked” free buffer block, and the value of BADNESS in such a buffer block is 0.
Level 2: There is a not “dirty” but “locked” free buffer block, and the value of BADNESS in such a buffer block is 1.
Level 3: There is a “dirty” but not “locked” free buffer block, and the value of BADNESS in such a buffer block is 2.
Level 4: There is a “dirty” and “locked” free buffer block, and the value of BADNESS in such a buffer block is 3.
The smaller the value of BADNESS is, the more convenient the buffer block is to use.
Otherwise, it is inconvenient.
The system has locked some buffer blocks, and their “dirty” flags are set to 0. Thus, it makes their BADNESS values become 1. In the present circumstance, this is the most convenient buffer block to use. Therefore, the system applies for a buffer block whose BADNESS value is 1 for process B. This buffer block is locked, which means that the buffer
r r
rw r
rw rw rw rw
Suspend Process A
Process B
Process B
Buffer zone
Process A
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item Figure 7.39 System has applied for a buffer block for process B.
block cannot be operated immediately. But it’s better than applying for a dirty buffer block. Figure 7.39 shows the buffer block that the system has applied for process B.
Process B is also suspended. The buffer block the system has applied is a “locked”
buffer block, and it leads to the process or system not being able to exchange data with the buffer block immediately. Thus, the system will directly call function wait_on_buffer() and process B will also be suspended as is shown in Figure 7.40. Note that the system and the hard disk continue to process the request.
The code is as follows:
The process C starts to execute and then subsequently is suspended. Process C starts to execute, which is a read disk process, and the system should also apply a buffer block for it. Based on the condition of buffer, the system applies for the same buffer block for process C and process B. From the introduction of Section 7.2.6, we learned that this buffer block
r r
rw r
r r
Suspend Suspend
Process A
Process B
Process B
Buffer zone
Process A
Request item
Disk rw
rw r
rw rw rw
Request item queue Locked IDLE
“read” request item NON-IDLE Dirty
“write” or “read” request item Figure 7.40 Process B is also suspended.
//code path:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) {
……
if (!bh) {
sleep_on(&buffer_wait);
goto repeat;
}
wait_on_buffer(bh); //process B is suspended here if (bh->b_count)
goto repeat;
……
}
is locked, and the buffer block cannot be operated, but it can be applied. So the process C will also be suspended.
Process C and process B are now suspended because of waiting for the same buffer block to unlock. These two processes form a process waiting queue.
Until now, three user processes are suspended in example 2, so it switches to process 0 to execute by default. The situation that they are suspended in is shown in Figure 7.41.
Process A is in the waiting queue of waiting for free request, but process B and process C are in the queue waiting for the same buffer block to unlock.
Process A and process C are awakened. Here we will introduce the process of the three user processes that are waken up. After they have been waken up, the system will continue to determine what user process will execute according to the various aspects of the situation of the buffer block and request items.
After a while, the hard disk has completed the synchronization task delivered by the request, and will produce a hard disk interrupt. The interrupt service routine begins to execute. The code is as follows:
rw rw rw rw r r
rw r
Process A
Process B Process C
Buffer zone
Suspend Suspend
Process A Process B Process C
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item Figure 7.41 Waiting queue in which the processes A, B, and C are and their running state.
//code path:kernel/blk_dev/blk.h:
extern inline void end_request(int uptodate) {
……
unlock_buffer(CURRENT->bh);
……
wake_up(&wait_for_request);
……
Process A is suspended for waiting for free request item. Then wake_up (&wait_for_
request), and this line of code will wake up process A as shown in the process A in the left bottom of Figure 7.42.
Process B and process C form a process waiting queue. Process C is waken up first because it is suspended later than process B as shown in the process C in the left bottom of Figure 7.42.
In addition, the operation of the data in the specified buffer block has already been completed, so the interrupt service routine will unlock the buffer block. The interrupt ser- vice routine will continue to call function do_hd_request after the above work has been done. If there are request items to deal with, it will send a write disk command to the hard disk again. Obviously, the hard disk continues to the subsequent synchronization. As can be seen from the right part of Figure 7.42, the hard disk is processing the next request item.
And, at the moment, there is an available free “write” request item.
We can see in Figure 7.42 that the time slice of process C is more than that of pro- cess A. Therefore, the system switches the current process from process 0 to process C.
r r
rw r
rw rw rw rw
Process A
Process C Process B
Buffer zone
Process A Process B Process C
Request item
Disk
Request item queue Locked IDLE NON-IDLE Dirty
“write” or “read” request item “read” request item
Figure 7.42 State of each process after the synchronization of data in the buffer block has completed.
}
extern inline void unlock_buffer(struct buffer_head * bh) {
……
bh->b_lock = 0;
wake_up(&bh->b_wait);
}