Zhang Chaoyang rickycheung@21cn.com
01 level computer science and technology department
experimental report
- Realize semaphore communication mechanism in Minix 2.0
This experiment report consists of three parts, including the first and second parts mainly analyzed the MiniX operating system, and the third part is an experimental exploration process for the Semaphore to the MiniX operating system.
First, the Message Mechanism Analysis of the MiniX Operating System
The Minix operating system is a micro-kernel structure. Its internal structure is based on kernel, supplemented by a collection of a set of servers. As shown in the following table:
User process 1
User process 2
User process 3
User process 4
...
User process
Mm
Memory Manager
FS
File system
...
Server process
Disk task
Terminal task
Clock task
System task
...
I / O task
Process management
Table 1 Description: The least two layers of two layers, process management, and I / O tasks constitute the kernel.
The process between the MINIX operating system, and between the user process is the communication mechanism of using messaging. So how does the Minix operating system implement a messaging mechanism? The following is the tracking of the source code.
Figure 1. Message transfer process
Fundamentally, the Minix operating system delivery message is interrupt by calling interrupt gate 33 (sysVec), and then falls into kernel implementation.
When MINIX is initiated, the interrupt door is initially interrupt (prot_init ()) is 33 (sysvec), and is loaded into the interrupt service routine (SRC / KERNEL / MPX386.S _S_CALL ).
When the process needs to send (receiving) messages, first modify Send (Receive) provided by SRC / LIB / I386 / RTS / _SENDREC.s, while SRC / LIB / I386 / RTS / _SENDREC.S SEND (Receive) is called Interrupt 33 (SysVec) service routine_s_call. _S_CALL is in turn into the kernel of Minix by calling SYS_CALL (in SRC / KERNEL / PROC.C). SYS_CALL transmits (receiving) messages to the target process using mini_send and mini_rec.
Second, the library of the MiniX operating system
Due to the following communication rules between the MINIX specified process:
a. You cannot mess with the user process.
b. User processes can only send, receive messages to mm and fs.
Therefore, when the user process wants to modify the function of the kernel, it will be provided by MM, FS as the medium or by both. Now use the fork () system call as an example.
When the user calls fork (), use src / lib / syscall / fork.s to SRC / LIB / POSIX / _FORK.C. And _fork.c trapped into MM with Sys_CALL, when MM completes the necessary operation to the Fork initialization, then call Task_Call again to the kernel. Its flow is shown below:
Figure 2. Fork calling process
Third, the implementation of MiniX semaphore
On the basis of understanding the Message Mechanism of Minix and the library calling process, the implementation of the MiniX semaphore is started.
First, since the user process cannot communicate with the message, the user process wants to pass the signal to the MM or kernel implementation through the system call through the system call. Therefore, it can be clear that the amount of semaphors should be provided to the user process in the form of a library.
Second, it is necessary to determine the specific implementation form of the semaphore. In the early days of implementation, I think there are two options:
Option One:
Directly utilize messages, wake up or block other user processes on the MM layer.
For example, when the user process A performs P operation, if the amount of signal is less than 0, the mm is blocked by the user process A by means of reply. When another user process B is operated V operation, if the value of the signal is not more than 0, the MM looks up the signal blocking process queue, then send a reply to the blocked user process. Option II:
In the kernel layer, the processes or block other user processes are woken up or blocked by direct operations of the process.
When the user process performs semaphore operation, the MM layer is an intermediary, first fall into the MM layer, then call the custom _taskcall (Systask, Sys_SEM, & M) from the MM layer, and then fall into the kernel. The kernel responds to the message in DO_SEM.
Finally, in the kernel layer, the user process queue is directly awakened and blocked.
Solution, short comparison:
The solution can be achieved as soon as the MM message loop is simply controlled by the Dont_reply variable. However, the program is a lack of robustness (Robust), first of all, because the user process is simple, it is determined by reply. If there is a user process at which other non-use semaphore, it is blocked by the user process that is blocked by the P operation, then the blocked user The process will be awakened, but the wake is not caused by V operations from the semaphore, which will have a logical fallacy.
Despite the complexity of the program, the program is more complex, but the robustness is improved. In Proc.h's process Struct Add Identifier Variable P_SEM_WAIT, wake up the user process or whether the message response is determined by the message, but is operated by the V operation, change p_sem_wait and use the Ready function to wake the user process.
I decided to adopt the second programs through the above comparison. The following is a detail:
Mainly used data structure:
Blocking process queue: The specific implementation is to establish a link relationship between PROC adding struct proc * p_next_block_proc, and add blocking process team head and tail pointer to the Semaphore structure.
Mainly use algorithms:
The process of awakening the semaphore is blocked, and the FCFS policy is used. The blocking user process is removed directly from the block of the semaphore. Of course, you can extend the wake-up strategy by parameters.
Calling P, V, CreatSemaphore, DELSEMAPHORE:
test program:
Program 1 reader and writer question:
#include
#include
#include
#include
#include
#define n 10
Void Enter_Item ()
{
CHAR BUFF;
Int Num;
Int fd;
FD = Open ("item", o_rdwr);
Lseek (fd, 1, seek_set);
Read (FD, & BUFF, 1);
BUFF ;
Num = (int) BUFF;
Printf ("/ NENTER ITEM:% D / N", NUM;
Lseek (fd, 1, seek_set);
Write (FD, & BUFF, 1);
Close (FD);
}
Void Remove_Item ()
{
CHAR BUFF;
Int Num;
Int fd;
FD = Open ("item", o_rdwr);
Lseek (fd, 1, seek_set);
Read (FD, & BUFF, 1);
BUFF -;
Num = (int) BUFF;
Printf ("/ NREMOVE ITEM: D / N", NUM);
Lseek (fd, 1, seek_set); Write (FD, & BUFF, 1);
Close (FD);
}
void main ()
{
INT EMPTY = CREATSEM (N);
INT full = creatsem (0);
INT MUTEX = CREATSEM (1);
INT fd = Creat ("item", 0751);
CHAR BUFF = 0;
Lseek (fd, 1, seek_set);
Write (FD, & BUFF, 1);
Close (FD);
IF (fork ()! = 0) {
While (1) {
p (EMPTY);
p (Mutex);
ENTER_ITEM ();
v (mutex);
v (FULL);
}
} else {
While (1) {
Sleep (2);
p (full);
p (Mutex);
REMOVE_ITEM ();
v (mutex);
v (EMPTY);
}
}
}
Description: Refer to the pipeline (PIPE), the file Item is used to share data between the processes.
February 11, 2005
