十. 内核线程

发表于 | 更新于 | 分类于

实现线程函数

观察一下这段c语言代码

1
2
3
4
5
6
7
8
9
10
11
12
void threadFunc(void *arg)
{
	printf("thread function\n");
}

int main()
{
	printf("main function\n");
	
	_beginthread(threadFunc, 0, NULL);	
	return 0;
}

这里只是举个简单的例子，没有考虑错误处理和资源回收。

在程序中，在main函数中输出了一句话，然后开启一个线程，然后让这个线程也输出一句话。通过这个简单的例子差不多就可以建立线程最初的印象了，线程就是运行一段函数的载体。

我在刚开始接触线程的时候对它的理解是这样的：

在一个程序中，至少是有一条线程的，那就是主线程。这个主线程和普通线程也是类似的。它也是运行一段函数的载体，但是它是入口函数运行的载体。这个入口函数放到c语言里面来讲就是平时所用的main函数。

线程的生命周期就是它执行的函数的生命周期，当函数执行完成之后，这条线程的使命也就完成了。当然，线程的使命结束了不代表它就消亡了，这条线程也可能被挂起，留待将来有需要时再将其唤醒。

线程才是真正的执行体，进程只是为程序的执行提供资源。

线程的执行时间和顺序根据他的调度策略来。

主线程的存亡代表整个进程的存亡。主线程执行完成之后，代表整个进程要干的活都已经全部干完了，那么此时进程已经没有存在的必要了，它就会被操作系统回收。

线程函数和普通函数的区别

对线程有了一个基本的理解之后，那么来了解一下，线程执行的函数和平常的函数调用有什么区别？

1
2
3
4
5
6
7
8
9
int funca(int num)
{
    funcb(num);
}

int funcb(int num)
{
    printf("%d", num);
}

普通的函数之间发生函数调用的时候，主要的故事都发生在被调用函数的栈中。

首先，备份主调函数的栈，在被调函数的栈顶存放主调函数的返回地址。

然后，根据函数调用约定，在被调函数的栈中存放好要传递的参数。

最后，执行被调函数。

一般的函数调用是随着此函数所在的调度单元一块在处理器上运行的，这个调度单元可能是整个进程，也可能是某个线程。因为线程用也可以发生函数调用嘛。在这个调度单元中，就会保存它所依赖的上下文环境。如寄存器，栈等。

线程是一套机制，它能够为一段代码也就是线程函数创造它所依赖的上下文环境，从而让其具有独立性，可以单独的在处理器上执行。线程函数与普通函数的区别应该就是在这个上下文环境中了。普通函数的上下文环境依赖于执行它的执行流，线程函数想要执行就得创建它的上下文环境。

下面就通过代码简单的模拟一下线程的创建执行过程

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
// 线程的状态
typedef enum tag_task_status
{
    TASK_RUNNING,
    TASK_READY,
    TASK_BLOCKED,
    TASK_WAITING,
    TASK_HANGING,
    TASK_DIED
}task_status;

// 线程栈
typedef struct tag_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;
}thread_stack;

typedef struct tag_task_struct
{
    uint32_t *self_kstack; // 内核线程的栈顶地址
    task_status status;    // 当前线程的状态
    char name[16];
    uint8_t priority;
    uint32_t stack_magic;   // 栈的边界标记，用来检测栈溢出
}task_struct;

目前只是简单的模拟一下线程的创建执行过程，所以过程比较简单，这里是用到了ret指令的一个小技巧。

平常发生的函数调用都是通过汇编指令call实现的，这个是属于我们主动去调用这个函数。而线程函数并不是我们主动调用的，它是由操作系统的调度器来调用的，时间片分配到了哪个线程上，哪个线程就占有CPU执行代码。这里会通过ret指令来实现伪被动调用，是一种欺骗CPU的办法。

CPU执行哪条指令是通过EIP的指向来决定的，而ret指令在返回的时候，当前的栈顶就会被当做是返回地址，这个返回地址会被赋值给EIP。也就是说，我们可以把某个函数的地址放在栈顶，通过这个函数来执行线程函数。那么在ret返回的时候，就会进入我们指定的函数当中，这个函数就会来调用线程函数。

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

    pthread->status = TASK_RUNNING;
    pthread->priority = prio;
    pthread->ticks = prio;
    pthread->elapsed_ticks = 0;
    pthread->pgdir = NULL;

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

void thread_create(task_struct* pthread, thread_func function, void* func_arg)
{
    // 先预留中断使用栈的空间
    pthread->self_kstack -= sizeof(intr_stack);

    // 留出线程栈空间
    pthread->self_kstack -= sizeof(thread_stack);

    thread_stack* kthread_stack = (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; 
}

这两个函数主要是对线程的信心进程初始化。由于栈是向下增长的，所以在init中，首先让其指向了分配的线程空间(也就是一页大小的空间，下面可以看到)的最高地址处，然后在create_thread函数中，首先留出了一块空间，这个是将来线程调度时会使用到的中断栈，再留出线程栈的空间，方便从下往上填充数据。此时栈的数据如下。

线程栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void kernel_thread(thread_func *function, void *func_arg)
{
    function(func_arg);
}

// 创建一优先级为prio的线程,线程名为name,线程所执行的函数是function(func_arg) 
task_struct* thread_start(char* name, int prio, thread_func function, void*  func_arg) 
{ 
    // pcb都位于内核空间,包括用户进程的pcb也是在内核空间
    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;  
}

thread_start就是开启线程的接口函数，在调用的时候主要是通过里面的内联汇编进入到线程函数中，该内联汇编的主要作用是准备好数据之后执行ret，此时会从栈顶会得到返回地址，该地址也就是上面赋值的eip，也就是kernel_thread的地址，然后执行该函数，kernel_thread从栈中得到参数，也就是栈顶+4的真正要执行的线程函数地址，和栈顶+8的线程函数所需的参数。

线程调度

上面简单的模拟了一下线程的创建，但是没有实现线程的调度工作，所以创建线程之后，CPU只会在该线程上执行，所以表现出来还是单线程。

这里会采用轮询算法实现多线程的调度工作。每产生一个时钟中断就算是一个时钟周期，当前线程的时钟周期执行完了之后，就会将该线程放到队尾，换下一个线程执行。

每一个线程所能执行的时钟周期由它的优先级决定。

用了一个双向链表来存储线程的节点信息，该双向链表结构如下

1
2
3
4
5
6
7
8
9
10
11
struct list_elem
{
    struct list_elem *prev;
    struct list_elem *next;
};

struct list
{
    struct list_elem head;
    struct list_elem tail;
};

初始化线程信息

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
typedef struct tag_task_struct
{
    uint32_t *self_kstack; // 内核线程的栈顶地址
    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 stack_magic;   // 栈的边界标记，用来检测栈溢出
}task_struct;

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

    if (pthread == main_thread)
    {
        pthread->status = TASK_RUNNING;
    }
    else
    {
        pthread->status = TASK_READY;
    }

    pthread->priority = prio;
    pthread->ticks = prio;
    pthread->elapsed_ticks = 0;
    pthread->pgdir = NULL;

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

创建线程时将线程添加进链表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建一优先级为prio的线程,线程名为name,线程所执行的函数是function(func_arg) 
task_struct* thread_start(char* name, int prio, thread_func function, void*  func_arg) 
{ 
    // pcb都位于内核空间,包括用户进程的pcb也是在内核空间
    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;  
}

初始化内核主线程。

在当初写内核加载器的时候，内核的栈就已将预留出来了。当时内核的入口地址是0xc009f000。内核的栈地址在0xc009e000处，这块空间时不需要额外进行分配的。由于目前已知运行在内核上，可以通过running_thread()直接获取到该页的起始地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
task_struct *running_thread()
{
    uint32_t esp;

    asm ("mov %%esp, %0" : "=g" (esp));
    return (task_struct *)(esp & 0xfffff000);
}

static void make_main_thread()
{
    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);
}

线程调度器

该调度器会在线程的时间片用完之后被调用。如果该线程是在运行态因为时间片用完的情况下，直接将其加入到就绪队列的队尾。因为其他原因被挂起的情况暂不处理。

然后会从就绪队列中取出下一个节点。该节点是就绪线程的节点地址。也就是task_struct中的general_tag地址，需要通过该地址找到task_struct的首地址。这里通过宏来实现，实现过程也很简单。用该节点的地址 - general_tag在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
31
32
33
#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))

void schedule()
{
    ASSERT(intr_get_status() == INTR_OFF);

    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);
    task_struct* next = elem2entry(task_struct, general_tag, thread_tag);
    next->status = TASK_RUNNING;
    switch_to(cur, next);
}

switch_to函数用来实现线程的切换，它需要做的就是保存当前环境，进入到另一个线程当中，进入的方式就是通过前面介绍的ret指令

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

时钟中断号是0x20，没发生一次时钟中断，就要将当前线程的可执行时间片减一，直到他时间片用完，进行线程调度。下面是时钟中断处理函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void intr_timer_handler()
{
    task_struct *cur_thread = running_thread();

    ASSERT(cur_thread->stack_magic == 0x19971234);

    cur_thread->elapsed_ticks++;

    ticks++;

    if(cur_thread->ticks == 0)
    {
        schedule();
    }
    else
    {
        cur_thread->ticks--;
    }
}

线程调度总算是差不多了。个人感觉还有很多地方理解不到位，里面如果有错误，还望指出。

运行一下看看结果如何

mark