目錄 一、前景回顧 二、線程的實現 三、線程的切換 四、運行測試 一、前景回顧 上一回我們實現了記憶體管理系統,說實話代碼還是比較多,看起來還是比較頭疼的,不過為了知識這都是小事。這一節終於可以來實現我們的線程了,以前學操作系統的時候,聽到的最多的就是什麼線程,進程等,這一回我們來自己動手實現一下,加 ...
目錄
一、前景回顧
二、線程的實現
三、線程的切換
四、運行測試
上一回我們實現了記憶體管理系統,說實話代碼還是比較多,看起來還是比較頭疼的,不過為了知識這都是小事。這一節終於可以來實現我們的線程了,以前學操作系統的時候,聽到的最多的就是什麼線程,進程等,這一回我們來自己動手實現一下,加深對線程的理解。
我相信能認真去看這篇博客的同學,不會是零基礎。所以我也就不再深入地去講解進程和線程的區別。這裡我引入書中的話:
線程是什麼?具有能動性、執行力、獨立的代碼塊。
進程是什麼?進程=線程+資源。
先貼上代碼,在project/kernel目錄下新建list.c、list.h以及thread.c和thread.h文件。
1 #include "list.h"
2 #include "interrupt.h"
3 #include "print.h"
4
5 void list_init(struct list*list)
6 {
7 list->head.prev = NULL;
8 list->head.next = &list->tail;
9 list->tail.prev = &list->head;
10 list->tail.next = NULL;
11 }
12
13 /*將鏈表元素elem插入到元素before之前*/
14 void list_insert_before(struct list_elem *before, struct list_elem *elem)
15 {
16 enum intr_status old_state = intr_disable();
17 before->prev->next = elem;
18 elem->prev = before->prev;
19
20 elem->next = before;
21 before->prev = elem;
22 intr_set_status(old_state);
23 }
24
25 /*添加元素到列表隊首,類似棧push操作*/
26 void list_push(struct list *plist, struct list_elem *elem)
27 {
28 list_insert_before(plist->head.next, elem);//在隊頭插入elem
29 }
30
31 /*追加元素到鏈表隊尾,類似隊列的先進先出*/
32 void list_append(struct list *plist, struct list_elem *elem)
33 {
34 list_insert_before(&plist->tail, elem);
35 }
36
37 /*使元素pelem脫離鏈表*/
38 void list_remove(struct list_elem *elem)
39 {
40 enum intr_status old_state = intr_disable();
41 elem->prev->next = elem->next;
42 elem->next->prev = elem->prev;
43 intr_set_status(old_state);
44 }
45
46
47 /*將鏈表第一個元素彈出並返回,類似棧的pop操作*/
48 struct list_elem *list_pop(struct list *plist)
49 {
50 struct list_elem *elem = plist->head.next;
51 list_remove(elem);
52 return elem;
53 }
54
55 /*從鏈表中查找元素obj_elem,成功返回true,失敗返回false*/
56 bool elem_find(struct list *plist, struct list_elem *obj_elem)
57 {
58 struct list_elem *elem = plist->head.next;
59 while (elem != &plist->tail) {
60 if (elem == obj_elem) {
61 return true;
62 }
63 elem = elem->next;
64 }
65 return false;
66 }
67
68 /*返回鏈表長度*/
69 uint32_t list_len(struct list *plist)
70 {
71 struct list_elem *elem = plist->head.next;
72 uint32_t length = 0;
73 while (elem != &plist->tail) {
74 length++;
75 elem = elem->next;
76 }
77 return length;
78 }
79
80 /*判斷鏈表是否為空,空時返回true,否則返回false*/
81 bool list_empty(struct list *plist)
82 {
83 return (plist->head.next == &plist->tail ? true : false);
84 }
85
86
87 /*把列表plist中的每個元素elem和arg傳給回調函數func*/
88 struct list_elem *list_traversal(struct list *plist, function func, int arg)
89 {
90 struct list_elem *elem = plist->head.next;
91 //如果隊列為空,就必然沒有符合條件的節點,直接返回NULL
92 if (list_empty(plist)) {
93 return NULL;
94 }
95
96 while (elem != &plist->tail) {
97 if (func(elem, arg)) {
98 return elem;
99 }
100 elem = elem->next;
101 }
102 return NULL;
103 }
list.c
1 #ifndef __LIB_KERNEL_LIST_H
2 #define __LIB_KERNEL_LIST_H
3 #include "stdint.h"
4
5 #define offset(struct_type, member) (int)(&((struct_type *)0)->member)
6 #define elem2entry(struct_type, struct_member_name, elem_ptr) \
7 (struct_type *)((int)elem_ptr - offset(struct_type, struct_member_name))
8
9 struct list_elem {
10 struct list_elem *prev; //前驅節點
11 struct list_elem *next; //後繼節點
12 };
13
14 struct list {
15 struct list_elem head;
16 struct list_elem tail;
17 };
18
19 typedef bool function(struct list_elem *, int arg);
20
21 struct list_elem *list_traversal(struct list *plist, function func, int arg);
22 bool list_empty(struct list *plist);
23 uint32_t list_len(struct list *plist);
24 bool elem_find(struct list *plist, struct list_elem *obj_elem);
25 struct list_elem *list_pop(struct list *plist) ;
26 void list_remove(struct list_elem *elem);
27 void list_append(struct list *plist, struct list_elem *elem);
28 void list_push(struct list *plist, struct list_elem *elem);
29 void list_insert_before(struct list_elem *before, struct list_elem *elem);
30 void list_init(struct list*list);
31
32 #endif
list.h
#include "thread.h"
#include "string.h"
#include "memory.h"
#include "list.h"
#include "interrupt.h"
#include "debug.h"
#include "print.h"
#include "stddef.h"
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 volatile ("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);
}
/*初始化線程PCB*/
void init_thread(struct task_struct *pthread, char *name, int prio)
{
memset(pthread, 0, sizeof(*pthread));
strcpy(pthread->name, name);
/*由於main函數也封裝成了一個線程,並且他是一直在運行的,所以將其直接設置為TASK_RUNNING*/
if (pthread == main_thread) {
pthread->status = TASK_RUNNING;
} else {
pthread->status = TASK_READY;
}
//pthread->status = TASK_RUNNING;
pthread->priority = prio;
pthread->ticks = prio;
pthread->elapsed_ticks = 0;
pthread->pgdir = NULL;
pthread->self_kstack = (uint32_t *)((uint32_t)pthread + PG_SIZE);
pthread->stack_magic = 0x19870916;
}
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->edi = kthread_stack->esi = 0;
}
/*創建一個優先順序為prio的線程,線程名字為name,線程所執行的函數為function(func_arg)*/
struct task_struct *thread_start(char *name, int prio, thread_func function, void *func_arg)
{
/*創建線程的pcb,大小為4kb*/
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);
/*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(void)
{
//put_str("schedule\n");
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);
}
/*初始化線程環境*/
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.c
#ifndef __KERNEL_THREAD_H
#define __KERNEL_THREAD_H
#include "stdint.h"
#include "list.h"
#include "memory.h"
/*自定義通用函數類型,它將在很多線程函數中作為形參類型*/
typedef void thread_func (void *);
#define PG_SIZE 4096
/*進程或線程的狀態*/
enum task_status {
TASK_RUNNING,
TASK_READY,
TASK_BLOCKED,
TASK_WAITING,
TASK_HANGING,
TASK_DIED
};
/****************中斷棧intr_stack****************/
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;
/*以下由cpu從低特權級進入高特權級時壓入*/
uint32_t err_code;
void (*eip)(void);
uint32_t cs;
uint32_t eflags;
void *esp;
uint32_t ss;
};
/***************線程棧thread_stack**********/
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;
};
/************進程或者線程的pcb,程式控制塊**********/
struct task_struct
{
uint32_t *self_kstack; //每個內核線程自己的內核棧
enum task_status status;
uint8_t priority;
char name[16];
uint8_t ticks; //每次在處理器上執行的時間滴答數
/*此任務自從上CPU運行至今占用了多少滴答數,也就是這個任務執行了多久時間*/
uint32_t elapsed_ticks;
/*general_tag的作用是用於線程在一般的隊列中的節點*/
struct list_elem general_tag;
/*all_list_tag的作用是用於線程thread_all_list的節點*/
struct list_elem all_list_tag;
uint32_t *pgdir;//進程自己頁表的虛擬地址
uint32_t stack_magic;
};
void schedule(void);
struct task_struct *running_thread(void);
static void kernel_thread(thread_func *function, void *func_arg);
void init_thread(struct task_struct *pthread, char *name, int prio);
void thread_create(struct task_struct *pthread, thread_func function, void *func_arg);
struct task_struct *thread_start(char *name, int prio, thread_func function, void *func_arg);
static void make_main_thread(void);
void thread_init(void);
#endif
thread.h
不過我並不建議現在就去看代碼,我當時看這一章看得雲里霧裡,後面捋了好久,現在希望你能跟著我的思路從巨集觀上瞭解線程的創建,再回去掐細節就很好理解了。
首先,我們先定義PCB結構,PCB結構由中斷棧、線程棧和task_struct組成:
1 /****************中斷棧intr_stack****************/
2 struct intr_stack {
3 uint32_t vec_no;
4 uint32_t edi;
5 uint32_t esi;
6 uint32_t ebp;
7 uint32_t esp_dummy;
8 uint32_t ebx;
9 uint32_t edx;
10 uint32_t ecx;
11 uint32_t eax;
12 uint32_t gs;
13 uint32_t fs;
14 uint32_t es;
15 uint32_t ds;
16
17 /*以下由cpu從低特權級進入高特權級時壓入*/
18 uint32_t err_code;
19 void (*eip)(void);
20 uint32_t cs;
21 uint32_t eflags;
22 void *esp;
23 uint32_t ss;
24 };
25
26 /***************線程棧thread_stack**********/
27 struct thread_stack
28 {
29 uint32_t ebp;
30 uint32_t ebx;
31 uint32_t edi;
32 uint32_t esi;
33
34 void (*eip) (thread_func *func, void *func_arg);
35 void (*unused_retaddr);
36 thread_func *function;
37 void *func_arg;
38 };
39
40 /************進程或者線程的pcb,程式控制塊**********/
41 struct task_struct
42 {
43 uint32_t *self_kstack; //每個內核線程自己的內核棧
44 enum task_status status; //線程或進程狀態
45 uint8_t priority; //線程或進程狀態
46
47 char name[16]; //線程或進程名稱
48 uint8_t ticks; //每次在處理器上執行的時間滴答數
49
50 /*此任務自從上CPU運行至今占用了多少滴答數,也就是這個任務執行了多久時間*/
51 uint32_t elapsed_ticks;
52
53 /*general_tag的作用是用於線程在一般的隊列中的節點*/
54 struct list_elem general_tag;
55
56 /*all_list_tag的作用是用於線程thread_all_list的節點*/
57 struct list_elem all_list_tag;
58
59 uint32_t *pgdir; //進程自己頁表的虛擬地址
60
61 uint32_t stack_magic; //魔數 邊緣檢測使用
62 };
PCB
有了PCB,那麼如何實現線程呢?在Linux中提供創建線程的函數為:
int pthread_create(pthread_t *id , pthread_attr_t *attr, void(*fun)(void*), void *arg);
其中fun就是線程將要執行的函數,arg就是要往函數裡面傳遞的參數。
照貓畫虎,我們也實現一個類似的函數,就叫做:
struct task_struct *thread_start(char *name, int prio, thread_func function, void *func_arg);
其中name表示線程名字,prio表示線程優先順序,function表示線程將要執行的函數,func_arg表示傳遞給函數的參數。
在這個函數中我們對線程PCB噼里啪啦進行初始化等一系列操作之後,最後在記憶體中出現了這麼一塊東西:
PCB在記憶體中的結構如上圖所示,從上往下,首先是intr_stack,中斷棧,它的作用是什麼呢?假設我們的線程被調度在CPU上運行,突然來了一個中斷,這時CPU肯定不能馬上轉頭去處理中斷,需要先把線程當前的運行環境給保存下來,然後才去處理中斷。保存在哪裡呢?就保存在這個中斷棧中,關於這部分後面章節還會詳細講到,這裡先不管;隨後是thread_stack,又叫線程棧,它的作用就是保存線程需要運行的函數以及傳遞給該函數的參數,可以看到eip指向的函數:kernel_thread(thread_func *, void *)就是我們最終線程需要去執行的函數。至於其他的幾個參數,待會兒再說;最後是task_struct,它呢就是保存了線程的一些基本信息,比如線程名稱、優先順序、狀態等等。
線程是怎麼切換的呢?或者換句話說,線程是怎麼被調度上CPU,又怎麼被調度下CPU的呢?這裡就不賣關子了,還記得我們線上程的初始化中,有一個ticks的變數麽?這個ticks變數在初始化時就被賦了一定的值。另一邊,在我們的系統中開啟了一個定時器中斷,這個中斷每隔一段時間就會進入中斷處理函數,在中斷處理函數中將當前線程的ticks減1,當ticks被減為0後就調用schedule函數將當前線程調下,將下一個就緒線程調度上CPU,否則便從中斷處理函數返回繼續執行當前線程的程式。
現線上程的切換我們也講完了,不過我想你可能還是迷迷糊糊,心想就這?我還是不懂嘛。
不急,我們還是帶入具體情況來一步一步分析。現在我們來假想這麼一種情況,假如我們的線程A的ticks已經減為0,那麼意味著線程A要被換下,而下一個線程B要被換上,讓我們來看一下線程A是如何切換到線程B的。先來看看schedule()這個函數,schedule()定義在thread.c文件中,這個函數就是調度函數。
/*實現任務調度*/
void schedule(void)
{
//put_str("schedule\n");
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 = NU