Songqian Li's Blog

去历史上留点故事

线程和进程将分两部分实现,本章先讲解线程。

9.1 实现内核线程

9.1.1 执行流

在处理器数量不变的情况下,多任务操作系统采用多道程序设计的方式,使处理器在所有任务之间来回切换,这称为“伪并行”,由操作系统中的任务调度器决定当前处理器执行哪个任务。
任务调度其是操作系统中用于把软件轮流调度上处理器运行的一个软件模块,它是操作系统的一部分。调度器在内核中维护一个任务表(也称进程表、线程表或调度表),然后按照一定的算法,从任务表中选择一个任务,然后把该任务放到处理器上运行,当任务运行的时间片到期后,再从任务表中找另外一个任务放到处理器上运行。

9.1.2 线程是什么

在线程中调用函数是让所运行的函数能够以调度单元的身份独立上处理器运行,当函数可以独立运行时,就会有更大的好处,那就是可以让程序中的多个函数(执行流)以并行的方式运行(伪并行),为程序提速。

9.1.3 进程与线程的关系、区别简述

进程拥有整个地址空间,其中包括各种资源, 进程中的所有线程共享同一个地址空间。概括来讲,进程=线程+资源。
为什么要有线程?进程采用多个执行流和其他进程抢处理器资源,这样就节省了单个进程的总执行时间。
执行流、调度单位、运行实体等概念都是针对线程而言的,线程才是解决问题的思路、步骤,它是具有能动性的指令,因此只有它才能上处理器运行,即一切执行流其实都是线程,因为任何时候进程中都至少存在一个线程。

9.1.4 进程、线程的状态

  • 阻塞态:需要等待外界条件的状态
  • 就绪态:外界条件成立时,进程可以随时准备运行的状态
  • 运行态:正在处理器上运行的进程状态

9.1.5 进程的身份证——PCB

PCB,Process Control Block,即程序控制块,用来记录与此进程相关的信息,比如进程状态、PID、优先级等。
image.png
PCB 的实际格式取决于操作系统的功能复杂度。
PCB 中的寄存器映像保存了该进程运行时所有寄存器的值。
进程使用的栈也属于 PCB 的一部分,不过此栈是进程所使用的 0 特权级下内核栈(不是 3 特权级下的用户栈)。

9.1.6 实现线程的两种方式——内核或用户进程

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

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

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

9.2 在内核空间实现线程

9.2.1 简单的 PCB 及线程栈的实现

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
#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"

/**
* @description 自定义通用函数类型,它将在很多线程函数中做为形参类型
*/
typedef void thread_func(void*);

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

/*********** 中断栈intr_stack ***********
* 此结构用于中断发生时保护程序(线程或进程)的上下文环境:
* 进程或线程被外部中断或软中断打断时,会按照此结构压入上下文
* 寄存器, intr_exit中的出栈操作是此结构的逆操作
* 此栈在线程自己的内核栈中位置固定,所在页的最顶端
********************************************/
struct intr_stack {
uint32_t vec_no; // kernel.S 宏VECTOR中push %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时使用 ****/

/* 参数unused_ret只为占位置充数为返回地址 */
void (*unused_retaddr);
thread_func* function; // 由Kernel_thread所调用的函数名
void* func_arg; // 由Kernel_thread所调用的函数所需的参数
};

/**
* @description 进程或线程的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

中断栈 intr_stack 用于中断发生时保护程序的上下文环境,大概结构如图所示:
image.png
具体内容见kernel.Sintr%1entry函数的压栈过程。

线程栈 thread_stack

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

  1. 线程是使函数单独上处理器运行的机制,因此线程肯定得知道要运行哪个函数,首次执行某个函数时,eip 中便保存该函数的地址。
  2. 将来使用 switch_to 函数实现任务切换。当任务切换时,此 eip 用于保存任务切换后的新任务的返回地址。

C 编译器是按照 ABI (Application Binary Interface)规则来编译 C 程序的,ABI 规则中规定:”ebp、ebx、edi、esi 和 esp 五个寄存器归主调函数所用,其余的机器村归被调函数所用”,即在被调函数执行完后这 5 个寄存器的值不应该被改变,故在被调函数执行前需要保存该 5 个寄存器的值。而 esp 的值会由调用约定来保证,因此这里不打算保护 esp 的值。

9.2 线程的实现

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
#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) {
/* 先预留中断使用栈的空间,可见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);
pthread->status = TASK_RUNNING;
pthread->priority = prio;
/* self_kstack是线程自己在内核态下使用的栈顶地址 */
pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
pthread->stack_magic = 0x19870916; // 自定义的魔数
}
/* 创建一优先级为prio的线程,线程名为name,线程所执行的函数是function(func_arg) */
/*
* name:线程名
* prio:线程优先级
* 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);
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,这都是给内核调度器使用的结构,属于内核管理的数据, 因此将来用户进程的 PCB 也依然要从内核物理内存池中申请。
线程创建函数 thread_start,在该函数内调用 init_thread 初始化线程,然后调用 thread_create 创建线程。
需要注意的是:

  1. init_thread 中优先级 prio 目前没什么用,将来它的作用体现在任务在处理器上执行的时间片长度,优先级越高执行时间片越长;
  2. pthread->self_kstack 是线程自己在 0 特权级下所用的栈,在线程创建之初,它被初始化为线程 PCB 的最顶端,即(uint32_t)pthread+ PG_SIZE;
  3. PCB 上端是 0 特权级栈,将来线程在内核态下的任何栈操作用此 PCB 中的栈,如果出现了某些异常导致入栈操作过多,这会破坏 PCB 低处的线程信息。因此需要检测这些线程信息是否被破坏了,stack_magic 被安排在线程信息的最边缘,作为它与栈的边缘,以后在线程调度时会用到。
  4. thread_ create 的功能是初始化线程栈 thread_stack,将待执行的函数和参数放到 thread_stack 中相应的位置。
  5. kernel_thread 并不是通过 call 指令调用的,而是通过 ret 来执行的,因此无法按照正常的函数调用 kernel_thread(funcition,func_arg) 来执行,只能将参数放在 kernel_thread 所用的栈中。
  6. movl %0, %%esp是使得 thread->self_kstack 的值作为栈顶,此时指向线程栈的最低处。

然后在 kernel/main.c 中调用 thread_start。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "print.h"
#include "init.h"
#include "thread.h"

void k_thraed_a(void*);

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

thread_start("k_thread_a",31, thread_a, "argA ");

while (1);
return 0;
}

// 在线程中运行的函数
void k_thread_a(void* arg) {
// 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用
char* para = arg;
while (1) {
put_str(para);
}
}

然后编译运行, 满屏 argA,说明运行成功。
image.png

9.3 核心数据结构,双向链表

在 lib/kernel 下创建 list.h 和 list.c:
list.h:

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
#ifndef __LIB_KERNEL_LIST_H
#define __LIB_KERNEL_LIST_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个元素,第1个元素为head.next */
struct list_elem head;
/* tail是队尾,同样是固定不变的 */
struct list_elem tail;
};

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

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_H

需要注意到是,表示链表结点的是 list_elem ,该结点只有前驱结点只恨 prev 和后继结点指针 next,不包含数据成员。这里链表单纯是为了将已有的数据以一定的时序链起来。

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
#include "list.h"
#include "interrupt.h"

/* 初始化双向链表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前驱元素的后继元素更新为elem, 暂时使before脱离链表*/
before->prev->next = elem;

/* 更新elem自己的前驱结点为before的前驱,
* 更新elem自己的后继结点为before, 于是before又回到链表 */
elem->prev = before->prev;
elem->next = before;

/* 更新before的前驱结点为elem */
before->prev = elem;

intr_set_status(old_status);
}

/* 添加元素到列表队首,类似栈push操作 */
void list_push(struct list* plist, struct list_elem* elem) {
list_insert_before(plist->head.next, elem); // 在队头插入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;
/* 如果队列为空,就必然没有符合条件的结点,故直接返回NULL */
if (list_empty(plist)) {
return NULL;
}

while (elem != &plist->tail) {
if (func(elem, arg)) { // func返回ture则认为该元素在回调函数中符合条件,命中,故停止继续遍历
return elem;
} // 若回调函数func返回true,则继续遍历
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);
}

list.c 中使用了关中断的函数 intr_disable,因为系统中有些数据是公共资源,对于它的修改应该保证是原子操作。因此对于链表中数据的添加和删除操作中加入了关中断操作。

9.4 多线程调度

9.4.1 简单优先级调度的基础

本节目标是完善 thread.c 和 thread.h,完成线程的轮询调度。
task_struct 完善:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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运行后至今占用了多少cpu嘀嗒数,即任务执行时间

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

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

新增字段解释:

  • ticks:时间片,每次时钟中断都会将当前任务的 ticks-1,减到 0 就被换下处理器。
  • elapsed_ticks用于记录任务在处理器上运行的时钟嘀嗒数,从开始执行到运行结束所经历的总时钟数。
  • general_tag是线程的标签,当线程被加入就绪队列或等待队列时,就把该线程 PCB 中 general_tag 的地址加入队列。
  • all_list_tag是线程在全部线程队列的标签。将来可以通过 elem2entry 宏获取 PCB 地址,从而访问 thread。general_tag同理。
  • pgdir是任务自己的页表。线程和进程最大的区别就是进程独享自己的地址空间,若该任务是线程,pgdir 为 NULL,若为进程才被赋值。(难道不是线程共享 pgdir?)

thread.c 中新增:

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
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() {
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);
}
/* 初始化线程基本信息 */
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函数也封装成一个线程,并且它一直是运行的,故将其直接设为TASK_RUNNING
pthread->status = TASK_RUNNING;
}
else {
pthread->status = TASK_READY;
}
pthread->priority = prio;
/* self_kstack是线程自己在内核态下使用的栈顶地址 */
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) {
/* pcb都位于内核空间,包括用户进程的pcb也是在内核空间 */
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(void) {
/* 因为main线程早已运行,咱们在loader.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);
}

这里要注意几点:

  1. 开头定义了全局的数据结构,这里要说明的是thread_tag是用来保存将 tag 转换为 PCB 过程中 tag 的值(?)。
  2. 外部函数switch_to后面介绍。
  3. 新增的函数running_thread功能是返回线程的 PCB 地址。
  4. kernel_thread中添加了开中断。这是由于我们的任务调度机制基于时钟中断,通过中断将控制权交到内核手中,并由内核的任务调度器 schedule 将任务调度到处理器上。
  5. make_main_thread 是将主线程完善成线程的结构。

9.4.2 任务调度器和任务切换

本节工作是实现调度器和任务切换。
调度器主要任务就是读写就绪队列,增删里面的结点。
线程每次在处理器上的执行时间是由其 ticks 决定的,在初始化线程时将线程 PCB 的 ticks 初始化为 prio,优先级越高,ticks 越大。每发生一次时钟中断,时钟中断的处理程序便将当前运行的线程的 ticks 减 1.当 ticks 为 0 时,时钟中断处理程序调用调度器 schedule,选择下一个线程上处理器。
调度器是从就绪队列 thread_ready_list 中选择上处理器运行的线程,按照先进先出的顺序始终调度队头的线程。schedule 并不仅由时钟中断处理程序来调用,它还有被其他函数调用的情况。因为被换下处理器的原因除了时间片用完还有其他原因。
先修改一下 kernel/interrupt.c 的中断处理函数,方便处理异常退出处理器的情况:

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
/* 通用的中断处理函数,一般用在异常出现时的处理 */
static void general_intr_handler(uint8_t vec_nr) {
if (vec_nr == 0x27 || vec_nr == 0x2f) { // 0x2f是从片8259A上的最后一个irq引脚,保留
return; //IRQ7和IRQ15会产生伪中断(spurious interrupt),无须处理。
}
/* 将光标置为0,从屏幕左上角清出一片打印异常信息的区域,方便阅读 */
set_cursor(0);
int cursor_pos = 0;
while(cursor_pos < 320) {
put_char(' ');
cursor_pos++;
}

set_cursor(0); // 重置光标为屏幕左上角
put_str("!!!!!!! excetion message begin !!!!!!!!\n");
set_cursor(88); // 从第2行第8个字符开始打印
put_str(intr_name[vec_nr]);
if (vec_nr == 14) { // 若为Pagefault,将缺失的地址打印出来并悬停
int page_fault_vaddr = 0;
asm ("movl %%cr2, %0" : "=r" (page_fault_vaddr)); // cr2是存放造成page_fault的地址
put_str("\npage fault addr is ");put_int(page_fault_vaddr);
}
put_str("\n!!!!!!! excetion message end !!!!!!!!\n");
// 能进入中断处理程序就表示已经处在关中断情况下,
// 不会出现调度进程的情况。故下面的死循环不会再被中断。
while(1);
}

在 device/timer.c 添加时钟中断处理程序,并将时钟中断添加到中断处理程序数组中:

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
#include "interrupt.h"
#include "thread.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 { // 将当前进程的时间片-1
cur_thread->ticks--;
}
}

/**
* @description 初始化PIT8253
*/
void timer_init() {
put_str("timer_init start\n");
// 设置8253的定时周期,也就是发中断的周期
frequency_set(CONTRER0_PORT, COUNTER0_NO, READ_WRITE_LATCH, COUNTER_MODE, COUNTER0_VALUE);
register_handler(0x20, intr_timer_handler);
put_str("timer_init done\n");
}

同时要在 kernel/interrupt.c 中实现 register_handler:

1
2
3
4
5
6
7
8
9
10
/**
* 为中断注册中断处理程序
* @param vector_no 中断向量号
* @param function 中断处理程序
*/
void register_handler(uint8_t vector_no, intr_handler function) {
/* idt_table数组中的函数是在进入中断后根据中断向量号调用的,
* 见kernel/kernel.S的call [idt_table + %1*4] */
idt_table[vector_no] = function;
}

在 kernel/thread.c 中实现调度器 schedule:

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
/**
* 任务调度
*/
void schedule() {

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; // 重新将当前线程的ticks再重置为其priority;
cur->status = TASK_READY;
} else {
/* 若此线程需要某事件发生后才能继续上cpu运行,
不需要将其加入队列,因为当前线程不在就绪队列中。*/
}

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

有关 schedule 需要说明一下:

  • schedule 操作需要关中断,保证调度操作为原子操作。
  • 如果线程不是因为时间片到了而被换下处理器,可能是被阻塞。
  • 有一种情况是就绪队列为空,需要实现一个 idle 线程,避免无线程调度。这里暂时没有实现,先用ASSERT来保障。

任务切换需要进行上下文保护:

  1. 上下文保护的第一部分负责保存任务进入中断前的全部寄存器。目的是能让任务恢复到中断前,这部分工作在 kernel.S 中由 intr%1entry 完成。
  2. 上下文保护的第二部分负责保存 esi、edi、ebx 和 ebp 四个寄存器。目的是让任务恢复执行在任务切换发生时剩下尚未执行的内核代码,利用第一部分保护的寄存器环境彻底恢复任务。这部分由函数 switch_to 完成。

我们在 thread/switch.S 中实现 switch_to 函数,switch_to 函数的作用是保存 cur 线程的寄存器映像,将下一个线程 next 的寄存器映像装载到处理器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[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. task_struct的self_kstack字段,
; self_kstack在task_struct中的偏移为0,
; 所以直接往thread开头处存4字节便可。
;------------------ 以上是备份当前线程的环境,下面是恢复下一个线程的环境 ----------------
mov eax, [esp + 24] ; 得到栈中的参数next, next = [esp+24]
mov esp, [eax] ; pcb的第一个成员是self_kstack成员,用来记录0级栈顶指针,
; 用来上cpu时恢复0级栈,0级栈中保存了进程或线程所有信息,包括3级栈指针
pop ebp
pop ebx
pop edi
pop esi
ret ; 返回到上面switch_to下面的那句注释的返回地址,
; 未由中断进入,第一次执行时会返回到kernel_thread
  • 程序 6~9 行是遵循 ABI 原则,保护好 esi、edi、ebx、ebp 寄存器,在函数的开头进行寄存器保护是个习惯,避免后面操作影响它们的值。此时栈的情况如图所示:

image.png

  • 程序 11 行是获取 cur 线程的地址,12 行则是将内核栈栈顶放到 cur 线程的地址位上,因为线程 task_struct 结构中内核栈 kstack 的偏移量为 0,cur 线程的地址即为线程的内核栈地址。
  • 程序 15 行使获取 next 线程的地址,然后将 next 线程的内核栈栈顶地址赋值给 esp,从而实现内核栈切换。

最后我们需要启用线程调度。在 thread.c 中添加:

1
2
3
4
5
6
7
8
9
10
11
/**
* 初始化线程环境
*/
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 done\n");
}

然后将 thread_init 加入到 init.c 的 init_all 函数中。
我们尝试创建多个线程:

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void) {
put_str("I am kernel\n");
init_all();

thread_start("k_thread_a", 31, k_thread_a, "argA ");
thread_start("k_thread_b", 8, k_thread_a, "argB ");

intr_enable(); // 打开中断, 使时钟中断起作用
while (1) {
put_str("Main ");
}
return 0;
}

由于时间片长度等于优先级,所以预期输出 argA 的数量应约为 argB 的 4 倍,主函数优先级也为 31,故 argA 和 Main 数量应该相等。
输出:
image.png
在预期输出上是没问题,但是出现了连续空格,甚至出现了一般保护性异常,这是怎么回事?
问题来自于临界区代码资源竞争,这个问题将在下一章中解决。
整体来看,本章实现了内核多线程以及线程调度,但是对于进程和线程 PCB 的差异、用户进程的实现以及 idle 线程的实现需要我们在后续的学习中补充。

相关文章
评论
分享
  • 《操作系统真象还原》:第十章 输入输出系统

    上一章中我们遇到的字符混乱和 GP 异常问题,根本原因是由于临界区代码的资源竞争,这需要一些互斥的方法来保证操作的原子性。 10.1 同步机制——锁 10.1.1 排查 GP 异常,理解原子操作 多线程执行刷屏时光标值越界导致...

    《操作系统真象还原》:第十章 输入输出系统
  • GPU虚拟化

    用户层虚拟化 本地 API 拦截和 API formwarding 在用户态实现一个函数库,假设叫 libwrapper, 它要实现底层库的所有 API; 让 APP 调用这个 libwrapper。如何做? libwrap...

    GPU虚拟化
  • 硬件虚拟化

    硬件虚拟化介绍 硬件虚拟化要做的事情 体系结构支持 体系结构 实现功能 作用 模式切换 Host CPU <-> Guest CPU 切换 CPU 资源隔离 二阶段地址转换 GVA-> GPA...

    硬件虚拟化
  • 《操作系统真象还原》:第八章 内存管理系统

    8.1 makefile 简介 这部分可参考阮一峰的讲解:https://www.ruanyifeng.com/blog/2015/02/make.html 8.1.1 makefile 是什么 makefile 是 Linu...

    《操作系统真象还原》:第八章 内存管理系统
  • 《操作系统真象还原》:第七章 中断

    7.1 中断是什么,为什么要有中断 运用中断能够显著提升并发,从而大幅提升效率。 7.2 操作系统是中断驱动的 略 7.3 中断分类 把中断按事件来源分类,来自 CPU 外部的中断就称为外部中断,来自 CPU 内部的中断称为内部...

    《操作系统真象还原》:第七章 中断
  • 《操作系统真象还原》:第六章 完善内核

    6.1 函数调用约定简介 咱们实验使用cdecl。这里提一下stdcall,cdecl与stdcall的区别在于由谁来回收栈空间。 stdcall是被调用者清理参数所占的栈空间。 举例来说: 12int subtract(int ...

    《操作系统真象还原》:第六章 完善内核
  • 《操作系统真象还原》:第五章 保护模式进阶——加载内核

    5.3 加载内核 5.3.1 用 C 语言写内核 第一个 C 语言代码: 1234int main(void) { while(1); return 0;} 这个内核文件什么都没做,通过while(1)这个死循...

    《操作系统真象还原》:第五章 保护模式进阶——加载内核
  • 《操作系统真象还原》:第五章 保护模式进阶——内存分页机制

    从这一刻起,我们才算开始了真正的操作系统学习之旅 5.1 获取物理内存容量 5.1.1 Linux 获取内存的方法 在 Linux 2.6 内核总是用detect_memory函数来获取内存容量的。其函数本质上是通过调用 BI...

    《操作系统真象还原》:第五章 保护模式进阶——内存分页机制
  • 《操作系统真象还原》:第四章 保护模式入门

    4.1 保护模式概述 在本章大家会见到全局描述符表、中断描述符表、各种门结构,这是 CPU 提供给应用的,咱们用好就行。 保护模式强调的是“保护”,它是在 Intel 80286 CPU 中首次出现,这是继 8086 之后,Inte...

    《操作系统真象还原》:第四章 保护模式入门
  • 《操作系统真象还原》:第三章 完善MBR——I/O接口

    3.3 让我们对显示器说点什么吧 3.3.1 CPU 如何与外设通信——IO 接口 IO 接口功能: 设置数据缓冲,解决 CPU 与外设的速度不匹配 设置信号电平转换电路 设置数据格式转换 设置时序控制电路来同步 CPU 和外部...

    《操作系统真象还原》:第三章 完善MBR——I/O接口