一、课程设计题目及内容 题目六：C 语言实现用户态线程 内容：在不用操作系统提供的pthread系列函数的情况下，用C语言自行实现用户态线程，包括控制流切换、上下文切换、线程设计和主动切换、时间片轮转调度等功能。 环境：ubuntu 16.04 32位操作系统-----Very import！！！！ 方法：在以下资料指导下完成： 访问资料（操作系统基础： C 语言实现用户态线程（实战）） 二、程序中使用的数据结构及主要符号说明
struct thread_struct { int id; //thread_id void (*thread_func)();//The function for thread processing int esp; // esp(Top of running stack) unsigned int wakeuptime; // wakeuptime int status; // The status of running int counter; //The number of counter int priority; // The priority value int stack[STACK_SIZE];//Running stack };**程序中主要用到的数据结构是线程的结构体thread_struct，线程的结构体中保存了线程中应该有的属性和方法，符号说明如下：
id:用来记录线程的id，即thread_id thread_func:用来记录线程所用来执行的函数 esp:用来记录程序运行中的栈顶，即栈顶指针 wakeuptime:用来记录线程的唤醒时间，利用当前时间+时间间隔计算得出 status:用来记录线程的运行状态，包括RUNNING，SLEEP，EXIT，READY等 counter:用来记录线程需要占用的时间片 priority:用来记录线程的优先级 stack:线程运行所需要的栈空间**三、程序流程图
四、带有注释的源程序 1.thread.h，用来定义线程结构体以及一些需要用到的宏变量，以及声明线程函数
#define STACK_SIZE 1024 //Define max size of thread_stack #define THR_TASKS 32 //Define max size of thread #define THREAD_STATUS_RUNNING 0//Status:running #define THREAD_STATUS_SLEEP 1 //Status:sleep #define THREAD_STATUS_READY 2 //Status:ready #define THREAD_STATUS_EXIT 3 //Status:exit struct thread_struct { int id; //thread_id void (*thread_func)();//The function for thread processing int esp; // esp(Top of running stack) unsigned int wakeuptime; // wakeuptime int status; // The status of running int counter; //The number of counter int priority; // The priority value int stack[STACK_SIZE];//Running stack }; int thread_create(int *tid,void (*start_routine)()); int thread_join(int tid); void mysleep(int seconds);2.thread.c，实现线程的相关函数thread_create、thread_join等
#include "thread.h" #include <stdlib.h> #include <signal.h> #include <sys/time.h> #include <stdio.h> static struct thread_struct init_task = {0, NULL, THREAD_STATUS_RUNNING, 0, 0, 15, 15, {0}}; struct thread_struct *current = &init_task; //Init current thread struct thread_struct *task[THR_TASKS] = {&init_task,}; //Init task list void schedule(); //Define schedule void start(struct thread_struct *tsk) { tsk->thread_func(); //Run thread tsk->status = THREAD_STATUS_EXIT; //status printf("Thread %d excited\n",tsk->id); task[tsk->id] = NULL; //Set current position to NULL schedule(); //Schedule } int thread_create(int *tid, void (*start_routine)()) { int id = -1; //Init the thread_id struct thread_struct *tsk = (struct thread_struct *)malloc(sizeof(struct thread_struct)); //Find a null task position while (++id < THR_TASKS && task[id]) ; //Can't find a null task position if (id == THR_TASKS) return -1; task[id] = tsk; //Put the tsk into right position if (tid) //Set id ro tid *tid = id; tsk->id = id; //Set id to thread_id tsk->thread_func = start_routine; //The function of thread processing int *stack = tsk->stack; // Get address of thread stack tsk->esp = (int)(stack + STACK_SIZE - 11); //Get esp-The top of stack tsk->status = THREAD_STATUS_RUNNING; //set running to status tsk->wakeuptime = 0; //Set wakeuptime tsk->counter = 15; //Set counter tsk->priority = 15; //set priority // Running stack // Low address stack[STACK_SIZE - 11] = 7; // eflags stack[STACK_SIZE - 10] = 6; // eax stack[STACK_SIZE - 9] = 5; // edx stack[STACK_SIZE - 8] = 4; // ecx stack[STACK_SIZE - 7] = 3; // ebx stack[STACK_SIZE - 6] = 2; // esi stack[STACK_SIZE - 5] = 1; // edi stack[STACK_SIZE - 4] = 0; // old ebp stack[STACK_SIZE - 3] = (int)start; // ret to start stack[STACK_SIZE - 2] = 100; // ret to unknown stack[STACK_SIZE - 1] = (int)tsk; // The args of start // High address return 0; } int thread_join(int tid) { //While status is not exit,continue to schedule while(task[tid]->status != THREAD_STATUS_EXIT) { schedule(); } free(task[tid]); //Free memory of task[tid] task[tid] = NULL; //Set this task position to NULL }3.switch.s，使用汇编语言编写，用于线程的切换（运行过程中栈的切换）
.section .text .global switch_to_next switch_to_next: push %ebp mov %esp,%ebp push %edi push %esi push %ebx push %edx push %ecx push %eax pushfl mov current,%eax mov %esp,8(%eax) mov 8(%ebp),%eax mov %eax,current mov 8(%eax),%esp popfl popl %eax popl %edx popl %ecx popl %ebx popl %esi popl %edi popl %ebp ret4.schedule.c，实现线程的调度算法，利用时钟中断计算出时间片，并沿用了Linus大神写的时间片轮转算法。
#include "thread.h" #include <stdlib.h> #include <sys/time.h> #include <signal.h> #include <stdio.h> extern struct thread_struct *current; //Has defined in schedule.c extern struct thread_struct *task[THR_TASKS]; //Has defined in schedule.c //Declare function switch_to_next //function switch_to_next has defined in switch.s void switch_to_next(struct thread_struct *next); static unsigned int getmstime() //Function getmstime { struct timeval tv; if (gettimeofday(&tv, NULL) < 0) { perror("gettimeofday"); exit(-1); } return tv.tv_sec * 1000 + tv.tv_usec / 1000; } //Function pick in order to select next thread to run //It was written by Linus,by using algorithm RR //I think that is the best way to shedule static struct thread_struct *pick() { int i, next, c; for (i = 0; i < THR_TASKS; ++i) { if (task[i] && task[i]->status != THREAD_STATUS_EXIT && getmstime() > task[i]->wakeuptime) { task[i]->status = THREAD_STATUS_RUNNING; } } while (1) { c = -1; next = 0; for (i = 0; i < THR_TASKS; ++i) { if (!task[i]) continue; if (task[i]->status == THREAD_STATUS_RUNNING && task[i]->counter > c) { c = task[i]->counter; next = i; } } if (c) break; // If all counter are zero,reset the counter if (c == 0) { for (i = 0; i < THR_TASKS; ++i) { if (task[i]) { task[i]->counter = task[i]->priority + (task[i]->counter >> 1); } } } } return task[next]; //Return the next struct of thread } //Close alarm void closealarm() { sigset_t mask; sigemptyset(&mask); sigaddset(&mask, SIGALRM); if (sigprocmask(SIG_BLOCK, &mask, NULL) < 0) { perror("sigprocmask BLOCK"); } } //Open alarm void openalarm() { sigset_t mask; sigemptyset(&mask); sigaddset(&mask, SIGALRM); if (sigprocmask(SIG_UNBLOCK, &mask, NULL) < 0) { perror("sigprocmask BLOCK"); } } //Fuction schedule //In order to switch to next task void schedule() { struct thread_struct *next = pick(); if (next) { switch_to_next(next); } // schedule never return } //Function mysleep in oreder to achieve sleep void mysleep(int seconds) { //pass the arg seconds //Set the wakeup time of current thread current->wakeuptime = getmstime() + 1000 * seconds; //Set the status of current thread to sleep current->status = THREAD_STATUS_SLEEP; //sleep and schedule to run other threads schedule(); } static void do_timer() { //Function Clock interrupt if (--current->counter > 0) return; current->counter = 0; schedule(); } __attribute__((constructor)) //Clock interrupt static void init() { struct itimerval value; value.it_value.tv_sec = 0; value.it_value.tv_usec = 1000; value.it_interval.tv_sec = 0; value.it_interval.tv_usec = 1000 * 10; // vulue is 10 ms if (setitimer(ITIMER_REAL, &value, NULL) < 0) { perror("setitimer"); } signal(SIGALRM, do_timer); }5.func.h，定义了四个用于创建线程的函数，fun1、fun2、fun3以及fun4
#include <stdio.h> extern void mysleep(int seconds); void fun1() { int i = 10; while (i--) { printf("Wanna--fun1 is running\n"); mysleep(2); } } void fun2() { int i = 10; while (i--) { printf("Wanna--fun2 is running\n"); mysleep(1); } } void fun3() { int i = 2; while (i--) { printf("Wanna--fun3 is running\n"); mysleep(5); } } void fun4() { int i = 15; int m; int n; while(i--) { printf("Wanna--fun4 is running\n"); for (m = 0; m < 1000; ++m) for (n = 0; n < 1000; ++n); } }6.main.c,程序的主函数，用来创建和执行线程
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include "thread.h" #include "func.h" extern void schedule(); int main() { int tid1, tid2, tid3, tid4; thread_create(&tid1, fun1); printf("Thread %d has been created\n", tid1); thread_create(&tid2, fun2); printf("Thread %d has been created\n", tid2); thread_create(&tid3, fun3); printf("Thread %d has been created\n", tid3); thread_create(&tid4, fun4); printf("Thread %d has been created\n", tid4); int i = 2; while (i--) { printf("Wanna--Main is running\n"); mysleep(3); } thread_join(tid1); thread_join(tid2); thread_join(tid3); thread_join(tid4); return 0; }7.Makefile，方便进行多文件编译
main:main.c thread.c thread.h schedule.c func.h switch.s gcc -g main.c thread.c schedule.c func.h switch.s -o main run: ./main五、程序的初值（如有）和执行结果 另外附加Github地址：访问作者的Github 也可以使用下面的命令克隆
git clone https://github.com/wanna280/thread_schedule.git六、实验结果分析、实验收获和体会 实验当中采用的是个人阿里云服务器，并安装的Ubuntu 16.04 LTS的系统镜像。由于个人习惯不喜欢直接跑虚拟机（电脑原因，很卡），因此采用的是ssh去连接服务器的方式去运行Linux系统的程序，这样方便我在多台设备之间随时去编写代码。 在实验中，我跟着博客一步步的走，首先在程序的执行栈的那里卡了很久，老是不明白那个执行栈的过程究竟是什么样的，看汇编代码时有着那种单条语句看懂，但是连起来是什么意思就啥都不懂的感觉，因为之前对这方面的了解很少，所以一直卡着不能往下走，最终我用笔在纸上一步步的画执行过程，一次次的错（因为不理解）打击了我的心态，都有点想放弃的感觉，不过我从来都是不达目的不罢休，于是一直卡在那里，最终慢慢的，网上查了不少资料，也一步步的跟着走，还根据很多实例c语言代码的反汇编代码去一个个的实践，最终实践了利用缓冲区溢出这一程序员经常遇到但是却不以为意的bug实现了运行栈的切换，从而实现所谓的控制流切换功能，最终去调用了在main函数中没有调用，但是却已经给予实现的函数了的函数。然后在c语言中嵌入汇编代码实现了运行栈的切换，这一原理也去实现了所谓的控制流切换。在这个过程中我还利用到了gdb的方式去查看反汇编代码，也能根据这个构造字符串去调用没有调用到的函数。 接着，写了switch.s这一上下文切换的函数，并在main函数中自己构造了两个栈去实现所谓的线程切换。然后根据线程的一些基础属性和方法，构建了thread_struct这一线程结构体，去保存一些线程内的内容，封装了thread_create这一函数用来创建线程，start的函数用来启动线程，在start过程中又会不断的挑选下一个线程去进行运行，于是另外封装了函数pick用来从任务列表当中去挑选下一个线程进行运行，并且这里由于我们的上下文切换，不再像之前，只是一个数字的切换，现在改成了结构体的方式来切换，传递的参数都是一个结构体，于是这里修改了汇编代码switch.s用来切换上下文。由于每个函数中当中都会使用到调度的重复赘余内容，于是这里又封装了一个函数schedule去替换重复赘余的内容。 接下来，使用自定义函数mysleep去替换掉调用的sleep函数，由于sleep在底层会涉及到调度的内容，因此将调度函数schedule和时钟中断封装在一起成为mysleep函数，时钟中断的内容我不熟，于是借用了大神的方法去实现。在这里，又涉及到线程的运行状态的问题，因此我又在结构体当中去封装了运行状态status字段，以及唤醒时间wakeuptime字段。并对有涉及到这方面的函数进行相应的更改。 最后就是时间片轮转算法（RR）这一如今操作系统当中使用最广泛的算法，这里也需要用到时间片和优先级的属性，于是在线程结构体当中继续添加字段counter、priority字段，并对相应的内容，比如线程初始化等相关内容进行更改，定义了时钟中断函数do_timer，最后时间片轮转算法的内容是借鉴了Linus大神在Linux0.11中写的代码。最终挫折无限，bug无限，一步步的实现了用户态的线程。 在这个过程中使用到了多文件编译，于是这里我用vim编写了Makefile文件进行更方便的多文件编译，也是在这个过程当中学会了Makefile的使用。 很不错的课程设计项目，虽然我是在博客的一步步引导之下完成的，但是自己也确实从中收获到了不少，对于线程的调度，究竟是怎么来实现的，让我们明白了使用pthread.h中为我们提供的threa_create、thread_join函数的底层原理，并且在之前我对线程的了解仅仅是从课本上去了解，也从没这么近距离的去弄明白线程的底层原理。在很多的编程语言当中，都会利用到线程的知识，比如C#、Java等语言当中线程的使用都是很多的，这次的课程设计让我对这方面的知识了解更深入了。关于线程的调度当中的同步和互斥等相关的内容，由于本人技术原因，还没对其进行实践，不过我相信我会在接下来的时间里去好好学习相关知识，自己去完善相应的板块的代码。与此同时，我已经将代码整个项目上传到Github，方便我以后的学习和完善。
