7. Buffer and Multiprocess File 343
7.6 Example 1: Process Waiting Queue of Buffer Block
Below we present a case in which more than one process operates the same file at the same time. We use this to embody the problem of the sharing problem and explain clearly the principle of the process waiting queue.
Suppose there is a file named hello.txt on your hard disk. The file’s size is 700 B (which is smaller than the size of a data block). A buffer block can carry the entire contents of this file when it is loaded in. Once three processes start operating, this file is equivalent to that they are operating the same buffer block relying on the system. This will produce the process waiting queue. This section will detail the process of generating the queue and waking up the processes in the queue.
Here we introduce the scene of example 1. The three processes are as follows:
Process A is about reading the disk. The purpose is to read 100 bytes in the hello.txt file into the buffer[100]. The specific code is as follows:
Process B is about reading the disk too. The purpose is to read 200 bytes in the hello.
txt file into the buffer[200]. The specific code is as follows:
void FunA();
void main() {
……
FunA();
……
}
void FunA() {
char buffer[100];
int i,j;
//open the file
int fd = open(“/mnt/user/user1/user2/hello.txt”, O_RDWR,0644));
//read the file
read(fd,buffer,sizeof(buffer));
//close the file close(fd);
for(i=0;i<1000000;i++)//Time-consuming piece {
for(j=0;j<1000000;j++) {
; } } return;
}
Process C is about writing the disk. The purpose is to write characters “ABCDE” in str1[] to the hello.txt file. The specific code is as follows:
void FunB();
void main() {
……
FunB();
……
}
void FunB() {
char buffer[200];
int i,j;
//open file
int fd = open(“/mnt/user/user1/user2/hello.txt”,O_RDWR,0644));
//read the file
read(fd,buffer,sizeof(buffer));
//close the file close(fd);
for(i=0;i<1000000;i++)//Time-consuming piece {
for(j=0;j<1000000;j++) {
; }
} return;
}
void FunC();
void main() {
……
FunC();
……
}
void FunC() {
char str1[]=“ABCDE”;
int i,j;
//open file
int fd = open(“/mnt/user/user1/user2/hello.txt”, O_RDWR,0644));
//write file
write(fd,str1,strlen(str1));
//close file close(fd);
for(i=0;i<1000000;i++)//Time-consuming piece {
for(j=0;j<1000000;j++) {
; }
} return;
}
The execution order of these three processes is process A first, process B second, and process C the last. These three processes have no parent-child relationship.
Let’s look at the specific implementation process.
Process A is suspended after reading the file. After it is started, process A exe- cutes the sentence “int fd = open (“/mnt/user/user1/user2/hello.txt”, O_RDWR,0644))”.
Function open() will eventually be mapped to sys_open() function to execute. Function sys_open()’s implementation is introduced in Chapter 5. The specific code is as follows:
Implementation is shown in Figure 7.12.
Then the sentence “read(fd, buffer, sizeof (buffer))” is executed. The function read() will eventually be mapped to function sys_read() to execute. The function sys_read() will call function file_read() to read the contents of the file. Function file_read() calls function bread() to read data from the hard disk. The specific code is as follows:
//code source: fs/open.c:
int sys_open(const char * filename,int flag,int mode) {
……
(current->filp[fd] = f)->f_count++; //bind *filp[20] in process A with items //corresponding to file_table[64],and add //file handle count
……
if ((i = open_namei(filename,flag,mode,&inode))<0) { //To obtain the I node in //hello.txt file
……
f->f_mode = inode->i_mode; //set file attributes using i-node //attributes,
f->f_flags = flag; //set file operations with the flag //parameter
f->f_count = 1; //File reference count plus 1
f->f_inode = inode; //build relationships between the i-node //and the file.
f->f_pos = 0; //File read and write pointer is set to 0
return (fd); //return the file handle to the user space
}
//code source: fs/read_write.c:
int sys_read(unsigned int fd,char * buf,int count) //Reading data from hello.txt file //fd is the file handle, buf is a user-space pointer, //and count is the number of bytes to read
if (S_ISDIR(inode->i_mode) || S_ISREG(inode->i_mode)) { if (count+file->f_pos > inode->i_size)
count = inode->i_size - file->f_pos;
if (count< = 0) return 0;
return file_read(inode,file,buf,count); //Read specified data of process }
printk(“(Read)inode->i_mode =%06o\n\r”,inode->i_mode);
return -EINVAL;
}
//code source:fs/file_dev.c:
int file_read(struct m_inode * inode, struct file * filp, char * buf, int count) {
……
if (nr = bmap(inode,(filp->f_pos)/BLOCK_SIZE)) {
if (!(bh = bread(inode->i_dev,nr))) //read data from the hard disk break;
} else bh = NULL;
……
}
The implementation process after entering function bread() has been described in detail in Section 3.3.1. The code is as follows:
Process A is suspended in function wait_on_buffer(). The code is as follows:
Kernel
ROM BIOS and VGA
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
task_struct of process A
The page that task_struct of process A resides
i node of hello.txt
filp[20]
Process status
Process 0 Process A
Interruptible Ready
Current process inode_table[32] file_table[64]
Figure 7.12 System open file hello.txt for process A.
//code source:fs/buffer.c:
struct buffer_head * bread(int dev,int block) //read data from the hard disk {
……
if (!(bh = getblk(dev,block)))//Apply for a free buffer block
ll_rw_block(READ,bh); //The buffer block is locked and is bound with //request item, sending disc reading instruction wait_on_buffer(bh); //suspend the process waiting for unlocked
//buffer block, if (bh->b_uptodate)
return bh;
……
}
The buffer block has been locked when ll_rw_block() function is being executed (as is described in Section 3.3.1.3). If the result of (bh->b_lock) is true, function sleep_on() is called. Arguments that is transported is &bh->b_wait and bh->b_wait, which represents a pointer of the process that is waiting for the unlocking of the buffer block. All the b_wait in all the buffer blocks are set to NULL (as mentioned in Section 2.10) when the system is initialized. And this buffer block is a new application, which has never been used by other processes. So the value of bh->b_wait is NULL at this time. Next, the process enters the following function sleep_on(). The code is as follows:
From the introduction of arguments in sleep_on() function we learned that *p points to bh->b_wait. *p stores the pointer of process A, which means that process A is waiting for buffer block bh to be unlocked.
Calling function schedule() and switching to execute process B after the process A is suspended. At the same time, the hard disk is also transporting data to the data register port. This situation is shown below:
The progress bar representing process A in Figure 7.13 is turned into gray, which means process A is suspended.
It is worth noting that tmp in the code is stored in the kernel stack of the process A as NULL. Bh->b_wait stores the pointer of process A (Figure 7.14).
//code source:fs/buffer.c:
static inline void wait_on_buffer(struct buffer_head * bh)//suspend the process waiting for unlocked buffer block,
{
cli();//Interrupt off
while (bh->b_lock) //Detect whether the buffer block is locked sleep_on(&bh->b_wait); //suspend the buffer block process
//(A process), and switch to //other process
sti();//Open interrupt }
//code source:kernel/sched.c:
void sleep_on(struct task_struct **p) {
struct task_struct *tmp;
if (!p) return;
if (current = = &(init_task.task)) panic(“task[0] trying to sleep”);
tmp = *p; //at this time tmp stores
//NULL
*p = current; //*p stores pointer of
//process A
current->state = TASK_UNINTERRUPTIBLE; //set process A to //uninterruptible state
schedule(); //switch process
if (tmp)
tmp->state = 0;
}
Process B was suspended after reading the file. Process B first executes the sen- tence int fd = open (“/mnt/user/user1/user2/hello.txt”, O_RDWR,0644)). Function open() will eventually be mapped to function sys_open() to execute. Function sys_open() will apply for a free new entries in the file management table file_table[64] to mount[20] file_
table[64] empty entries mount and the *filp in task_struct in process B. Although the process B and process A are opening the same file, these two processes’ operation of the
Kernel
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Buffer block
Disk Disk read data continually
Process status
Process 0 Process A
Interruptible Uninterruptible Current process
ROM BIOS and VGA
Figure 7.13 System reads data in hello.txt and suspends process A.
Process A
Kernel stack
task_struct
NULL b_wait
bh
tmp
……
……
Figure 7.14 Set process A into wait queue.
file are not related to each other. As a result, two sets of books are needed. The specific code is as follows:
The scenario of binding is shown below:
The hard disk is constantly reading data, which means the request of reading the disk from process A is not yet completed (Figure 7.15).
The process calls function open_namei() and gets i node in hello.txt file and finally mounts the i node and file_table[64]. The specific code is as follows:
It is worth noting that the way to get the i node from the hello.txt file is different from the way process A gets i node. The specific code is as follows:
//code source:fs/open.c:
int sys_open(const char * filename,int flag,int mode) {
……
for(fd = 0 ; fd<NR_OPEN ; fd++) if (!current->filp[fd])
break;
……
for (i = 0 ; i<NR_FILE ; i++,f++) if (!f->f_count) break;
……
(current->filp[fd] = f)->f_count++; //bind *filp[20] in process B and items //corresponding to file_table[64],and add file handle count if ((i = open_namei(filename,flag,mode,&inode))<0) { //To obtain the I-node in
//hello.txt file
……
f->f_mode = inode->i_mode; //set file attributes using i-node attributes f->f_flags = flag; //set file operations with the flag parameter f->f_count = 1; //File reference count plus 1
f->f_inode = inode; //build relationships between the i-node and the file.
f->f_pos = 0; //File read and write pointer is set to 0 return (fd); //return the file handle to the user space }
//code source:fs/namei.c:
int open_namei(const char * pathname, int flag, int mode, struct m_inode ** res_inode)
{
……
if (flag & O_EXCL) return -EEXIST;
if (!(inode = iget(dev,inr))) //To obtain the I node return -EACCES;
……
}
//code source:fs/open.c:
int sys_open(const char * filename,int flag,int mode) {
……
if ((i = open_namei(filename,flag,mode,&inode))<0) {//To obtain the I node in hello.txt file
……
f->f_mode = inode->i_mode; //set file attributes using i-node attributes f->f_flags = flag; //set file operations with the flag parameter f->f_count = 1; //File reference count plus 1
f->f_inode = inode; //build relationships between the i-node and the file.
f->f_pos = 0; //File read and write pointer is set to 0 return (fd); //return the file handle to the user space }
Kernel
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
task_struct of process B
The page that task_struct of process B resides
file_table[64]
filp[20]
Attach new item in file_table[64] and
new item in filp[20] Disk reads data continually Process status Disk
Process 0 Process A Process B
Interruptible Uninterruptible Ready
Current process
ROM BIOS and VGA
Figure 7.15 System build relationships between process B and the kernel file management table.
//code source:fs/namei.c:
struct m_inode * iget(int dev,int nr) {
……
empty = get_empty_inode(); //apply for free entry in inode_table[32]
……
while (inode < NR_INODE+inode_table) {//Traversethe entire inode_table[32]
if (inode->i_dev ! = dev || inode->i_num ! = nr) {//If can not find a ready-made list, then keep looking
continue;
}
wait_on_inode(inode);
if (inode->i_dev ! = dev || inode->i_num ! = nr) {
……
continue;
}
inode->i_count++; //if ready-made i-node in hello.txt file can be find, //reference count increases
……
if (empty) //free entry found in inode_table[32] is useless, release it iput(empty);
return inode; //return i-node in hello.txt }
……
}
The application of a free i-node scenario is shown in Figure 7.16.
One file is only corresponding to one i node. Two sets of accounts are needed to record the operation to the file by process A and B. But there is only one i node that operates in hello.txt. Process A has loaded i node into inode_table[32]. Process B needs to continue to use the i node then.
The i node operation scenario of the above code is shown in Figure 7.17.
After opening the file, process B runs the sentence read(fd,buffer,sizeof(buffer)); and reads the content in the file hello.txt. Function read() will eventually be mapped to func- tion sys_read() to execute. Then function sys_read() calls function file_read() to read the contents of the file. Function file_read() calls function bread() to read data from the hard disk. The specific code is as follows:
ROM BIOS and VGA
Kernel
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
inode_table[32] Disk reads data continually
Disk
Process status
Get the new free i node table item
Process 0 Process A Process B
Interruptible Uninterruptible Ready
Current process
Figure 7.16 System creates the conditions for loading the i node in.
//code source:fs/read_write.c:
int sys_read(unsigned int fd,char * buf,int count) //Reading data from hello.txt file
{ //fd is the file handle, buf is a user-
//space pointer, and count is the number of //bytes to read
if (S_ISDIR(inode->i_mode) || S_ISREG(inode->i_mode)) { if (count+file->f_pos > inode->i_size)
count = inode->i_size - file->f_pos;
if (count< = 0) return 0;
return file_read(inode,file,buf,count); //read specific data of process }
printk(“(Read)inode->i_mode =%06o\n\r”,inode->i_mode);
return -EINVAL;
}
Kernel
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
task_struct of process B
The page where task_struct of process B resides
inode_table[32] file_table[64]
filp[20]
The newly applied i node has not been used
Process B shares the i node
of hello.txt with process A Disk reads data continually
Disk
Process status
Process 0 Process A Process B
Interruptible Uninterruptible Ready
Current process ROM BIOS
and VGA
Figure 7.17 System finds the i node already loaded into file hello.txt for process B.
//code source:fs/file_dev.c:
int file_read(struct m_inode * inode, struct file * filp, char * buf, int count) {
……
if (nr = bmap(inode,(filp->f_pos)/BLOCK_SIZE)) {
if (!(bh = bread(inode->i_dev,nr))) //read data from the hard disk break;
} else
bh = NULL;
……
}
The implementation process after entering the bread() function has been described in detail in Section 3.3.1. The specific code is as follows:
The execution scenario of function getblk() and function ll_rw_block() is different. It returns immediately after entering function getblk() because the data block correspond- ing to the file hello.txt has been loaded into the buffer block. The specific code is as follows:
Then execute function ll_rw_block(). As the buffer block has been locked, process B will be suspended by the system due to waiting for the buffer block to be unlocked. The specific code is as follows:
//code source:fs/buffer.c:
struct buffer_head * bread(int dev,int block)//read data from the hard disk {
……
if (!(bh = getblk(dev,block))) //Apply for a free buffer block
……
ll_rw_block(READ,bh); //The buffer block is locked and is bound //with request item, sending disc reading //instruction
wait_on_buffer(bh); //suspend the process waiting for unlocked //buffer block
if (bh->b_uptodate) return bh;
……
}
//code source:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) //apply for a buffer block {
……
if (bh = get_hash_table(dev,block)) //At this point the
//specified buffer block can //be found in the hash table return bh; //return to the bh pointer directly
……
}
//code source:kernel/blk_drv/ll_rw_block.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);//set the request }
static void make_request(int major,int rw, struct buffer_head * bh) {
……
Then the kernel executes function sleep_on(). It is the same file that is operated by processes A and B in Example 1. And it is corresponding to the same buffer block bh. The value of b_wait in the buffer block is set to the task_struct pointer of process A. So the scene of executing the function sleep_on() is completely different from the implementa- tion of the previous process A. The specific code is as follows:
The kernel calls the function schedule() after process A is suspended and switches to process C to execute.
At the same time, the hard disk is transacting data to the data register port. This sce- nario is shown in Figure 7.18.
It is worth noting that tmp in the code is stored in the kernel stack of the process B and is stored as task_struct pointer of process A. At this time, bh-> b_wait stored the pointer of the process B as shown in Figure 7.19.
Process C is suspended after writing files. Process C is excuted, and in the same operation hello.txt file, the data is written to the file. The data is written to the hello.txt file after the process C starts to execute. The technical route of executing process C is
lock_buffer(bh);//lock the buffer block the bh pointing to
if ((rw == WRITE && !bh->b_dirt) || (rw == READ && bh->b_uptodate)) { unlock_buffer(bh);
return;
}
……
}
static inline void lock_buffer(struct buffer_head * bh)//lock the buffer block {
cli();
while (bh->b_lock) //if the buffer block is already locked sleep_on(&bh->b_wait); //suspend the process waiting for the
//buffer block
bh->b_lock = 1; //If program executed to here, it means the //buffer block is not locked. Then lock it sti();
}
//code source:kernel/sched.c:
void sleep_on(struct task_struct **p) {
struct task_struct *tmp;
if (!p) return;
if (current = = &(init_task.task)) panic("task[0] trying to sleep");
tmp = *p; //at this time tmp stores task_struct
//pointer of process A
*p = current; //*p stores pointer of process B
current->state = TASK_UNINTERRUPTIBLE; //set process B to uninterruptible //waiting state
schedule(); //switch process
if (tmp)
tmp->state = 0;
}
broadly consistent with the process B. Execute the sentence int fd = open(“/mnt/user/
user1/user2/hello.txt”, O_RDWR,0644)) first. Function open() will eventually be mapped to function sys_open() to execute. The final results of the implementation of function sys_open() is that a free entry is reapplied in the file_table[64] and *filp[20] in task_struct of process C binds with file_table[64] in the free entry.
Process A Process B
NULL Pointer of process A
Kernel stack tmp Kernel stack tmp
task_struct task_struct
……
……
……
……
b_wait bh
Figure 7.19 Process B was set to TASK_UNINTERRUPTIBLE and added to the process wait queue.
Kernel
ROM BIOS and VGA
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Disk reads data continually
Disk Process status
Process 0 Process A Process B
Interruptible Uninterruptible Uninterruptible Current process
Figure 7.18 Process B was set to TASK_UNINTERRUPTIBLE.