发表于 | 分类于 | 0 | 阅读次数 134

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

partC主要是实现抢占式调度以及允许environment之间传递消息。

Clock Interrupts and Preemption

当运行user/spin测试程序的时候，会如下图所示：

测试程序的代码如下所示：

#include <inc/lib.h>

void
umain(int argc, char **argv)
{
  envid_t env;

  cprintf("I am the parent.  Forking the child...\n");
  if ((env = fork()) == 0) {
    cprintf("I am the child.  Spinning...\n");
    while (1)
      /* do nothing */;
  }

  cprintf("I am the parent.  Running the child...\n");
  sys_yield();
  sys_yield();
  sys_yield();
  sys_yield();
  sys_yield();
  sys_yield();
  sys_yield();
  sys_yield();

  cprintf("I am the parent.  Killing the child...\n");
  sys_env_destroy(env);
}

测试程序将会fork出一个child environment，而这个child environment在它获得CPU的控制权之后，将会永远空转下去，kernel和parnet environment都不会再获得CPU的控制权。假如这样的话，user mode environment通过无限的循环，可以很容易的将整个系统停止并且不再将CPU还给kernel或者其他environment。所以为了解决这种情况，我们需要让kernel可以抢占一个正在运行的environment，强制性重新拿回CPU的控制权。为了实现这个，我们需要让JOS kernel支持来自时钟的硬件中断。

Interrupt discipline

外部的中断被称为IRQs，这里有16个可能的IRQs，编号为0-15。从IRQ number到IDT entry的映射是不固定的。picirq.c中的pic_init将IRQs 0-15映射到IDT entries的IRQ_OFFSET到IRQ_OFFSET+15，同时inc/trap.h中，IRQ_OFFSET被定义为32，所以IDT entries的32-47是跟IRQs 0-15相对应的。举个例子clock interrupt是IRQ 0，那么对应的IDT表的位置就是IRQ_OFFSET+0，所以IDT[IRQ_OFFSET+0]就包含了clock interrupt handler的地址。由于我们IRQ_OFFSET被选择为32，所以设备的中断不会和处理器的异常/中断等冲突。

在早期PC机运行MS-DOS的时候，IRQ_OFFSET是0，这个将会在处理硬件设备中断和处理处理器异常之间造成很大混淆。（设备中断、硬件中断、外部中断这三者概念上差不多，就目前来看的话）

在JOS中，我们相对xv6 Unix做了一个关键的简化。在kernel中外部设备中断是不允许的（这个跟xv6还是一样，都只有在user space的时候才是允许的）。外部中断是由eflags寄存器中FL_IF标志位控制的（inc/mmu.h），当这个位被设置的时候，外部中断是允许的。这个FL_IF通过几种方式修改来修改，但是由于我们的简化，所以我们仅仅在进入或者退出user mode的时候通过保存或者恢复eflags寄存器来修改。

在我们的environments运行的时候，我们需要确保FL_IF标志位已经被设置了，这样子当外部中断来的时候，我们将这个中断交给处理器然后通过相应的interrupt code来处理。但是bootloader的第一条指令把外部中断给屏蔽了，并且到目前为止都没有重新使能它。

start:
 	.code16                     # Assemble for 16-bit mode
	cli                         # Disable interrupts

下面我们修改kern/trapentry.S和kern/trap.c文件来初始化IDT表中合适的entryies，并且给IRQs 0-15提供handler。

跟我们当初给0-31初始化IDT表和设置handler类似，我们首先修改kern/trapentry.S文件的内容，在lab3后面加上以下内容即可

TRAPHANDLER_NOEC(irq_timer_handler, IRQ_OFFSET + IRQ_TIMER)
TRAPHANDLER_NOEC(irq_kbd_handler, IRQ_OFFSET + IRQ_KBD)
TRAPHANDLER_NOEC(irq_serial_handler, IRQ_OFFSET + IRQ_SERIAL)
TRAPHANDLER_NOEC(irq_spurious_handler, IRQ_OFFSET + IRQ_SPURIOUS)
TRAPHANDLER_NOEC(irq_ide_handler, IRQ_OFFSET + IRQ_IDE)
TRAPHANDLER_NOEC(irq_error_handler, IRQ_OFFSET + IRQ_ERROR)

为啥不把0-15加个遍呢？因为inc/trap.h中只提到了以下这些

#define IRQ_OFFSET  32  // IRQ 0 corresponds to int IRQ_OFFSET

// Hardware IRQ numbers. We receive these as (IRQ_OFFSET+IRQ_WHATEVER)
#define IRQ_TIMER        0
#define IRQ_KBD          1
#define IRQ_SERIAL       4
#define IRQ_SPURIOUS     7
#define IRQ_IDE         14
#define IRQ_ERROR       19

之后修改kern/trap.c中的trap_init()函数，添加如下内容：

void trap_init(){
    	......
    // LAB 4: Preemptive Multitasking
    void irq_timer_handler();
    void irq_kbd_handler();
    void irq_serial_handler();
    void irq_spurious_handler();
    void irq_ide_handler();
    void irq_error_handler();
		......
    // LAB 4: Preemptive Multitasking
    SETGATE(idt[IRQ_OFFSET + IRQ_TIMER], 0, GD_KT, irq_timer_handler, 3);
    SETGATE(idt[IRQ_OFFSET + IRQ_KBD], 0, GD_KT, irq_kbd_handler, 3);
    SETGATE(idt[IRQ_OFFSET + IRQ_SERIAL], 0, GD_KT, irq_serial_handler, 3);
    SETGATE(idt[IRQ_OFFSET + IRQ_SPURIOUS], 0, GD_KT, irq_spurious_handler, 3);
    SETGATE(idt[IRQ_OFFSET + IRQ_IDE], 0, GD_KT, irq_ide_handler, 3);
    SETGATE(idt[IRQ_OFFSET + IRQ_ERROR], 0, GD_KT, irq_error_handler, 3);
 		......
}

经过上面的步骤之后，当有收到外部设备中断的时候，有了相应的handler了。下面我们修改kern/env.c的env_alloc()函数来确保user environment运行的时候，外部设备中断是使能了的。

// Enable interrupts while in user mode.
// LAB 4: Your code here.
e->env_tf.tf_eflags |= FL_IF;

同时把sched_halt()中的sti指令前面的注释去掉，这样空闲的CPU将会取消中断屏蔽。

// Reset stack pointer, enable interrupts and then halt.
asm volatile (
    "movl $0, %%ebp\n"
    "movl %0, %%esp\n"
    "pushl $0\n"
    "pushl $0\n"
    // Uncomment the following line after completing exercise 13
    "sti\n"
    "1:\n"
    "hlt\n"
    "jmp 1b\n"
: : "a" (thiscpu->cpu_ts.ts_esp0));

Handling Clock Interrupts

init.c中的i386_init()调用了lapic_init()和pic_init()函数，这些函数已经设置了clock和中断控制器来产生中断。同时上面的实验中也使能了外部设备中断和设置了相应的IDT表，下面我们需要来处理这些中断。

修改kernel的trap_dispatch()函数，当一个clock interrupt发生的时候调用sched_yield()函数让它找到一个不同的environment来运行。

// Handle clock interrupts. Don't forget to acknowledge the
// interrupt using lapic_eoi() before calling the scheduler!
// LAB 4: Your code here.
if(tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER){
    lapic_eoi();
    sched_yield();
}

完成上面的代码之后，是可以成功运行user/spin的了。parent environment fork出一个child，sys_yield()将会把CPU的控制权交给child，但是在一定时间片之后，又会回到parent中。在最终运行完之后会kill child environment。

	......
SMP: CPU 0 found 1 CPU(s)
enabled interrupts: 1 2
[00000000] new env 00001000
I am the parent.  Forking the child...
[00001000] new env 00001001
I am the parent.  Running the child...
I am the child.  Spinning...
I am the parent.  Killing the child...
[00001000] destroying 00001001
[00001000] free env 00001001
[00001000] exiting gracefully
[00001000] free env 00001000
No runnable environments in the system!
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K>

当我们运行stresssched的时候，也会通过，输出的效果如下所示

[00000000] new env 00001000
[00001000] new env 00001001
[00001000] new env 00001002
[00001000] new env 00001003
[00001000] new env 00001004
	......
[00001001] free env 00001001
[00001002] stresssched on CPU 0
[00001002] exiting gracefully
[00001002] free env 00001002
	......
[00001014] stresssched on CPU 0
[00001014] exiting gracefully
[00001014] free env 00001014
No runnable environments in the system!

Inter-Process communication (IPC)

在JOS上应该叫做 "inter-environment communication" 或者"IEC"，但是其他人都称它为IPC，所以我们使用IPC这个术语。

我们一直关注操作系统隔离的方面，这种方式给每一个程序造成了它们都有属于自己的一台机器的假象。而另一个重要的服务是允许程序之间可以通信，这是相当强大的。Unix的pipe模型就是一个典型的例子。现在有很多进程间通信的模式，但是我们选择一个简单的IPC机制来实现，并让它工作起来。

IPC in JOS

我们将会实现一些JOS kernel system call，这些system calls共同合作提供了一个简单的进程之间通信的机制。我们将会实现两个system callssys_ipc_recv 和sys_ipc_try_send，之后我们还要实现两个library的封装 ipc_recv 和ipc_send.

使用JOS的IPC机制，可以传给其他environment的“messages”由以下两部分组成：

  • 一个32-bit的值
  • 一个可选的页映射

允许environment在消息中传递页映射是一种很有效的方式，它可以传递比一个32bit的整型数据更合适的数据，并且这样允许了environment设置共享内存区。

Sending and Receiving Messages

一个environment使用sys_ipc_recv来获取消息。这个system call将不会调度当前的environment并且不会重新运行它，直到它收到一个message。当一个environment在等待收到消息的时候，任何一个environment可以向它发送消息。同样的，PartA实现的权限检查将不再适合IPC，因为IPC system call是需要很安全的，通过发送消息一个environment不能很容易造成另一个environment崩溃的（除非目标environment本身就buggy）。

一个environment使用sys_ipc_try_send来发送一个消息。 如果被指定的environment正在等待接收的（目标environment 调用了 sys_ipc_recv，但是还没有得到一个值），那么将会发送这个值然后返回0，否则将会返回-E_IPC_NOT_RECV表示指定的environment当前不希望收到一个值。

在user space的library函数ipc_recv将会调用sys_ipc_recv ，之后会在environment的struct Env寻找收到的值的相关信息。ipc_send将会反复调用sys_ipc_try_send直到发送成功。

Transferring Pages

当一个environment调用sys_ipc_recv之后，这个environment就开始等待收到一个页映射了。如果发送方发送了一个page，那么这page将会被映射到接受者地址空间的dstva处（dstva需要在UTOP下面）。如果在dstva已经有映射了，那么将取消前面的映射。

如果一个environment调用sys_ipc_try_send，那么意味发送方想把映射在srcva（在UTOP下面）的页发送过去，并且将页的权限设置为perm。

在一个成功的IPC之后，发送方将原始页的映射保留在地址空间的srcva处，同时接收方在接收方的地址空间的dstva也获得相同物理页的映射，那么最终这个传递的页在接收方和发送方之间变成了共享的。如果发送方和接受方都没有表明要传输一个page，那么就不传输页了。在任何IPC之后，kernel将接收方的Env结构体中的env_ipc_perm设置成接受到的页权限，如果是0那么表示没有页被接受到。

Implementing IPC

实现kern/syscall.c中sys_ipc_recv()和sys_ipc_try_send这两个system call，根据注释的提示内容来实现。同时在实现过程envid2env()的checkperm参数设置为0，这表示任何environment都可以给其他environment传递IPC messages，kernel仅仅检查target envid是不是有效的。

首先实现sys_ipc_recv()system call，根据提示首先是检查dstva，假如dstva小于UTOP的话那么就必须要对齐。之后设置env为not runnable，recving设置为true，目标地址设置为dstva，message来的envid设置为0，最后通过调度算法放弃CPU。

static int
sys_ipc_recv(void *dstva)
{
  // LAB 4: Your code here.
  struct Env *env = curenv;

  if(dstva < (void *)UTOP && PGOFF(dstva)){
    return -E_INVAL;
  }

  env->env_status = ENV_NOT_RUNNABLE;
  env->env_ipc_recving = true;
  env->env_ipc_dstva = dstva;
  env->env_ipc_from = 0;
  sys_yield();

  return 0;
}

接下去实现sys_ipc_try_send()system call，这部分我们需要明白的两个重要的点是：

  1. 进程间的通信，其实是修改目标env的相关信息来实现的；
  2. sys_ipc_try_send()这个system call其实是传递value或者传递一个页，只是页是可选的，value是必须的。所以不管怎么样对于target value的赋值肯定是有的，但是page的传递是需要判断的，那么如何判断这个page是不是需要的呢，其实根据srcva这个值来判断，假如这个值大于等于UTOP，那么只剩下传递value了，而不传递页了。所以我们会发现大部分的检查都是在srcva小于UTOP的基础之上的，假如不满足小于UTOP这个条件，那么所有的if判断都不会成立，那么自然就只剩下传递value这个值了。

之后为什么env->env_tf.tf_regs.reg_eax = 0;因为在接受者返回之前执行的地方之后，需要返回0值才表示接受到消息了。

static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
  // LAB 4: Your code here.
  struct Env *env;
  struct PageInfo *pp;
  int re;
  pte_t *entry;

  // if environment envid doesn't currently exist(no need to check permissions)
  if((re = envid2env(envid, &env, 0)) < 0){
    return re;
  }

  if(!env->env_ipc_recving || env->env_ipc_from){
    return -E_IPC_NOT_RECV;
  }

  if(srcva < (void *)UTOP){
    if(PGOFF(srcva)){
      return -E_INVAL;
    }

    if(((perm & (PTE_U | PTE_P)) != (PTE_U|PTE_P)) || (perm & ~PTE_SYSCALL)){
      return -E_INVAL;
    }

    if(!(pp = page_lookup(curenv->env_pgdir, srcva, &entry))){
      return -E_INVAL;
    }

    if((perm & PTE_W) && !(*entry & PTE_W)){
      return -E_INVAL;
    }
    if(env->env_ipc_dstva){
      if((re = page_insert(env->env_pgdir, pp, env->env_ipc_dstva, perm)) < 0){
        return re;
      }
      env->env_ipc_perm = perm;
    }
  }

  // set the target env
  env->env_ipc_recving = 0;
  env->env_ipc_from = sys_getenvid();
  env->env_ipc_value = value;
  env->env_status = ENV_RUNNABLE;
  env->env_tf.tf_regs.reg_eax = 0;
    
  return 0;
}

最后我们实现lib/ipc.c中的ipc_recv()和ipc_send()这两个库函数。ipc_recv()这个函数，主要是负责调用sys_ipc_recv系统调用以及将接受到的值存在。其中pg可能为NULL，那么表示不传递页，但是直接把这个值当参数传进去的，因为NULL的值是0，0还是一个有效的还是会传递页，根据我们上面的分析，要想不想传递页，需要给一个大于等于UTOP的值，所以在pg为NULL的时候，我们将pg设置为UTOP。

int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
  // LAB 4: Your code here.
  int re;
  int env_from;
  int env_perm;
   
  if(pg == NULL){
    pg = (void *)UTOP;
  } 
  
  if(!(re = sys_ipc_recv(pg))){
    env_from = thisenv->env_ipc_from;
    env_perm = thisenv->env_ipc_perm;
    re = thisenv->env_ipc_value;
  }else{
    env_from = 0;
    env_perm = 0; 
  }
  
  if(from_env_store){
    *from_env_store = env_from;
  }
  if(perm_store){
    *perm_store = env_perm;
  }
 
  return re;
}

ipec_send()这个函数，则负责调用sys_ipc_try_send()发送消息直至发送成功，也就是返回值为0的时候。提示中说到当返回值为-E_IPC_NOT_RECV的时候不用panic，而这个返回值表示要接受message的target environment可能还没有处在接受message 状态或者其他environment正在给target发送message，那么也就意味着当前这个进程消息一直没有发送成功，所以需要一直执行发送这个操作，为了对CPU更友好一点，我们使用了sys_yield()，这个函数将会把调度其他的进程，之后当当前这个进程又被调度之后，那么会继续执行发送操作。一旦发送成功之后，那么则退出。

void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
  // LAB 4: Your code here.
  int re;

  if(pg == NULL){
    pg = (void *)UTOP;
  }
  while(1){
    re = sys_ipc_try_send(to_env, val, pg, perm);
    if(re == -E_IPC_NOT_RECV){
      sys_yield();
    }else if(re == 0){
      break;
    }else{
      panic("ipc_send: %e", re);
    }
  }
}

最后的最后，我们使用make grade来测试一下实验的效果如何

卷死我
  • 本文作者： dawnguo
  • 本文链接： /archives/55
  • 版权声明： 本博客所有文章除特别声明外，均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处！
0%