线程和进程将分两部分实现,本章先讲解线程。
9.1 实现内核线程
9.1.1 执行流
在处理器数量不变的情况下,多任务操作系统采用多道程序设计的方式,使处理器在所有任务之间来回切换,这称为“伪并行”,由操作系统中的任务调度器决定当前处理器执行哪个任务。
任务调度其是操作系统中用于把软件轮流调度上处理器运行的一个软件模块,它是操作系统的一部分。调度器在内核中维护一个任务表(也称进程表、线程表或调度表),然后按照一定的算法,从任务表中选择一个任务,然后把该任务放到处理器上运行,当任务运行的时间片到期后,再从任务表中找另外一个任务放到处理器上运行。
9.1.2 线程是什么
在线程中调用函数是让所运行的函数能够以调度单元的身份独立上处理器运行,当函数可以独立运行时,就会有更大的好处,那就是可以让程序中的多个函数(执行流)以并行的方式运行(伪并行),为程序提速。
9.1.3 进程与线程的关系、区别简述
进程拥有整个地址空间,其中包括各种资源, 进程中的所有线程共享同一个地址空间。概括来讲,进程=线程+资源。
为什么要有线程?进程采用多个执行流和其他进程抢处理器资源,这样就节省了单个进程的总执行时间。
执行流、调度单位、运行实体等概念都是针对线程而言的,线程才是解决问题的思路、步骤,它是具有能动性的指令,因此只有它才能上处理器运行,即一切执行流其实都是线程,因为任何时候进程中都至少存在一个线程。
9.1.4 进程、线程的状态
- 阻塞态:需要等待外界条件的状态
- 就绪态:外界条件成立时,进程可以随时准备运行的状态
- 运行态:正在处理器上运行的进程状态
9.1.5 进程的身份证——PCB
PCB,Process Control Block,即程序控制块,用来记录与此进程相关的信息,比如进程状态、PID、优先级等。
PCB 的实际格式取决于操作系统的功能复杂度。
PCB 中的寄存器映像
保存了该进程运行时所有寄存器的值。
进程使用的栈也属于 PCB 的一部分,不过此栈是进程所使用的 0 特权级下内核栈(不是 3 特权级下的用户栈)。
9.1.6 实现线程的两种方式——内核或用户进程
实现线程有两种方式:在用户空间实现线程或者在内核空间实现线程
- 在用户空间实现线程:可移植性强,对处理器来说,会进行进程级别的调度,无法精确到进程中自己实现的具体线程中去
- 在内核空间实现线程:可以以线程级别来调度执行流,效率更高
如果是程序内实现线程,那处理器调度任务的时候以进程为单位进行,一个进程分配的时间片还是那么多。
如果是内核里实现线程,这处理器调度任务的时候以线程为单位进行,一个进程内如果有多个线程,则这个进程占用的时间片会多一些,达到提速的效果。
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"
typedef void thread_func(void*);
enum task_status { TASK_RUNNING, TASK_READY, TASK_BLOCKED, TASK_WAITING, TASK_HANGING, TASK_DIED };
struct intr_stack { uint32_t vec_no; uint32_t edi; uint32_t esi; uint32_t ebp; uint32_t esp_dummy; uint32_t ebx; uint32_t edx; uint32_t ecx; uint32_t eax; uint32_t gs; uint32_t fs; uint32_t es; uint32_t ds;
uint32_t err_code; void (*eip) (void); uint32_t cs; uint32_t eflags; void* esp; uint32_t ss; };
struct thread_stack { uint32_t ebp; uint32_t ebx; uint32_t edi; uint32_t esi;
void (*eip) (thread_func* func, void* func_arg);
void (*unused_retaddr); thread_func* function; void* func_arg; };
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 用于中断发生时保护程序的上下文环境,大概结构如图所示:
具体内容见kernel.S
中intr%1entry
函数的压栈过程。
线程栈 thread_stack
线程栈 thread_stack 有两个作用,主要体现在第 5 个成员 eip 上:
- 线程是使函数单独上处理器运行的机制,因此线程肯定得知道要运行哪个函数,首次执行某个函数时,eip 中便保存该函数的地址。
- 将来使用 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
static void kernel_thread(thread_func* function, void* func_arg) { function(func_arg); }
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 = 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; pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE); 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); 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 创建线程。
需要注意的是:
- init_thread 中优先级 prio 目前没什么用,将来它的作用体现在任务在处理器上执行的时间片长度,优先级越高执行时间片越长;
- pthread->self_kstack 是线程自己在 0 特权级下所用的栈,在线程创建之初,它被初始化为线程 PCB 的最顶端,即(uint32_t)pthread+ PG_SIZE;
- PCB 上端是 0 特权级栈,将来线程在内核态下的任何栈操作用此 PCB 中的栈,如果出现了某些异常导致入栈操作过多,这会破坏 PCB 低处的线程信息。因此需要检测这些线程信息是否被破坏了,stack_magic 被安排在线程信息的最边缘,作为它与栈的边缘,以后在线程调度时会用到。
- thread_ create 的功能是初始化线程栈 thread_stack,将待执行的函数和参数放到 thread_stack 中相应的位置。
- kernel_thread 并不是通过 call 指令调用的,而是通过 ret 来执行的,因此无法按照正常的函数调用 kernel_thread(funcition,func_arg) 来执行,只能将参数放在 kernel_thread 所用的栈中。
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) { char* para = arg; while (1) { put_str(para); } }
|
然后编译运行, 满屏 argA,说明运行成功。
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 { struct list_elem head; struct list_elem tail; };
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
|
需要注意到是,表示链表结点的是 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"
void list_init (struct list* list) { list->head.prev = NULL; list->head.next = &list->tail; list->tail.prev = &list->head; list->tail.next = NULL; }
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); }
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; }
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; }
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 ? 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;
struct list_elem general_tag; struct list_elem all_list_tag;
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; 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);
struct task_struct* running_thread() { uint32_t esp; asm ("mov %%esp, %0" : "=g" (esp)); return (struct task_struct*) (esp & 0xfffff000); }
static void kernel_thread(thread_func* function, void* func_arg) { 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) { pthread->status = TASK_RUNNING; } else { pthread->status = TASK_READY; } pthread->priority = prio; 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; }
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); }
|
这里要注意几点:
- 开头定义了全局的数据结构,这里要说明的是
thread_tag
是用来保存将 tag 转换为 PCB 过程中 tag 的值(?)。
- 外部函数
switch_to
后面介绍。
- 新增的函数
running_thread
功能是返回线程的 PCB 地址。
- 在
kernel_thread
中添加了开中断。这是由于我们的任务调度机制基于时钟中断,通过中断将控制权交到内核手中,并由内核的任务调度器 schedule 将任务调度到处理器上。
- 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) { return; } 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); put_str(intr_name[vec_nr]); if (vec_nr == 14) { int page_fault_vaddr = 0; asm ("movl %%cr2, %0" : "=r" (page_fault_vaddr)); 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;
static void intr_timer_handler(void) { struct task_struct* cur_thread = running_thread();
ASSERT(cur_thread->stack_magic == 0x19870916);
cur_thread->elapsed_ticks++; ticks++;
if (cur_thread->ticks == 0) { schedule(); } else { cur_thread->ticks--; } }
void timer_init() { put_str("timer_init start\n"); 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
|
void register_handler(uint8_t vector_no, intr_handler function) {
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) { 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); }
|
有关 schedule 需要说明一下:
- schedule 操作需要关中断,保证调度操作为原子操作。
- 如果线程不是因为时间片到了而被换下处理器,可能是被阻塞。
- 有一种情况是就绪队列为空,需要实现一个 idle 线程,避免无线程调度。这里暂时没有实现,先用
ASSERT
来保障。
任务切换需要进行上下文保护:
- 上下文保护的第一部分负责保存任务进入中断前的全部寄存器。目的是能让任务恢复到中断前,这部分工作在 kernel.S 中由 intr%1entry 完成。
- 上下文保护的第二部分负责保存 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 寄存器,在函数的开头进行寄存器保护是个习惯,避免后面操作影响它们的值。此时栈的情况如图所示:
- 程序 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);
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 数量应该相等。
输出:
在预期输出上是没问题,但是出现了连续空格,甚至出现了一般保护性异常,这是怎么回事?
问题来自于临界区代码资源竞争,这个问题将在下一章中解决。
整体来看,本章实现了内核多线程以及线程调度,但是对于进程和线程 PCB 的差异、用户进程的实现以及 idle 线程的实现需要我们在后续的学习中补充。