操作系统真象还原实验记录之实验十五：多线程调度

对应书P428 9.4节

1.相关基础知识

2.实验记录

2.1 实验流程

上次实验中，实现了一个线程的运行：具体是

1.申请了一页物理页作为PCB

2.init_thread填写了位于PCB所在物理页最低地址处的PCB结构体

3.thread_create留出位于PCB所在物理页最高地址的中断栈、线程栈的位置，并填写了线程栈的各个成员，其中eip赋值成了函数kernel_thread地址。

4.最后一句内联汇编将esp置为线程栈首地址，ret开启了线程，执行kernel_thread函数。

对比学习

本次实验实现了多线程的调度，增加的功能如下

1.增了加专门的时钟中断处理函数，判断如果当前线程时间片用完，则执行调度函数schedule

2.schedule对当前线程如果时间片用完，则加入就绪队列，然后弹出队头，调用switch_to(cur,next)函数

3.switch_to函数保护当前线程环境，恢复下一个线程环境，ret开始执行下一个线程。

具体流程如下：

1.main.c里的init_all创建了主线程main_thread，为运行态，然后thread_start创建了两个线程。

注意：此时的thread_start没有ret指令了，说明没有开启此线程，仅仅完成了单线程实验init和create的工作，并将线程挂上就绪队列，此线程的开启由时钟中断引出。

2.main线程时间片31，argA时间片31，argB时间片8。开中断后，时钟中断频繁发生，cpu频繁执行新写的时钟中断处理程序，不断判断主线程时间片是否够用，如果为0，在schedule中将主线程则放入就绪队列，补满时间片，并出栈队头的argA，从而执行argA线程。

3.之后便是依次循环执行，因此main argA argB会循环打印。

串联下用到的函数。

main.c 里调用thread_init

thread_init调用make_main_thread

make_main_thread里先调用running_thread()，由于loader.s已经将esp赋值为0xc009f000，取前20位则获得预留好的的PCB页首地址。（TMD这得到的明明就是下一页最低地址，书上到底是什么意思）

调用init_thread(main_thread, “main”, 31)，设置好位于实地址0x0009e000物理页的PCB的成员变量，其中状态为运行态。然后init_all执行完毕。

之后调用两个thread_start函数，这个函数先申请了一页物理页用作PCB，然后调用了init_thread将申请的PCB结构体赋值好，然后调用thread_create在该物理页最高地址留出中断栈、线程栈，并且填写线程栈。最后加入就绪队列和全部线程队列。

然后main.c就开始一直循环打印main，直到时钟中断处理程序把他的时间片消耗完，然后执行schedule(cur,next)函数

当esp位于主线程的PCB最低地址时，schedule(cur,next)函数中，可以直接cur=running_thread()获得当前线程pcb，加入队尾，然后在就绪队列出队一个pcb作为next，注意这里出队的不是PCB地址，需要转化后才是PCB。随后执行switch(cur,next)

switch(cur,next)函数中，先在任务切换时的栈里拿到cur，从而拿到cur里的self_kstack保存到eax。然后又在任务切换时的栈里拿到next，将next里的self_kstack赋值给esp，然后pop掉几个寄存器后，一句ret开启函数kernel_thread,kernel_thread不断执行function打印argA，直到他又被时钟中断给消耗光时间片。

2.2 main.c

#include "interrupt.h"#include "init.h"#include "thread.h"#include "print.h"void k_thread_a(void* );void k_thread_b(void* );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_b, "argB ");   intr_enable();   while(1){	put_str("Main ");}   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);	}		}

2.3 init.c

#include "init.h"#include "print.h"#include "interrupt.h"#include "../device/timer.h"/*负责初始化所有模块 */void init_all() {   put_str("init_all\n");   idt_init();	     // 初始化中断   mem_init();	     // 初始化内存管理系统 thread_init();    // 初始化线程相关结构	timer_init(); }

2.4 thread.c

#include "thread.h"#include "stdint.h"#include "string.h"#include "global.h"#include "debug.h"#include "interrupt.h"#include "print.h"#include "memory.h"#include "list.h"struct task_struct* main_thread;    // 主线程PCBstruct list thread_ready_list;	    // 就绪队列struct list thread_all_list;	    // 所有任务队列static struct list_elem* thread_tag;// 用于保存队列中的线程结点/* 获取当前线程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); }/* 初始化线程栈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);   if (pthread == main_thread) {/* 由于把main函数也封装成一个线程,并且它一直是运行的,故将其直接设为TASK_RUNNING */      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->ticks = prio;   pthread->elapsed_ticks = 0;   pthread->pgdir = NULL;   pthread->stack_magic = 0x19870916;	  // 自定义的魔数}/* 创建一优先级为prio的线程,线程名为name,线程所执行的函数是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);   /* 确保之前不在队列中 */   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,就是为其预留了tcb,地址为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);}/* 实现任务调度 */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);}/* 初始化线程环境 */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");}

2.5 thread.h

#ifndef __THREAD_THREAD_H#define __THREAD_THREAD_H#include "stdint.h"#include "list.h"#include "bitmap.h"#include "memory.h"#define TASK_NAME_LEN 16#define MAX_FILES_OPEN_PER_PROC 8/* 自定义通用函数类型,它将在很多线程函数中做为形参类型 */typedef void thread_func(void*);typedef int16_t pid_t;/* 进程或线程的状态 */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所调用的函数所需的参数};/* 进程或线程的pcb,程序控制块 */struct task_struct {   uint32_t* self_kstack;	 // 各内核线程都用自己的内核栈   enum task_status status;   char name[16];   uint8_t priority;   uint8_t ticks;	   // 每次在处理器上执行的时间嘀嗒数/* 此任务自上cpu运行后至今占用了多少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;	 // 用这串数字做栈的边界标记,用于检测栈的溢出};extern struct list thread_ready_list;extern struct list thread_all_list;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);struct task_struct* running_thread(void);void schedule(void);void thread_init(void);#endif

2.6 timer.c

#include "timer.h"#include "io.h"#include "print.h"#include "interrupt.h"#include "thread.h"#include "debug.h"#define IRQ0_FREQUENCY	   100#define INPUT_FREQUENCY	   1193180#define COUNTER0_VALUE	   INPUT_FREQUENCY / IRQ0_FREQUENCY#define CONTRER0_PORT	   0x40#define COUNTER0_NO	   0#define COUNTER_MODE	   2#define READ_WRITE_LATCH   3#define PIT_CONTROL_PORT   0x43uint32_t ticks;          // ticks是内核自中断开启以来总共的嘀嗒数/* 把操作的计数器counter_no、读写锁属性rwl、计数器模式counter_mode写入模式控制寄存器并赋予初始值counter_value */static void frequency_set(uint8_t counter_port, \			  uint8_t counter_no, \			  uint8_t rwl, \			  uint8_t counter_mode, \			  uint16_t counter_value) {/* 往控制字寄存器端口0x43中写入控制字 */   outb(PIT_CONTROL_PORT, (uint8_t)(counter_no << 6 | rwl << 4 | counter_mode << 1));/* 先写入counter_value的低8位 */   outb(counter_port, (uint8_t)counter_value);/* 再写入counter_value的高8位 */   outb(counter_port, (uint8_t)counter_value >> 8);}/* 时钟的中断处理函数 */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--;   }}/* 初始化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");}

2.7 interrupt.c 增加函数

void register_handler(uint8_t vector_no, intr_handler function);/* 在中断处理程序数组第vector_no个元素中注册安装中断处理程序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; }

2.8 switch.S

[bits 32]section .textglobal switch_toswitch_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

2.9 list.h

#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

2.9 list.c

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

3.实验结果

自行更新makefile

运行bochs

转载地址：http://jyqof.baihongyu.com/

你可能感兴趣的文章