《操作系统真象还原》chapter10 笔记与思考

First Post:

Last Update:

PART 1 <锁Lock>

    首先是上一章的地址访问错误问题。首先回忆一下本书的打印字符串功能是如何实现的：

  • 读取当前光标值
  • 将光标值转换为坐标值
  • 向坐标写入字符
  • 更新光标值

    其中，更新光标的过程如下：

  • 通知光标寄存器将要设置高8位
  • 设置高8位
  • 通知光标寄存器将要设置低8位
  • 设置低8位

    接下来，当引入多线程以后，设想如下一个执行过程：首先假设存在线程A和线程B

  • 线程A尝试打印字符，打印结束以后，线程A进入第四步更新光标
  • 更新光标时，当执行到通知设置低8位时，中断发生，切换到线程B

    此时，光标的坐标才刚设置了新的高8位，低8位已经被计算出来了，但还没能设置到寄存器中。但如果没有换行等，尚且不会影响到以后的打印，因为高位坐标浮动不大。

  • 线程B也需要打印字符，它也走到更新光标的时候。当它通知寄存器接下来要设置高8位时，发生中断，切换到线程A
  • 现在，光标寄存器以为接下来要设置高8位，而线程A则继续执行设置步骤，将本应该设置到低8位的值放到高位去了。

    低位的浮动极大，诸如0xfc这样的值被放进高位，将直接导致内存访问异常。

    那么朴素一点的解决方法就是，别让线程在打印的时候被中断。但这也不太现实，因为不只是打印字符串函数会这样，所有需要访问全局资源的函数都可能出现这个问题。并且这些函数也往往都是些底层函数，这样做对debug来说似乎不太友好，层层封装还有额外消耗，所以针对资源访问，引入一个锁来替代关闭中断。

    锁的思路也不复杂：

首先，为全局资源添加一个锁(体现为结构体，其中带有一个value)。

接下来，任何线程尝试访问该资源时，首先查看资源是否已经上锁。若上锁，则直接将自己阻塞(加入该锁本身的阻塞队列)，等待直到被唤醒为止；若未上锁，则获得该锁以防其他线程也访问该资源，然后将所有事情做完以后，释放该锁，然后主动去唤醒阻塞队列中的线程。

    上面的过程是没有关中断的，显然，它仍然是能够被调度的，那些不需要访问该资源的线程自然就不会因为你需要访问全局资源而被卡脖子了。而那些需要访问本资源的线程则会在尝试访问时因为锁已经被获取了，所以陷入阻塞状态，直到当前拿着锁的线程释放锁以后主动唤醒自己。

    具体的代码实现如下：

1
2
3
4
5
6
7
8
9
struct semaphore {
   uint8_t  value;
   struct   list waiters;
};
struct lock {
   struct   task_struct* holder;        // 锁的持有者
   struct   semaphore semaphore;        // 用二元信号量实现锁
   uint32_t holder_repeat_nr;            // 锁的持有者重复申请锁的次数
};

    通过信号量来实现锁的功能。本书的方法如下：

信号量初值为1。当有线程需要获得锁时，先将信号量减一，然后把holder指向自己的PCB；而释放锁则需要先将holder指向NULL，然后将信号量加一。

    而检测锁的方式是在需要操作信号量的时候进行一次判断：

减一时：如果信号量为0，则表示锁已经被取走，将自己加入锁的等待队列以后阻塞自己。

加一时：如果等待队列非空，那就唤醒等待队列里的第一个线程，然后把信号量增加

如上两个操作均需要在关闭中断的情况下进行，即原子操作

    至于唤醒和阻塞的实现也同样不复杂：

阻塞：将线程从调度器的调度队列里摘出，加入等待队列。

唤醒：将线程从等待队列里摘出，加入调度器的调度队列。

    现在我们就知道是什么情况了。只要没有线程去唤醒这些被阻塞的线程，它们就永远不会被调度器选中。那么最开始的问题是解决了，只需要把put_str这样的函数再封装一次，在外部加上获取锁和释放锁的操作，就能保证不会有上面那样的错误出现了；而对于不需要打印字符串的线程也能够正常的进行操作。

PART 2 <键盘驱动>

    虽然本章第二节开始都在讲这个，但概况起来看，内容不是很多，个人认为更多的是一些了解性的知识。

    在中断那章有注意到，8259A芯片的IRQ1对应的就是键盘中断了。键盘每次击键时都会发生若干次中断，具体过程如下：

键盘内置的8048芯片在每次按下按键时，会根据不同的按键向8042芯片发送对应的扫描码，同时在松开按键的时候也会发送不同的扫描码。

8042芯片将该扫描码转换成兼容早期键盘的第一套扫描码后，将其送到固定的端口，同时触发8259A芯片的中断。

(注：扫描码多为单字节，但也存在多字节扫描码，每传输一个字节的扫描码就需要触发一次中断，因此一个按键就可能触发多次中断)

8259A芯片在接收中断以后做对应的处理。键盘驱动似乎就是对应的中断处理函数 **(笔者还不确定这么说是否合适)**。

    扫描码如下：注释中标明了每列的意思。

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
static char keymap[][2] = {
/* 扫描码   未与shift组合  与shift组合*/
/* ---------------------------------- */
/* 0x00 */    {0,    0},        
/* 0x01 */    {esc,    esc},        
/* 0x02 */    {'1',    '!'},        
/* 0x03 */    {'2',    '@'},        
/* 0x04 */    {'3',    '#'},        
/* 0x05 */    {'4',    '$'},        
/* 0x06 */    {'5',    '%'},        
/* 0x07 */    {'6',    '^'},        
/* 0x08 */    {'7',    '&'},        
/* 0x09 */    {'8',    '*'},        
/* 0x0A */    {'9',    '('},        
/* 0x0B */    {'0',    ')'},        
/* 0x0C */    {'-',    '_'},        
/* 0x0D */    {'=',    '+'},        
/* 0x0E */    {backspace, backspace},    
/* 0x0F */    {tab,    tab},        
/* 0x10 */    {'q',    'Q'},        
/* 0x11 */    {'w',    'W'},        
/* 0x12 */    {'e',    'E'},        
/* 0x13 */    {'r',    'R'},        
/* 0x14 */    {'t',    'T'},        
/* 0x15 */    {'y',    'Y'},        
/* 0x16 */    {'u',    'U'},        
/* 0x17 */    {'i',    'I'},        
/* 0x18 */    {'o',    'O'},        
/* 0x19 */    {'p',    'P'},        
/* 0x1A */    {'[',    '{'},        
/* 0x1B */    {']',    '}'},        
/* 0x1C */    {enter,  enter},
/* 0x1D */    {ctrl_l_char, ctrl_l_char},
/* 0x1E */    {'a',    'A'},        
/* 0x1F */    {'s',    'S'},        
/* 0x20 */    {'d',    'D'},        
/* 0x21 */    {'f',    'F'},        
/* 0x22 */    {'g',    'G'},        
/* 0x23 */    {'h',    'H'},        
/* 0x24 */    {'j',    'J'},        
/* 0x25 */    {'k',    'K'},        
/* 0x26 */    {'l',    'L'},        
/* 0x27 */    {';',    ':'},        
/* 0x28 */    {'\'',    '"'},        
/* 0x29 */    {'`',    '~'},        
/* 0x2A */    {shift_l_char, shift_l_char},    
/* 0x2B */    {'\\',    ''},        
/* 0x2C */    {'z',    'Z'},        
/* 0x2D */    {'x',    'X'},        
/* 0x2E */    {'c',    'C'},        
/* 0x2F */    {'v',    'V'},        
/* 0x30 */    {'b',    'B'},        
/* 0x31 */    {'n',    'N'},        
/* 0x32 */    {'m',    'M'},        
/* 0x33 */    {',',    '<'},        
/* 0x34 */    {'.',    '>'},        
/* 0x35 */    {'/',    '?'},
/* 0x36    */    {shift_r_char, shift_r_char},    
/* 0x37 */    {'*',    '*'},        
/* 0x38 */    {alt_l_char, alt_l_char},
/* 0x39 */    {' ',    ' '},        
/* 0x3A */    {caps_lock_char, caps_lock_char}
/*其它按键暂不处理*/
};

    但需要注意的是，只有处理器每次从0x60号端口取走一字节的扫描码以后，键盘才会触发下一次中断。所以对于一些组合键或是多字节扫描码的按键来说，需要多次中断才能判明用户的行为。所以中断处理函数似乎变得有些臃肿。

注：同一个按键按下时产生“通码”，松开时产生“断码”。通码和断码从开始就设计好了，它们只差了二进制数的第七位。对于第七位为0的数是通码，为1的则为断码。下述代码的break_code就是断码，make_code是通码。

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
/* 键盘中断处理程序 */
static void intr_keyboard_handler(void) {
/* 这次中断发生前的上一次中断,以下任意三个键是否有按下 */
   bool ctrl_down_last = ctrl_status;      
   bool shift_down_last = shift_status;
   bool caps_lock_last = caps_lock_status;
   bool break_code;
   uint16_t scancode = inb(KBD_BUF_PORT);
/* 若扫描码是e0开头的,表示此键的按下将产生多个扫描码,
 * 所以马上结束此次中断处理函数,等待下一个扫描码进来*/ 
   if (scancode == 0xe0) { 
      ext_scancode = true;    // 打开e0标记
      return;
   }
/* 如果上次是以0xe0开头,将扫描码合并 */
   if (ext_scancode) {
      scancode = ((0xe000)  scancode);
      ext_scancode = false;   // 关闭e0标记
   }   
   break_code = ((scancode & 0x0080) != 0);   // 获取break_code

   if (break_code) {   // 若是断码break_code(按键弹起时产生的扫描码)
   /* 由于ctrl_r 和alt_r的make_code和break_code都是两字节,
   所以可用下面的方法取make_code,多字节的扫描码暂不处理 */
      uint16_t make_code = (scancode &= 0xff7f);   // 得到其make_code(按键按下时产生的扫描码)
   /* 若是任意以下三个键弹起了,将状态置为false */
      if (make_code == ctrl_l_make  make_code == ctrl_r_make) {
     ctrl_status = false;
      } else if (make_code == shift_l_make  make_code == shift_r_make) {
     shift_status = false;
      } else if (make_code == alt_l_make  make_code == alt_r_make) {
     alt_status = false;
      } /* 由于caps_lock不是弹起后关闭,所以需要单独处理 */
      return;   // 直接返回结束此次中断处理程序
   } 
   /* 若为通码,只处理数组中定义的键以及alt_right和ctrl键,全是make_code */
   else if ((scancode > 0x00 && scancode < 0x3b)  \
           (scancode == alt_r_make)  \
           (scancode == ctrl_r_make)) {
      bool shift = false;  // 判断是否与shift组合,用来在一维数组中索引对应的字符
      if ((scancode < 0x0e)  (scancode == 0x29)  \
     (scancode == 0x1a)  (scancode == 0x1b)  \
     (scancode == 0x2b)  (scancode == 0x27)  \
     (scancode == 0x28)  (scancode == 0x33)  \
     (scancode == 0x34)  (scancode == 0x35)) {  
        /****** 代表两个字母的键 ********
             0x0e 数字'0'~'9',字符'-',字符'='
             0x29 字符'`'
             0x1a 字符'['
             0x1b 字符']'
             0x2b 字符'\\'
             0x27 字符';'
             0x28 字符'\''
             0x33 字符','
             0x34 字符'.'
             0x35 字符'/' 
        *******************************/
     if (shift_down_last) {  // 如果同时按下了shift键
        shift = true;
     }
      } else {      // 默认为字母键
     if (shift_down_last && caps_lock_last) {  // 如果shift和capslock同时按下
        shift = false;
     } else if (shift_down_last  caps_lock_last) { // 如果shift和capslock任意被按下
        shift = true;
     } else {
        shift = false;
     }
      }
      uint8_t index = (scancode &= 0x00ff);  // 将扫描码的高字节置0,主要是针对高字节是e0的扫描码.
      char cur_char = keymap[index][shift];  // 在数组中找到对应的字符

   /* 如果cur_char不为0,也就是ascii码为除'\0'外的字符就加入键盘缓冲区中 */
      if (cur_char) {

     /*****************  快捷键ctrl+l和ctrl+u的处理 *********************
      * 下面是把ctrl+l和ctrl+u这两种组合键产生的字符置为:
      * cur_char的asc码-字符a的asc码, 此差值比较小,
      * 属于asc码表中不可见的字符部分.故不会产生可见字符.
      * 我们在shell中将ascii值为l-a和u-a的分别处理为清屏和删除输入的快捷键*/
     if ((ctrl_down_last && cur_char == 'l')  (ctrl_down_last && cur_char == 'u')) {
        cur_char -= 'a';
     }
      /****************************************************************/
   /* 若kbd_buf中未满并且待加入的cur_char不为0,
    * 则将其加入到缓冲区kbd_buf中 */
     if (!ioq_full(&kbd_buf)) {
        ioq_putchar(&kbd_buf, cur_char);
     }
     return;
      }
      /* 记录本次是否按下了下面几类控制键之一,供下次键入时判断组合键 */
      if (scancode == ctrl_l_make  scancode == ctrl_r_make) {
     ctrl_status = true;
      } else if (scancode == shift_l_make  scancode == shift_r_make) {
     shift_status = true;
      } else if (scancode == alt_l_make  scancode == alt_r_make) {
     alt_status = true;
      } else if (scancode == caps_lock_make) {
      /* 不管之前是否有按下caps_lock键,当再次按下时则状态取反,
       * 即:已经开启时,再按下同样的键是关闭。关闭时按下表示开启。*/
     caps_lock_status = !caps_lock_status;
      }
   } else {
      put_str("unknown key\n");
   }
}

    然后将该函数注册到IDT中即可。但是我们只是让自己敲的键盘字符出现的屏幕上，并不是像shell那样能被读取。这些字符并不是出现在缓冲区里的，所以本书最后一节实现了一个简单的环形缓冲区，用以暂存从键盘上输入的字符，让其他程序能够从该缓冲区里读出用户键入的数据。

注：上面的intr_keyboard_handler来自本章最后一节，实际上它已经实现了缓冲区了。通过ioq_putchar函数将数据放入缓冲区中。

PART 3 <环形缓冲区>

    最后一节也没有太多内容了，关于环形缓冲区的思路随便搜一下就能找到。还有关于生产者和消费者的问题，个人认为书上的表述并不太好，还是看代码字节理解来得更快。本节内容并不是什么复杂的东西，这里就不赘述了。

1
2
3
4
5
6
7
8
struct ioqueue {
    struct lock lock;
    struct task_struct* producer;
    struct task_struct* consumer;
    char buf[bufsize];                // 缓冲区大小
    int32_t head;                // 队首,数据往队首处写入
    int32_t tail;                // 队尾,数据从队尾处读出
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ioq_putchar(struct ioqueue* ioq, char byte) {
   ASSERT(intr_get_status() == INTR_OFF);
   while (ioq_full(ioq)) {
      lock_acquire(&ioq->lock);
      ioq_wait(&ioq->producer);
      lock_release(&ioq->lock);
   }
   ioq->buf[ioq->head] = byte;      // 把字节放入缓冲区中
   ioq->head = next_pos(ioq->head); // 把写游标移到下一位置

   if (ioq->consumer != NULL) {
      wakeup(&ioq->consumer);          // 唤醒消费者
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
char ioq_getchar(struct ioqueue* ioq) {
   ASSERT(intr_get_status() == INTR_OFF);
   while (ioq_empty(ioq)) {
      lock_acquire(&ioq->lock);     
      ioq_wait(&ioq->consumer);
      lock_release(&ioq->lock);
   }
   char byte = ioq->buf[ioq->tail];      // 从缓冲区中取出
   ioq->tail = next_pos(ioq->tail);      // 把读游标移到下一位置
   if (ioq->producer != NULL) {
      wakeup(&ioq->producer);          // 唤醒生产者
   }
   return byte; 
}

    两个函数分别从缓冲区中放入和读取一个字节。此处的缓冲区也属于全局资源，所以也需要加锁，同时是用while进行判断的，因为可能唤醒该线程的时，线程还是不符合条件的情况出现。

    然后现在回顾上一个PART的中intr_keyboard_handler函数。

1
2
3
4
struct ioqueue kbd_buf;
          if (!ioq_full(&kbd_buf)) {
        ioq_putchar(&kbd_buf, cur_char);
     }

    kbd_buf是内核全局变量，也就是内核缓冲区。键盘的输入会存入内核缓冲区，然后由其他程序读出以实现交互(其实就是本书本章本节前面实现的控制台了)。

插画ID：92002347

≡