IGNORANT

操作系统实验——线程创建与调度

说明:

最近做了实验二和实验三,由于两者相关,所以堆在一起总结。
另外注意到,各个bbs上也流传着往届学长写的总结,这也是老师只甩给我们PPT,我们也能做出这实验的原因之一。

在此呢,我就写写自己的总结,当然也参考了往届学长的做法(,并且还把老师的PPT抄了一遍)。

实验目的

实验内容

先贴实验内容:(EPOS系统,我会在上篇文章的实验一给出)

预备知识

线程API

下面说明实验所用到的API函数。
线程创建

int task_create(void *tos, void (*func)(void *pv), void *pv);

tos :用户栈的栈顶指针
func :线程函数
pv :传递给线程函数func的参数,一般传结构体指针以传多个参数
返回值 :大于0,则表示新创建线程之ID

线程退出

int task_exit(int code_exit);

code_exit :线程的退出代码

获取当前线程的ID

int task_getid();

等待线程退出

int task_wait(int tid, int *pcode_exit);

tid :要等待线程之ID
pcode_exit :如果非NULL,用于保存线程tid的退出代码

Sample:

// Define thread function
void tsk_foo(void* pv) {
    printf("This is task foo with tid=%d\r\n", task_getid());
    // exit this task
    task_exit(0);
}
int main() {
    unsigned int st_Size = 1024 * 1024;
    // alloc user stack
    unsigned char* stack_foo = (unsigned char*)malloc(st_Size);
    // create thread
    int tid_foo = task_create(stack_foo + st_Size, tsk_foo, pv);
    // waiting for the quiting of threads
    task_wait(tid_foo, NULL);
    // release the memory
    free(stack_foo);
}

随机数组生成

void RandDemo() {
    srand(time(NULL));    // Use current time as seed for random generator
    int i;
    for (i = 0; i < n; i++) {
        //generate elements are between 0~max_Elem
        array[i] == rand() % max_Elem;    
    }
}

图形模式API

下面说明本实验可能用到的API函数。
获取当前系统支持的图形模式

int list_graphic_modes();

需在文本模式下运行才可看到结果。
老师PPT参考模式列表:

进入图形模式

int init_graphic(int mode);

mode: 为上述图形模式对应的值,如int mode=0x100

获取屏幕的分辨率
直接访问变量获取:
水平:g_graphic_dev.XResolution
垂直:g_graphic_dev.YResolution

注:g_graphic_dev在graphics.h中被声明为一个全局变量,使用时应包含此头文件。

打像素点

void setPixel(int x, int y, COLORREF cr); 

(x, y)是像素点坐标
cr是颜色,用宏定义RGB(r,g,b)生成,其中r,g,b的取值范围都是0-255

如何从cr中取出r,g,b?用getXValue(cr),其中X=R,G,B,如getRValue(cr)取出cr的R分量值。

退出图形模式

int exit_graphic();

线程调度

优先级

线程数据结构
epos的线程数据结构为单向链表:

注意:

关于定点数

本次实验为追求性能采用了定点数去定义一部分变量。

注:文件fixedptc.h中定义了定点数类型fixedpt及其运算,所以使用时需包含该头文件

另外,阅读往届学长的实验报告,发现代码中出现很多的fixedpt_mul(,)fixedpt_div(,)fixedpt_add(,)fixedpt_sub(,)fixedpt_fromint(,)fixedpt_toint(,)FIXEDPT_ONE……这是出于对性能的考虑。
但其中fixedpt_add(,)fixedpt_sub(,)的宏定义如下:

#define fixedpt_add(A,B) ((A) + (B))
#define fixedpt_sub(A,B) ((A) - (B)

因此定点加减法可直接使用+、-,因为没任何性能提升,反而让代码像a piece of shit。

实验步骤

增加tcb属性nice

说明:

①kernelkernel.h中,为线程数据结构struct tcb线程的静态优先级nice属性。

struct tcb {
    ……
    struct fpu fpu; //数学协处理器的寄存器
    int nice;   //static priority

    uint32_t signature; //必须是最后一个字段
    ……
};

②在kerneltask.c中,函数sys_task_create中初始化nice=0

struct tcb* sys_task_create(void* tos, void (*func)(void* pv), void* pv) {
    ……
    new->signature = TASK_SIGNATURE;

    new->nice = 0;  // initialize the static priority
    ……
}

增加系统调用

系统调用说明:

①按照实验一,增加系统调用getpriority ,setpriority,
大致步骤略述:

  1. \userapp\include\syscall.h 声明系统调用API
  2. \userapp\lib\syscall-wrapper.S 定义封装例程
  3. \include\syscall-nr.h 定义系统调用号
  4. \kernel\kernel.h 声明系统调用服务例程函数sys_setprioritysys_getpriority
  5. \kernel\machdep.c 实现两个系统调用服务例程函数。
  6. \kernel\machdep.c 在系统调用分发函数syscall()中根据系统调用号加入SYSCALL_xxx分支。

②主要代码:
syscall()分发函数中添加分支:

switch (ctx->eax) {
    ……
    case SYSCALL_getpriority: 
    {
        int ttid = *((int*)(ctx->esp + 4));
        ctx->eax = sys_getpriority(ttid);
    } break;
    case SYSCALL_setpriority:
    {
        int ttid = *((int*)(ctx->esp + 4));
        int pprio = *((int*)(ctx->esp + 8));
        ctx->eax = sys_setpriority(ttid, pprio);
    } break;
    ……
}

系统调用服务例程函数的实现:

struct tcb* GetSelectedTcb(tid) {
    struct tcb* selected_Tcb;
    if (tid) {  // tid!=1
        uint32_t flags;
        save_flags_cli(flags);  // avoid interrupting
        selected_Tcb = g_task_head;
        // find the tcb whose tid == tid
        while (selected_Tcb != NULL) {
            if (selected_Tcb->tid == tid) break;
            selected_Tcb = selected_Tcb->next;
        }
        restore_flags(flags);
    } else  // tid==0,return current tcb
        selected_Tcb = g_task_running;
    return selected_Tcb;
}
int sys_getpriority(int tid) {
    struct tcb* selected_Tcb = GetSelectedTcb(tid);
    return selected_Tcb != NULL ? selected_Tcb->nice + NZERO : -1;
}

int sys_setpriority(int tid, int prio) {
    int op_Result = 0;  // if failed,return -1, otherwise 0
    int valid_Prio = prio > 0 && prio < 2 * NZERO - 1;
    struct tcb* selected_Tcb;
    selected_Tcb = valid_Prio == 1 ? GetSelectedTcb(tid) : NULL;
    selected_Tcb != NULL ? (selected_Tcb->nice = prio - NZERO)
                         : (op_Result = -1);
    return op_Result;
}

tcb增加动态优先级属性

待增加的变量说明

更新规则:
estcpu:
$$estcpu \Leftarrow \frac{2\times g\_load\_avg}{2\times g\_load\_avg +1} \times estcpu+nice$$
可化为
$$estcpu \Leftarrow estcpu-\frac{estcpu}{2\times g\_load\_avg +1}+nice$$
prority:
$$prority \Leftarrow PRI\_USER\_MAX-\frac{estcpu}{4}-2\times nice$$
g_load_avg:
$$g\_load\_avg \Leftarrow \frac{59}{60}\times g\_load\_avg+\frac{1}{60}\times nready$$
可化为
$$g\_load\_avg \Leftarrow g\_load\_avg-\frac{g\_load\_avg}{60}+\frac{ nready}{60}$$

①在struct tcb中,增加两个属性estcpu, priority,头部声明一个全局变量g_load_avg
kernelkernel.h中:
nice属性后插入

int nice;   //static priority  
fixedpt estcpu; //record the time of using cpu  
int priority;   //the priority of thread  

头部需声明:

#include"fixedptc.h"      
#define NZERO 20    //The bound of static priority  
fixedpt g_load_avg; //System average load  

在kerneltask.c中:
头部声明:

#define PRI_USER_MIN 0  
#define PRI_USER_MAX 127  

②在函数sys_task_createnew->nice=0后初始化estcpu=0

new->nice = 0;  // initialize the static priority  
new->estcpu = fixedpt_fromint(0);  
new->priority =  
    PRI_USER_MAX;  // new->priority=PRI_USER_MAX-(estcpu/4)-(nice*2);  
                   // initial the dynamic priority 

③在init_task()中初始化g_load_avg

void init_task() {  
        ……  
    g_task_own_fpu = NULL;  
  
    g_load_avg = fixedpt_fromint(0);  
        ……  
}  

④每次定时器中断更新estcpug_load_avg
在kerneltimer.c中isr_timer()函数前添加UpdateEstcpu()实现每秒为所有线程(运行、就绪和等待)更新estcpug_load_avgisr_timer()中每次定时器中断更新estcpu,其中g_timer_ticks % HZ == 0表示已过1秒,此时应调用UpdateEstcpu()

/**Update estcpu*/
void UpdateEstcpu()
{
    int nready = 0;
    struct tcb* p_Tcb = g_task_head; //point to some tcb in the linked list

    fixedpt deno = g_load_avg + g_load_avg + FIXEDPT_ONE; //the denominator of ratio as estcpu updating

    while (p_Tcb != NULL) {
        //count the num of thread in ready queue
        if (p_Tcb != task0 && p_Tcb->state == TASK_STATE_READY)
            nready++;
        //update estcpu
        p_Tcb->estcpu = p_Tcb->estcpu
            - fixedpt_div(p_Tcb->estcpu, deno)
            + fixedpt_fromint(p_Tcb->nice);
        p_Tcb = p_Tcb->next;
    }
    //update the average load
    g_load_avg = g_load_avg
        - fixedpt_div(g_load_avg, fixedpt_fromint(60))
        + fixedpt_div(fixedpt_fromint(nready), fixedpt_fromint(60));
}

/**
 * 定时器的中断处理程序
 */
void isr_timer(uint32_t irq, struct context* ctx)
{
    g_timer_ticks++;
    //sys_putchar('.');

    if (g_task_running != NULL) {
        //如果是task0在运行,则强制调度
        if (g_task_running->tid == 0) {
            g_resched = 1;
        } else {
            //否则,把当前线程的时间片减一
            --g_task_running->timeslice;

            //update estcpu for every timer tick
            if (g_task_running != task0)
                g_task_running->estcpu = g_task_running->estcpu + FIXEDPT_ONE;

            //如果当前线程用完了时间片,也要强制调度
            if (g_task_running->timeslice <= 0) {
                g_resched = 1;
                g_task_running->timeslice = TASK_TIMESLICE_DEFAULT;
            }
        }
    }
    //one second has gone
    if (g_timer_ticks % HZ == 0)
        UpdateEstcpu();
}

优先级调度算法

调度算法:
①线程链表中仅有task0 ? (切换到task0,重新调度) : ②
②队首为task0 ? (从g_task_head->next开始遍历,然后③) : (从g_task_head开始遍历,然后③)
③从遍历列表中找出最大优先级的tcb,同时更新priority(除task0)
④切换到选中的tcb,重新调度

算法实现:
修改kerneltask.c中的函数schedule(),实现优先级调度算法。
附上修改后的代码,说明见注释:

/**
 *  Calculate the priority,
 *  Find the highest-priority thread, return it
 *  Maybe there's only task0, return it
 */
struct tcb* SelectedTcb() {
    struct tcb* p_Tcb;
    struct tcb* maxprio_Tcb;
    maxprio_Tcb = p_Tcb = g_task_head;
    while (p_Tcb != NULL) {
        // update the priority
        p_Tcb->priority =
            PRI_USER_MAX -
            fixedpt_toint(fixedpt_div(p_Tcb->estcpu, fixedpt_fromint(4))) -
            p_Tcb->nice * 2;
        if (p_Tcb->priority < PRI_USER_MIN) p_Tcb->priority = PRI_USER_MIN;
        if (p_Tcb->priority > PRI_USER_MAX) p_Tcb->priority = PRI_USER_MAX;
        if (p_Tcb != task0)
            if (p_Tcb->priority >=
                    maxprio_Tcb
                        ->priority &&  // search the highest-priority thread
                p_Tcb->state == TASK_STATE_READY)
                maxprio_Tcb = p_Tcb;
        p_Tcb = p_Tcb->next;
    }
    return maxprio_Tcb;  // return the max prio one, maybe task0
}
/**
 * CPU调度器函数
 *
 * 注意:该函数的执行不能被中断
 */
void schedule() {
    struct tcb* select = SelectedTcb();
    if (select == g_task_running) {
        if (select->state == TASK_STATE_READY) {
            return;
        }
        select = task0;
    }
    // printk("0x%d -> 0x%d\r\n", (g_task_running == NULL) ? -1 :
    // g_task_running->tid, select->tid);
    if (select->signature != TASK_SIGNATURE)
        printk("warning: kernel stack of task #%d overflow!!!", select->tid);
    g_resched = 0;
    switch_to(select);
}

测试调度器

后面的工作就是创建线程、定义线程函数、折腾画图函数等操作,不做介绍,直接贴代码。
main.c函数中:

……
#include "graphics.h"
#include "lab3.h"
……
/**
 * 第一个运行在用户模式的线程所执行的函数
 */
void main(void* pv) {
    printf("task #%d: I'm the first user task(pv=0x%08x)!\r\n", task_getid(),
           pv);

    // TODO: Your code goes here
    test_lab3();

    while (1)
        ;
    task_exit(0);

}

lab3.h

#ifndef _LAB3_
#define _LAB3_
/*
#include <inttypes.h>
#include <math.h>
#include <netinet/in.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <syscall.h>
#include "graphics.h"
*/

#define ar_Size 100
#define max_Elem 300
uint16_t w_Line;
uint16_t l_Ratio;
struct Thr {
    int tid;
    int prio;
};

void DrawPrioBar(int length, int LorR) {
    uint16_t x = g_graphic_dev.XResolution / 2;
    int sign = LorR;
    COLORREF cr;
    if (sign == -1)
        cr = RGB(255, 0, 0);
    else
        cr = RGB(0, 255, 0);
    int i, j;
    for (i = 0; i <= 20; ++i)
        for (j = 0; j <= 78; ++j) setPixel(x + sign * i, j, RGB(119, 136, 153));
    for (i = 0; i <= 20; ++i)
        for (j = 0; j <= 78 - 2 * length; ++j)
            setPixel(x + sign * i, 78 - j, cr);
    for (j = 0; j < 78; ++j) setPixel(x, j, RGB(255, 255, 255));
}

void tsk_foo_control(void* pv) {
    int key;
    struct Thr* th = (struct Thr*)pv;
    int tid_A = th[0].tid;
    int prio_A = th[0].prio;
    int tid_B = th[1].tid;
    int prio_B = th[1].prio;

    while (1) {
        key = getchar();
        switch (key) {
            case 0x4800: {  // UP
                if (prio_A >= 1 && prio_A <= 40) {
                    setpriority(tid_A, --prio_A);
                    DrawPrioBar(getpriority(tid_A), -1);
                }
            } break;
            case 0x5000: {  // DOWN
                if (prio_A >= -1 && prio_A <= 38) {
                    setpriority(tid_A, ++prio_A);
                    DrawPrioBar(getpriority(tid_A), -1);
                }
            } break;
            case 0x4d00: {  // RIGHT
                if (prio_B >= 1 && prio_B <= 40) {
                    setpriority(tid_B, --prio_B);
                    DrawPrioBar(getpriority(tid_B), 1);
                }
            } break;
            case 0x4b00: {  // LEFT
                if (prio_B >= -1 && prio_B <= 38) {
                    setpriority(tid_B, ++prio_B);
                    DrawPrioBar(getpriority(tid_B), 1);
                }
            } break;
            default: {
            }
        }
    }
    task_exit(0);
}

//  create 2 arrays
void Generate2arrays(int* ar_1, int* ar_2) {
    srand(time(NULL));
    int i, j;
    float x_Begin = g_graphic_dev.XResolution / 2;
    for (i = 0; i < ar_Size; i++) {
        ar_1[i] = ar_2[i] = rand() % max_Elem;
        // draw lines
        line(0, i * w_Line, ar_1[i] * l_Ratio, i * w_Line, RGB(255, 0, 0));
        line(x_Begin + 28, i * w_Line, x_Begin + 28 + ar_1[i] * l_Ratio,
             i * w_Line, RGB(0, 255, 0));
    }
    for (i = -20; i <= 20; ++i)
        for (j = 0; j <= 78; ++j) setPixel(x_Begin + i, j, RGB(119, 136, 153));
    for (j = 0; j < g_graphic_dev.YResolution; ++j)
        setPixel(x_Begin, j, RGB(255, 255, 255));
}

// set time delay for thread action
void DrawDelay(long lMs) {
    long lRemainingMilliSecond = (lMs) % 1000;
    long lNanoSecond = lRemainingMilliSecond * 1000000;
    struct timespec ts_sleep, ts_remaining;
    ts_sleep.tv_sec = (lMs) / 1000;
    ts_sleep.tv_nsec = lNanoSecond;
    nanosleep(&ts_sleep, &ts_remaining);
}

// swap two elements and draw the lines
void SwapLine(int* array, int area_Num, int a_lineNum, int b_lineNum,
              COLORREF cr) {
    int l_fixed = 28 * area_Num;
    int r_fixed = 28 * (area_Num - 1) * 0;
    uint16_t x_Begin = area_Num * g_graphic_dev.XResolution / 2 + l_fixed;
    line(x_Begin, a_lineNum * w_Line,
         x_Begin + array[a_lineNum] * l_Ratio + r_fixed, a_lineNum * w_Line,
         RGB(0, 0, 0));
    line(x_Begin, a_lineNum * w_Line,
         x_Begin + array[b_lineNum] * l_Ratio + r_fixed, a_lineNum * w_Line,
         cr);
    line(x_Begin, b_lineNum * w_Line,
         x_Begin + array[b_lineNum] * l_Ratio + r_fixed, b_lineNum * w_Line,
         RGB(0, 0, 0));
    line(x_Begin, b_lineNum * w_Line,
         x_Begin + array[a_lineNum] * l_Ratio + r_fixed, b_lineNum * w_Line,
         cr);
    int tmp = array[a_lineNum];
    array[a_lineNum] = array[b_lineNum];
    array[b_lineNum] = tmp;
    DrawDelay(55);
}

void tsk_foo_BubbleSort_1(void* pv) {
    int i, j;
    int* array = (int*)pv;
    for (i = 0; i < ar_Size; i++)
        for (j = ar_Size - 1; j > i; j--)
            if (array[j] < array[j - 1])
                SwapLine(array, 0, j, j - 1, RGB(255, 0, 0));
    task_exit(0);
}

void tsk_foo_BubbleSort_2(void* pv) {
    int i, j;
    int* array = (int*)pv;
    for (i = 0; i < ar_Size; i++)
        for (j = ar_Size - 1; j > i; j--)
            if (array[j] < array[j - 1])
                SwapLine(array, 1, j, j - 1, RGB(0, 255, 0));
    task_exit(0);
}

void test_lab3() {
    // declare 2 arrays
    int arr1[ar_Size];
    int arr2[ar_Size];

    // enter the gui
    int graphMode = 0x143;
    init_graphic(graphMode);

    // calculate the ratio(maybe there's no need to do these)
    l_Ratio = g_graphic_dev.XResolution / 2.0 / max_Elem;
    w_Line = g_graphic_dev.YResolution / (float)ar_Size;
    // generate 2 arrays and draw!
    Generate2arrays(arr1, arr2);

    // alloc stack size
    unsigned int st_Size = 1024 * 1024;
    // create 2 sort threads
    unsigned char* stack_Sort1 = (unsigned char*)malloc(st_Size);
    int tid_Sort1 =
        task_create(stack_Sort1 + st_Size, tsk_foo_BubbleSort_1, arr1);
    unsigned char* stack_Sort2 = (unsigned char*)malloc(st_Size);
    int tid_Sort2 =
        task_create(stack_Sort2 + st_Size, tsk_foo_BubbleSort_2, arr2);
    // initial the priorities
    setpriority(tid_Sort1, 10);
    setpriority(tid_Sort2, 10);
    DrawPrioBar(getpriority(tid_Sort1), -1);
    DrawPrioBar(getpriority(tid_Sort2), 1);
    // create the control thread
    struct Thr th[2] = {{tid_Sort1, 10}, {tid_Sort2, 10}};
    unsigned char* stack_Ctr = (unsigned char*)malloc(st_Size);
    int tid_Ctr = task_create(stack_Ctr + st_Size, tsk_foo_control, th);
    setpriority(tid_Ctr, 1);  // nice = -19

    task_wait(tid_Sort1, NULL);
    task_wait(tid_Sort2, NULL);
    task_wait(tid_Ctr, NULL);
    free(stack_Sort1);
    free(stack_Sort2);
    free(stack_Ctr);
    printf("Mession Success, Well Done!\n");
}

#endif  //_LAB3_

实验结果

总结

若有时间,计划折腾其他调度算法。

感谢:林坤、王凯学长!

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »