title:SYSU-2024操作系统lab3实验报告

date:2024-04-28 23:54:26

tags:os

comments:true

author:zyh

实验名称: Lab5 内核线程

学生姓名: 庄云皓

学生学号: 22336327

实验成绩:

报告时间: 2023-5-5

1. 实验要求

Assignment 1 printf的实现

学习可变参数机制，然后实现printf，你可以在材料中的printf上进行改进，或者从头开始实现自己的printf函数。结果截图并说说你是怎么做的。

Assignment 2 线程的实现

自行设计PCB，可以添加更多的属性，如优先级等，然后根据你的PCB来实现线程，演示执行结果。

Assignment 3 线程调度切换的秘密

操作系统的线程能够并发执行的秘密在于我们需要中断线程的执行，保存当前线程的状态，然后调度下一个线程上处理机，最后使被调度上处理机的线程从之前被中断点处恢复执行。现在，同学们可以亲手揭开这个秘密。

编写若干个线程函数，使用gdb跟踪 c_time_interrupt_handler、asm_switch_thread等函数，观察线程切换前后栈、寄存器、PC等变化，结合gdb、材料中“线程的调度”的内容来跟踪并说明下面两个过程。

一个新创建的线程是如何被调度然后开始执行的。
一个正在执行的线程是如何被中断然后被换下处理器的，以及换上处理机后又是如何从被中断点开始执行的。

通过上面这个练习，同学们应该能够进一步理解操作系统是如何实现线程的并发执行的。

（必做与选做）Assignment 4 调度算法的实现

在材料中，我们已经学习了如何使用时间片轮转算法来实现线程调度。但线程调度算法不止一种，例如

先来先服务。
最短作业（进程）优先。
响应比最高者优先算法。
优先级调度算法。
多级反馈队列调度算法。

此外，我们的调度算法还可以是抢占式的。

现在，同学们需要将线程调度算法修改为上面提到的算法或者是同学们自己设计的算法。然后，同学们需要自行编写测试样例来呈现你的算法实现的正确性和基本逻辑。最后，将结果截图并说说你是怎么做的。（先来先服务为必做，其他为选做）

参考资料：https://zhuanlan.zhihu.com/p/97071815

Tips：

先来先服务最简单。
有些调度算法的实现可能需要用到中断。

2. 实验过程

Assignment 1

1.1可变参数机制

实现这些宏

宏	用法说明
`va_list`	定义一个指向可变参数列表的指针。
`void va_start(va_list ap, last_arg)`	初始化可变参数列表指针 `ap`，使其指向可变参数列表的起始位置，即函数的固定参数列表的最后一个参数 `last_arg`的后面第一个参数。
`type va_arg(va_list ap, type)`	以类型 `type`返回可变参数，并使 `ap`指向下一个参数。
`void va_end(va_list ap)`	清零 `ap`。

typedef char *va_list;
#define _INTSIZEOF(n) ((sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1))
#define va_start(ap, v) (ap = (va_list)&v + _INTSIZEOF(v))
#define va_arg(ap, type) (*(type *)((ap += _INTSIZEOF(type)) - _INTSIZEOF(type)))
#define va_end(ap) (ap = (va_list)0)

注意这里的 _INTSIZIOF: ~(sizeof(int) - 1)为0xfffffffc ,任何地址与它&后将低两位清零，为了实现向上对齐，我们需要先加上(sizeof(int)-1)后再和0xfffffffc相与，此时得到的结果就是向上4字节对齐的。

1.2 实现printf增加%b和%f功能

实现了print(“%b,n),j和print(“%f”,n),分别将i以2进制和float浮点数，保留六位小数输出

让我们先解释一下printf实现的过程，我们需要用到可变参数机制，

解释一下printf中的代码：

如果 % 的下一个字符是’\0’，则退出；如果是’c’，则以字符的格式返回一个可变参数列表中的参数，并将其加入缓冲区；如果是’s’，则输出并清空缓冲区，并以char*的格式返回一个可变参数列表中的参数，并直接打印；如果是’d’，则以int的格式返回一个可变参数列表中的参数，转换为字符串后加入缓冲区；如果是’x’，则以int的格式返回一个可变参数列表中的参数，进行进制转换，然后转换为字符串，加入缓冲区；

%b的实现只需把%x中的itos(number, temp, (fmt[i] == ‘d’ ? 10 : 16));改成itos(number, temp, (fmt[i] == ‘d’ ? 10 : 2));

%f的实现参考了printf的实现

简单地说，先把浮点数分成整数部分和小数部分，然后将整数和小数分别转换为单个字符打印。因为是保留六位小数，小数先*1000000再按整数方式来打印，具体代码见关键代码部分

测试一下：

printf("print percentage: %%\n"
           "print char \"N\": %c\n"
           "print string \"Hello World!\": %s\n"
           "print decimal: \"-1234\": %d\n"
           "print hexadecimal \"0x7abcdef0\": %x\n"
           "print binary \"0b10\": %b\n"
           "print float \"3.1415\": %f\n",
           'N', "Hello World!", -1234, 0x7abcdef0, 0b10,3.1415);

Assignment 2

线程的描述

先介绍一下进程控制块PCB:

在实验中用一个结构体表示，包括栈指针，线程名，状态，优先级，线程id等内容

struct PCB
{
    int *stack;                      // 栈指针，用于调度时保存esp
    char name[MAX_PROGRAM_NAME + 1]; // 线程名
    enum ProgramStatus status;       // 线程的状态
    int priority;                    // 线程优先级
    int pid;                         // 线程pid
    int ticks;                       // 线程时间片总时间
    int ticksPassedBy;               // 线程已执行时间
    ListItem tagInGeneralList;       // 线程队列标识
    ListItem tagInAllList;           // 线程队列标识
};

解释几个变量的含义：
ticks是线程剩余的执行次数。在时间片调度算法中，每发生中断一次记为一个tick，当ticks=0时，线程会被换下处理器，然后将其他线程换上处理器执行。

ticksPassedBy是线程总共执行的tick的次数。

tagInGeneralList和tagInAllList是线程在线程队列中的标识，用于在线程队列中找到线程的PCB。这两个变量的lListItem类型表示队列中的一个元素，是一个结构体，结构体中两个指针变量分别指向前面和后面的元素。用链表来实现进程队列，链表结构详见 ‘include/list.h’

stack线程栈表示如下

对许多线程管理我们需要声明一个声明一个程序管理类 ProgramManager.

用于线程和进程的创建和管理，代码见 include/program.h

#ifndef PROGRAM_H
#define PROGRAM_H

class ProgramManager
{

};

#endif

线程的创建：

1.我们在 include/program.h中对程序管理类 ProgramManager中的变量和函数进行声明。

class ProgramManager
{
public:
    List allPrograms;   // 所有状态的线程/进程的队列
    List readyPrograms; // 处于ready(就绪态)的线程/进程的队列
    PCB *running;       // 当前执行的线程
public:
    ProgramManager();
    void initialize();

    // 创建一个线程并放入就绪队列

    // function：线程执行的函数
    // parameter：指向函数的参数的指针
    // name：线程的名称
    // priority：线程的优先级

    // 成功，返回pid；失败，返回-1
    int executeThread(ThreadFunction function, void *parameter, const char *name, int priority);

    // 分配一个PCB
    PCB *allocatePCB();
    // 归还一个PCB
    // program：待释放的PCB
    void releasePCB(PCB *program);

    // 执行线程调度
    void schedule();

    // zu se huan xing
    void MESA_WakeUp(PCB *program);
};

void program_exit();

2.向内存申请PCB空间（以下内容见src/kernel/program.cpp)

（1）声明PCB的空间和PCB分配状态数组

在内存中开辟一个PCB_SIZE * MAX_PROGRAM_AMOUNT个字节的空间用于分配给所有线程的thread->stack。这里我们把PCB大小设置为4096（4kb)

1	char PCB_SET[PCB_SIZE * MAX_PROGRAM_AMOUNT];//MAX_PROGRAM_AMOUNT个PCB的大小空间

再用一个bool类型数组表示PCB分配状态

1 2	// PCB的分配状态，true表示已经分配，false表示未分配。 bool PCB_SET_STATUS[MAX_PROGRAM_AMOUNT];

如果已经给一个线程分配了PCB则将该线程对应的PCB_SET_STATUS中的数置1

（2）allocatePCB和releasePCB

具体进行分配的过程我们通过program_manager中的函数

// 分配一个PCB
PCB *allocatePCB();
// 归还一个PCB
void releasePCB(PCB *program);

来实现。两个函数实现的代码放置在 src/kernel/program.cpp

PCB *ProgramManager::allocatePCB()
{
    for (int i = 0; i < MAX_PROGRAM_AMOUNT; ++i)
    {
        if (!PCB_SET_STATUS[i])
        {
            PCB_SET_STATUS[i] = true;
            return (PCB *)((int)PCB_SET + PCB_SIZE * i);
        }
    }

    return nullptr;
}

这个函数对PCB_SET_STATUS中的元素依次判断看该位置对应的PCB_SET空间是否已经被类配了，如果没有没有则返回第i个PCB的起始地址（对于第𝑖个PCB，PCB_SET的首地址加上i×PCBSIZE𝑖×𝑃𝐶𝐵𝑆𝐼𝑍𝐸就是第i𝑖个PCB的起始地址）

有PCB的分配就有PCB的释放，如下所示。

void ProgramManager::releasePCB(PCB *program)
{
    int index = ((int)program - (int)PCB_SET) / PCB_SIZE;
    PCB_SET_STATUS[index] = false;
}

releasePCB接受一个PCB指针 program，然后计算出 program指向的PCB在 PCB_SET中的位置，然后将 PCB_SET_STATUS中的对应位置设置 false即可。

（3）excuteThread的实现

在这里我们规定线程只能执行返回值为void，参数为void *的函数
我们在include/Program.h中将上面提到的这个函数定义为ThreadFunction。

1	typedef void(ThreadFunction)(void );

在ProgramManager类中声明一个用于创建线程的函数executeThread：

    // 创建一个线程并放入就绪队列
    // function：线程执行的函数
    // parameter：指向函数的参数的指针
    // name：线程的名称
    // priority：线程的优先级
    // 成功，返回pid；失败，返回-1
int executeThread(ThreadFunction function, void *parameter, const char *name, int priority);

我们在src/kernel/program.cpp中实现executeThread，如下所示。

int ProgramManager::executeThread(ThreadFunction function, void *parameter, const char *name, int priority)
{
    // 关中断，防止创建线程的过程被打断
    bool status = interruptManager.getInterruptStatus();
    interruptManager.disableInterrupt();

    // 分配一页作为PCB
    PCB *thread = allocatePCB();

    if (!thread)
        return -1;

    // 初始化分配的页
    memset(thread, 0, PCB_SIZE);

    for (int i = 0; i < MAX_PROGRAM_NAME && name[i]; ++i)
    {
        thread->name[i] = name[i];
    }

    thread->status = ProgramStatus::READY;
    thread->priority = priority;
    thread->ticks = priority * 10;
    thread->ticksPassedBy = 0;
    thread->pid = ((int)thread - (int)PCB_SET) / PCB_SIZE;

    // 线程栈
    thread->stack = (int *)((int)thread + PCB_SIZE);
    thread->stack -= 7;
    thread->stack[0] = 0;
    thread->stack[1] = 0;
    thread->stack[2] = 0;
    thread->stack[3] = 0;
    thread->stack[4] = (int)function;
    thread->stack[5] = (int)program_exit;
    thread->stack[6] = (int)parameter;

    allPrograms.push_back(&(thread->tagInAllList));
    readyPrograms.push_back(&(thread->tagInGeneralList));

    // 恢复中断
    interruptManager.setInterruptStatus(status);

    return thread->pid;
}

我们现在逐步地分析线程创建的逻辑。

（1）关中断

3-5行保存中断状态然后关中断，诸如PCB分配的工作实际上都需要进行线程互斥处理，我们在这里使用开关中断实现线程互斥为什么开/关中断有效呢？在后面可以看到，我们是在时钟中断发生时来进行线程调度的，因此关中断后，时钟中断无法被响应，线程就无法被调度，直到再次开中断。只要线程无法被调度，那么线程的工作也就无法被其他线程打断，因此就实现了线程互斥。

关中断后，我们需要在函数返回前，也就是第44行恢复中断。

开/关中断等相关的的函数定义在 include/interrupt.h中，如下所示。

class InterruptManager
{

    ...

    // 开中断
    void enableInterrupt();
    // 关中断
    void disableInterrupt();
    // 获取中断状态
    // 返回true，中断开启；返回false，中断关闭
    bool getInterruptStatus();
    // 设置中断状态
    // status=true，开中断；status=false，关中断
    void setInterruptStatus(bool status);

    ...
};

函数的实现比较简单，放置在 src/interrupt/interrupt.cpp中，这里便不再赘述，现在我们回到 executeThread。

（2）申请PCB空间，对PCB中的内容进行初始化

第8行，关中断后，我们向 PCB_SET申请一个线程的PCB，然后我们在第14行使用 memeset将PCB清0。memeset的声明和定义分别在 include/stdlib.h和 src/utils/stdlib.cpp。

第16-25行，我们设置PCB的成员 name、status、priority、ticks、ticksPassedBy和 pid。这里，线程初始的 ticks我们简单地设置为 10倍的 priority。pid则简单地使用PCB在 PCB_SET的位置来代替。

第28行，我们初始化线程的栈。我们将栈放置在PCB中，而线程的栈是从PCB的顶部开始向下增长的，所以不会与位于PCB低地址的 name和 pid等变量冲突。线程栈的初始地址是PCB的起始地址加上 PCB_SIZE。

第29-36行，我们在栈中放入7个整数值。

4个为0的值是要放到ebp，ebx，edi，esi中的。
thread->stack[4]是线程执行的函数的起始地址。
thread->stack[5]是线程的返回地址，所有的线程执行完毕后都会返回到这个地址。
thread->stack[6]是线程的参数的地址。

至于这4部份的作用我们在线程的调度中统一讲解。

（3）将线程放进 allPrograms和 readyPrograms

创建完线程的PCB后，我们将其放入到 allPrograms和 readyPrograms中，等待时钟中断来的时候，这个新创建的线程就可以被调度上处理器。

（4)开中断

最后我们将中断的状态恢复，此时我们便创建了一个线程。

Assignment 3

3.1一个新创建的线程是如何被调度然后开始执行?

我们来看setup.cpp中调用的汇编函数asm_switch_thread(0, firstThread);
将参数和返回地址压栈后，我们将 ebp，ebx，edi，esi 依次压栈（因为这几个存器的值可能会在被调函数中被修改，要先保护起来）。现在的栈状态如下：

29行[esp+5 * 4]表示PCB * cur这个指针变量的值（也就是指向空间的地址），把它赋值给eax。32行[esp+6 * 4]则是PCB *next.

注意30行保存当前栈指针esp到PCB::stack中.[eax]就是PCB * cur这个指针变量的值, 因为PCB第一个变量就是int stack,[eax]其实就是PCB::stack所在地址(int*)((int)thread+PCB_SIZE)-7

下面32-33行我们将PCB next值写入eax,将next->stack的值写入esp
也就是说，现在esp由原来线程的stack切换为了next->stack.

通过调试过程来具体观察一下：
初始时esp为0x7bc0,

33行之后，可以看到esp的值变成了thread1的stack的地址,接着36行到39行弹出thread1的栈中内容（全都是0）到四个寄存器中。因为现在的esp已经变成了thread1的stack,返回地址也是函数first_thread的首地址。ret执行后就跳转到了first_thread函数。（如下图所示，先pop4个0到寄存器，然后返回，返回地址是function的地址）

然后我们便进入了first_thread

3.2一个正在执行的线程是如何被中断然后被换下处理器的，以及换上处理器后又是如何从被中断点开始执行的?

现在我们着重关注RR时间片轮转调度的过程，首先在中断处理函数处设置断点：

观察cur->ticks和cur->ticksPassedBy的变化

每一次发生时钟中断时，中断处理函数都会将当前进程PCB的ticks-1,ticksPassedBy+1,当cur->ticks为0时进行进程切换。

接下来我们观察这个进程如何被换下处理器。时间片用完后进行调度，进入schedule函数内部，因为当前进程还在运行，我们把它放在ready队列的队尾，并将ticks重置。

接着获取ready队列的头一个元素，简单做一些变量的修改后，把ready队列头pop出来，接着我们又进入了asm_swith_thread(cur,next)

进行线程栈的切换，ret后返回second_thread.

thread1已经被换下处理器了，thread1下一次被换上处理器是具体如何执行的呢?

thread3的时间片用完以后，进入scedule函数，调用asm_swith_thread(cur,next),此时的next指向的是thread1,因为thread1已经不是新的进程了，此时它的ebp不为0.

注意到，这里函数返回地址132695是schedule函数中调用asm_swith_thread(cur,next)语句的地址，调用完该函数后返回原来位置。然后schedule函数执行完，继续执行完他所在的c_time_interrupt_handle后返回asm_time_interrupt_handle，该函数iret后返回了thread1执行到的位置，也就是asm_halt中的死循环。

Assignment 4

4.1FIFO

相比于assignment23修改了：

c_time_interrupt_handler()中把队cur->ticks的处理全都去掉

线程都没有死循环

void program_exit()中如果ready队列非空则进行调度。

if (!programManager.readyPrograms.empty())
{
    programManager.schedule();
}

结果见实验结果

4.1优先级调度

在ProgramManager::schedule()函数中找当前ready队列优先级最大的任务，具体代码见关键代码部分

将thread1,2,3的优先级分别设置为1,2,3,那么会依次执行thread3,2,1,结果见实验结果部分

3. 关键代码

Assignment1

case 'f':{
                // 接收浮点型 保留6为小数，不采取四舍五入
                float ArgFloVal = va_arg(ap, double);
                if (ArgFloVal < 0)
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    ArgFloVal = -ArgFloVal;
                }
                unsigned long val_seg = (unsigned long)ArgFloVal;// 取整数部分
                unsigned long val_temp = val_seg;      // 临时保存整数部分数据
                ArgFloVal = ArgFloVal - val_seg;// 得出余下的小数部分
                // 计算整数部分长度
                int cnt = 0;
                if (val_seg)
                {
                    while (val_seg) {
                        cnt++;
                        val_seg /= 10;
                    }
                }
                else cnt = 1;// 数字0的长度为1
                //counter += cnt;// 字符个数加上整数的长度
                // 将整数转为单个字符打印
                while (cnt)
                {
                    val_seg = val_temp / m_pow_n(10, cnt - 1);
                    val_temp %= m_pow_n(10, cnt - 1);
                    //my_send_char((char)val_seg + '0');
                    counter += printf_add_to_buffer(buffer, (char)val_seg + '0', idx, BUF_LEN);
                    cnt--;
                }
                // 打印小数点
                counter += printf_add_to_buffer(buffer,'.', idx, BUF_LEN);

                // 开始输出小数部分
                ArgFloVal *= 1000000;
                // printf("\r\n %f\r\n", ArgFloVal);
                cnt = 6;
                val_temp = (int)ArgFloVal;// 取整数部分
                while (cnt)
                {
                    val_seg = val_temp / m_pow_n(10, cnt - 1);
                    val_temp %= m_pow_n(10, cnt - 1);
                    counter += printf_add_to_buffer(buffer, (char)val_seg + '0', idx, BUF_LEN);
                    //my_send_char((char)val_seg + '0');
                    cnt--;
                }
                //ret_num += 6;
                //pStr++;
				break;
            }
            case 'd':{
             int temp = va_arg(ap, int);

                if (temp < 0)
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    temp = -temp;
                }

                itos(number, temp, 10 );

                for (int j = 0; number[j]; ++j)
                {
                    counter += printf_add_to_buffer(buffer, number[j], idx, BUF_LEN);
                }
                break;
            }
            case 'b':{
                int temp = va_arg(ap, int);

                if (temp < 0 && fmt[i] == 'd')
                {
                    counter += printf_add_to_buffer(buffer, '-', idx, BUF_LEN);
                    temp = -temp;
                }

                itos(number, temp, (fmt[i] == 'd' ? 10 : 2));

                for (int j = 0; number[j]; ++j)
                {
                    counter += printf_add_to_buffer(buffer, number[j], idx, BUF_LEN);
                }
                break;
            }

Assignment3

代码的解释见实验过程部分

asm_switch_thread:
    push ebp
    push ebx
    push edi
    push esi

    mov eax, [esp + 5 * 4]
    mov [eax], esp ; 保存当前栈指针到PCB中，以便日后恢复

    mov eax, [esp + 6 * 4]
    mov esp, [eax] ; 此时栈已经从cur栈切换到next栈

    pop esi
    pop edi
    pop ebx
    pop ebp

    sti
    ret

Assignment 4

优先级调度

void ProgramManager::schedule()
{
    bool status = interruptManager.getInterruptStatus();
    interruptManager.disableInterrupt();

    if (readyPrograms.size() == 0)
    {
        interruptManager.setInterruptStatus(status);
        return;
    }

    if (running->status == ProgramStatus::RUNNING)
    {
        running->status = ProgramStatus::READY;
        running->ticks = running->priority * 10;
        readyPrograms.push_back(&(running->tagInGeneralList));
    }
    else if (running->status == ProgramStatus::DEAD)
    {
        releasePCB(running);
    }
    //初始化max,next,nextid,ready队列的size
    int max = -1;
    PCB* next = nullptr;
    int nextid = 0;
    int size = readyPrograms.size();
    //找到优先级最大的线程
    for(int i = 0;i<size;i++){
        ListItem* item = readyPrograms.at(i);
        PCB* tmp = ListItem2PCB(item, tagInGeneralList);
        if(tmp->priority > max){
            max = tmp->priority;
            nextid = i;
            next = tmp;
        }
    }

    //ListItem *item = readyPrograms.front();
    //PCB *next = ListItem2PCB(item, tagInGeneralList);
    //从ready队列中取出，将该线程状态置为running
    PCB *cur = running;
    next->status = ProgramStatus::RUNNING;
    running = next;
    readyPrograms.erase(nextid);
    //切换线程栈，实现线程的切换
    asm_switch_thread(cur, next);

    interruptManager.setInterruptStatus(status);
}

4. 实验结果

Assignment1:

printf %b（二进制）和%f(保留六位小数)

Assignment2:

Assignment3:

见实验过程部分

Assignment4:

4.1 FIFO

4.2 优先级调度

5.实验总结

通过这次实验，学习了可变参数机制，并增添了实验中的pringf函数的功能，线程在操作系统中的描述，调度方式。复现实验很容易，但要深入理解其中的每一处细节并准确描述出来很难。我在Assignment3中开始由于对函数调用过程中栈的变化不熟悉卡了很久，后来看到其他同学的解释时才更加深入理解了 asm_switch_thread的设计,感受到了设计的巧妙之处。