你管这破玩意儿叫操作系统源码(五)

本文为学习操作系统源码 (低并发编程)所作笔记，仅供学习参考，不做任何商业用途,若有侵权，请联系删除。

第十八回 | 大名鼎鼎的进程调度就是从这里开始的

第18回 | 大名鼎鼎的进程调度就是从这里开始的 (qq.com)

shed_init 进程调度初始化

1
2
3
4
5
void sched_init(void) {
    set_tss_desc(gdt+4, &(init_task.task.tss));
    set_ldt_desc(gdt+5, &(init_task.task.ldt));
    ...
}

两行代码初始化了下 TSS 和 LDT。

先别急问这俩结构是啥。还记得之前讲的全局描述符表 gdt 么？它在内存的这个位置，并且被设置成了这个样子。

第八回 | 烦死了又要重新设置一遍 idt 和 gdt (qq.com)

TSS 叫任务状态段，就是保存和恢复进程的上下文的，所谓上下文，其实就是各个寄存器的信息而已，这样进程切换的时候，才能做到保存和恢复上下文，继续执行。

由它的数据结构你应该可以看出点意思。

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
struct tss_struct{
    long back_link;
    long esp0;
    long ss0;
    long esp1;
    long ss1;
    long esp2;
    long ss2;
    long cr3;
    long eip;
    long eflags;
    long eax, ecx, edx, ebx;
    long esp;
    long ebp;
    long esi;
    long edi;
    long es;
    long cs;
    long ss;
    long ds;
    long fs;
    long gs;
    long ldt;
    long trace_bitmap;
    struct i387_struct i387;
};

而 LDT 叫局部描述符表，是与 GDT 全局描述符表相对应的，内核态的代码用 GDT 里的数据段和代码段，而用户进程的代码用每个用户进程自己的 LDT 里得数据段和代码段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct desc_struct {
    unsigned long a,b;
}

struct task_struct * task[64] = {&(init_task.task), };

void sched_init(void) {
    ...
    int i;
    struct desc_struct * p;
        p = gdt+6;
    for(i=1;i<64;i++) {
        task[i] = NULL;
        p->a=p->b=0;
        p++;
        p->a=p->b=0;
        p++;
    }
    ...
}

这段代码有个循环，干了两件事。

一个是给一个长度为 64，结构为 task_struct 的数组 task 附上初始值。

这个 task_struct 结构就是代表每一个进程的信息，这可是个相当相当重要的结构了，把它放在心里。

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
struct task_struct {
/* these are hardcoded - don't touch */
    long state; /* -1 unrunnable, 0 runnable, >0 stopped */
    long counter;
    long priority;
    long signal;
    struct sigaction sigaction[32];
    long blocked; /* bitmap of masked signals */
  /* various fields */
    int exit_code;
    unsigned long start_code,end_code,end_data,brk,start_stack;
    long pid,father,pgrp,session,leader;
    unsigned short uid,euid,suid;
    unsigned short gid,egid,sgid;
    long alarm;
    long utime,stime,cutime,cstime,start_time;
    unsigned short used_math;
  /* file system info */
    int tty;  /* -1 if no tty, so it must be signed */
    unsigned short umask;
    struct m_inode * pwd;
    struct m_inode * root;
    struct m_inode * executable;
    unsigned long close_on_exec;
    struct file * filp[NR_OPEN];
  /* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
    struct desc_struct ldt[3];
  /* tss for this task */
    struct tss_struct tss;
};

这个循环做的另一件事，是给 gdt 剩下的位置填充上 0，也就是把剩下留给 TSS 和 LDT 的描述符都先附上空值。

往后展望一下的话，就是以后每创建一个新进程，就会在后面添加一组 TSS 和 LDT 表示这个进程的任务状态段以及局部描述符表信息。

那为什么一开始就先有了一组 TSS 和 LDT 呢？现在也没创建进程呀。错了，现在虽然我们还没有建立起进程调度的机制，但我们正在运行的代码就是会作为未来的一个进程的指令流。

也就是当未来进程调度机制一建立起来，正在执行的代码就会化身成为进程 0 的代码。所以我们需要提前把这些未来会作为进程 0 的信息写好。

初始化了一组 TSS 和 LDT 后，再往下看两行。

1
2
3
4
5
6
7
8
9
#define ltr(n) __asm__("ltr %%ax"::"a" (_TSS(n)))
#define lldt(n) __asm__("lldt %%ax"::"a" (_LDT(n)))

void sched_init(void) {
    ...
    ltr(0);
    lldt(0);
    ...
}

还记得 lidt 和 lgdt 指令么？一个是给 idtr 寄存器赋值，以告诉 CPU 中断描述符表 idt 在内存的位置；一个是给 gdtr 寄存器赋值，以告诉 CPU 全局描述符表 gdt 在内存的位置。

ltr 是给 tr 寄存器赋值，以告诉 CPU 任务状态段 TSS 在内存的位置；lldt 一个是给 ldt 寄存器赋值，以告诉 CPU 局部描述符 LDT 在内存的位置。

CPU 之后就能通过 tr 寄存器找到当前进程的任务状态段信息，也就是上下文信息，以及通过 ldt 寄存器找到当前进程在用的局部描述符表信息。

我们继续看。

1
2
3
4
5
6
7
8
9
10
void sched_init(void) {
    ...
    outb_p(0x36,0x43);      /* binary, mode 3, LSB/MSB, ch 0 */
    outb_p(LATCH & 0xff , 0x40);    /* LSB */
    outb(LATCH >> 8 , 0x40);    /* MSB */
    set_intr_gate(0x20,&timer_interrupt);
    outb(inb_p(0x21)&~0x01,0x21);
    set_system_gate(0x80,&system_call);
    ...
}

四行端口读写代码，两行设置中断代码。

而这次交互的外设是一个可编程定时器的芯片，这四行代码就开启了这个定时器，之后这个定时器变会持续的、以一定频率的向 CPU 发出中断信号。

而这段代码中设置的两个中断，第一个就是时钟中断，中断号为 0x20，中断处理程序为 timer_interrupt。那么每次定时器向 CPU 发出中断后，便会执行这个函数。

第二个设置的中断叫系统调用 system_call，中断号是 0x80，这个中断又是个非常非常非常非常非常非常非常重要的中断，所有用户态程序想要调用内核提供的方法，都需要基于这个系统调用来进行。

比如 Java 程序员写一个 read，底层会执行汇编指令 int 0x80，这就会触发系统调用这个中断，最终调用到 Linux 里的 sys_read 方法。

中断号 中断处理函数
0 ~ 0x10 trap_init 里设置的一堆
0x20 timer_interrupt
0x21 keyboard_interrupt
0x80 system_call

第十九回 | 操作系统就是用这两个面试常考的结构管理的缓冲区

第19回 | 操作系统就是用这两个面试常考的结构管理的缓冲区 (qq.com)

缓冲区初始化 buffer_init()

首先要注意到，这个函数传了个参数 buffer_memory_end，这个是在老早之前就设置好的，就在第12回 | 管理内存前先划分出三个边界值，回顾下。

而且我们在 第13回 | 主内存初始化 mem_init 中，用 mem_init 设置好了主内存的管理结构 mam_map。

我们还是采用之前的方式，就假设内存只有 8M，把一些不相干的分支去掉，方便理解。

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
extern int end;
struct buffer_head * start_buffer = (struct buffer_head *) &end;

void buffer_init(long buffer_end) {
    struct buffer_head * h = start_buffer;
    void * b = (void *) buffer_end;
    while ( (b -= 1024) >= ((void *) (h+1)) ) {
        h->b_dev = 0;
        h->b_dirt = 0;
        h->b_count = 0;
        h->b_lock = 0;
        h->b_uptodate = 0;
        h->b_wait = NULL;
        h->b_next = NULL;
        h->b_prev = NULL;
        h->b_data = (char *) b;
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
    }
    h--;
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    for (int i=0;i<307;i++)
        hash_table[i]=NULL;
}

虽然很长，但其实就造了两个数据结构而已。

不过别急，我们先看这一行代码。

1
2
3
4
5
extern int end;
void buffer_init(long buffer_end) {
    struct buffer_head * start_buffer = (struct buffer_head *) &end;
    ...
}

这里有个外部变量 end，而我们的缓冲区开始位置 start_buffer 就等于这个变量的内存地址。

这个外部变量 end 并不是操作系统代码写就的，而是由链接器 ld 在链接整个程序时设置的一个外部变量，帮我们计算好了整个内核代码的末尾地址。

那在这之前的是内核代码区域肯定不能用，在这之后的，就给 buffer 用了。所以我们的内存分布图可以更精确一点了。

内核程序和缓冲区的划分，肯定有个分界线，这个分界线就是 end 变量的值。

可是内核程序占多大内存在写的时候完全不知道，就算知道了如果改动一点代码也会变化，所以就由程序编译链接时由链接器程序帮我们把这个内核代码末端的地址计算出来，作为一个外部变量 end 我们拿来即用，就方便多了。

整段代码创造了哪两个管理结构？

我们先看这段结构。

1
2
3
4
5
6
7
8
9
10
11
12
void buffer_init(long buffer_end) {
    struct buffer_head * h = start_buffer;
    void * b = (void *) buffer_end;
    while ( (b -= 1024) >= ((void *) (h+1)) ) {
        ...
        h->b_data = (char *) b;
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
    }
    ...
}

一个是 buffer_head 结构的 h，代表缓冲头，其指针值是 start_buffer，刚刚我们计算过了，就是图中的内核代码末端地址 end，也就是缓冲区开头。

一个是 b，代表缓冲块，指针值是 buffer_end，也就是图中的 2M，就是缓冲区结尾。

缓冲区结尾的 b 每次循环 -1024，也就是一页的值，缓冲区结尾的 h 每次循环 +1（一个 buffer_head 大小的内存），直到碰一块为止。

可以看到，其实这个 b 就代表缓冲块，h 代表缓冲头，一个从上往下，一个从下往上。

而且这个过程中，h 被附上了属性值，其中比较关键的是这个 buffer 所表示的数据部分 b_data，也就是指向了上面的缓冲块 b。

还有这个 buffer 的前后空闲 buffer 的指针 b_prev_free 和 b_next_free。

当缓冲头 h 的所有 next 和 prev 指针都指向彼此时，就构成了一个双向链表。继续看。

1
2
3
4
5
6
7
void buffer_init(long buffer_end) {
    ...
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    ...
}

这三行代码，结合刚刚的双向链表 h，我画出图，你就懂了。

看，free_list 指向了缓冲头双向链表的第一个结构，然后就可以顺着这个结构，从双向链表中遍历到任何一个缓冲头结构了，而通过缓冲头又可以找到这个缓冲头对应的缓冲块。

简单说，缓冲头就是具体缓冲块的管理结构，而 free_list 开头的双向链表又是缓冲头的管理结构，整个管理体系就这样建立起来了。

现在，从 free_list 开始遍历，就可以找到这里的所有内容了。

不过，还有最后一个事，能帮助更好管理，往下看。

1
2
3
4
5
void buffer_init(long buffer_end) {
    ...
    for (i=0;i<307;i++)
        hash_table[i]=NULL;
}

一个 307 大小的 hash_table 数组，这是干嘛的呢？

其实今天的这个代码在 buffer.c 中，而 buffer.c 是在 fs 包下的，也就是文件系统包下的。所以它今后是为文件系统而服务，具体是内核程序如果需要访问块设备中的数据，就都需要经过缓冲区来间接地操作。

也就是说，读取块设备的数据（硬盘中的数据），需要先读到缓冲区中，如果缓冲区已有了，就不用从块设备读取了，直接取走。

那怎么知道缓冲区已经有了要读取的块设备中的数据呢？从双向链表从头遍历当然可以，但是这效率可太低了。所以需要一个 hashmap 的结构方便快速查找，这就是 hash_table 这个数组的作用。

之后当要读取某个块设备上的数据时，首先要搜索相应的缓冲块，是下面这个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define _hashfn(dev,block) (((unsigned)(dev^block))%307)
#define hash(dev,block) hash_table[_hashfn(dev,block)]

// 搜索合适的缓冲块 
struct buffer_head * getblk(int dev,int block) {
    ...
    struct buffer_head bh = get_hash_table(dev,block)；
    ...
}

struct buffer_head * get_hash_table(int dev, int block) {
    ...    
    find_buffer(dev,block);
    ...
}

static struct buffer_head * find_buffer(int dev, int block) { 
    ...     
    hash(dev,block);
    ...
}

一路跟下来发现，就是通过

dev^block % 307

即

(设备号^逻辑块号) Mod 307

找到在 hash_table 里的索引下标，接下来就和 Java 里的 HashMap 类似，如果哈希冲突就形成链表，画成图就是这样。

回过头来看看我们目前的进度吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void main(void) {
    ...
    mem_init(main_memory_start,memory_end);
    trap_init();
    blk_dev_init();
    chr_dev_init();
    tty_init();
    time_init();
    sched_init();
    buffer_init(buffer_memory_end);
    hd_init();
    floppy_init();
    
    sti();
    move_to_user_mode();
    if (!fork()) {init();}
    for(;;) pause();
}

整个初始化的部分，就差 hd_init 和 floppy_init 这两个块设备的初始化还没讲了。

而且幸运的是，floppy_init 是软盘初始化，现在软盘几乎都被淘汰了，计算机中也没有软盘驱动器了，所以这个我们完全可以不看，那就剩下一个 hd_init 硬盘初始化了，非常简单！

任何操作系统的管理都离不开这些初始化工作所建立的数据结构

第二十回 | 硬盘初始化

第20回 | 硬盘初始化 hd_init (qq.com)

我们直接看 hd_init 这个硬盘初始化干了什么？

1
2
3
4
5
6
7
8
9
10
11
12
//struct blk_dev_struct {
//    void (*request_fn)(void);
//    struct request * current_request;
//};
//extern struct blk_dev_struct blk_dev[NR_BLK_DEV];

void hd_init(void) {
    blk_dev[3].request_fn = do_hd_request;
    set_intr_gate(0x2E,&hd_interrupt);
    outb_p(inb_p(0x21)&0xfb,0x21);
    outb(inb_p(0xA1)&0xbf,0xA1); 
}

就这？一共就四行代码。

没错，初始化嘛，往往都比较简单，尤其是对硬件设备的初始化，大体都是：

1. 往某些 IO 端口上读写一些数据，表示开启它；

2. 然后再向中断向量表中添加一个中断，使得 CPU 能够响应这个硬件设备的动作；

3. 最后再初始化一些数据结构来管理。不过像是内存管理可能结构复杂些，外设的管理，相对就简单很多了。

看第一行代码：

1
2
3
4
void hd_init(void) {
    blk_dev[3].request_fn = do_hd_request;
    ...
}

我们把 blk_dev 数组索引 3 位置处的块设备管理结构 blk_dev_struct 的 request_fn 赋值为了 do_hd_request，这是啥意思呢？

因为有很多块设备，所以 Linux 0.11 内核用了一个 blk_dev[] 来进行管理，每一个索引表示一个块设备。

Linux 0.11 内核用了一个 blk_dev[] 来进行管理，每一个索引表示一个块设备。

1
2
3
4
5
6
7
8
9
struct blk_dev_struct blk_dev[NR_BLK_DEV] = {
    { NULL, NULL },     /* no_dev */
    { NULL, NULL },     /* dev mem */
    { NULL, NULL },     /* dev fd */
    { NULL, NULL },     /* dev hd */
    { NULL, NULL },     /* dev ttyx */
    { NULL, NULL },     /* dev tty */
    { NULL, NULL }      /* dev lp */
};

你看，索引为 3 这个位置，就表示给硬盘 hd 这个块设备留的位置。

那么每个块设备执行读写请求都有自己的函数实现，在上层看来都是一个统一函数 request_fn 即可，具体实现各有不同，对于硬盘来说，这个实现就是 do_hd_request 函数。

我们再看第二行。

1
2
3
4
5
void hd_init(void) {
    ...
    set_intr_gate(0x2E,&hd_interrupt);
    ...
}

对于中断我们已经很熟悉了，这里就是又设置了一个新的中断，中断号是 0x2E，中断处理函数是 hd_interrupt，也就是说硬盘发生读写时，硬盘会发出中断信号给 CPU，之后 CPU 便会陷入中断处理程序，也就是执行 hd_interrupt 函数。

1
2
3
4
5
6
7
8
9
10
11
_hd_interrupt:
    ...
    xchgl _do_hd,%edx
    ...
    
// 如果是读盘操作，这个 do_hd 是 read_intr
static void read_intr(void) {
    ...
    do_hd_request();
    ...
}

好了，又多了一个中断，那我们再次梳理下目前开启的中断都有哪些。

中断号 中断处理函数
0 ~ 0x10 trap_init 里设置的一堆
0x20 timer_interrupt
0x21 keyboard_interrupt
0x2E hd_interrupt
0x80 system_call

看到最后，你会发现操作系统就是一个靠中断驱动的死循环而已，如果不发生任何中断，操作系统会一直在一个死循环里等待。换句话说，让操作系统工作的唯一方式，就是触发中断。

1
2
3
4
5
void hd_init(void) {
    ...
    outb_p(inb_p(0x21)&0xfb,0x21);
    outb(inb_p(0xA1)&0xbf,0xA1); 
}

就是往几个 IO 端口上读写，其作用是允许硬盘控制器发送中断请求信号，仅此而已。

看看读硬盘最最底层的操作流程，是怎样的。

我们看硬盘的端口表。

端口 读 写
0x1F0 数据寄存器 数据寄存器
0x1F1 错误寄存器 特征寄存器
0x1F2 扇区计数寄存器 扇区计数寄存器
0x1F3 扇区号寄存器或 LBA 块地址 0~7 扇区号或 LBA 块地址 0~7
0x1F4 磁道数低 8 位或 LBA 块地址 8~15 磁道数低 8 位或 LBA 块地址 8~15
0x1F5 磁道数高 8 位或 LBA 块地址 16~23 磁道数高 8 位或 LBA 块地址 16~23
0x1F6 驱动器/磁头或 LBA 块地址 24~27 驱动器/磁头或 LBA 块地址 24~27
0x1F7 命令寄存器或状态寄存器 命令寄存器

那读硬盘就是，往除了第一个以外的后面几个端口写数据，告诉要读硬盘的哪个扇区，读多少。然后再从 0x1F0 端口一个字节一个字节的读数据。这就完成了一次硬盘读操作。

1. 在 0x1F2 写入要读取的扇区数

2. 在 0x1F3 ~ 0x1F6 这四个端口写入计算好的起始 LBA 地址

3. 在 0x1F7 处写入读命令的指令号

4. 不断检测 0x1F7 （此时已成为状态寄存器的含义）的忙位

5. 如果第四步骤为不忙，则开始不断从 0x1F0 处读取数据到内存指定位置，直到读完

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void hd_out(unsigned int drive,unsigned int nsect,unsigned int sect,
        unsigned int head,unsigned int cyl,unsigned int cmd,
        void (*intr_addr)(void)) {
    ...
    do_hd = intr_addr;
    outb_p(hd_info[drive].ctl,HD_CMD);
    port = 0x1f0;
    outb_p(hd_info[drive].wpcom>>2,++port);
    outb_p(nsect,++port);
    outb_p(sect,++port);
    outb_p(cyl,++port);
    outb_p(cyl>>8,++port);
    outb_p(0xA0|(drive<<4)|head,++port);
    outb(cmd,++port);
}

第二部分完结

第二部分完结撒花！大战前期的初始化工作 (qq.com)

操作系统
你管这破玩意儿叫操作系统源码(五)
https://www.spacezxy.top/2023/04/05/OperatingSystem/Operating-system-source-code-5/
作者
Xavier ZXY
发布于
2023年4月5日
许可协议