极简
文章
145
分类
10
评论
1

线程-进阶-任务调度

| 自制操作系统 •
字数总计 60778 | 阅读时长 151分钟 | 阅读量 42

前置内容：线程-基础-加载线程
本节分支：thread-schedule

概览

  • 任务链表
    通常使用链表来维护任务队列。链表本身不是本节的重点，所以笔者将其放在文末。
  • 任务调度基础
    基于上节内容对 thread.c 和 thread.h 进行改进。
  • 任务切换
    改进时钟中断，添加任务调度器，开始任务切换。

任务调度基础

thread.h

//thread.h
struct task_struct 
{
    uint32_t* self_kstack;	      
    enum task_status status;
    char name[16];
    uint8_t priority;
    uint8_t ticks;	              
    uint32_t elapsed_ticks;       
    struct list_elem general_tag; 
    struct list_elem all_list_tag;
    uint32_t* pgdir;              
    uint32_t stack_magic;         
};

thread.h 中只对 task_struct 添加了一些成员：

  • ticks： 时间片，任务刚被调度时，时间片被初始化为 priority，随后每发生一次时钟中断 ticks 就减 1，减到 0 后被换下 CPU 。
  • elapsed_ticks： 记录该任务一共被运行了多少 CPU 滴答数。它和 ticks 的区别是：ticks 减到 0 时任务被换下 CPU，但此时任务可能还未执行完毕，所以重新加入到任务队列等待下一次被调度。所以，elapsed_ticks 记录的是从任务初次被调度到任务执行结束所经过的总滴答数，而 ticks 只是任务的一次倒计时。
  • general_tag： 当任务处于就绪或其他等待状态时，需要把该 tag 添加到 thread_ready_list 或其他相应等待队列中。将 tag 加入到队列就相当于将 task_struct 加入到队列吗？是的，可以通过 tag 来定位 task_struct，原因很简单，因为这些 tag 本来就位于 task_struct 内存中，只需要根据成员的偏移量就能反向推断出 task_struct 的地址。文末会演示这一过程。
    通过tag将各个PCB连接成队列
  • all_list_tag： thread_all_list 用来管理所有任务，所有任务的 all_list_tag 都需要加入到 thread_all_list 中。
  • pgdir： 上节提到过，对于进程，pgdir 指向自己的页目录表；对于线程，pgdir 被初始化为 NULL 。注意，pgdir 中装的是虚拟地址，经过手动转换变成物理地址后才会加载进 CR2 ，这是后话。

thread.c

#define PG_SIZE 4096

struct task_struct* main_thread;    // 主线程PCB
struct list thread_ready_list;	    // 就绪队列
struct list thread_all_list;	    // 所有任务队列
static struct list_elem* thread_tag;// 用于保存队列中的线程结点
static uint32_t tmp_esp;

/* 获取当前线程pcb指针 */
struct task_struct* running_thread() 
{
    asm volatile("mov tmp_esp,esp");
    /* 取esp整数部分即pcb起始地址 */
    return (struct task_struct*)(tmp_esp & 0xfffff000);
}

/* 由kernel_thread去执行function(func_arg) */
static void kernel_thread(thread_func* function, void* func_arg) 
{
/* 执行function前要开中断,避免后面的时钟中断被屏蔽,而无法调度其它线程 */
    intr_enable();
    function(func_arg);
}

/* 初始化线程栈thread_stack,将待执行的函数和参数放到thread_stack中相应的位置 */
void thread_create(struct task_struct* pthread, thread_func function, void* func_arg) 
{
    /* 先预留中断使用栈的空间,可见thread.h中定义的结构 */
    pthread->self_kstack -= sizeof(struct intr_stack);

    /* 再留出线程栈空间,可见thread.h中定义 */
    pthread->self_kstack -= sizeof(struct thread_stack);
    struct thread_stack* kthread_stack = (struct thread_stack*)pthread->self_kstack;
    kthread_stack->eip = kernel_thread;
    kthread_stack->function = function;
    kthread_stack->func_arg = func_arg;
    kthread_stack->ebp = kthread_stack->ebx = kthread_stack->esi = kthread_stack->edi = 0;
}

/* 初始化线程基本信息 */
void init_thread(struct task_struct* pthread, char* name, int prio) 
{
    memset(pthread, 0, sizeof(*pthread));
    strcpy(pthread->name, name);

    if (pthread == main_thread)
        pthread->status = TASK_RUNNING;
    else
        pthread->status = TASK_READY;
    
    pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
    pthread->priority = prio;
    pthread->ticks = prio;
    pthread->elapsed_ticks = 0;
    pthread->pgdir = NULL;
    pthread->stack_magic = 0x19870916;	  // 自定义的魔数
}


struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg) 
{
    struct task_struct* thread = get_kernel_pages(1);
    init_thread(thread, name, prio);
    thread_create(thread, function, func_arg);
    /* 确保之前不在队列中 */
    assert(!elem_find(&thread_ready_list, &thread->general_tag));
    /* 加入就绪线程队列 */
    list_append(&thread_ready_list, &thread->general_tag);
    /* 确保之前不在队列中 */
    assert(!elem_find(&thread_all_list, &thread->all_list_tag));
    /* 加入全部线程队列 */
    list_append(&thread_all_list, &thread->all_list_tag);
    return thread;
}

/* 将kernel中的main函数完善为主线程 */
static void make_main_thread()
{
/* 因为main线程早已运行,咱们在guide.S中进入内核时mov esp,0xc009f000,
已经为其预留了pcb,地址为0xc009e000,因此不需要通过get_kernel_page另分配一页*/
    main_thread = running_thread();
    init_thread(main_thread, "main", 31);

/* main函数就是当前线程,当前线程不在thread_ready_list中,
 * 所以只将其加在thread_all_list中. */
    assert(!elem_find(&thread_all_list, &main_thread->all_list_tag));
    list_append(&thread_all_list, &main_thread->all_list_tag);

}

/* 任务调度 */
void schedule() 
{

    assert(intr_get_status() == INTR_OFF);

    struct task_struct* cur = running_thread();
    if (cur->status == TASK_RUNNING)    // 若当前线程只是时间片到了,将其加入到就绪队列尾,等待重新被调度
    {  
        assert(!elem_find(&thread_ready_list, &cur->general_tag));
        list_append(&thread_ready_list, &cur->general_tag);
        cur->ticks = cur->priority;     // 重新将当前线程的ticks再重置为其priority;
        cur->status = TASK_READY;
    } 
    else
    {
        // 若当前线程是被阻塞了,则不需要将其加入到就绪队列中
    }
    assert(!list_empty(&thread_ready_list));
    thread_tag = NULL;	  
    
    //将thread_ready_list队列中的第一个就绪线程弹出,准备将其调度上cpu.
    thread_tag = list_pop(&thread_ready_list);
    struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag);
    next->status = TASK_RUNNING;
    switch_to(cur, next);
}

/* 初始化线程环境 */
void thread_init(void) {
    put_str("thread_init start\n",DEFUALT);
    list_init(&thread_ready_list);
    list_init(&thread_all_list);
/* 将当前main函数创建为线程 */
    make_main_thread();
    put_str("thread_init done\n",DEFUALT);
}

老规矩，讲解以上代码前先理理脉络：

  1. 开启线程机制前需要调用 thread_init() 来初始化线程环境，内容包括初始化就绪任务链表和所有任务链表、创建 main 线程。
  2. 初始化线程环境后即可调用 thread_start() 创建线程。在此函数中进入如下动作：
    1）调用 init_thread() 初始化线程信息，
    2）调用 thread_create() 将线程函数及其参数写入到线程栈中。
    3）将该线程加入到 thread_ready_list 和 thread_all_list 中。
  3. 随后等待调度。

下面进行代码讲解：

  • 第 12 行，使用内联汇编取得当前 esp 的值。和之前一样，内联汇编中用到的 C 变量必须是全局或者全局静态变量，因此使用全局静态变量 tmp_esp 中转。

  • 第 14 行，因为栈位于 PCB 中，而 PCB 大小为一页，所以将 esp 向下取页框，即得 PCB 起始地址。

  • 第 21 行，进入线程函数 function() 前需要先打开中断，这里需要重点说明其原因：任务切换是由时钟中断驱动的，也就是说，schedule() 是在时钟中断里被调用的，任务调度后直接进入 function() 执行任务 ，并不会返回中断（iret） ，这样一来，就相当于任务的调度和执行都发生在中断里。咋们之前说过，进入中断后 IF 位自动置 0，也就是屏蔽外部中断，如此一来，进入该任务后就无法发生时钟中断来调度其他任务啦，于是，该任务独占了 CPU 控制权！为了防止这种情况发生，我们需要在进入任务前手动开启中断 ！！！

  • 第 68 行，只有将该任务加入到 thread_ready_list 队列中，才会被 CPU 调度 ；目前还没有体现到 thread_all_list 的作用，后续才会用到该队列。

  • 第 77 行，从 CPU 被启动的那一刻，执行流就一直在按我们的代码运行。现在，我们要将该执行流也包装成线程（即kernel_main线程）并加入到队列中，否则调度其他任务后就没法回到主线程了 。注意 guide.s ：

    [BITS 32]
extern kernel_main
global _start
section .text
_start:
    mov esp, 0xc009f000
    jmp kernel_main

    第 6 行，进入内核前必须将 esp 指向主线程 PCB 的顶端，即 0xc009f00 处，否则无法根据 esp 定位到 PCB 。

  • 第 92 行，schedule() 函数可能在时钟中断里被调用，也可能被后续将要说到的 thread_block() 函数调用。因此，在 schedule() 中需要考虑当前线程是出于什么原因才被换下 CPU 的，是因为时间片到期？还是说被阻塞了？所以必须针对不同的状态做出相应的应对措施 。另外，最下方调用的 switch_to 是汇编函数，下文会重点讲解。

  • 第 109 行，由于我们还未实现 idle 线程，所以就绪队列可能为空，为了避免无线程可调度的情况，暂用 assert 来保障。

  • 第 114 行，elem2entry() 是宏函数，用来将 general_tag 或 all_list_tag 转换为对应的 task_strcut 指针。此函数在文末介绍链表时会谈到。

其他就没什么好说的了，下面进入正题。

任务切换

我们采用的调度方式是 轮询（Round-Robin，RR） ，这是一种基础的调度方式。轮询，说白了就是按先进先出（FIFO）的顺序一个一个调度。切换任务时，从 thread_ready_list 弹出队首，并将其调度上 CPU 。注意，正在执行的任务的状态是 RUNNING，该任务不在 thread_ready_list 中，而在 thread_all_list 中。

完整的任务调度分为三个大步：

  1. 进入时钟中断
  2. 时钟中断调用 schedule()
  3. schedule() 调用 switch_to()

1.进入时钟中断
还记得吗？在加入中断一文中，我们将每个中断处理函数都统一初始化为 general_intr_handler() ，这是一般化函数，只是用来告诉我们发生了什么中断，以便于排错。现在咋们就需要将时钟中断专门化了，见以下代码：

//idt.c
//.......
void register_handler(uint8_t vector_no, intr_handler function)
{
    interrupt_handler_table[vector_no] = function;
}

//timer.c

uint32_t ticks;          // ticks是内核自中断开启以来总共的嘀嗒数
/* 时钟的中断处理函数 */
static void intr_timer_handler(void)
{
    struct task_struct* cur_thread = running_thread();

    assert(cur_thread->stack_magic == 0x19870916);  // 检查栈是否溢出

    cur_thread->elapsed_ticks++;                    // 记录此线程占用的cpu时间嘀
    ticks++;	  //从内核第一次处理时间中断后开始至今的滴哒数,内核态和用户态总共的嘀哒数

    if (cur_thread->ticks == 0)                     // 若进程时间片用完就开始调度新的进程上cpu
        schedule();
    else                                            // 将当前进程的时间片-1
        cur_thread->ticks--;

}

void timer_init()
{
    put_str("timer_init start...\n",DEFUALT);
    frequency_set(CONTRER0_PORT, COUNTER0_NO, READ_WRITE_LATCH, COUNTER_MODE, COUNTER0_VALUE);
    register_handler(0x20, intr_timer_handler);  
    put_str("timer_init done: Clock interrupt frequency increased to 100Hz\n",DEFUALT);
}
  • 全局变量 ticks 用来记录自中断开启后经历的总滴答数，类似于系统运行时长的概念。该变量当前保留，未来可能会用到。
  • 第 14 行，cur_thread->ticks == 0 意味着该任务还未结束，但时间片已经到期 ，所以进入 schedule() ，将该任务重新放入队尾等待下一次调度。
  • 第 25 行，注册专门的时钟中断。

进入schedule()

上文已作讲解，不再说明。

进入switch_to

[bits 32]
section .text
global switch_to
switch_to:
   ;栈中此处是返回地址
   push esi
   push edi
   push ebx
   push ebp

   mov eax, [esp + 20]     ; 得到栈中的参数cur, cur = [esp+20]
   mov [eax], esp          ; 保存栈顶指针esp
                           
                           
;------------------  以上是保存当前线程的栈，下面是恢复下一个线程的栈  ----------------
   mov eax, [esp + 24]     ; 得到栈中的参数next, next = [esp+24]
   mov esp, [eax]          ; 恢复esp
                           
   pop ebp
   pop ebx
   pop edi
   pop esi
   ret                     ;第一次执行时会返回到kernel_thread
                           ;后续执行则会返回到schedule函数
  • 关于 esi、edi、ebx、ebp 的压栈问题已在线程-基础-加载线程中阐述。
  • 参数 cur 和 next 分别是当前任务和下个任务的 task_struct 指针，需要强调的是，由于 task_struct 的首个成员是 self_kstack，所以可以认为 cur 和 next 指针也是指向 self_kstack ！这样一来，self_kstack 的真正作用便清晰了——记录线程被换下瞬间的 esp 值 。

switch_to 是任务调度的核心，它向我们直接展示了操作系统是如何通过栈切换来完成任务调度的 。不过，大家可能还是很迷糊，不急，让我们看看实际的调度过程：

以下解析的步骤和上图的序号相对应

  1. 当前执行流位于 kernel_main() 主线程，esp 当然也位于 kernel_main 的 PCB 顶端。某一时刻，时钟中断发生，中断压栈保护任务现场 ，接着进入 schedule() ，进而到 switch_to() 。switch_to() 前半段将当前 esp 的值保存到 kernel_main 的 self_kstack 中。

    为什么 cur 和 中断栈之间还有个省略号？这只是想告诉大家，实际的线程栈情况和 thread_stack 结构体并不能一一对应，比如，调用 schedule() 函数还需要将返回地址压栈呢，而这个并没有考虑进 thread_stack 或 intr_stack ，所以栈中的数据实际上是错位的！不能通过该结构体取得栈内对应的值。intr_stack 也同样不能对应，比如，在 kernel_main() 中调用了一个函数，执行此函数时发生中断，此时的 esp 就不是从 0xc009f000 开始的啦！

  2. 执行 mov esp,[eax] 后即完成栈切换。注意，这个新任务是首次被调度的，它的线程栈已经在 thread_create() 中被我们设计好了 。

    为啥没省略号了？因为现在对齐啦！！！要知道，在 thread_create() 中，我们跳过了中断栈和线程栈，将 self_kstack 不偏不倚地指向了线程栈的起点，所以这里是完全对齐了的，也是基于这一点，下面的 pop 和 ret 才能正确执行。

  3. 四次 pop 并 ret，成功进入 eip 对应的 kernel_thread() ，进而 function() ，任务开始执行。

  4. 某时刻，中断再次发生，中断压栈，再一路来到 switch_to() 上半部分，即保存当前栈。注意，由图可见，此时中断压栈是发生在线程栈中而非中断栈中！

    注意步骤 3 和步骤 4 的栈中的 eip 差异，这点差异非常重要！步骤 3 中的 eip 是我们设计好的，指向 kernel_thread() ；而步骤 4 中的 eip 是 schedule() 中调用 switch_to() 时留下的返回地址，也就是说将来会通过这个 eip 回到 schedule() 。
    另外再次强调，中断之所以能够再次发生，是因为我们进入 function() 前手动打开了中断，这并不是 iret 的功劳。

  5. 执行 switch_to() 的下半部分，mov esp,[eax] ，切换任务栈。

  6. 接着 pop 并 ret，依次退出 switch_to() 、schedule() 和中断函数，恢复 kernel_main() 的任务。

  7. 一段时间后，中断发生，保存当前栈。

  8. 恢复之前的栈。此时的 eip 是 schedule() 留下的返回地址（而非 kernel_thread 的地址）。

  9. pop 并 ret，依次退出 switch_to() 、schedule() 和中断函数，恢复线程任务。

    可见，该线程的线程栈栈底将一直存留这三个参数，这并不重要。问题是，当任务结束后，kernel_thread() 该如何返回呢？这个占位符原本应该是 switch_to 调用 kernel_thread() 留下的返回地址，但现在它仅是一个占位符，这意味着任务结束后 kernel_thread() 将无法正常返回！ 所以，在我们的操作系统中，线程返回不能通过普通 return 的方式进行 ，而要专门调用一个线程退出函数（ thread_exit() ）来结束任务，这是后话，目前我们的策略是强制要求在任务末端放一个 while(1) ，以避免任务结束。关于这点的实验演示见以下视频。

为什么使用 ret 来调用 kernel_thread() ？
从上面的过程你可以发现，switch_to 的最后一句 ret ，在线程首次被调度时，是进入 kernel_thread() ；后续被调度时，则是返回到主调函数 schedule() 中。所以此处的 ret 有双重作用！而你可以通过 ret 调用 kernel_thread，也可以使用 ret 来返回 schedule，但你可不能使用 call 来返回 schedule 吧？这也是为什么要使用 ret 而非 call 来调用 kernel_thread() 的原因！

{%
dplayer
“url=/2022/video/thread_exit.mp4”
“pic=/2022/image/1.jpg” //设置封面图，同样是放在根目录下面
“loop=false” //循环播放
“theme=#FADFA3” //主题
“autoplay=false” //自动播放
“screenshot=true” //允许截屏
“hotkey=true” //允许hotKey，比如点击空格暂停视频等操作
“preload=auto” //预加载：auto
“volume=0.9” //初始音量
“playbackSpeed=1”//播放速度1倍速，可以选择1.5,2等
“lang=zh-cn”//语言
“mutex=true”//播放互斥，就比如其他视频播放就会导致这个视频自动暂停

​ “id=9E2E3368B56CD123BB4”
​ “api=https://api.prprpr.me/dplayer/”
​ “token=tokendemo”
​ “maximum=1000”
​ “addition=[‘https://api.prprpr.me/dplayer/v3/bilibili?aid=4157142’]”
​ “user=DIYgod”
​ “bottom=15%”
​ “unlimited=true”

%}

可见，一旦任务退出，就引发缺页异常。不知道有没有眼尖的小伙伴看见 while 语句中，打印语句上下的 STI 和 CLI ？为什么要在 put_str() 的上下分别放置这两条语句呢？先让我们看看，如果去掉这两条语句会发生什么：

{%
dplayer
“url=/2022/video/thread_intr.mp4”
“pic=/2022/image/1.jpg” //设置封面图，同样是放在根目录下面
“loop=false” //循环播放
“theme=#FADFA3” //主题
“autoplay=false” //自动播放
“screenshot=true” //允许截屏
“hotkey=true” //允许hotKey，比如点击空格暂停视频等操作
“preload=auto” //预加载：auto
“volume=0.9” //初始音量
“playbackSpeed=1”//播放速度1倍速，可以选择1.5,2等
“lang=zh-cn”//语言
“mutex=true”//播放互斥，就比如其他视频播放就会导致这个视频自动暂停

​ “id=9E2E3368B56CD123BB4”
​ “api=https://api.prprpr.me/dplayer/”
​ “token=tokendemo”
​ “maximum=1000”
​ “addition=[‘https://api.prprpr.me/dplayer/v3/bilibili?aid=4157142’]”
​ “user=DIYgod”
​ “bottom=15%”
​ “unlimited=true”

%}
看见了吗？若去掉 STI 和 CLI ，则会发生 0xd 号异常。这涉及到锁相关的内容，将在下节内容详细介绍。

另外，说说笔者在这里遇见的一个大坑，看下面的 interrupt.s ：

//修改后的interrupt.s
%macro VECTOR 2
INTERRUPT_ENTRY_%1:        ;中断处理entry
    %2
    push ds
    push es
    push fs
    push gs
    pushad

    mov al,0x20            ;中断结束命令EOI
    out 0xa0,al            ;向从片发送
    out 0x20,al            ;向主片发送

    push dword %1
    call [interrupt_handler_table + %1*4]
    add esp, 4             ;外平栈

    popad
    pop gs
    pop fs
    pop es
    pop ds

    add esp,4			   ;跨过error_code,以保持堆栈平衡
    iret				   ;从中断返回,32位下等同指令iretd

上面是修改后的 interrupt.s ，也就是现在的版本。而之前，笔者是像下面这样写的：

%macro VECTOR 2
INTERRUPT_ENTRY_%1:        ;中断处理entry
    %2
    push ds
    push es
    push fs
    push gs
    pushad

    push dword %1
    call [interrupt_handler_table + %1*4]
    add esp, 4             ;外平栈

    popad
    pop gs
    pop fs
    pop es
    pop ds

    mov al,0x20            ;中断结束命令EOI
    out 0xa0,al            ;向从片发送
    out 0x20,al            ;向主片发送

    add esp,4			   ;跨过error_code,以保持堆栈平衡
    iret				   ;从中断返回,32位下等同指令iretd

嗯？只是处理 EOI 的代码改变了位置，有什么影响吗？影响可大了！前文已经强调，任务调度在时钟中断处理函数(第11行)中进行的，调度完成后直接开始执行任务，并不会返回到中断内并执行末尾的 iret 指令；而中断发生后 CPU 会自动将 IF 位置零来屏蔽外部中断，因此，为了防止任务独占 CPU，任务（即function())正式开始前还要手动开中断。问题来了，8259A 芯片发送中断信号后，必须要收到 CPU 发来的 EOI 结束命令后才会继续发送中断，否则即使你开了中断也没用！ 所以，按上面的写法，进入第 11 行时钟中断处理函数后，压根不会执行后面的 EOI 发送代码，时钟中断无法产生，后续的任务调度也就没法进行了！这里坑了笔者两天之久！

链表

双向链表是用来维护任务队列的核心数据结构。数据结构不是本系列博客的重点，所以就不详细展开了，仅强调几个要点。

//list.h
#define offset(struct_type,member) (int)(&((struct_type*)0)->member)
#define elem2entry(struct_type, struct_member_name, elem_ptr) \
        (struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))

struct list_elem 
{
    struct list_elem* prev;  // 前躯结点
    struct list_elem* next;  // 后继结点
};

struct list 
{
    struct list_elem head;   //头节点
    struct list_elem tail;   //尾节点
};

//自定义函数类型function,用于在list_traversal中做回调函数
typedef bool (function)(struct list_elem*, int);

void list_init (struct list*);
void list_insert_before(struct list_elem* before, struct list_elem* elem);
void list_push(struct list* plist, struct list_elem* elem);
void list_iterate(struct list* plist);
void list_append(struct list* plist, struct list_elem* elem);
void list_remove(struct list_elem* pelem);
struct list_elem* list_pop(struct list* plist);
bool list_empty(struct list* plist);
uint32_t list_len(struct list* plist);
struct list_elem* list_traversal(struct list* plist, function func, int arg);
bool elem_find(struct list* plist, struct list_elem* obj_elem);

  • offset 宏用来计算结构体内的某成员相对于该结构体起始处的偏移量。这个操作很骚，可以说将指针运用得炉火纯青了：

    (int)(&((struct_type*)0)->member)

    将 0 强制转换为 struct_type* 指针，换句话说，该指针指向 struct_type 类型的结构体，而该结构体位于地址 0x0000 处 。如此一来，由于是以地址 0x0000 为基准，所以该结构体中成员的地址即为此成员相对于该结构体的偏移量。

  • elem2entry 宏就好说了，用 tag 指针减去 tag 偏移量即得结构体的起始地址。

    struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag); //thread.c第114行

    那么，为什么这两个操作设计成宏而非函数呢？留给读者自己思考。

  • 注意，list 中的 head 是头节点，而非首元节点；尾节点同理；节点只会插在 head 与 tail 之间。

    头节点是一个不存放任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题 ；
    首元节点是链表中第一个存有数据的节点；首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；

  • 第 19 行，自定义函数类型，该类型在 list_traversal() 中作为回调函数的类型。如果不使用 typedef，那么第 30 行声明就需改成：

    struct list_elem* list_traversal(struct list* plist, bool (func)(struct list_elem*, int), int arg);

    显然，这种方式没有上一种方式好看。list_traversal() 函数当前还未使用，后续用到了再介绍。

//list.c
/* 初始化双向链表list */
void list_init (struct list* list)
{
    list->head.prev = NULL;
    list->head.next = &list->tail;
    list->tail.prev = &list->head;
    list->tail.next = NULL;
}

/* 把链表元素elem插入在元素before之前 */
void list_insert_before(struct list_elem* before, struct list_elem* elem)
{
    enum intr_status old_status = intr_disable();
    before->prev->next = elem;
    elem->prev = before->prev;
    elem->next = before;
    before->prev = elem;
    intr_set_status(old_status);
}

/* 添加元素到列表队首 */
void list_push(struct list* plist, struct list_elem* elem)
{
    list_insert_before(plist->head.next, elem);
}

/* 追加元素到链表队尾 */
void list_append(struct list* plist, struct list_elem* elem)
{
    list_insert_before(&plist->tail, elem); 
}

/* 使元素pelem脱离链表 */
void list_remove(struct list_elem* pelem)
{
    enum intr_status old_status = intr_disable();
    pelem->prev->next = pelem->next;
    pelem->next->prev = pelem->prev;
    intr_set_status(old_status);
}

/* 将链表第一个元素弹出并返回,类似栈的pop操作 */
struct list_elem* list_pop(struct list* plist)
{
    struct list_elem* elem = plist->head.next;
    list_remove(elem);
    return elem;
}

/* 从链表中查找元素obj_elem,成功时返回true,失败时返回false */
bool elem_find(struct list* plist, struct list_elem* obj_elem)
{
    struct list_elem* elem = plist->head.next;
    while (elem != &plist->tail)
    {
        if (elem == obj_elem)
            return true;
        elem = elem->next;
    }
    return false;
}

/* 把列表plist中的每个元素elem和arg传给回调函数func,
 * arg给func用来判断elem是否符合条件.
 * 本函数的功能是遍历列表内所有元素,逐个判断是否有符合条件的元素。
 * 找到符合条件的元素返回元素指针,否则返回NULL. */
struct list_elem* list_traversal(struct list* plist, function func, int arg) {
    struct list_elem* elem = plist->head.next;
    if (list_empty(plist))
        return NULL;
    while (elem != &plist->tail)
    {
        if (func(elem, arg))   
            return elem;
        elem = elem->next;     

    }
    return NULL;
}

/* 返回链表长度 */
uint32_t list_len(struct list* plist)
{
    struct list_elem* elem = plist->head.next;
    uint32_t length = 0;
    while (elem != &plist->tail)
    {
        length++;
        elem = elem->next;
    }
    return length;
}

/* 判断链表是否为空,空时返回true,否则返回false */
bool list_empty(struct list* plist)
{
    return (plist->head.next == &plist->tail ? true : false);
}

上面的函数都是常规的链表操作，不再解释。

本文结束。经过这两节的煎熬，想必读者朋友们也憔悴了吧？哈哈，休息再战！

文章作者： 极简
本文链接：
版权声明： 本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 后端技术分享！
自制操作系统
喜欢就支持一下吧