一、微内核和宏内核
宏内核包括 UNIX,MS-DOS，linux
微内核有 Mach，Windows/NT，Minix
二、进程间通信IPC
分析程序a的执行过程，程序a执行效果如下图
发送消息方
1.调用get_ticks()获得
kernel/main.c
void TestA()
{while (1) {
printf("<Ticks:%d>", get_ticks());
milli_delay(200);
}
}
2. get_ticks()会调用send_recv
kernel/main.c
PUBLIC int get_ticks()
{
MESSAGEmsg;
reset_msg(&msg); //清空消息
msg.type =GET_TICKS; // GET_TICKS=2
send_recv(BOTH,TASK_SYS, &msg); // BOTH =3 //
returnmsg.RETVAL; RETVAL=u.m3.m3il
}
3. send_recv调用系统级的函数sendrec
kernel/proc.c
/*****************************************************************************
* send_recv
*****************************************************************************/
PUBLIC int send_recv(int function, int src_dest, MESSAGE*msg)//用户级的
{
int ret =0;
if(function == RECEIVE)
memset(msg,0, sizeof(MESSAGE));
switch(function) {
case BOTH: // BOTH=3
ret= sendrec(SEND,src_dest, msg);
if(ret == 0)
ret= sendrec(RECEIVE,src_dest, msg);
break;
case SEND: // SEND=
case RECEIVE: //RECEIVE=2
ret= sendrec(function,src_dest, msg);
break;
default:
assert((function== BOTH) ||
(function == SEND) || (function ==RECEIVE));
break;
}
return ret;
}
4. sendrec就是sys_sendrec函数，此函数调用msg_receive和msg_send
[1]a/kernel/syscall.asm
sendrec:
mov eax,_NR_sendrec //_NR_sendrec=0x1
mov ebx,[esp + 4] ; function
mov ecx,[esp + 8] ; src_dest
mov edx,[esp + 12] ; p_msg
int INT_VECTOR_SYS_CALL
ret
[2]kernel/protect.c
PUBLIC void init_prot()
{
…………..
init_idt_desc(INT_VECTOR_SYS_CALL, DA_386IGate,sys_call, PRIVILEGE_USER);
…………..
}
[3]kernel/kernel.asm
sys_call:
call save
sti
push esi
push dword [p_proc_ready]
push edx
push ecx
push ebx
call [sys_call_table + eax * 4]
add esp, 4 * 4
pop esi
mov [esi + EAXREG - P_STACKBASE], eax
cli
ret
[4]kerne/global.c
PUBLIC system_call sys_call_table[NR_SYS_CALL] = {sys_printx,sys_sendrec};
发现sendrec会调用sys_sendrec
kernel/proc.c
PUBLIC intsys_sendrec(int function, int src_dest, MESSAGE* m, struct proc* p)
{
assert(k_reenter== 0); /* make sure we are not inring0 */
assert((src_dest>= 0 && src_dest < NR_TASKS + NR_PROCS) ||
src_dest == ANY ||
src_dest == INTERRUPT);
int ret = 0;
int caller = proc2pid(p);
MESSAGE* mla = (MESSAGE*)va2la(caller,m);
mla->source = caller;
assert(mla->source!= src_dest);
/**
* Actually we have the third message type:BOTH. However, it is not
* allowed to be passed to the kernel directly.Kernel doesn't know
* it at all. It is transformed into a SENDfollowed by a RECEIVE
* by `send_recv()'.
*/
if (function == SEND) {
ret = msg_send(p, src_dest,m);
if (ret != 0)
return ret;
}
else if (function == RECEIVE) {
ret = msg_receive(p,src_dest, m);
if (ret != 0)
return ret;
}
else {
panic("{sys_sendrec}invalid function: "
"%d (SEND:%d, RECEIVE:%d).",function, SEND, RECEIVE);
}
return 0;
}
5.msg_send和msg_receive
其中使用的函数
ldt_seg_linear()每个进程都有自己的LDT,位于进程表的中间，这个函数就是根据LDT中描述符的索引来求得描述符所指向的段的基地址。
va2la()用来由虚拟地址求线性地址，它用到了ldt_seg_linear()
reset_msg()用于把一个消息的每个字节清零。
block()阻塞一个进程
unbock()解除一个进程的阻塞
deadlock()简单地判断是否发生死锁。方法是判断消息的发送是否构成一个环，如果构成环则意味着发生死锁，比如A试图发消息给B，同时B试图给C，C试图给A发消息，那么死锁就发生了，因为A,B,C三个进程都将无限等待下去
/*****************************************************************************
* msg_send
*****************************************************************************/
*****************************************************************************/
PRIVATEint msg_send(struct proc* current, int dest, MESSAGE* m)
{
structproc* sender = current;
structproc* p_dest = proc_table + dest; /* proc dest */
assert(proc2pid(sender)!= dest);
/* checkfor deadlock here */
if(deadlock(proc2pid(sender), dest)) {
panic(">>DEADLOCK<<%s->%s", sender->name, p_dest->name);
}
if((p_dest->p_flags & RECEIVING) && /* dest is waiting for the msg*/
(p_dest->p_recvfrom == proc2pid(sender)||
p_dest->p_recvfrom == ANY)) {
assert(p_dest->p_msg);
assert(m);
phys_copy(va2la(dest,p_dest->p_msg),
va2la(proc2pid(sender), m),
sizeof(MESSAGE));
p_dest->p_msg= 0;
p_dest->p_flags&= ~RECEIVING; /* dest has received the msg */
p_dest->p_recvfrom= NO_TASK;
unblock(p_dest);
assert(p_dest->p_flags== 0);
assert(p_dest->p_msg== 0);
assert(p_dest->p_recvfrom== NO_TASK);
assert(p_dest->p_sendto== NO_TASK);
assert(sender->p_flags== 0);
assert(sender->p_msg== 0);
assert(sender->p_recvfrom== NO_TASK);
assert(sender->p_sendto== NO_TASK);
}
else { /*dest is not waiting for the msg */
sender->p_flags|= SENDING;
assert(sender->p_flags== SENDING);
sender->p_sendto= dest;
sender->p_msg= m;
/*append to the sending queue */
structproc * p;
if(p_dest->q_sending) {
p= p_dest->q_sending;
while(p->next_sending)
p= p->next_sending;
p->next_sending= sender;
}
else{
p_dest->q_sending= sender;
}
sender->next_sending= 0;
block(sender);
assert(sender->p_flags== SENDING);
assert(sender->p_msg!= 0);
assert(sender->p_recvfrom== NO_TASK);
assert(sender->p_sendto== dest);
}
return 0;
}
/*****************************************************************************
* msg_receive
*****************************************************************************/
*****************************************************************************/
PRIVATEint msg_receive(struct proc* current, int src, MESSAGE* m)
{
structproc* p_who_wanna_recv = current; /**
* This name is a little bit
* wierd, but it makes me
* think clearly, so I keep
* it.
*/
structproc* p_from = 0; /* from which the message will be fetched */
structproc* prev = 0;
int copyok= 0;
assert(proc2pid(p_who_wanna_recv)!= src);
if((p_who_wanna_recv->has_int_msg) &&
((src== ANY) || (src == INTERRUPT))) {
/*There is an interrupt needs p_who_wanna_recv's handling and
* p_who_wanna_recv is ready to handle it.
*/
MESSAGEmsg;
reset_msg(&msg);
msg.source= INTERRUPT;
msg.type= HARD_INT;
assert(m);
phys_copy(va2la(proc2pid(p_who_wanna_recv),m), &msg,
sizeof(MESSAGE));
p_who_wanna_recv->has_int_msg= 0;
assert(p_who_wanna_recv->p_flags== 0);
assert(p_who_wanna_recv->p_msg== 0);
assert(p_who_wanna_recv->p_sendto== NO_TASK);
assert(p_who_wanna_recv->has_int_msg== 0);
return0;
}
/* Arriveshere if no interrupt for p_who_wanna_recv. */
if (src ==ANY) {
/*p_who_wanna_recv is ready to receive messages from
* ANY proc, we'll check the sending queue andpick the
* first proc in it.
*/
if(p_who_wanna_recv->q_sending) {
p_from= p_who_wanna_recv->q_sending;
copyok= 1;
assert(p_who_wanna_recv->p_flags== 0);
assert(p_who_wanna_recv->p_msg== 0);
assert(p_who_wanna_recv->p_recvfrom== NO_TASK);
assert(p_who_wanna_recv->p_sendto== NO_TASK);
assert(p_who_wanna_recv->q_sending!= 0);
assert(p_from->p_flags== SENDING);
assert(p_from->p_msg!= 0);
assert(p_from->p_recvfrom== NO_TASK);
assert(p_from->p_sendto== proc2pid(p_who_wanna_recv));
}
}
else {
/*p_who_wanna_recv wants to receive a message from
* a certain proc: src.
*/
p_from= &proc_table[src];
if((p_from->p_flags & SENDING) &&
(p_from->p_sendto ==proc2pid(p_who_wanna_recv))) {
/*Perfect, src is sending a message to
* p_who_wanna_recv.
*/
copyok= 1;
structproc* p = p_who_wanna_recv->q_sending;
assert(p);/* p_from must have been appended to the
* queue, so the queue must not be NULL
*/
while(p) {
assert(p_from->p_flags& SENDING);
if(proc2pid(p) == src) { /* if p is the one */
p_from= p;
break;
}
prev= p;
p= p->next_sending;
}
assert(p_who_wanna_recv->p_flags== 0);
assert(p_who_wanna_recv->p_msg== 0);
assert(p_who_wanna_recv->p_recvfrom== NO_TASK);
assert(p_who_wanna_recv->p_sendto== NO_TASK);
assert(p_who_wanna_recv->q_sending!= 0);
assert(p_from->p_flags== SENDING);
assert(p_from->p_msg!= 0);
assert(p_from->p_recvfrom== NO_TASK);
assert(p_from->p_sendto== proc2pid(p_who_wanna_recv));
}
}
if (copyok){
/*It's determined from which proc the message will
* be copied. Note that this proc must havebeen
* waiting for this moment in the queue, so weshould
* remove it from the queue.
*/
if(p_from == p_who_wanna_recv->q_sending) { /* the 1st one */
assert(prev== 0);
p_who_wanna_recv->q_sending= p_from->next_sending;
p_from->next_sending= 0;
}
else{
assert(prev);
prev->next_sending= p_from->next_sending;
p_from->next_sending= 0;
}
assert(m);
assert(p_from->p_msg);
/*copy the message */
phys_copy(va2la(proc2pid(p_who_wanna_recv),m),
va2la(proc2pid(p_from), p_from->p_msg),
sizeof(MESSAGE));
p_from->p_msg= 0;
p_from->p_sendto= NO_TASK;
p_from->p_flags&= ~SENDING;
unblock(p_from);
}
else { /* nobody's sending any msg */
/*Set p_flags so that p_who_wanna_recv will not
* be scheduled until it is unblocked.
*/
p_who_wanna_recv->p_flags|= RECEIVING;
p_who_wanna_recv->p_msg= m;
if(src == ANY)
p_who_wanna_recv->p_recvfrom= ANY;
else
p_who_wanna_recv->p_recvfrom= proc2pid(p_from);
block(p_who_wanna_recv);
assert(p_who_wanna_recv->p_flags== RECEIVING);
assert(p_who_wanna_recv->p_msg!= 0);
assert(p_who_wanna_recv->p_recvfrom!= NO_TASK);
assert(p_who_wanna_recv->p_sendto== NO_TASK);
assert(p_who_wanna_recv->has_int_msg== 0);
}
return 0;
}
接收消息方
新建一个系统进程来接收用户进程的消息，并且返回ticks值。新建一个系统进程，叫SYSTASK
1.kernel/main.c
PUBLIC int kernel_main()
{
…..
p_task = task_table + i; //内核任务
…..
}
2.kernel/global.c
PUBLIC structtask task_table[NR_TASKS] = {
{task_tty,STACK_SIZE_TTY, "TTY"},
{task_sys,STACK_SIZE_SYS, "SYS"}}; //任务名是SYS，任务将执行的函数是task_sys，
3. kernel/systask.c
/*****************************************************************************
* <Ring 1> The main loop of TASK SYS.
*****************************************************************************/
PUBLIC void task_sys()
{
MESSAGEmsg;
while (1) {
send_recv(RECEIVE,ANY, &msg);
intsrc = msg.source;
switch(msg.type) {
case GET_TICKS:
msg.RETVAL= ticks;
send_recv(SEND,src, &msg); //发送消息
break;
default:
panic("unknownmsg type");
break;
}
}
}
新的结构体
1.进程表的新成员proc
a/include/proc.h
structproc {
struct stackframe regs; /* process registers saved in stack frame*/
u16 ldt_sel; /* gdt selector giving ldt baseand limit */
struct descriptor ldts[LDT_SIZE]; /*local descs for code and data */
int ticks; /* remained ticks */
int priority;
u32 pid; /* process id passed in fromMM */
char name[16]; //进程名
int p_flags; //用于标明进程的状态，有三种，第一种:0进程正在运行，第二种:SENDING进程处于发送消息的状态。由于消息还未送达，进程被阻塞。第三种:RECEIVING进程处于接收消息的状态。由于消息还未收到，进程被阻塞。
MESSAGE * p_msg; //指向消息体的指针
int p_recvfrom; //假设进程P想要接收消息，但目前没有进程发送消息给它，本成员记录P想要从谁那里接收消息
int p_sendto; //假设进程P想要发送消息，但目前没有进程接收它，本成员记录P想要发送消息给谁
inthas_int_msg; //如果有一个终端需要某进程来处理，或者换句话说，某进程正在等待一个中断发生——比如硬盘驱动可能会等待
硬盘中断的发生，系统在得知中断发生后会将此位置为1。
struct proc *q_sending; //如果有若干进程—比如啊a，b和c—都向同一个进程P发送消息，而P此时并未准备接受消息，那么A,B,C将会排成一个队列，进程P的q_sending指向第一个试图发送消息的进程
struct proc *next_sending; //试图发送消息A,B,C三进程排成的队列的实现方式是这样的:目的进程P的进程表的q_sending指向A，进程A的进程表next_sending指向B，进程B的进程表的next_sending指向C，进程C的进程表的next_sending指向空
int nr_tty;
};
2.发送消息的流程
假设有进程A想要向B发送消息M，那么过程将会是这样的:
A首先准备好M
A通过系统调用sendrec，最终调用msg_send
简单判断是否发生死锁
判断目标进程B是否正在等待来自A的消息：
如果是:消息被复制给B，B被解除阻塞，继续运行
如果否:A被阻塞，并被加入到B的发送队列中
假设有进程B想要接收消息(来自特定进程，中断或者任意进程)，那么过程将会是这样的
1. B准备一个空的消息结构体M， 用于接收消息。
2. B通过系统调用sendrec， 最终调用msg_receive。 3. 判断B是否有个来自硬件的消息（ 通过has_int_msg） ， 如果是， 并且B准备接收来自中断的消息或准备接收任意消息， 则马上准备一个消息给B， 并返回。 4. 如果B想接收来自任意进程的消息， 则从自己的发送队列中选取第一个（ 如果队列非空的话） ， 将其消息复制给M。 5. 如果B是想接收来自特定进程A的消息， 则先判断A是否正在等待向B发送消息， 若是的话， 将其消息复制给M。 6. 如果此时没有任何进程发消息给B， B会被阻塞。 值得说明的是， 不管是接收方还是发送方， 都各自维护一个消息结构体， 只不过发送方的结构体是携带了消息内容的而接收方
3.新加的函数assert()和panic()
#define ASSERT
#ifdef ASSERT
voidassertion_failure(char *exp, char *file, char *base_file, int line);
#defineassert(exp) if (exp) ; \
else assertion_failure(#exp, __FILE__, __BASE_FILE__, __LINE__)
#else
#define assert(exp)
#endif
__FILE__将被展开成当前输入的文件。在这里，它告诉我们哪个文件中产生了异常。
__BASE_FILE__可被认为是传递给编译器的那个文件名。比如你在m.c中包含了n.h，而n.h中的某一个assert函数失败
了，则__FILE__为n.h， __BASE_FILE__为m.c。
__LINE__将被展开成当前的行号。
4.新的调度算法，加入阻塞
当p_flags为0时才让其运行
kernel/proc.c
PUBLIC voidschedule()
{
struct proc* p;
int greatest_ticks= 0;
while (!greatest_ticks) {
for (p = &FIRST_PROC; p<= &LAST_PROC; p++) {
if (p->p_flags ==0) {
if (p->ticks > greatest_ticks) {
greatest_ticks= p->ticks;
p_proc_ready= p;
}
}
}
if (!greatest_ticks)
for (p =&FIRST_PROC; p <= &LAST_PROC; p++)
if(p->p_flags == 0)
p->ticks= p->priority;
}
}
