这一篇博客中,我将完成PA1的收尾部分，我将完成完成对表达式求值的功能拓展，和程序监视点的实现，预计要花费较多的时间。可能很多内容也需要好好学习理解一下。

PA1 监视点

扩展表达式求值的功能

之前我们实现了算数表达式基本的求值（对整数的基本四则运算与结合律），但这些表达式都是常数组成的，他们的值不会发生变化，导致这样的表达式在监视点中没有任何意义，所以我们需要为我们的表达式拓展以下功能：

1
2
3
4
5
6
7
8
9
10
11
12

<expr> ::= <decimal-number>
  | <hexadecimal-number>    # 以"0x"开头
  | <reg_name>              # 以"$"开头
  | "(" <expr> ")"
  | <expr> "+" <expr>
  | <expr> "-" <expr>
  | <expr> "*" <expr>
  | <expr> "/" <expr>
  | <expr> "==" <expr>
  | <expr> "!=" <expr>
  | <expr> "&&" <expr>
  | "*" <expr>              # 指针解引用

那么首先我们就需要向框架中添加对应的解析，即更新程序的正则匹配逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

enum {
  TK_NOTYPE = 256, 
  TK_EQ, TK_NEQ, TK_AND,
  TK_HEX, TK_NUM, TK_REG,
};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {
  {" +", TK_NOTYPE},                // spaces
  {"==", TK_EQ},                    // equal
  {"!=", TK_NEQ},                   // unequal
  {"&&", TK_AND},                   // and
  {"\\+", '+'},                     // plus
  {"-", '-'},                       // minus
  {"\\*", '*'},                     // multi
  {"/", '/'},                       // div
  {"\\(", '('},                     // left brace
  {"\\)", ')'},                     // right brace
  {"0[xX][0-9a-fA-F]+", TK_HEX},    // hex number
  {"[0-9]+", TK_NUM},               // number
  {"\\$(zero|ra|sp|gp|tp|t[0-6]|s[0-9]|s1[0-1]|a[0-7])", TK_REG},   // reg
};

这里需要注意两个问题：

• 一是 对于reg值得获取，框架代码在/src/isa/$ISA/reg.c中提供了isa_reg_str2val()作为接口，它将返回名字为s的寄存器的值，且设置success用于指示是否匹配成功。

• 二是 我们需要注意到对指针解引用的识别，对于符号*它可能是乘号，也可能是对地址的解引用。实际上我们可以通过看其前一个标识的类型，我们就可以判断它的用法，所以可以给出框架代码如下:

  1 2 3 4 5 6 7 8 9 10 11 12 13

  if (!make_token(e)) { *success = false; return 0; } /* TODO: Implement code to evaluate the expression. */ for (i = 0; i < nr_token; i ++) { // certain type 视具体情况而定 if (tokens[i].type == '*' && (i == 0 || tokens[i - 1].type == certain type) ) { tokens[i].type = DEREF; } } return eval(?, ?);

现在我们开始进一步的拓展我们的表达式的能力：

寄存器接口完善

我们需要根据$后的寄存器名，来获取对应的寄存器的值，并设置success:

1
2
3
4
5
6
7
8
9

word_t isa_reg_str2val(const char *s, bool *success) {
  *success = true;
  if(!strcmp(s,"zero")) return 0;
  for(int i=0;i<32;i++){
    if(!strcmp(s,regs[i])) return cpu.gpr[i];
  }
  *success = false;
  return -1;
}

当发现寄存器返回值为-1时，则说明寄存器名称错误，我们要停止计算

表达式计算拓展

我们添加的功能有十六进制数的解析、寄存器的解析、还有部分简单逻辑运算的解析，我们依次分析，需要在哪些地方添加哪些功能：

首先是token的解析存储阶段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

switch (rules[i].token_type) {
          case TK_HEX:
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[nr_token].str[j] = substr_start[j];
            tokens[nr_token].str[substr_len]='\0';
            break;
          case TK_NUM:  
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[nr_token].str[j] = substr_start[j];
            tokens[nr_token].str[substr_len]='\0';
            break;
          case TK_REG:
            tokens[nr_token].type = rules[i].token_type;
            for(int j=0;j<substr_len-1;j++)
              tokens[nr_token].str[j] = substr_start[j+1];
            tokens[nr_token].str[substr_len-1]='\0';
            break;
        ...
}

我们添加了对十六进制标识符和寄存器的存储。

同时我们也要注意在eval()，由于我们引入了十六进制和寄存器进入表达式解析中，所以对于最小的子表达式

1
2
3

<expr> ::= <decimal-number>
  | <hexadecimal-number>   
  | <reg_name>      

我们的解析应该展开为：

1
2
3
4
5
6
7
8
9
10
11
12

...
else if(start==end){
    if(tokens[start].type==TK_REG){
      bool success = false;
      word_t val = isa_reg_str2val(tokens[start].str,&success);
      if(success) return val;
      printf("Invalid register name: %s\n", tokens[start].str);
      return -1;
    }
    return strtol(tokens[start].str,NULL,0);
}
...

由于我们添加了逻辑表达式，所以我们还需要更新其对表达式的拆分和运算，首先是运算部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

...
else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case TK_EQ: return (val1==val2);
      case TK_NEQ: return (val1!=val2);
      case TK_AND: return (val1&&val2);
      case '+': return val1+val2;
      case '-': return val1-val2; 
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
...

与之而来的问题是，在引入逻辑表达式之后，我们该怎么拆分我们的表达式呢？我们知道对于目前已有的运算符，我们有* / > + - >逻辑运算的优先级关系，所以我们可以根据上一节中的规则来更新我们的主运算符号的选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

static int get_token(int start, int end){
  int token = -1;
  int par = 0;
  int min_priority = -1;
  for(int i=start;i<=end;i++){
    int tmp=tokens[i].type;
    if(tmp==TK_NUM) continue;
    if(tmp=='(') par++;
    else if(tmp==')'){
      par--;
      if(par<0) return -1;
    }
    if(par!=0) continue;
    switch (tmp){
    case TK_EQ: case TK_NEQ: case TK_AND:
      if(min_priority<=3){
        min_priority=3;
        token=i;
      }
      break;
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
  }
  if(token != -1){
    // Log("Main operator: %c at position %d\n", tokens[token].type, token);
  } else {
    printf("No operator found in range [%d, %d]\n", start, end);
  }
  return token;
}

至此，我们就完成了对于运算符的解析和拓展。

解引用分析

最后我们还需要解决的一个问题就是对于指针的解引用，我们根据框架代码，对负号和解引用的标识符进行替换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  for(int i=0;i<nr_token;i++){
    if((tokens[i].type=='*'||tokens[i].type=='-')&&
        (i==0||
        tokens[i-1].type=='+'||
        tokens[i-1].type=='-'||
        tokens[i-1].type=='*'||
        tokens[i-1].type=='/'||
        tokens[i-1].type=='('||
        tokens[i-1].type==TK_AND||
        tokens[i-1].type==TK_EQ||
        tokens[i-1].type==TK_NEQ)
      ){
        if(tokens[i].type == '*') tokens[i].type = DEREF;
        else tokens[i].type = NEGATIVE;
    }
  }
  word_t val = eval(0,nr_token-1);
  *success = (val!=-1);
  return val;
}

由于他们都是一元运算符，在计算的过程中拥有最高的优先级，所以我们需要更新搜索主运算符的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

...
switch (tmp){
    case DEREF: case NEGATIVE:
      if(min_priority<=0){
        min_priority=0;
        token=i;
      }
      break;
    case TK_EQ: case TK_NEQ: case TK_AND:
      if(min_priority<=3){
        min_priority=3;
        token=i;
      }
      break;
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
...

然后再最终的对表达式的整合中优先处理一元运算符号，再处理二元运算符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

...
else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }

    if(tokens[op].type == DEREF || tokens[op].type == NEGATIVE) {
      word_t val = eval(op+1, end);
      if(val == -1) return -1;
      if(tokens[op].type == DEREF) return vaddr_read(val, 4);
      else return -val;
    }
    
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case TK_EQ: return (val1==val2);
      case TK_NEQ: return (val1!=val2);
      case TK_AND: return (val1&&val2);
      case '+': return val1+val2;
      case '-': return val1-val2; 
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
...

至此我们完成了对表达式运算符的拓展。

实现监视点

监视器允许我们设置监视点，当监视点中的表达式满足时，nemu就将nemu_state设置成NEMU_STOP，此时我们就可以对程序状态进行观察。

不过首先我们需要能够将所有监视点管理组织起来，在框架代码中已经定义好了监视点的结构和监视点池的结构：

1
2
3
4
5
6
7
8
9
10

typedef struct watchpoint {
  int NO;	// 监视器的编号
  struct watchpoint *next;

  /* TODO: Add more members if necessary */

} WP;

static WP wp_pool[NR_WP] = {};
static WP *head = NULL, *free_ = NULL;

我们需要管理两个链表head和free_。head用于存放使用中的监视点结构，free_用于组织空闲的监视点结构，我们可以使用init_wp_pool()函数，对两个链表进行初始化。

为了进一步的管理监视点池，我们需要两个函数：

• WP* new_wp()：用于从空闲的监视点池中选择一个监视点进行使用，同时也要对剩余监视点的数量进行判断
• void free_wp(WP* wp)： 用于将正在使用中的监视点存回空闲链表中

实现了对监视点池的管理之后，我们就需要实现监视点的相关功能了（以下是需要完成的要求）：

• 当用户给出一个待监视表达式时, 你需要通过new_wp()申请一个空闲的监视点结构, 并将表达式记录下来. 然后在trace_and_difftest()函数(在nemu/src/cpu/cpu-exec.c中定义)的最后扫描所有的监视点, 每当cpu_exec()的循环执行完一条指令, 都会调用一次trace_and_difftest()函数. 在扫描监视点的过程中, 你需要对监视点的相应表达式进行求值(你之前已经实现表达式求值的功能了), 并比较它们的值有没有发生变化, 若发生了变化, 程序就因触发了监视点而暂停下来, 你需要将nemu_state.state变量设置为NEMU_STOP来达到暂停的效果. 最后输出一句话提示用户触发了监视点, 并返回到sdb_mainloop()循环中等待用户的命令.
• 使用info w命令来打印使用中的监视点信息, 至于要打印什么, 你可以参考GDB中info watchpoints的运行结果.
• 使用d命令来删除监视点, 你只需要释放相应的监视点结构即可.

监视点池的管理

这里我想监视点的结构中添加了一个used属性，用来判断当前监视点是否被启用，据此，我们就可以实现对监视点池中的监视点的使用和空闲的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

WP* new_wp(){
  if(free_==NULL){
    printf("No free watchpoint avilable\n");
    return NULL;
  }
  WP* wp = free_;
  free_ = free_->next;
  wp->used = 1;
  wp->next = head;
  head = wp;
  printf(ANSI_FMT("Create watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
  return wp;
}

void free_wp(WP* wp){
  if(wp==NULL||!wp->used) printf("Invalid watchpoint to free\n");
  if(head==wp){
    head = head->next;
  }else{
    WP* prev = head;
    while(prev!=NULL&&prev->next!=wp) prev = prev->next;
    if(prev!=NULL) prev->next = wp->next;
    wp->used=0;
    wp->next = free_;
    free_ = wp;
    printf(ANSI_FMT("Free watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
  }
}

现在我们需要进一步的完成监视点的功能，以及用于调用的接口

监视点功能实现

监视点的功能实际上就是在每一次执行之后，遍历一遍监视点链表，如果设置的表达式发生了改变，那么我们说监视点被触发了。所以我们要做的事情很简单，遍历计算表达式的值是否发生改变，如果是，则触发监视点：

1
2
3
4
5
6
7
8
9
10
11
12
13

void wp_diff(){
  WP* wp = head;
  while(wp){
    bool _;
    word_t new = expr(wp->expr,&_);
    if(wp->val!=new){
      printf(ANSI_FMT("Watchpoint #%d: %s\n Old value = 0x%08x\n New value = 0x%08x\n",ANSI_FG_BLUE),wp->NO,wp->expr,wp->val,new);
      wp->val = new;
      nemu_state.state = NEMU_STOP;
    }
    wp = wp->next;
  }
}

由于NEMU在每次执行时都会在execute()中调用trace_and_difftest()我们在这个程序中加入每次对监视点的判断wp_diff()

现在我们只需要进一步完成监视点的接口，使得我们可以方便的创建销毁查看他们：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

P* new_wp(){
  if(free_==NULL){
    printf("No free watchpoint avilable\n");
    return NULL;
  }
  WP* wp = free_;
  free_ = free_->next;
  wp->used = 1;
  wp->next = head;
  head = wp;
  return wp;
}

WP* NO2wp(int i){
  return &wp_pool[i];
}

void free_wp(WP* wp){
  if(wp==NULL||!wp->used){printf("Invalid watchpoint to free\n");return;}
  if(head==wp){
    head = head->next;
  }else{
    WP* prev = head;
    while(prev!=NULL&&prev->next!=wp) prev = prev->next;
    if(prev!=NULL) prev->next = wp->next;
    wp->used=0;
    wp->next = free_;
    free_ = wp;
  }
  printf(ANSI_FMT("Free watchpoint #%d\n",ANSI_FG_BLUE),wp->NO);
}

void wp_set(char* expr,word_t val){
  WP* wp = new_wp();
  strcpy(wp->expr,expr);
  wp->val = val;
  printf(ANSI_FMT("Create watchpoint #%d: %s\n",ANSI_FG_BLUE),wp->NO,wp->expr);
}

void wp_display(){
  WP* tmp = head;
  while(tmp!=NULL){
    tmp = tmp->next;
  }
}

我们在终端进行调用，实现info w，d NO，w EXPR等功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static int cmd_w(char* args){
  bool success = false;
  word_t val = expr(args,&success);
  if(!success){
    printf("Invalid expression: %s\n",args);
  }else{
    wp_set(args,val);
  }
  return 0;
}

static int cmd_d(char* args){
  int NO = atoi(args);
  free_wp(NO2wp(NO));
  return 0;
}

void wp_display(){
  WP* tmp = head;
  while(tmp!=NULL){
    printf("Watchpoint #%d -> %s\n",tmp->NO,tmp->expr);
    tmp = tmp->next;
  }
}

至此我们就实现了监视点的功能。

对于断点我们可以通过w $pc=？的方式来让程序停止

我们先前反复提到了一个式子EXPR，它代表着表达式含义，常见的表达式是通过操作符连接的。这里我们需要为我们的框架实现一个表达式求值的功能。我们要解决的问题是求值一个字符串表示的表达式。

PA1 表达式求值

为了简单起见，我们先从数学表达式求值实现开始。

数学表达式求值

如下的一个表达式的字符串：

1

"5 + 4 * 3 / 2 - 1"

我们应该怎么求出它的值？我们可以分成两个简单的步骤：

• 首先识别出表达式中的单元
• 根据表达式的归纳定义进行递归求值

词法分析

词法分析要做的事情就是识别出表达式中的单元，这里的单元指的就是有着独立含义的子串，我们称之为token。具体而言我们需要将表达式中所有的单元都赋予一个标签，方便之后根据标签来对表达式进行处理。这里我们使用正则表达式来对token进行处理。

出于简单起见，这里我们暂时只对以下的token类型进行处理：

• 十进制整数
• +，-，*，/
• (，)
• 空格串（一个或者多个空格）

首先我们需要使用正则表达式来编写用于识别这些token类型的规则，框架中演示了怎么对其进行匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"==", TK_EQ},        // equal
};

这些规则，在init_sdb()时调用了init_regex()来将其编译成正则结构体并存储在re中：

1
2
3
4
5
6
7
8
9
10
11
12

void init_regex() {
  int i;
  char error_msg[128];
  int ret;
  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

如果编译不通过，可能是你编写的token匹配的规则不符合正则表达式的语法。现在，我们可以给出一个待匹配的表达式，我们利用make_token()来识别出其中的token。用position变量指示当前待匹配的位置，然后按顺序对当前位置的字符串进行匹配。当一个规则匹配成功，并且匹配出的字串属于position指出的位置时，我们就成功的识别出了一个token。我们则使用Token结构体来将它的内容记录下来。

1
2
3
4
5
6

typedef struct token {
  int type;
  char str[32];
} Token;
static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

其中type成员用于记录token的类型，然后str用来保存token相应的字串。tokens数组用来保存识别出的token信息，而nr_token则用来指示被识别出的token数目。

现在我们需要向算数表达式中的各种tokens类型添加规则，在成功识别出tokenhi后，将token的信息一次记录到tokens数组之中。

1
2
3
4
5
6
7
8
9
10
11
12

rules[] = {
  // 这里需要注意对这些内容的匹配是有优先顺序的，从上到下
  {" +", TK_NOTYPE},    // spaces
  {"==", TK_EQ},        // equal
  {"\\+", '+'},         // plus
  {"-", '-'},           // minus
  {"\\*", '*'},         // multi
  {"/", '/'},       	// div
  {"\\(", '('},         // left brace
  {"\\)", ')'},         // right brace
  {"[0-9]+", TK_NUM},   // number
};

然后我们就需要将匹配到的token放入tokens中，并对它的各个字段进行赋值。对于大多数类型，我们只需要简单的保存它的类型就行了，但是对于有数据内容的token，我们需要保存它的data，在这里既是保存它的子串内容信息，方便我们进行进一步的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

static bool make_token(char *e) {
  int position = 0;
  int i;
  int index=0;
  regmatch_t pmatch;
  nr_token = 0;
  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;
        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);
        position += substr_len;
        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        switch (rules[i].token_type) {
          case TK_NUM:  
            tokens[index].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[index].str[j] = substr_start[j];
            // printf("The num is %s\n",tokens[index].str);
            break;
          default:
            tokens[index].type = rules[i].token_type;
        }
        index++;
        break;
      }
    }
    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }
  return true;
}

我们可以看到整个识别token的过程，每当我们获取一个token时，我们都会使用Log()将它的匹配规则，子串下标，子串长度，和对应的子串信息打印出来。便于我们观察标识符匹配的中间过程。对于未匹配到的类型，我们也会将其内容进行返回。

中间部分则是我们对token信息的存储过程，目前我们只对十进制整数的内容进行了保存，对于其他的标识符号，则是简单的保存类型。现在我们可以进一步的进行表达式求值了。

递归求值

我们现在将求值表达式的token识别出来之后就可以进行求值了。我们现在是对token数组进行处理，方便起见，我们称其为token表达式。（将空格忽略）

接下来，根据表达式的归纳定义特性，我们可以使用递归来进行求值：

1
2
3
4
5
6

<expr> ::= <number>    # 一个数是表达式
  | "(" <expr> ")"     # 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>  # 两个表达式相加也是表达式
  | <expr> "-" <expr>  # 接下来你全懂了
  | <expr> "*" <expr>
  | <expr> "/" <expr>

这种表示方法就是我们常说的BNF，我们可以这里理解，长表达式是由短表达式构成的，那么我们可以先对短表达式进行求值，然后再进一步的对长表达式进行求值。

为了在token表达式中指示一个子表达式，我么可以使用两个整数p和q来指示子表达式的开始和结束位置，现在我们就可以写出一个求值函数的框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    /* We should do more things here. */
  }
}

其中check_parentheses()用于判断表达式是否被一堆匹配的括号所包围，同时检查表达式左右的括号是否匹配，如果不匹配，那么这个表达式就是非法的。我们以此来尝试实现：

1
2
3
4
5
6
7
8
9
10
11
12
13

static int check_parentheses(int start, int end){
  int cond=0;
  if(tokens[start].type!='('||tokens[end].type!=')') return 0;
  for(int i=start;i<=end;i++){
    if(tokens[i].type=='(') cond++;
    if(tokens[i].type==')'){
      cond--;
      if(cond<0) return -1;
    }
    if(cond==0) return (i == end) ? 1 : 0;
  }
  return (cond==0)?1:-1;
}

现在我们的框架代码，已经可以处理BNF的开始两种情况啦。像现在我们需要进一步的考虑剩下的情况，即四则运算的处理。但是问题在于，我们怎么对一个长表达式处理，将其分解为各个小的短表达式，并保证语法的正确呢？

我们以下为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

"4 + 3 * ( 2 - 1 )"
/*********************/
case 1:
    "+"
   /   \
"4"     "3 * ( 2 - 1 )"
case 2:
        "*"
       /   \
"4 + 3"     "( 2 - 1 )"
case 3:
              "-"
             /   \
"4 + 3 * ( 2"     "1 )"

我们可以看到只有第一种情况是正确的，第二种情况违背了算术符号的优先级，而第三种情况则使得表达式的括号不再匹配。通过以上的例子，我们就可以总结出寻找主运算符（可以将一个长表达式分解成两个短表达式的运算符号）的逻辑了：

• 非运算符的token不是主运算符
• 出现在一对括号中的token不是主运算符号
• 主运算符的优先级在表达式中应该是最低的
• 有多个运算符的优先级最低时，根据结合性，最后被结合的运算符为主运算符号

现在我们根据以上规则来扫描出每个表达式中的主运算符号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

static int get_token(int start, int end){
  int token = -1;
  int par = 0;
  int min_priority = -1;
  for(int i=start;i<=end;i++){
    int tmp=tokens[i].type;
    if(tmp==TK_NUM) continue;
    if(tmp=='(') par++;
    else if(tmp==')'){
      par--;
      if(par<0) return -1;
    }
    if(par!=0) continue;
    switch (tmp){
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
  }
  if(token != -1){
    // Log("Main operator: %c at position %d\n", tokens[token].type, token);
  } else {
    printf("No operator found in range [%d, %d]\n", start, end);
  }
  return token;
}

找到表达式的主运算符之后，事情就变得简单了，我们先对两个分裂出来的子表达式进行递归求值，然后根据主运算符号的两个子表达式进行计算即可，现在我们的框架代码更新如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    op = the position of 主运算符 in the token expression;
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);

    switch (op_type) {
      case '+': return val1 + val2;
      case '-': /* ... */
      case '*': /* ... */
      case '/': /* ... */
      default: assert(0);
    }
  }
}

现在，我们需要利用现有的规则和函数来填补实现我们的求值函数eval():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

static int eval(int start, int end){
  if(start>end){
    printf("Unknown expression.\n");
    return -1;
  }else if(start==end){
    return atoi(tokens[start].str);
  }else if(check_parentheses(start,end)==1){
    return eval(start+1,end-1);
  }else if(check_parentheses(start,end)==-1){
    printf("parenthese mismatch error\n");
    return -1;
  }else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case '+': return val1+val2;
      case '-': return val1-val2;
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
}

经过测试，基本可以处理大多数情况了。我们现在可以将其封装在expr()中，然后实现p方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  word_t val = eval(0,nr_token-1);
  *success = (val!=-1);
  return val;
}

static int cmd_p(char* args){
  bool success;
  word_t val=expr(args,&success);
  if(success==true)
    printf("%d\n",val);
  return 0;
}

出于限制，我们只使用uint32_t作为我们的返回类型。

测试代码

按照PA的要求，我们现在应该测试一下我们这个函数，但是我就跳过这一部分了，因为赶时间。

NEME是一个用于执行其他用户程序的虚拟计算机，对于运行在NEMU中的应用程序，外部的调试器难以获取其详细的信息，往往需要对引用程序内部下断点的方法来观察程序运行。

但是对于NEMU而言，应用程序的状态是可见的，因此我们需要一个简单有效的方法来观察并调试应用程序的内部状态，所以我们需要设计简易调试器，作为NEMU的基础设施，方便日后的进一步处理。

PA1 基础设施

我们需要在monitor中实现一个简单的sdb。相关的框架代码存放在src\monitor\sdb中，我们可以在cmd_table中查看目前已有的指令。

1
2
3
4
5
6
7
8
9
10

static struct {
  const char *name;
  const char *description;
  int (*handler) (char *);
} cmd_table [] = {
  { "help", "Display information about all supported commands", cmd_help },
  { "c", "Continue the execution of the program", cmd_c },
  { "q", "Exit NEMU", cmd_q },
  /* TODO: Add more commands */
};

在PA1中我们要实现的功能还有：

今天则从最基本的三个功能开始实现：

• 单步执行
• 打印寄存器状态
• 扫描内存状态

解析命令

NEMU通过库对命令行输入进行处理。我们可以在函数rl_gets()中看到对readline()函数的包装。然后在sdb_mainloop()中通过调用其获取，命令行内容。后续对获取的命令行内容进行解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for (char *str; (str = rl_gets()) != NULL; ) {
    char *str_end = str + strlen(str);

    /* extract the first token as the command */
    char *cmd = strtok(str, " ");
    if (cmd == NULL) { continue; }

    /* treat the remaining string as the arguments,
     * which may need further parsing
     */
    char *args = cmd + strlen(cmd) + 1;
    if (args >= str_end) {
      args = NULL;
}

这里程序将命令行内容解析为命令cmd和命令行参数args，我们接受cmd和args的指针，然后根据cmd调用对应的指令。不过这里需要注意。对于多参数的指令，我们需要对args进行额外的处理。

单步执行

现在我们开始进行单步执行的操作，首先我们需要向cmd_table中添加我们的指令和对应的处理函数：

1

{ "si", "si [N]", cmd_si},

然后对于si的执行逻辑我们写在处理函数cmd_si中。

对于单步执行的实现，我们希望CPU一次只执行一条指令，我们自然会想到先前的负责CPU执行的函数cpu_exec()，我们可以参考c/continue的实现来完成。

1
2
3
4
5
6
7
8
9

static int cmd_si(char *args) {
  if(args==NULL){
    cpu_exec(1);
    return 0;
  }
  int step = strtol(args,NULL,0);
  cpu_exec(step);
  return 0;
}

当使用si是默认步进一条指令，当给出指定参数时，不仅指定的步数。

显示寄存器

寄存器和ISA架构是相关的，所以框架中为我们在src/isa/$ISA/reg.c中设置了相应的接口isa_regs_display()，我们只需要完善这个接口。然后在处理函数中调用它就好了。

我们先向cmd_tale中添加对应的功能:

1

{ "info", "info [r/w]", cmd_info},

使用cmd_info()作为命令的处理函数。

1
2
3
4
5
6
7
8
9

static int cmd_info(char* args){
  if(strncmp(args,"r\0",1)){
    printf("Unknown arguments '%s'\n",args);
    return 0;
  }else{
    isa_reg_display();
    return 0;
  }
}

由于之后还要拓展所以需要对info的参数进行匹配。这里我们调用了框架提供的接口进行使用isa_regs_display():

1
2
3
4
5
6
7
8

void isa_reg_display() {
  for(int i=0;i<32;i+=4){
    printf("[%s]\t0x%08x |\t",regs[i],cpu.gpr[i]);
    printf("[%s]\t0x%08x |\t",regs[i+1],cpu.gpr[i+1]);
    printf("[%s]\t0x%08x |\t",regs[i+2],cpu.gpr[i+2]);
    printf("[%s]\t0x%08x\n",regs[i+3],cpu.gpr[i+3]);
  }
}

我们通过对应的格式打印cpu结构中的通用寄存器的值即可。

扫描内存

由于我们还没有实现对表达式的求值和解析，所以在指定内存时，我们暂时只支持十六进制。至于扫描内存，我们只需要从指定的位置起始，使用内存接口打印指定长度的字节即可。我们可以在src\memory\vaddr.c中找到我们可使用的接口。

由于我们的应用程序是运行在虚拟空间中的，所以我们使用的是虚拟内存读取vaddr_read()。现在我们可以尝试开始实现这个功能，首先我们需要向cmd_table()，添加功能函数：

1

{ "x", "x [N] EXPR", cmd_x}

由于这一部分我们需要使用两个参数，所以我们还需要对args进行预处理，用于为内存扫描提供参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

char* arg1=strtok(args, " ");
if(arg1==NULL){
  printf("No argument1 , the format 'x [N] EXPR'\n");
  return 0;
}else{
  len = strtol(arg1,NULL,0);
}
char* arg2=strtok(NULL, " ");
if(arg2==NULL){
  printf("No argument2 , the format 'x [N] EXPR'\n");
  return 0;
}else{
  addr = strtol(arg2,NULL,0);
}

这里我们使用strtol来划分参数，然后使用strtol将参数转换为对应的数值，作为接口的参数，然后我们就可以通过访问接口，遍历打印指定位置的内存数数据了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

static int cmd_x(char* args){
  int len;
  int addr;
  char* arg1=strtok(args, " ");
  if(arg1==NULL){
    printf("No argument1 , the format 'x [N] EXPR'\n");
    return 0;
  }else{
    len = strtol(arg1,NULL,0);
  }
  char* arg2=strtok(NULL, " ");
  if(arg2==NULL){
    printf("No argument2 , the format 'x [N] EXPR'\n");
    return 0;
  }else{
    addr = strtol(arg2,NULL,0);
  }
  for(int i=0;i<len;){
    printf(ANSI_FMT("0x%08x:  ",ANSI_FG_BLUE),addr);
    for(int j=0;i<len&&j<4;i++,j++){
      uint32_t data = vaddr_read(addr, 4);
      printf("0x%08x  ",data);
      addr += 4;	
    }
    printf("\n");
  }
  return 0;
} 

至此，我们就完成了PA1中的基础设施。

这个月发生了各种各样的事情，我特别累也特别疲惫。对于上次以后的总结，我几乎记不得中间都做了哪些事情。我不想对这一个月的经历过多谈论，我心里是十分难过的。

接下来一段时间会很忙，忙在哪些地方呢？

• NJU PA实验，我要坚持写下去
• 操作系统真象还原，我也要坚持看下去，我希望能通过这本书的指引，实现一个自己的操作系统。之后我想仿写xv6的源代码，实现一个基本的操作系统内核。
• 最近新接的科研训练项目，主题是基于动态欺骗的主动网络防护技术，现在还在写文档阶段，非常无聊和痛苦
• 这个学期冗杂的课程，还有各种活动

直白的说，我这个月是感情失利了。我和在一起四年的一个女生分开了。感觉就是很难过，不知道怎么用语言描述，我一开始天天躺着，天天打游戏来麻痹自己，但是感觉都没什么用。我不知道怎么办，我想各种办法去转移自己的注意力，但是无论做什么都没办法集中自己，这几天睡得也很晚，总之就是精神状态很差。

但是我也不该，也不愿意一直这么下去，我找各种各样得事情给自己，不知不觉就这么多事情了。现在已经过去了大半个月了，不想刚开始一样一想到就会好难过，但是偶尔还是会难过。我觉得生活还得继续，不能一直自暴自弃，继续走下去，也许我会遇到更好的女生，也许我会以更好的状态遇见她。我这么想着，慢慢开始忙碌起来，身体还是很疲惫，依然需要时间去习惯与适应。

可能十月份会非常忙吧，各种各样的事情，所以国庆也不能闲着，要抓紧时间。可能这个学期能玩游戏的时间会越来越少，但还是要坚持住。这也是我第一次参加科研训练，我对科研学习的过程也一直很感兴趣，我想好好体验一下这个过程。

还有PA实验和操作系统，本来操作系统是想跟着JYY老师的课程学习的，现在看来是没什么时间了。还要概率论、离散数学、密码学应用基础，这些课基本还没听过，也不知道怎么办。这个学期的408课程也是牢的没边，也不知道怎么办。

这么看了这个学期还真是坎坷，和我暑假时预想的一点也不一样。当然我也没想到会和她分手QAQ，不过现在她还是愿意陪我聊天的，说不定以后还有机会。事到如今只能，继续坚持下去。希望以后会越来越好，也希望我能在这段时间里慢慢获得成长。

PA1 RTFSC

框架代码

由于NEMU-PA是一个很庞大的框架系统，所以要在其基础之上开发需要对框架代码进行熟悉。所以最重要的一步应该是阅读程序的源代码。在课件中，已经给出了相关代码的简要结构说明，按照标题简单理解即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

nemu
├── configs                    # 预先提供的一些配置文件
├── include                    # 存放全局使用的头文件
│   ├── common.h               # 公用的头文件
│   ├── config                 # 配置系统生成的头文件, 用于维护配置选项更新的时间戳
│   ├── cpu
│   │   ├── cpu.h
│   │   ├── decode.h           # 译码相关
│   │   ├── difftest.h
│   │   └── ifetch.h           # 取指相关
│   ├── debug.h                # 一些方便调试用的宏
│   ├── device                 # 设备相关
│   ├── difftest-def.h
│   ├── generated
│   │   └── autoconf.h         # 配置系统生成的头文件, 用于根据配置信息定义相关的宏
│   ├── isa.h                  # ISA相关
│   ├── macro.h                # 一些方便的宏定义
│   ├── memory                 # 访问内存相关
│   └── utils.h
├── Kconfig                    # 配置信息管理的规则
├── Makefile                   # Makefile构建脚本
├── README.md
├── resource                   # 一些辅助资源
├── scripts                    # Makefile构建脚本
│   ├── build.mk
│   ├── config.mk
│   ├── git.mk                 # git版本控制相关
│   └── native.mk
├── src                        # 源文件
│   ├── cpu
│   │   └── cpu-exec.c         # 指令执行的主循环
│   ├── device                 # 设备相关
│   ├── engine
│   │   └── interpreter        # 解释器的实现
│   ├── filelist.mk
│   ├── isa                    # ISA相关的实现
│   │   ├── mips32
│   │   ├── riscv32
│   │   ├── riscv64
│   │   └── x86
│   ├── memory                 # 内存访问的实现
│   ├── monitor
│   │   ├── monitor.c
│   │   └── sdb                # 简易调试器
│   │       ├── expr.c         # 表达式求值的实现
│   │       ├── sdb.c          # 简易调试器的命令处理
│   │       └── watchpoint.c   # 监视点的实现
│   ├── nemu-main.c            # 你知道的...
│   └── utils                  # 一些公共的功能
│       ├── log.c              # 日志文件相关
│       ├── rand.c
│       ├── state.c
│       └── timer.c
└── tools                      # 一些工具
    ├── fixdep                 # 依赖修复, 配合配置系统进行使用
    ├── gen-expr
    ├── kconfig                # 配置系统
    ├── kvm-diff
    ├── qemu-diff
    └── spike-diff

为了支持不同的ISA形式。框架代码将NEMU分成两部分：ISA的相关实现和ISA无关的框架代码。其中不同的ISA被存放在src/isa目录下，用于提供接口，其余部分框架则是相同的实现。这里我们选择RISCV作为我们的ISA，现在我们就可以对整个框架代码进行分析了。

配置系统和项目构建

系统的主要配置文件存放在主目录下的Kconfig文件中，当我们运行make memuconfig时，会弹出一个可视化的编辑界面，程序会将我们的选择对应的添加到include\generate\autoconf.h中，用于编译时设置。从而实现对框架代码的简易配置。

对于更复杂的过程，涉及到makefile的编写，这里暂时忽略。

准备第一个客户应用

NEMU作为一个模拟的计算机系统，主要的功能就是运行客户程序。我们可以从头观察NEMU的项目框架，来查看，NEMU是怎么进行初始化，并且将客户应用加载到内存中运行的。

首先是进入nemu-main.c中，可以看到形如CONFIG_XX的宏定义字样，我们可以在autoconf.h中找到相关的宏定义，根据部分宏的配置，可能会编译时忽略或是开启部分功能。

NEMU的框架代码主要通过函数进行包装，进入nemu-main.c中，首先执行的是init_moniter(),步进程序可以看到monitor的初始化过程，对于mem和seed都是简单的设置，可以之间看源代码

其中init_isa()的代码比较特殊，也比较关键：

1
2
3
4
5
6
7
8
9
10
11
12
13

static void restart() {
  /* Set the initial program counter. */
  cpu.pc = RESET_VECTOR;

  /* The zero register is always 0. */
  cpu.gpr[0] = 0;
}
void init_isa() {
  /* Load built-in image. */
  memcpy(guest_to_host(RESET_VECTOR), img, sizeof(img));
  /* Initialize this virtual computer system. */
  restart();
}

程序首先将img（这里是初始程序，加载到主机的起始地址），具体的内容可以在isa\risc32\init.c中查看看，restart()的作用是将CPU复位成初始状态，这里主要是将pc置0，并将riscv的第一个寄存器设置为0，作为零寄存器。

通过查看memory目录我们可以知道，NEMU为客户计算机提供了128MB的物理内存，同时我们将客户程序读入到内存的固定内存位置RESET_VECTOR。

在这里我们需要分清楚主机和客户机的区别，主机就是运行NEMU的物理计算机，客户机就是在NEMU上运行的计算机程序。我们使用guest_to_host()和host_to_guest()进行主机和客户机地址的相互转换。guest_to_host()将我们在客户机的物理地址转换成在NEMU内存中的数组地址，host_to_guest()则将内存中的数组地址转换成客户机的物理地址。

我们可以在include\memory\paddr.h中找到对RESET_VECTOR的定义，由于这里我们没有设置CONFIG_PC_RESET_OFFSET所以内存的加载从pmem[0]开始。

接着程序调用load_image()用于向内存中加载程序，如果没有给出img参数，则NEMU使用内置的初始化程序，我们可以在isa/risc32/init.c中看到。

然后程序调用welcome(),我们编译运行时看到的信息就是来自这里。

运行第一个客户运用

在monitor完成初始化之后，nemu-main.c会进入下一个程序engine_start中的sdb_mainloop()，并输出提示符指示输入：

1

(nemu)

在src\monitor\sdb\sdb.c中，程序预设了一个cnd_table，设置在sdb中支持的指令：

1
2
3
4
5
6
7
8

cmd_table [] = {
  { "help", "Display information about all supported commands", cmd_help },
  { "c", "Continue the execution of the program", cmd_c },
  { "q", "Exit NEMU", cmd_q },

  /* TODO: Add more commands */

};

对于参数的处理和选择执行可以通过阅读sdb_mainloop理解，这里我们主要将注意力放到cmd_c()的调用函数cpu_exec()上，它是我们模拟器运行程序的cpu执行的核心，这里传入了一个参数-1但由于是uint64_t表示，所以实际上的数值是0xFFFFFFFFFFFFFFFF，即持续执行，这里我们进一步的步入追踪，最终查看到exec_once()，他负责将pc设置成下一条指令执行的位置。

现在NEMU会不断的进行执行，首先它执行的便是我们的内置程序：

1
2
3
4
5
6
7

static const uint32_t img [] = {
  0x00000297,  // auipc t0,0
  0x00028823,  // sb  zero,16(t0)
  0x0102c503,  // lbu a0,16(t0)
  0x00100073,  // ebreak (used as nemu_trap)
  0xdeadbeef,  // some data
};

在NEMU中我们将ebreak的语义设置成，接受a0的数据作为退出状态。同时为了检测客户程序的退出，设置了以下三种状态：

• HIT GOOD TRAP - 客户程序正确地结束执行
• HIT BAD TRAP - 客户程序错误地结束执行
• ABORT - 客户程序意外终止, 并未结束执行

我们在nemu中使用c就可以获得以下输出：

1

nemu: HIT GOOD TRAP at pc = 0x8000000c

即nemu的客户程序在pc = 0x8000000c处成功退出。退出cpu_exec()之后，我们再使用q退出nemu程序。

优美的退出

我们运行NEMU后直接使用q会产生报错：

1
2
3
4
5
6
7
8
9
10
11
12

ylin@Ylin:~/ics2025/nemu$ make run
/home/ylin/ics2025/nemu/build/riscv32-nemu-interpreter --log=/home/ylin/ics2025/nemu/build/nemu-log.txt
[src/utils/log.c:30 init_log] Log is written to /home/ylin/ics2025/nemu/build/nemu-log.txt
[src/memory/paddr.c:50 init_mem] physical memory area [0x80000000, 0x87ffffff]
[src/monitor/monitor.c:51 load_img] No image is given. Use the default build-in image.
[src/monitor/monitor.c:28 welcome] Trace: ON
[src/monitor/monitor.c:29 welcome] If trace is enabled, a log file will be generated to record the trace. This may lead to a large log file. If it is not necessary, you can disable it in menuconfig
[src/monitor/monitor.c:32 welcome] Build time: 20:11:21, Sep 26 2025
Welcome to riscv32-NEMU!
For help, type "help"
(nemu) q
make: *** [/home/ylin/ics2025/nemu/scripts/native.mk:38: run] Error 1

我们需要找出原因并解决这个问题。

这是cmd_q的源代码：

1
2
3

static int cmd_q(char *args) {
  return -1;
}

我们输入q后会因为sdb_mainloop的判断逻辑退出到nemu_main执行is_exit_status_bad():

1
2
3
4
5

int is_exit_status_bad() {
  int good = (nemu_state.state == NEMU_END && nemu_state.halt_ret == 0) ||
    (nemu_state.state == NEMU_QUIT);
  return !good;
}

程序会检测nemu的状态而决定以什么情况退出，我们之前的报错则是因为，我们没有为NEMU设置任何状态，NEMU以默认状态退出，因此返回错误。想要优雅的退出，我们只需要再退出前设置好NEMU的状态。因此我们对cmd_q()函数进行重写

1
2
3
4

static int cmd_q(char *args) {
  nemu_state.state = NEMU_QUIT;
  return -1;
}

这个学期抽取一部分课余时间用来完成NJU的PA实验，争取能做多少做多少。

第一篇先从环境配置开始，这里我使用的程序环境是WSL+Vscode。

PA0 Getting Source Code For PAs

拉取源码

由于我的git环境已经配置好了，所以直接在我的主目录下面clone文件内容就行了：

1

git clone -b 2025 git@github.com:NJU-ProjectN/ics-pa.git ics2025

然后cd ics2025，以后这个目录就是项目的工程目录了。由于我不需要追踪进度，所以就不用提交信息啥的，直接进行初始化就行了：

1
2

git branch -m master
bash init.sh nemu

为了方便子项目的编译，init.sh会向环境变量中添加部分环境变量，这里可以通过

1
2

echo $NEMU_HOME
cd $NEMU_HOME

来验证环境变量是否正确设置，如果没有的话，使用source /.bashrc来激活cd

分支创建

现在我们需要创建一个新的分支，作为pa0的工作分支，之后每个阶段的PA都会单独设置一个分支，再进行合并，我们可以使用git branch来查看现有分支，然后我们：

1
2
3
4
5

❯ git checkout -b pa0
Switched to a new branch 'pa0'
❯ git branch
  master
* pa0

从而创建并跳转到一个新的分支上，然后我们修改一下makefile（因为我们不需要跟踪进度）

编译运行NEMU

通过make menuconfig进行文件的编译：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

ylin@Ylin:~/ics2025/nemu$ make menuconfig
/home/ylin/ics2025/nemu/scripts/config.mk:20: Warning: .config does not exist!
/home/ylin/ics2025/nemu/scripts/config.mk:21: To build the project, first run 'make menuconfig'.
+ CC confdata.c
+ CC expr.c
+ CC preprocess.c
+ CC symbol.c
+ CC util.c
+ YACC build/parser.tab.h
+ LEX build/lexer.lex.c
+ CC build/lexer.lex.c
+ CC build/parser.tab.c
+ CC mconf.c
+ CC lxdialog/inputbox.c
+ CC lxdialog/yesno.c
+ CC lxdialog/textbox.c
+ CC lxdialog/checklist.c
+ CC lxdialog/util.c
+ CC lxdialog/menubox.c
+ LD /home/ylin/ics2025/nemu/tools/kconfig/build/mconf
+ CC confdata.c
+ CC expr.c
+ CC preprocess.c
+ CC symbol.c
+ CC util.c
+ CC build/lexer.lex.c
+ CC build/parser.tab.c
+ CC conf.c
+ LD /home/ylin/ics2025/nemu/tools/kconfig/build/conf
+ CC fixdep.c
+ LD /home/ylin/ics2025/nemu/tools/fixdep/build/fixdep


*** End of the configuration.
*** Execute 'make' to start the build or try 'make help'.

实际上这是再设置make的配置文件，会跳出一个可视化界面，按照自己的需求选择即可，这里我选择了DEBUG的信息。第一次编译的时候有报错，缺少了几个程序，安装即可正常运行。然后make即可。如果编译有误，可以通过make clean删除内容再进行编译。

现在可以通过make run来运行这个项目，可以得到：

1
2
3
4
5
6
7
8
9
10
11
12
13

ylin@Ylin:~/ics2025/nemu$ make run
/home/ylin/ics2025/nemu/build/riscv32-nemu-interpreter --log=/home/ylin/ics2025/nemu/build/nemu-log.txt
[src/utils/log.c:30 init_log] Log is written to /home/ylin/ics2025/nemu/build/nemu-log.txt
[src/memory/paddr.c:50 init_mem] physical memory area [0x80000000, 0x87ffffff]
[src/monitor/monitor.c:51 load_img] No image is given. Use the default build-in image.
[src/monitor/monitor.c:28 welcome] Trace: ON
[src/monitor/monitor.c:29 welcome] If trace is enabled, a log file will be generated to record the trace. This may lead to a large log file. If it is not necessary, you can disable it in menuconfig
[src/monitor/monitor.c:32 welcome] Build time: 20:05:51, Sep 26 2025
Welcome to riscv32-NEMU!
For help, type "help"
[src/monitor/monitor.c:35 welcome] Exercise: Please remove me in the source code and compile NEMU again.
riscv32-nemu-interpreter: src/monitor/monitor.c:36: welcome: Assertion `0' failed.
make: *** [/home/ylin/ics2025/nemu/scripts/native.mk:38: run] Aborted (core dumped)

这里可以看到一段报错riscv32-nemu-interpreter: src/monitor/monitor.c:36: welcome: Assertion0’ failed.`，这个是实验的第一个简单测试，我们到源码处，注释掉指定的错误语句即可：

1
2
3
4
5
6
7
8
9
10
11

static void welcome() {
  Log("Trace: %s", MUXDEF(CONFIG_TRACE, ANSI_FMT("ON", ANSI_FG_GREEN), ANSI_FMT("OFF", ANSI_FG_RED)));
  IFDEF(CONFIG_TRACE, Log("If trace is enabled, a log file will be generated "
        "to record the trace. This may lead to a large log file. "
        "If it is not necessary, you can disable it in menuconfig"));
  Log("Build time: %s, %s", __TIME__, __DATE__);
  printf("Welcome to %s-NEMU!\n", ANSI_FMT(str(__GUEST_ISA__), ANSI_FG_YELLOW ANSI_BG_RED));
  printf("For help, type \"help\"\n");
 // Log("Exercise: Please remove me in the source code and compile NEMU again.");
 // assert(0);
}

这里设置了一个断言，让我们再运行时必定停止在这里。

现在我们可以正常的使用我们的程序了，同时我们也可以使用make gdb来进行对NEMU的调试。

PA1 开天辟地的篇章

计算机的本质就是状态机，从CPU出发，我们可以简单的将CPU的行为总结为

1
2
3
4
5

while (1) {
  从PC指示的存储器位置取出指令;
  执行指令;
  更新PC;
}

我们的计算机实际上是从一个初始状态开始（就是硬件所指定的通电后的复位状态），计算机有一个程序计数器，始终指向下一段要执行的指令地址，当我们从地址取出要执行的指令，当我们对指令进行执行。程序的状态就发生了改变，我们称之为状态的迁移。

所以计算机的一切行为对我们而言都是可溯源的，我们只需要理解状态机的规则，与进行的动作，我们就可以还原任意时刻计算机内存的状态。我们就可以知道每一个动作背后的原理和现象。

PA实验则是通过对NEMU的设计，还原和理解真实计算机的各种功能和实现。所以对于计算机系统的学习是十分有帮助的。希望自己能坚持做下去吧。最近还挺忙的，但还是要加油。

上一篇中我们研究了虚拟内存在理想状态下的工作模式，现在我们要结合实际案例，来进一步了解虚拟内存在具体环境下是怎么工作的：

Intel Core7/Linux内存系统

Core i7地址翻译

我们的系统是一个运行Linux的Intel Core i7。下图是其处理器的一个封装结构：

包括四个核，一个大的所有核共享的L3高速缓存，以及一个DDR3内存控制器。每个核中都有L1L2的高速缓存，还有TLB条目缓存。其中L1、L2、L3高速缓存都是物理寻址的，块大小为64字节。L1和L2是8路组相联，L3是16路组相联。页大小可以在启动时配置为4KB或4MB大小。这里Linux使用的是4KB的页。

下图则展示了Core i7地址翻译的概况：

由于不同层级的页表中存储的条目不同，所以对于第一级、第二级、第三级的条目格式和第四级的条目格式。其地址字段结构略有不同：

对于第一级、第二级、第三级的条目格式。当P=1时（Linux中总是P=1），地址字段包含一个40位的物理页号（PPN），它指向下一级页表的开始处。（注：由于物理页面是4KB对齐的，所以起始地址应该是4096的倍数）：

对于第四级页表中条目的格式。当P=1，地址字段包括一个40位的PPN，指向物理内存中某一页的基地址。同样的，需要4KB对齐：

我们可以看到，PTE有三个权限位，用来控制对页的访问：

• R/W位确定页的内容是可读的还是只读的
• U/S位确定是否能在用户模式中访问该页，从而保护内核中的代码和数据不被用户程序访问
• XD位用来禁止从某些内存页取指令。通过限制只能执行只读代码段，从而避免溢出攻击

下图则反映了通过四级页表将虚拟地址翻译成物理地址的过程：

通常情况下，我们将地址翻译的分为两步：

1. MMU将虚拟地址翻译成物理地址
2. 将物理地址传送到L1高速缓存

然而，实际的硬件实现优化了地址翻译的过程，允许这两个步骤一定程度上的重叠进行。例如Core i7系统上的一个虚拟地址有12位的VPO，这些位和相应的物理地址的PPO相同。且有八路相联的、64个组和大小为63字节的缓存块的物理寻址的L1高速缓存。

因此每个物理地址有6个缓存偏移位和6个索引位。这12个位刚好和VPO相对应。当CPU翻译一个虚拟地址的时候，它发送VPN到MMU，发送VPO到L1。当MMU查找PTE的时候，L1高速缓存正在利用VPO位查找相应的组合块偏移，读出组中的8个标记的数据字。当MMU得到PPN时，缓存可以直接对这8个标记进行匹配。这样就极大程度的优化了地址翻译的过程。

Linux虚拟内存系统

我们现在需要对LInux的虚拟内存系统做一个简单的描述，以能够大致的了解一个实际的操作系统是怎么组织虚拟内存，并处理缺页的。

我们知道linux为每个进程维护了一个单独的虚拟地址空间，如下图所示：

在此之前我们从来没有讨论过，内核部分的虚拟内存，这一部分位于用户栈之上，现在我们需要进一步的去了解它。

内核虚拟内存包含内核中的代码和数据结构。内核虚拟内存中的某些区域被映射到所有进程共享的物理页面。例如，每个进程都共享内核的代码和数据结构。同时，内核将一片连续的虚拟地址空间映射到一片相同大小的物理地址空间，从而实现对虚拟内存的线性直接映射。这样对指定虚拟地址空间的访问，就可以通过固定的偏移映射来进行访问，而无需页表查找的模式。

内核虚拟内存的的其他区域则存储着每个进程都不相同的数据。如页表、内核在进程的上下文中执行代码时所用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

虚拟内存区域

Linux将虚拟内存组织成一些区域（也叫做段）。区域实际上就是一片连续的已分配的虚拟内存页，往往不同的区域负责不同的内容。例如代码段、数据段、堆、共享库段、用户栈都是不同的区域。大大小小的区域有不同的意义，所以每个存在的虚拟页面一定是属于某个区域的。区域的概念使得虚拟地址空间之间可以有间隙，且不用记录（不用分配）那些不被使用的虚拟内核空间。

下图就是一个用于记录进程中虚拟内存区域的内核数据结构：

内核为系统中的每个进程维护了一个独立的任务结构(task_struct)，任务结构中的元素包含或者指向内核运行这个进程所需要的所有信息（PID，指向用户栈的指针，可执行目标文件的名字，程序计数器…）

task_struct中的一个条目指向mm_struct，它描述了虚拟内存的当前状态。其中有两个我们感兴趣的字段：

• pgd：指向第一级页表的基址，运行时该值被存放在CR3控制寄存器中
• mmap指向一个vm_area_structs（区域结构）的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域。一个具体的区域结构包含以下字段：
  • vm_start：指向这个区域的起始处
  • vm_end：指向这个区域的结束处
  • vm_prot：描述这个区域内包含的所有页的读写许可权限
  • vm_flags：描述这个区域内的页面是与其他进程共享的，还是私有的（以及一些其他信息）
  • vm_next：指向链表中的下一个区域结构

Linux缺页异常处理

假设MMU在翻译某个虚拟地址A的时候，触发了一个缺页。这个异常会触发缺页处理程序，处理程序会执行下面的步骤：

• 虚拟地址A是否合法？

  换句话说就是A是否在某个区域结构定义的区域内吗？缺页处理程序会搜索区域结构的链表，把和每个区域结构中的vm_start和vm_end作比较。如果该指令不合法，就会触发一个段错误，从而终止这个进程。既图中”1”

• 试图进行的内存访问是否合法？

  换句话说就是进程是否有读、写或者执行这个区域内页面的权限？如果试图进行的操作是违法的，那么缺页处理程序就会触发一个保护异常，从而终止这个进程。既图中”2”

• 正常缺页

  排除以上的可能，那么这个缺页就是对合法的虚拟地址进行合法的操作造成的。处理程序会选择有一个牺牲页面，如果这个这个牺牲页面被修改过，就将其交换出去，换入新的页面并更新页表。当缺页处理程序返回时，重新启动引起缺页的指令，这次便可以正常的进行。既图中”3”

内存映射

Linux通过将一个虚拟内存区域和一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容，这个过程，我们就称之为内存映射。虚拟内存区域可以映射到两种类型的对象中的一种：

• Linux文件系统中的普通文件

  一个区域可以映射到一个普通的磁盘文件的连续部分。文件区被分成页大小的片，每一片的包含一个虚拟页面的初始内容。由于系统按需进行页面调度，所以这些虚拟页面美亚由实际交换进入物理内存，直到CPU第一次引用这个页面时，才会调入。对于区域大小大于文件的部分，用0填充余下部分。

• 匿名文件

  一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，内容全部为二进制0填充。CPU第一次引用这样一个区域内的虚拟页面时，内核在物理内存中查找，如果有空闲的物理页框，就用二进制0填充初始化，再建立虚拟页到物理页的映射；如果没有，就挑选一个合适的牺牲页，如果这个页面被修改过，就将其内容写回交换空间，并用二进制0覆盖这个物理页框，建立新的映射关系

这里我们还要知道，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换空间(swap file)之间换来换去。它相当于一个物理内存的页面的一个临时存储处，被替换的牺牲页被暂时的保存在这里。因此，交换空间限制着当前运行的进程能够分配的虚拟页面的总数。

共享对象

本章暂时结束。之后再回头搞一下，接下来要做一些实验和一些项目了。

我们已经学习了虚拟内存的作用和虚拟内存的基本使用过程，为了进一步的深入的理解虚拟内存的机制，我们需要要深入理解虚拟内存的基本原理。

地址翻译

现在我们将从底层除出发，理解硬件在虚拟内存中的角色。为了简化之后的说明，这里提前展示我们所要用到的符号以参考：

实际上，地址翻译就是一个N元素的虚拟地址空间(VAS)中的元素和一个M元素的物理地址空间(PAS)中元素的映射： $$ \begin{align*} MAP&:VAS \to PAS \cup \varnothing \\ MAP(A) &= \begin{cases} A' \text{ 如果虚拟地址A处的数据在PAS的物理地址A'处} \\ \varnothing \text{ 如果虚拟地址A处的数据不在物理内存中} \end{cases} \end{align*} $$ 下图演示了MMU如何利用页表来实现这种映射：

控制寄存器——页表基址寄存器（PTBR）指向当前页表。对于n位的虚拟地址，包含两个部分：

• 一个p位的虚拟页面偏移(VPO)
• 一个n-p位的虚拟页号(VPN)，作为页表的索引

MMU通过VPN选择对应的PTE，同时PTE中的内容实际上就是物理页号(PPN)，这样就可以通过虚拟页号访问到对应的物理页。至于偏移量，由于虚拟页和物理页的大小相同，所以虚拟页偏移量和物理页偏移量(PPO)是是相同的。

现在我们可以分析CPU硬件的执行步骤了：

当页面命中时：

1. 处理器生成一个虚拟地址VA并发送到MMU中
2. MMU生成PTE地址(将VA拆分成VPN和VPO，VPN作为PTE地址)，从内存中请求它
3. 内存向MMU返回PTE
4. MMU构造物理地址(返回的PTE就是PPN，物理地址=PPN+(PPO=VPO))发送给内存
5. 内存通过物理地址找到数据字节返回给CPU

当缺页时：

1. 前三步同上
2. 返回的PTE有效位为0，MMU触发异常，CPU控制传递到内核中的缺页异常处理程序
3. 缺页处理程序调入新的页面，并更新内存中的PTE
4. 缺页处理程序返回原来的进程，再次执行导致缺页的指令。此时页面命中

结合高速缓存和虚拟内存

我们的系统一般既有虚拟内存的机制又有SRAM高速缓存，那么对于SRAM高速缓存，我们是应该使用物理地址访问还是虚拟地址访问呢？下图是一个将其结合起来的方案：

我们使用物理寻址的方案，先将VA转换为PTEA然后在L1中检索，如果命中就直接返回PTE，未命中则再取一次。拿到PTE后构造出PA再对L1进行检索，如果命中就返回PA，未命中就再取一次。L1的存在可以帮我们节省数据传送的时间。页表条目本质上也是数据字，所以也可以被缓存在L1中。

利用TLB加速地址翻译

CPU每次产生一个虚拟地址都需要查阅一个PTE，以便于将虚拟地址进行翻译。每次从内存取数据都需要花费几十到几百的周期，为了解决这个问题，我们引入了高速缓存，在命中的情况下，将开销降到了1到2周期。为了尽可能的减少开销，我们在MMU中引入了一个关于PTE的小缓存，即翻译后备缓冲器(TLB)

TLB是一个小的缓存，其每一行都保存有一个由单个PTE组成的块。其结构如下：

用于组选择和行匹配的索引和标记字段都是从VPN提取出来的。如果TLB有T=2^t个组，那么TLB索引(TLBI)是由VPN的t个最低位组成的，而TLB标记(TLBT)是由VPN中剩余的位组成的（用来行匹配）。

下图展示了TLB的工作过程：

当TLB命中时：

• CPU产生VA
• MMU从TLB中取出相应的PTE
• MMU构造物理地址，发送到缓存
• 缓存返回数据字到CPU

当不命中时，MMU必须从L1中取出相应的PTE。新取出的PTE会覆盖TLB中的一个条目。

由于所有的地址翻译步骤都是在MMU中完成的，所以速度很快。

多级页表

到此为止，我们一直假设系统只使用一个单独的页表来进行地址翻译。如果我们有一个32位的地址空间、4KB的页面和一个4字节的PTE，那么即使我们只使用虚拟空间中很小的一部分，我们也需要一个4MB的页表驻留在内存中。对于64位的地址空间，这个问题更加明显，我们甚至需要4PB的页表常驻内存，这荒谬。为了解决这个问题，我们引入多级页表，用过层次结构来压缩。

我们以下图为例：

对于32位的地址空间，我们有4GB的地址空间，空间被分为4KB的页，每个页有一个4字节的页表条目。假设此时，虚拟空间有以下形式：内存的前2K个页面被分配给了代码和数据，接下来的6K个页面没有被分配，再接下里的1K个页面中有1023个未分配的页和一个分配作为栈的页面。

我们用一级页表中的每个PTE负责映射虚拟空间中一个4MB的片，这里的每一片都是由1024个连续的页面组成的。所以我们只需要1024个一级页表条目就可以指向4G大小的片。

如果片i中的每个页面都没有被分配，那么对应的一级页表条目i就是空的。反之，如果片i中至少有一个页是分配了的，那么一级PTEi就需要指向有一个二级页表的基址。每个二级页表的结构和一级页表都是一样的。

这种方法减少了内存的需求：

• 如果一级页表中的一个PTE是空的，那么对应的二级页表都不需要要存在，这样极大的节省了内存空间，因为虚拟地址空间大部分时候都是未分配的
• 只有一级页表才需要总是在主存中，VM系统在需要时创建、页面调入或调出二级表，进一步减少了主存的压力，只有常用的二级表才需要缓存在主存中

对于一个k级的页表层次结构的地址翻译。虚拟地址被分隔成k个VPN和一个VPO:

每个VPNi都是一个到第i个级页表的索引，第j级的每个页表中都指向第j+1级的某个页表的基址。第k级页表中的每个PTE包含某个物理页面的PPN，或一个磁盘块的地址。最终构造物理地址。

为了构造物理地址，MMU必须访问k个PTE。看上去开销很大，实际上TLB在这里会起到重要的作用，通过将不同层次上页表的PTE缓存起来，效率很不错。

端到端的地址翻译

讲了很多原理和过程，只有自己动手实践才是最真实的，我们用下面的的环境——在一个有TLB和L1 d-cache的系统上：

• 内存是按字节寻址的
• 内存访问是针对1字节的字
• 虚拟地址是14为长的(n=14)
• 物理地址是12位长的(m=12)
• 页面大小为64字节(P=64)
• TLB是四路组相联的，共有16个条目
• L1 d-cache是物理寻址、直接映射的，行大小4个字节16个组

然后是对于TLB和高速缓存，访问这些设备时，我们通过以下方法对位进行划分：

• TLB 因为TLB有四个组，所以VPN的低2位用来做TLBI，高6位作为TLBT

• 页表 这是一个单级设计，一共有256个页面，这里我们只关注前16个。为了方便，我们直接令VPN来标识PTE

• 高速缓存 每个块都是4字节，所以用低2位作为块偏移(CO)。因为有16组，所以接下来的4位做组索引(CI)。剩下的6位做标记(CT)

现在，假设CPU执行一条读地址0x3d4处字节的加载指令会发生什么？

首先MMU会对VA进行解析，并在TLB中查找是否有缓存的PTE:

我们根据索引找到，获取了TLB中缓存的PPN0x0D，从而和VPO构造出物理地址0x0354。现在MMU将物理地址发送到缓存。我们对地址进行解析，查看L1是否缓存了我们需要的数据：

我们根据标记，行索引，块偏移，得到了数据0x36，并将其返回到MMU，随后MMU又将数据返回到CPU。至此，我们就完成了一次虚拟内存的使用。

当然以上的演示，都是理想状态下简化的情况。实际上我们可能会遇到不命中的问题。如果TLB不命中，那么MMU必须从页表PTE中取出PPN。如果得到的PTE是无效的，那么就产生缺页，那么就调用缺页异常处理程序；如果是有效的，但是缓存不命中。那么则又需要进行取用…

总是听到诸如页表，分页机制一类的词汇，听起来让人感到十分的复杂。实际上这些都是涉及到虚拟内存相关的只是。一直以来对这一部分的知识都是望而生畏，现在好好来理解一下它：

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址，物理地址从0开始依次设置。这是最简单自然的结构，我们把CPU以这个结构用来访问地址的方式称为物理寻址。早期的计算机和一些数字处理器和嵌入式设备仍然使用这种方式，

现代处理器则是使用一种被称为虚拟寻址的方式来进行寻址。使用虚拟寻址，CPU会生成一个虚拟地址(VA)来访问主存，VA被送到内存之前会先转换为适当的物理地址，这个过程叫做地址翻译。有一个专门的硬件单元来完成这个任务——内存管理单元(MMU)。原理是利用存放在主存中的查询表来动态翻译虚拟地址，这个表中的内容由操作系统管理。

地址空间

地址空间是非负整数地址的有序集合。如果地址空间中的整数时连续的，我们说它是一个线性地址空间，我们假定之后用到的所有地址空间都是线性的。在一个带虚拟内存的系统中，CPU从有一个有N=2^n个地址的地址空间中生成虚拟地址，则这个地址口空间称为虚拟地址空间。

一个地址空间的大小是由表示最大地址所需要的位数来描述的。对于一个包含N=2^n个地址的虚拟地址空间，我们可以将其叫做为一个n位的地址空间。一个系统还带有一个物理地址空间，对应于系统中的物理内存的M个字节。

地址空间的概念实际上区分了两个概念：

• 数据对象(字节)
• 属性(地址)

所以我们应该意识到数据对象实际上可以有多个地址，只不过每一个地址都选自一个不同的地址空间，这就是我们虚拟空间所用到的概念。例如主存中的每一个字节都有有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存作为缓存工具

虚拟地址实际上就是一个由存放在磁盘上的N个连续的字节大小的单元组成数组，每一个字节都有着一个对应的虚拟地址，作为对这个数组的索引。磁盘上数组的内容被缓存在主存中。和其他的缓存一样，磁盘上的数据被分隔成块，这些快作为磁盘和主存之间的传输单元。

VM系统将虚拟内存分割为虚拟页的大小固定的块，每个虚拟页的大小为P=2^p字节。物理内存也被分隔为同样大小的物理页，也称页帧。

在任意时刻，虚拟页处于以下中的一种状态：

• 未分配：VM系统还没有创建的页。未分配的块不会有任何数据关联，不占用磁盘空间
• 已缓存：当前已缓存在物理内存中的已分配页
• 已分配：未缓存在物理内存中的已分配页

页表

在这里需要用到DRAM和SRAM的关系，可以查看存储器层次架构进行回顾。

和任何缓存一样，VM系统需要要一种方法来判定一个虚拟页是否被缓存在物理内存中的某个地方。如果命中，怎么确定这个虚拟页被存放在那个物理页中。如果不命中，系统需要判断虚拟页存放在磁盘的哪个位置，并在物理内存中选择有一个牺牲页，将虚拟页复制到这里，替换这个牺牲页。

通过操作系统软件、MMU和存放在物理内存中的页表，软硬联合，从而将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为一个物理地址的时候，都会读取页表。操作系统则负责维护页表中的内容，在磁盘和主存间来回传送页。页表的结构大致如下：

我们认识一下页表的基本数据结构，页表就是一个页表条目(PTE)的数组。虚拟地址空间中的每个页在页表中一个固定的偏移量处都有一个PTE（也就是说PTE的大小是固定的）。根据上面的这个简化模型，每个PTE实际上是由一个有效位和一个n位地址字段组成的：

• 有效位表明该虚拟也当前是否被缓存在主存中。
• n位地址字段，在有效位被设置的情况下，表示主存中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么这个地址指向该虚拟页在磁盘中的起始位置。

在上图中我们就可以看到虚拟页的三种状态：未分配、未缓存、已缓存。

页命中

当CPU想要读取包含在VP2中的虚拟内存的一个字时，地址翻译硬件会将虚拟地址作为一个索引来定位PTE2，然后再页表（内存）中读取它。因为设置了有效位，地址翻译硬件就会知道VP2被缓存在内存中，然后就会使用PTE中存储的物理内存地址，构造出这个字的物理地址。

缺页

缺页实际上就是缓存不命中，同上图。CPU引用了VP3中的一个字，地址翻译硬件根据有效位发现VP3并没有被缓存在内存中，于是触发一个缺页异常。这个异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页。程序将牺牲页复制回硬盘中，并将VP3覆盖牺牲页。并修改页表中它们的状态。然后返回，并将导致缺页的虚拟地址重新发送给地址翻译硬件，此时页命中，可以被正确处理：

这个在磁盘和内存之间传送页的活动叫做页面调度，仅在不命中的情况下才进行调度的策略是按需页面调度，我们之后都会使用这个策略。

分配页面

这个过程展示了当操作系统分配一个新的虚拟内存页时，对我们的示例页表产生的影响。在这个过程中，系统在磁盘上创建了一个空间并更新PTE5，使它指向磁盘上这个新创建的页面。

局部性分析

对于虚拟内存的策略，我们可能会认为这是一个效率极低的方案，因为它的不命中惩罚很大。但是实际上，它有着良好的局部性。局部性保证了，在任意时刻中，程序将趋于一个较小的活动页面上工作，例如空间局部性，较大的页空间确保了很好的空间局部性，因为对于数据结构，程序是按序访问的；对于时间局部性，一段内存往往会被反复利用，所以有着良好的时间局部性。

当然如果出现了工作集大小超出内存大小的情况时，程序可能会发生抖动，页面会不停的换进换出，带来严重的不命中开销。

虚拟内存作为内存管理的工具

虚拟内存不仅有着很好的缓存性能，同时它也很好的简化了内存管理，为我们提供了一个很好的内存保护机制。

实际上，操作系统为每个进程提供了一个独立的页表，也就是一个独立的虚拟空间，下图很好的展示了这一点：

注意，这里可以看到多个虚拟页面实际上是可以映射到同一个共享物理页面上。

通过按需页面调度和独立的虚拟地址空间的结合，系统对内存的使用和管理被极大的简化，VM系统简化了链接和加载、代码和数据共享、以及应用程序的内存分配…

简化链接

独立的地址空间也允许每个进程的内存映像使用相同的基本格式，而不用考虑代码和数据实际上被存储在哪里。这样的一致性简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。

简化加载

虚拟内存简化了向内存中加载可执行文件和共享对象文件的过程。要把目标文件中.text和.data节加载到一个新创建的进程中，Linux加载器会为代码段和数据段分配虚拟页，然后将其标为无效的（即未缓存）。而不是将其进行缓存，只有当页被引用到时，虚拟内存会按需调度这些页面。

将一组连续的虚拟页映射到任意一个文件的任意位置的表示法叫做内存映射我们会在之后涉及这些内容。

简化共享

一般而言，每个进程都有自己私有的代码，数据，堆栈等区域，这个其他进程是不共享的。操作系统为每个进程提供页表，将相应的虚拟页映射到不同的物理页面。也就是说，对于不同进程来说，尽管是同一个虚拟地址，但是实际上映射的是不同的物理地址。极大程度上简化了进程间私有的问题。

当然有时候进程间有也需要共享代码和数据，例如每个进程都调用相同的操作系统内核代码，操作系统会将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是为每个进程都分配一个副本。

简化内存分配

虚拟内存为用户进程提供了一个简单的分配额外内存的机制。当一个运行在用户进程的程序要求有一个额外的堆空间时，操作系统只需要分配适当的连续的虚拟内存页面，并将其映射到物理内存中的物理页面就行了。通过页表，操作系统也不用分配连续的物理页。使得页面可以随机的分布在物理内存中，提高了碎片空间的可用性。

虚拟内存作为内存保护的工具

操作系统需要有手段来控制对内存系统的访问，不应该允许用户进程对其只读代码段进行修改，也不应该允许它修改内核中的代码和数据结构，不应该允许它读写其他进程的私有内存或是修改和其他进程共享的虚拟原页面。而虚拟内存能够很好的实现这个机制：

当每次CPU生成一个地址时，地址翻译硬件都会读一个PTE，我们可以通过有效位来判断这个页面的状态。我们也可以通过添加额外的许可页来控制对一个虚拟页面内容的访问。

例如图中的，SUP位表示进程是否必须在内核模式下才能访问此页。READ和WRITE位则控制对原页面的读写访问。不同进程的页表中对同一个页的访问权是不同的，以此可以实现对进程内存访问的控制。

如果一条指令违反了这些许可条件，那么CPU就会触发保护故障，将控制传递给异常处理程序。LInux Shell一般将这个异常报告为Segmentation fault

我们先前实现了卷积神经网络的各层，以及基本的前向传播，现在我们要进一步的完善整个神经网络，通过反向传播实现对权重的更新，从而提高神经网络的准确性。

反向传播

现在我们已经完成了神经网络的前向传播，现在我们需要对每个层进行反向传播以更新权重，来寻来你神经网络。进行反向传播，我们需要注意两点：

• 在前向传播的阶段，我们需要在每一层换从它需要用于反向传播的数据（如中间值等）。这也反映了，任意反向传播的阶段，都需要有着相应的前向阶段。
• 在反向传播阶段，每一层都会接受一个梯度，并返回一个梯度。其接受其输出（$\frac{\partial L}{\partial out}$）的损失梯度，并返回其输入（$\frac{\partial L}{\partial in}$）的损失梯度

我们的训练过程应该是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13

# 前向传播
out = conv.forward((image / 255) - 0.5)
out = pool.forward(out)
out = softmax.forward(out)

# 初始化梯度
gradient = np.zeros(10)
# ...

# 反向传播
gradient = softmax.backprop(gradient)
gradient = pool.backprop(gradient)
gradient = conv.backprop(gradient)

现在我们将逐步构建我们的反向传播函数：

Softmax层反向传播

我们的损失函数是： $$ \begin{align*} L = -ln(p_c) \end{align*} $$ 所以我们首先要计算的就是对于softmax层反向传播阶段的输入，其中out_s就是softmax层的输出。一个包含了10个概率的向量，我们只在乎正确类别的损失，所以我们的第一个梯度为： $$ \begin{align*} \frac{\partial L}{\partial out_s(i)} = \begin{cases} 0 \space\space\space\space\space \text{ if i!=c} \\ -\frac{1}{p_i} \text{ if i=c} \end{cases} \end{align*} $$ 所以我们正确的初始梯度应该是：

1
2

gradient = np.zeros(10)
gradient[label] = -1 / out[label]

然后我们对softmax层的前向传播阶段进行一个缓存：

1
2
3
4
5
6
7
8
9
10
11
12
13

def forward(self, input):
    # 输入体积的形状
    self.last_input_shape = input.shape
    input = input.flatten()
    # 展平后的输入向量
    self.last_input = input
    
    totals = np.dot(input,self.weights) + self.biases
    # 输出结果（提供给激活函数）
    self.last_totals = totals
    exp = np.exp(totals)

    return exp/np.sum(exp,axis=0)

现在我们可以开始准备softmax层的反向传播了：

计算

我们已经计算出，损失对于激活函数值的梯度，我们现在需要进一步的推导，最终我们希望得到$\frac{\partial L}{\partial input} \frac{\partial L}{\partial w} \frac{\partial L}{\partial b}$

的梯度，以用于对权重的梯度训练。根据链式法则，我们应该有： $$ \begin{align*} \frac{\partial L}{\partial w} &= \frac{\partial L}{\partial out} * \frac{\partial out}{\partial t} * \frac{\partial t}{\partial w} \\ \frac{\partial L}{\partial b} &= \frac{\partial L}{\partial out} * \frac{\partial out}{\partial t} * \frac{\partial t}{\partial b} \\ \frac{\partial L}{\partial input} &= \frac{\partial L}{\partial out} * \frac{\partial out}{\partial t} * \frac{\partial t}{\partial input} \end{align*} $$ 其中 t = w * input + b，out则是softmax函数的输出值，我们可以依次求出。对于$\frac{\partial L}{\partial out}$我们有： $$ \begin{align*} out_s(c) &= \frac{e^{t_c}}{\sum_{i}e^{t_i}} = \frac{e^{t_c}}{S} \\ S &= \sum_{i}e^{t_i} \\ \to out_s(c) &= e^{t_c}S^{-1} \end{align*} $$ 现在我们求$\frac{\partial out_s(c)}{\partial t_k}$，需要分别考虑k=c和k!=c的情况，我们依次进行求导： $$ \begin{align*} \frac{\partial out_s(c)}{\partial t_k} &= \frac{\partial out_s(c)}{\partial S} *\frac{\partial S}{\partial t_k} \\ &= -e^{t_c}S^{-2}\frac{\partial S}{\partial t_k} \\ &= -e^{t_c}S^{-2}(e^{t_k}) \\ &= \frac{-e^{t_c}e^{t_k}}{S^2} \\ \\ \frac{\partial out_s(c)}{\partial t_c} &= \frac{Se^{t_c}-e^{t_c}\frac{\partial S}{\partial t_c}}{S^2} \\ &= \frac{Se^{t_c}-e^{t_c}e^{t_c}}{S^2} \\ &= \frac{e^{t_c}(S-e^{t_c})}{S^2} \\ \to \frac{\partial out_s(k)}{\partial t} &= \begin{cases} \frac{-e^{t_c}e^{t_k}}{S^2} \space\space\space\space \text{ if k!=c} \\ \frac{e^{t_c}(S-e^{t_c})}{S^2} \text{ if k=c} \end{cases} \end{align*} $$ 最后我们根据公式t = w * input + b得到: $$ \begin{align*} \frac{\partial t}{\partial w}&=input \\ \frac{\partial t}{\partial b}&=1 \\ \frac{\partial t}{\partial input}&=w \end{align*} $$ 现在我们可以用代码实现这个过程了

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def backprop(self,d_L_d_out):
    # d_L_d_out是这一层的输出梯度,作为参数
    # 返回d_L_d_in作为下一层的参数
    for i,gradient in enumerate(d_L_d_out):
        if gradient == 0:
            continue
        # e^totals
        t_exp = np.exp(self.last_totals)
        # S = sum(e^totals)
        S = np.sum(t_exp)
        # total对out[i]的梯度关系
        # 第一次是对所有的梯度进行更新
        d_out_d_t = -t_exp[i]*t_exp / (S**2)
        # 第二次是只对 =i 的梯度进行更新 从而使第一次的更新只针对 !=i 的梯度
        d_out_d_t[i] = t_exp[i]*(S-t_exp[i]) / (S**2)
        # 权重对total的梯度关系
        d_t_d_w = self.last_input
        d_t_d_b = 1
        d_t_d_input = self.weights
        # total对Loss的梯度关系
        d_L_d_t = gradient * d_out_d_t
        # 权重对Loss的梯度关系
        d_L_d_w = d_t_d_w[np.newaxis].T @ d_L_d_t[np.newaxis]
        d_L_d_b = d_L_d_t * d_t_d_b
        d_L_d_input = d_t_d_input @ d_L_d_t
        # 梯度训练
    self.weights -= self.learn_rate * d_L_d_w
    self.biases -= self.learn_rate * d_L_d_b
    # 返回梯度
    return d_L_d_input.reshape(self.last_input_shape)

由于softmax层的输入是一个输入体积，在一开始被我们展平处理了，但是我们返回的梯度也应该是一个同样大小的输入体积，所以我们需要通过reshape确保这层的返回的梯度和原始的输入格式相同。

我们可以测试一下softmax反向传播后的训练效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import numpy as np

from conv import Conv3x3
from maxpool import MaxPool2
from softmax import Softmax
import tensorflow as tf

(x_train, y_train), (x_test, y_test) = tf.keras.datasets.mnist.load_data()

test_images = x_test[:1000]
test_labels = y_test[:1000]

conv = Conv3x3(8)
pool = MaxPool2()
softmax = Softmax(13*13*8,10)

def forward(image,label):
    out = conv.forward((image / 255) - 0.5)
    out = pool.forward(out)
    out = softmax.forward(out)

    loss = -np.log(out[label])
    acc = 1 if np.argmax(out) == label else 0

    return out,loss,acc

def train(image,label):
    out, loss, acc = forward(image,label)
    gradient = np.zeros(10)
    gradient[label] = -1 / out[label]
    gradient = softmax.backprop(gradient)

    return loss,acc

print("Start!")
loss = 0
num_correct = 0

for i,(im,label) in enumerate(zip(test_images,test_labels)):
    _, l, acc = forward(im,label)
    if i%100 == 99:
        print(
            '[Step %d] Past 100 steps :Average Loss %.3f | Accuracy %d%%' %
            (i+1,loss/100,num_correct)
        )
        loss = 0
        num_correct = 0
    l,acc = train(im,label)
    loss += l
    num_correct += acc

可以看到准确率有明显的提升，说明我们softmax层的反向传播在很好的进行

1
2
3
4
5
6
7
8
9
10
11

Start!
[Step 100] Past 100 steps :Average Loss 2.112 | Accuracy 24%
[Step 200] Past 100 steps :Average Loss 1.940 | Accuracy 37%
[Step 300] Past 100 steps :Average Loss 1.686 | Accuracy 50%
[Step 400] Past 100 steps :Average Loss 1.606 | Accuracy 51%
[Step 500] Past 100 steps :Average Loss 1.451 | Accuracy 58%
[Step 600] Past 100 steps :Average Loss 1.362 | Accuracy 65%
[Step 700] Past 100 steps :Average Loss 1.264 | Accuracy 66%
[Step 800] Past 100 steps :Average Loss 1.057 | Accuracy 75%
[Step 900] Past 100 steps :Average Loss 0.978 | Accuracy 81%
[Step 1000] Past 100 steps :Average Loss 0.966 | Accuracy 78%

池化层传播

在前向传播的过程中，最大池化层接收一个输入体积，然后通过2x2区域的最大池化，将宽度和高度都减半。而在反向传播中，执行相反的操作：我们将损失梯度的宽度和高度都翻倍，通过将每个梯度值分配到对应的2x2区域的最大值位置：

每个梯度都被分配到原始最大值的位置，然后将其他梯度设置为0.

为什么是这这样的呢？在一个2x2区域中，由于我们只关注区域内的最大值，所以对于其他的非最大值，我们可以几乎忽略不计，因为它的改变对我们的输出结果没有影响，所以对于非最大像素，我们有$\frac{\partial L}{\partial inputs}=0$。另一方面来看，最大像素的$\frac{\partial output}{\partial input}=1$，这意味着$\frac{\partial L}{\partial output}=\frac{\partial L}{\partial input}$

所以对于这一层的反向传播，我们只需要简单的还原，并且填充梯度值到最大像素区域就行了

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def backprop(self,d_L_d_out):
    # 这里的self.last_input是前向阶段的数据缓存
    d_L_d_input = np.zeros(self.last_input.shape)
    for im_region,i,j in self.iterate_regions(self.last_input):
        h,w,f = im_region.shape
        amax = np.amax(im_region,axis=(0,1))

        for i2 in range(h):
            for j2 in range(w):
                for f2 in range(f):
                    # 搜寻区域内的最大值并赋梯度值
                    if im_region[i2,j2,f2] == amax[f2]:
                        d_L_d_input[i*2+i2, j*2+j2,f2] = d_L_d_out[i,j,f2]
    return d_L_d_input

这一部分并没有什么权重用来训练，所以只是一个简单的数据还原。

卷积层反向传播

卷积层的反向传播，我们需要的是卷积层中的滤波器的损失梯度，因为我们需要利用损失梯度来更新我们滤波器的权重，我们现在已经有了$\frac{\partial L}{\partial output}$，我们现在只需要计算$\frac{\partial output}{\partial filters}$，所以我们需要知道，改变一个滤波器的权重会怎么影响到卷积层的输出？

实际上修改滤波器的任意权重都可能会导致滤波器输出的整个图像，下面便是很好的示例：

同样的对任何滤波器权重+1都会使输出增加相应图像像素的值，所以输出像素相对于特定滤波器权重的导数应该就是相应的图像元素。我们可以通过数学计算来论证这一点

计算

$$ \begin{align*} out(i,j) &= convolve(image,filiter) \\ &= \sum_{x=0}^3{}\sum_{y=0}^{3}image(i+x,j+y)*filiter(x,y) \\ \to \frac{\partial out(i,j)}{\partial filiter(x,y)} &=image(i+x,i+y) \end{align*} $$

我们将输出的损失梯度引进来，我们就可以获得特定滤波器权重的损失梯度了： $$ \begin{align*} \frac{\partial L}{\partial filiter(x,y)} = \sum_{i}\sum_{j}\frac{\partial L}{\partial out(i,j)} * \frac{\partial out(i,j)}{\partial filter(x,y)} \end{align*} $$ 现在我们可以实现我们卷积层的反向传播了：

实现

1
2
3
4
5
6
7
8
9

def backprop(self, d_L_d_out):
    d_L_d_filters = np.zeros(self.filters.shape)

    for im_region, i, j in self.iterate_regions(self.last_input):
        for f in range(self.num_filters):
            d_L_d_filters[f] += d_L_d_out[i, j, f] * im_region

    self.filters -= self.learn_rate * d_L_d_filters
    return None

现在我们可以对我们的神经网络进行一个完整的训练了，我们可以看到训练的结果如下：

效果还是非常不错的。

完善

和之前的网络不同，CNN的训练集比较庞大，如果每次启动都要训练遍参数就太麻烦了，所以我们可以再每次训练之后将参数保存下来。下次再要使用就可以直接加载而不用重复训练。所以我们可以编写保存模型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import pickle

class ModelSaver:
    def __init__(self, model_name='MNIST_CNN'):
        self.model_name = model_name

    def save(self, conv, pool, softmax):
        data = {
            'conv_filters': conv.filters,
            'softmax_weights': softmax.weights,
            'softmax_biases': softmax.biases
        }
        filename = f'{self.model_name}.pkl'
        with open(filename, 'wb') as f:
            pickle.dump(data, f)
        print(f"保存参数到{filename}")

    def load(self, conv, pool, softmax):
        filename = f'{self.model_name}.pkl'
        try:
            with open(filename, 'rb') as f:
                data = pickle.load(f)

            conv.filters = data['conv_filters']
            softmax.weights = data['softmax_weights']
            softmax.biases = data['softmax_biases']
            print("模型参数加载成功")
            return True

        except FileNotFoundError:
            print("无可用模型参数")
            return False

如果我们想要自己尝试手写输入，来测试模型的效果，我们可能希望有个手写板，所以我们可以再写一个手写板的类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class DrawingBoard:
    def __init__(self, root):
        self.root = root
        self.root.title("画板")

        # 创建一个 Canvas 作为画板
        self.canvas = tk.Canvas(root, width=280, height=280, bg='white')
        self.canvas.pack()

        # 绑定鼠标事件
        self.canvas.bind("<B1-Motion>", self.paint)

        # 初始化绘图工具
        self.image = Image.new("RGB", (280, 280), "white")
        self.draw = ImageDraw.Draw(self.image)

        # 初始化画笔颜色和宽度
        self.brush_color = "black"
        self.brush_width = 5

        # 添加输出按钮
        self.output_button = tk.Button(root, text="输出", command=self.output_and_exit)
        self.output_button.pack()

    def paint(self, event):
        x1, y1 = (event.x - self.brush_width), (event.y - self.brush_width)
        x2, y2 = (event.x + self.brush_width), (event.y + self.brush_width)
        self.canvas.create_oval(x1, y1, x2, y2, fill=self.brush_color, outline=self.brush_color)
        self.draw.ellipse([x1, y1, x2, y2], fill=self.brush_color, outline=self.brush_color)

    def process_image(self):
        # 将图像调整为 28x28 像素
        processed_image = self.image.resize((28, 28), Image.Resampling.LANCZOS)
        processed_image = ImageOps.grayscale(processed_image)

        # 将图像转换为 NumPy 数组
        image_array = np.array(processed_image)

        # 确保像素值是整数
        image_array = image_array.astype(np.uint8)

        return image_array

    def output_and_exit(self):
        # 处理图像并获取数组
        self.image_array = self.process_image()

        # 保存图像
        processed_image = Image.fromarray(self.image_array)
        processed_image.save("temp.png")
        print("图片已保存为 temp.png")

        # 退出程序
        self.root.destroy()

现在我们就可以使用它了，我们先进行训练，然后用保存的参数，来进行手写数字识别，我把整个网络的源代码放在下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228