操作系统真象还原 学习笔记10--线程

selph
selph
发布于 2021-02-08 / 882 阅读
0
0

操作系统真象还原 学习笔记10--线程

本篇对应书籍第九章的内容

本篇内容介绍了线程是什么,多线程的原理,多线程用到的核心数据结构,以及通过代码实现了内核多线程的调度

本篇难点:

  • 理解线程是什么

线程是什么?

执行流

过去,计算机只有一个处理器,一次只能处理一个任务,下一个任务就得等这个任务执行完才能继续执行,为了不让大任务彻底把操作系统给堵塞,于是后来就出现了多任务操作系统,在单核CPU下,多任务是通过“伪并行”的方式实现的:

CPU执行每个任务就执行一会(一定CPU周期),然后切换执行下一个任务执行,以此循环

这个功能由软件实现,实现这个功能的软件叫做任务调度器(任务切换本质上就是改变了CPU中程序计数器的指向)

我们把程序计数器中下一条指令的地址所组成的执行的轨迹称为执行流

任何代码块都可以是执行流(大到整个程序文件即进程、小到一个函数即线程),只要在运行的时候,我们提供好上下文环境即可,上下文环境就是寄存器映像、栈、内存等

在任务调度器眼里,执行流是调度单元,也是处理器的基本执行单位

线程

线程的本质是函数的另一种执行方式,线程是一套机制,能够让所运行的函数能够以调度单元的身份独立上处理器进行执行,函数能够独立执行,可以让多个函数以并行的方式执行给程序提提速

普通的函数执行是加在程序中间进行执行的,线程的函数执行是独立出来单独让CPU处理

进程、线程的关系和区别

程序是静态的未运行的指令代码;

进程是正在运行的程序,程序运行需要各类资源,比如内存,寄存器,对处理器来说,进程是执行流的集合,控制流之间相互独立却共享资源,进程可以根据线程数量分为单线程进程和多线程进程;

线程是后来提出的概念名词,实际上就是独立的执行流,是独立能执行的代码块;

执行流、调度单位、运行实体等概念都是针对线程而言的,一切执行流都是线程

进程相当于是资源容器(拥有地址空间,页表等资源),线程是资源使用者

进程、线程的状态

操作系统把进程(线程)“执行过程”中所经历的不同阶段归为几类:

  • 阻塞态:等待外界条件
  • 就绪态:外界条件就绪
  • 运行态:正在运行的进程

状态的转变由调度器负责,状态是描述线程的

因为状态是人为定义的,调度器是人为编写的,所以调度方法和状态都可以人为修改

PCB 程序控制块

PCB,Process Control Block ,操作系统提供的PCB用来解决任务调度相关的问题,PCB 结构如图所示:

image-20210206124024470

每个进程都有自己的PCB,所有的PCB放到一张表格中来维护,就是进程表:

image-20210206124300400

PCB没有具体的格式,实际格式取决于操作系统。

实现线程的两种方式

实现线程有两种方式:在用户空间实现线程或者在内核空间实现线程

  1. 在用户空间实现线程:可移植性强,对处理器来说,会进行进程级别的调度,无法精确到进程中自己实现的具体线程中去
  2. 在内核空间实现线程:可以以线程级别来调度执行流,效率更高

如果是程序内实现线程,那处理器调度任务的时候以进程为单位进行,一个进程分配的时间片还是那么多

如果是内核里实现线程,这处理器调度任务的时候以线程为单位进行,一个进程内如果有多个线程,则这个进程占用的时间片会多一些,达到提速的效果

在内核空间实现线程

简单的PCB及线程栈的实现

thread/thread.h

#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"

// 自定义通用函数类型, 在线程函数中作为形参类型
typedef void thread_func(void*);

// 进程或线程状态
enum task_status {
    TASK_RUNNING,
    TASK_READY,
    TASK_BLOCKED,
    TASK_WAITING,
    TASK_HANGING,
    TASK_DIED
};

// 中断栈 intr_stack
// 用于中断发生时保护程序(线程或进程)的上下文环境:
// 进程或线程中断后,会按照此结构压入上下文寄存器
// 线程进入中断后, 位于 kernel.S 中的中断代码会通过此栈来保存上下文
struct intr_stack {
    uint32_t vec_no; // kernel.S 宏 VECTOR 中 %1 压入的中断号
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp_dummy;  // 虽然pushad把esp也压入,但esp是不断变化的,所以会被popad忽略
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;
    uint32_t gs;
    uint32_t fs;
    uint32_t es;
    uint32_t ds;

    // 以下由 cpu 从低特权级进入高特权级时压入
    uint32_t err_code;           // err_code会被压入在eip之后
    void (*eip) (void);
    uint32_t cs;
    uint32_t eflags;
    void* esp;
    uint32_t ss;
};

// 线程栈 thread_stack
// 用在 switch_to 时保存线程环境
struct thread_stack {
    uint32_t ebp;
    uint32_t ebx;
    uint32_t edi;
    uint32_t esi;

    // 线程第一次执行时, eip 指向待调用的函数 kernel_thread
    // 其他时候, eip 是指向 switch_to 的返回地址
    void (*eip) (thread_func* func, void* func_arg);

    
    // 以下仅供第一次被调度上 cpu 时使用
    void (*unused_retaddr);    			// unused_ret 只为占位置充数为返回地址,这里活用ret指令,ret指令是先将栈中地址恢复到eip,然后跳转过去,实际上eip被我们操纵,所以栈中地址无所谓是啥,eip会被我们修改的
    thread_func* function;              // 由 kernel_thread 所调用的函数名,线程中执行的函数
    void* func_arg;                     // 由 kernel_thread 所调用的函数所需的参数
};


// 进程或线程的 PCB
struct task_struct {
    uint32_t* self_kstack;              // 各内核线程都用自己的内核栈
    enum task_status status;
    uint8_t priority;                   // 线程优先级
    char name[16];
    uint32_t stack_magic;               // 栈的边界标记, 用于检测栈的溢出
};
void thread_create(struct task_struct* pthread, thread_func function, void* func_arg);
void init_thread(struct task_struct* pthread,char* name, int prio);
struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg);

#endif

intr_stack中断栈,用于保存中断发生时的上下文环境,进入中断后,中断入口程序所执行的上下文保护的一系列压栈操作都是压入了此结构

thread_stack线程栈,有两个作用,主要体现在eip上:

  1. 首次运行时,eip用来保存待运行的函数的地址
  2. 切换任务时,eip用来保存任务切换后的新任务的返回地址

其他4个成员是ABI(程序二进制接口)的规定,在函数调用前后这几个寄存器的值不能改变,一般由编译器负责生产,但是自己写汇编代码给C调用的时候,要手动完成这件事

”仅供第一次被调度上使用“这一段注释之后的三个内容:

    void (*unused_retaddr);    			
    thread_func* function;              
    void* func_arg;    

因为是用ret进行跳转执行,跳转执行后,使用参数中的函数地址+函数参数进行函数调用,函数调用的时候通常会使用call,这里没用call指令,所以得按照call指令的入栈形式来装填栈才行,第一个是返回地址,接下来是参数,所以这里需要一个占位符

下次再回到这个线程进行执行的时候,就是跳转过来的时候了,跳转的时候会重新指定栈顶位置,所以之后就再也用不上了

thread/thread.c

#include "thread.h"
#include "stdint.h"
#include "string.h"
#include "global.h"
#include "memory.h"

#define PG_SIZE 4096

// 由 kernel_thread 去执行 function(func_arg)
static void kernel_thread(thread_func* function, void* func_arg) {
    function(func_arg);
}

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

    // 在留出线程栈空间
    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 = 0;
    kthread_stack->ebx = 0;
    kthread_stack->esi = 0;
    kthread_stack->edi = 0;
}

// 初始化线程基本信息
// 待初始化线程指针(PCB),线程名称,线程优先级
void init_thread(struct task_struct* pthread,char* name, int prio){
    memset(pthread,0,sizeof(*pthread)); //清零
    strcpy(pthread->name, name);        //给线程的名字赋值

    pthread->status = TASK_RUNNING;     //线程的状态
    pthread->status = TASK_READY;

    // self_kstack 是线程自己在内核态下使用的栈顶地址
    pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
    pthread->stack_magic = 0x19870916; // 自定义魔数
}

// 线程所执行的函数是 function(func_arg)
struct task_struct* thread_start(char* name,            //线程名
                                 int prio,              //优先级
                                 thread_func function,  //要执行的函数
                                 void* func_arg)        //函数的参数
{
    // PCB 都位于内核空间, 包括用户进程的 PCB 也是在内核空间
    struct task_struct* thread = get_kernel_pages(1);   //申请一页内核空间存放PCB

    init_thread(thread, name, prio);                    //初始化线程
    thread_create(thread, function, func_arg);          //创建线程

    asm volatile("movl %0, %%esp; \
                  pop %%ebp; \
                  pop %%ebx; \
                  pop %%edi; \
                  pop %%esi; \
                  ret;"::"g"(thread->self_kstack):"memory");

    return thread;
}

无论是进程的还是线程的 PCB 都是给内核调度器使用的,所以要放在内核空间中

最后这段内联汇编就是在巧用ret指令进行跳转,使用ret的时候,此时的栈中指向的是返回地址,然后将该返回地址的值传递给eip,然后进行跳转,这里先通过mov指令将栈改成了该线程的线程栈self_kstack,这个栈在此时的位置上刚好是5个寄存器的值,依次pop4个固定的寄存器,然后下一个值就是eip的值,供ret指令使用,而此时的eip是我们线程函数的地址,就会直接跳转到kernel_thread函数然后执行内容,此时的栈里面3个数字依次是无用的占位符、函数地址、函数参数

我们现在实现的是内核单线程,让内核中的单个线程跑起来,线程就是个函数,让这个函数跑起来就行,但是还是想问,就是线程到底是什么,有了自己的PCB然后按照PCB中的值来进行工作就是线程了吧,此时thread_start函数的工作就是将PCB赋值,然后内联汇编ret执行执行

根据当前的信息,只能认为线程(此处指的是单线程进程)是有PCB的虚拟内存空间中执行的代码,PCB里写了关于当前执行代码的信息,如内核栈、状态、名字。也就是说线程是往内核空间中登记过PCB的程序。

kernel/main.c

#include "print.h"
#include "init.h"
#include "debug.h"
#include "memory.h"
#include "thread.h"

void k_thread_a(void*);

int main(){
	put_str("\nI am kernel\n");
	init_all();
	thread_start("k_thread_a",31,k_thread_a,"hello world\n");
	while(1);
	return 0;
}

void k_thread_a(void* arg){
	char* para = arg;
	while(1){
		put_str(para);
	}
}

运行 Bochs

makefile我就不发了,就按照用了哪些头文件来写就行

编译,运行:

函数成功被调用执行起来,打印一大堆hello world。

image-20210207014134389

核心数据结构,双向链表

内核中使用的数据结构是队列,用双向链表来进行维护,链表的关键在于链

lib/kernel/list.h

#ifndef __LIB_KERNEL_LISH_H
#define __LIB_KERNEL_LISH_H

#include "global.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 {
    // head 队首, 固定不变, 第 1 个元素为 head.next
    struct list_elem head;
    // tail 队尾, 固定不变
    struct list_elem tail;
};

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);

#endif

lib/kernel/list.c

#include "list.h"
#include "interrupt.h"

// 初始化双向链表
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);
}

// 将链表第一个元素弹出并返回
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;
}

// 在链表中查找使 func(elem, arg) 返回 true 的元素
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;
}

// 判断链表是否为空
bool list_empty(struct list* plist) {
    return (plist->head.next == &plist->tail);
}

系统中有些东西是公共资源,访问公共资源的代码片段叫临界区,临界区的代码执行必须是原子操作,要么执行完,要么不执行,所以此时需要用到关中断来实现原子操作,之后会使用锁来实现

多线程调度

简单优先级调度基础

这里的工作是完成线程的轮询调度

thread/thread.h

添加/修改如下内容:

// 进程或线程的 PCB
struct task_struct {
    uint32_t* self_kstack;         // 各内核线程都用自己的内核栈
    enum task_status status;
    char name[16];
    uint8_t priority;              // 线程优先级
    uint8_t ticks;                 // 每次在处理器上执行的时间嘀嗒数
    uint32_t elapsed_ticks;        // 此任务上 cpu 运行后至今占用了多少嘀嗒数

    struct list_elem general_tag;   // 用于线程在一般队列中的结点
    struct list_elem all_list_tag;  // 用于线程在 thread_all_list 中的结点

    uint32_t* pgdir;                // 进程自己页表的虚拟地址
    uint32_t stack_magic;           // 栈的边界标记, 用于检测栈的溢出
};

  • 这里的ticks和priority配合使用,当滴答数到0的时候,说明时间片到了,这个时候要被中断处理程序和调度器换下来,调度器会把priority重新赋值给ticks下次用
  • elapsed_ticks是计算总的滴答数
  • general_tag是一个链表节点,是线程的一个标签,当线程被加入到就绪队列或其他等待队列中时,就把该PCB的general_tag加入队列
  • all_list_tag是线程的另一个标签,专用于线程被加入全部线程队列时使用
  • pgdir是页表的虚拟地址,用于实现不同进程之间的独享内存空间,进程有值,线程则无值

当前即将处于单进程多线程的情况下,目前应该看不到进程是如何独享内存空间了

htread/thread.c

填改如下内容:基本上只是添加了一些内容

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

extern void switch_to(struct task_struct* cur, struct task_struct* next);

// 获取当前线程 PCB 指针
struct task_struct* running_thread(void) {
    uint32_t esp;
    asm("mov %%esp, %0" : "=g" (esp));
    // 取 esp 整数部分, 即 PCB 起始地址
    return (struct task_struct*)(esp & 0xfffff000);
}

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

新增了running_thread函数,这个函数的工作是获取当前线程的PCB指针,由于各个线程所用的0级栈都是在PCB当中的,所以取出来栈指针,然后根据分页机制定位到当前页的页首,就是PCB指针了,当时创建PCB的时候,专门申请了一个页,用来存放PCB

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

    if(pthread == main_thread) {
        // 把 main 函数也封装成一个线程, main 函数是一直运行的
        pthread->status = TASK_RUNNING;
    } else {
        pthread->status = TASK_READY;
    }
    // self_kstack 是线程自己在内核态下使用的栈顶地址
    pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
    pthread->priority = prio;
    pthread->priority = prio;
    pthread->elapsed_ticks = 0;
    pthread->pgdir = NULL;
    pthread->stack_magic = 0x19870916; // 自定义魔数
}

此处加入了对主线程的判断,如果是主线程就状态设为运行,否则就是就绪

// 线程所执行的函数是 function(func_arg)
struct task_struct* thread_start(char* name,            //线程名
                                 int prio,              //优先级
                                 thread_func function,  //要执行的函数
                                 void* func_arg)        //函数的参数
{
    // PCB 都位于内核空间, 包括用户进程的 PCB 也是在内核空间
    struct task_struct* thread = get_kernel_pages(1);   //申请一页内核空间存放PCB

    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;
}

此函数是创建线程的入口,init_thread初始化线程PCB,thread_create初始化线程PCB中的内核栈,到这里PCB就初始化完毕了,也就是线程就初始化完毕了,接下来将线程分别加入就绪队列和全部线程队列即可

// 将 main 函数封装为主线程
static void make_main_thread(void) {
    main_thread = running_thread();
    init_thread(main_thread, "main", 31);

    ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag));
    list_append(&thread_all_list, &main_thread->all_list_tag);
}

这里是给main函数一个PCB,成为主线程

线程在队列中的结构

image-20210208013825279

任务调度器和任务切换

任务调度器的工作是读写就绪队列,增删节点,节点就是PCB里面的general_tag,相当于PCB

这里设计的调度原理是:每个线程执行的时间由ticks决定,ticks由prio赋值,每经过一个时钟周期,ticks减1,到0时,切换任务

切换任务实际上就是把当前线程的ticks重置,然后把状态从RUNNING改为READY,然后重新加入就绪队列中,将队列中第一个节点作为下一个要运行的程序设置状态位RUNNING,弹出队列,然后将新线程的寄存器环境恢复,开始执行

这个理论分三部分实现:

  1. 时钟中断处理程序
  2. 调度器 schedule
  3. 任务切换函数 switch_to

注册时钟中断处理函数

kernel/interrupt.c

修改 general_intr_handler函数:

/*通用的中断处理请求*/
static void general_intr_handler(uint8_t vec_nr){
	if(vec_nr == 0x27 || vec_nr == 0x2f){
		// IRQ7 IRQ15 会产生伪中断,无需处理
		// 0x2f 是从片 8259A 上的最后一个 IRQ 引脚,保留项
		return ;
	}
    // 将光标置为屏幕左上角, 清理一块区域
    set_cursor(0);	//设置光标位置
    int cursor_pos = 0;
    while(cursor_pos < 320) {
        put_char(' ');
        cursor_pos++;
    }
    // 将光标重新置为屏幕左上角
    set_cursor(0);
    put_str("!!!!! exception message begin !!!!!\n");
    set_cursor(88); // 从第 2 行第 8 个字符开始打印
    put_str(intr_name[vec_nr]);
    if(vec_nr == 14) { // 若为 Pagefault, 将缺失的地址打印出来并悬停
        int page_fault_vaddr = 0;
        // cr2 存放造成 page_fault 的地址
        asm("movl %%cr2, %0" : "=r" (page_fault_vaddr));
        put_str("\npage fault addr is "); put_int(page_fault_vaddr);
    }

    put_str("\n!!!!! exception message end !!!!!\n");

    // 已经进入中断处理程序就表示已经处在关中断情况下
    // 不会出现线程调度的情况, 故下面的死循环不会再被中断
    while(1);
}

这里优化了之前的通用中断处理程序,让显示更加清晰,如果发生缺页异常,CPU会把导致此异常的地址存放到控制寄存器CR2中

// 在中断处理程序数组第 vector_no 个元素中注册安装中断处理程序 function
void register_handler(uint8_t vector_no, intr_handler function) {
    idt_table[vector_no] = function;
}

新增中断处理程序注册函数,通过这个函数直接修改中断向量表中指向的函数,通过数组下标的形式。

device/timer.c

增加如下内容:

#include "thread.h"
#include "debug.h"
#include "interrupt.h"

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 {
        cur_thread->ticks--;
    }
}

// 初始化 PIT8253
void timer_init() {
    put_str("timer_init start\n");
    // 设置 8253 的定时周期
    frequency_set(COUNTER0_PORT, COUNTER0_NO, READ_WRITE_LATCH, COUNTER_MODE, COUNTER0_VALUE);
    register_handler(0x21, intr_timer_handler);
    put_str("timer_init donw\n");
}

新增时钟处理程序intr_timer_handler,获取当前线程PCB之后,读取ticks,将总时钟数++,将ticks--,判断是否需要调度,ticks减到0的时候,通过schedule函数进行调度

修改的timer_init函数,将时钟处理程序注册到中断处理程序中

实现调度器

thread/thread.c

// 实现线程调度
void schedule(void) {
    ASSERT(intr_get_status() == INTR_OFF);

    struct task_struct* cur = running_thread();
    if(cur->status == TASK_RUNNING) {
        // 若此线程只是 CPU 时间片到了, 将其加入到就绪队尾
        ASSERT(!elem_find(&thread_ready_list, &cur->general_tag));
        list_append(&thread_ready_list, &cur->general_tag);
        cur->ticks = cur->priority;
        cur->status = TASK_READY;
    } else {
        // 若此线程阻塞, 不需要将其加入队列
    }

    ASSERT(!list_empty(&thread_ready_list));
    thread_tag = NULL;
    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);
}

时间片到时间了,进行调度,先获取当前线程信息(PCB),然后判断当前状态,如果是RUNNING则说明只是时间到了而已,那就把该线程重新加入线程就绪队列,然后重置ticks和状态

接下来取出下一个线程,获取其PCB地址,设置状态,通过switch_to函数进行环境准备

这里用的获取PCB的方法是另一种方法:获取当前tag在PCB结构体中的偏移量,用当前地址减去偏移量,然后就是PCB结构首地址了,然后类型强制转换即可

原来用的方法是对tag直接&0xfffff000,这样这个地址就直接是pcb的了

实现任务切换函数

image-20210208023728996

中断分为两种情况,一种是在用户态下被中断的情况,另一种是在内核态下被中断的情况:

第一部分是任务进入中断时的保护,保存当前全部寄存器

第二部分是保护内核环境的上下文,依据ABI,除了esp外,只保护esi/edi/ebx/ebp这4个寄存器,因为内核代码的执行由这4个寄存器决定,这几个寄存器的值可以让处理器把程序执行到内核代码的结束处

thread/switch.S

在用户态下被中断要保存所有寄存器映像,这点在中断初始化程序中已经完成了,这里需要完成在内核态下的处理:

[bits 32]
section .text
global switch_to
switch_to:
    ; 备份当前线程的环境
    push esi
    push edi
    push ebx
    push ebp

    mov eax, [esp+20] ; 获取栈中参数 cur
    mov [eax], esp    ; 保存栈顶指针 esp 到 task_struct 的 self_kstack 字段
                      ; self_kstack 在 task_struct 中的偏移为 0
                      ; 所以直接往 thread 开头处存 4 字节即可
    ; 恢复下一个线程的环境
    mov eax, [esp+24] ; 获取栈中参数 next
    mov esp, [eax]    ; pcb 的第一个成员是 self_kstack 成员
                      ; 它用来记录 0 级栈顶指针, 被换上 cpu 时用来恢复 0 级栈
                      ; 0 级栈中保存了进程或线程所有信息, 包括 3 级栈指针
    pop ebp
    pop ebx
    pop edi
    pop esi
    ret

这里分为上下两部分,首先,根据ABI,需要保护esi,edi,ebx,ebp四个寄存器,那我们就先按照要求push,保存到栈中,然后通过我们传递的参数1,将当前栈地址保存到参数1中,然后将参数2作为栈地址恢复到栈指针中,此时栈已经改变了,然后再恢复这四个寄存器实际上恢复的是下一个任务的栈的寄存器了,从而实现了切换寄存器

启动线程调度

thread/thread.c

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

先初始化线程队列,给主函数创建为线程

kernel/main.c

#include "print.h"
#include "init.h"
#include "debug.h"
#include "memory.h"
#include "thread.h"

void k_thread_a(void*);

int main(){
	put_str("\nI am kernel\n");
	init_all();

	thread_start("k_thread_a",31,k_thread_a,"A");
	thread_start("k_thread_b",20,k_thread_b,"#");
    intr_enable(); // 打开中断, 使时钟中断起作用


	while(1);
	return 0;
}

void k_thread_a(void* arg){
	char* para = arg;
	while(1){
		put_str(para);
	}
}

void k_thread_b(void* arg) {
    char* para = arg;
    while(1) {
        put_str(para);
    }
}

任务调度是时钟中断驱动的,所以需要打开中断,通过之前设置好的时钟中断处理程序来进行调度任务(时间片使用时间到,然后通过schedule函数修改队列,获取下一个线程的信息,通过switch_to进行任务切换)

运行 Bochs

编译,运行

makefile 真是难搞,需要的话直接去看我的代码文件吧,github链接在本系列文章第一篇有给出

这里有些函数没添加到头文件里,需要自行添加一下

运行效果:

image-20210208032531364

可以看到,两个线程和主线程交替执行了,主线程就是显示的空白,子线程分别显示A和#

异常

这里出现了异常,其实按理说,如果让主线程也输出字符的话,还是会出现空格,这是异常引起的,问题是临界区代码资源竞争,这将在下一章进行学习,这里就跳过了。

本篇总结

本篇的内容是线程,跟上一篇的内存管理系统一样,先实现了一半,剩下一半后面再完善,还有一些疑问没有解决,比如线程和进程的PCB之间啥关系,应该到进程那一章节就能解决了吧

线程是为了让程序并发提速而设计出来的概念,在本章的理解上,有PCB结构的执行流,就是线程,我们创建一个线程去执行函数,就需要先给它创建PCB,写上线程相关信息,然后存入队列准备执行

线程之间的PCB通过PCB中的两个tag成员来连接,这两个tag是链表节点,通过链表节点地址在PCB结构内,而PCB占据一个自然页,所以可通过链表节点直接获取到PCB的地址

线程的启动巧用ret指令进行跳转执行,因为线程是独立执行的代码块,不需要返回,也不需要返回值,多线程之间的通信会在之后讲到

使用轮询的方法进行调度

系统通过计时器中断实现任务调度,在计时器中断处理程序中获取当前PCB信息,判断其中的时间片是否用完,没用完就减一等下一次中断继续判断,时间片用完后,根据用完时的状态来将该任务放入不同的地方,如果在时间片用完的时候处于RUNNING状态,则将该线程放到就绪队列中,并将状态改外READY然后重置时间片

到这里,一个线程的执行结束了,下一步该进行线程切换了,线程切换需要将原来线程的寄存器都保存下来,然后将要切换的栈的寄存器都还原回去,修改完毕后,CPU 就会开始执行下一个线程了


总之,多线程的实现是通过为每个线程创建PCB结构,来存储PCB信息,通过时钟中断的中断处理程序获取PCB的信息,通过PCB的信息来判断是否切换,进行切换操作则需要保存/还原线程上下文环境。从而实现伪并发

参考资料

  • 《操作系统真象还原》Chapter 9

评论