GeekOS课程设计-Project 3

Love The Way You Lie 2022-10-13 12:44 128阅读 0赞

### Project 3 ###

*   *  1、实验任务
     *  2、实验原理
     *   *  2.1 四级反馈队列调度策略实现
         *  2.2 信号量操作
     *  3、具体实现
     *   *  编辑源文件
         *  编辑Makefile文件
         *  编辑.bochsrc文件
     *  4、运行结果
     *  5、课后作业
     *  感谢阅读

[源代码链接][Link 1]

## 1、实验任务 ##

研究进程调度算法，掌握用信号量实现进程间同步的方法。为 GeekOS 扩充进程调度算法——基于时间片轮转的进程多级反馈调度算法，并能用信号量实现进程协作。  
（1）实现src/geekos/syscall.c文件中的Sys\_SetSchedulingPolicy系统调用，它的功能是设置系统采用的何种进程调度策略；  
（2）实现src/geekos/syscall.c文件中的Sys\_GetTimeOfDay系统调用，它的功能是获取全局变量g\_numTicks的值；  
（3）实现函数Change\_Scheduling\_Policy()，具体实现不同调度算法的转换；  
（4）实现syscall.c中信号量有关的四个系统调用：sys\_createsemaphore()、sys\_P()、sys\_V()和sys\_destroysemaphore()。

## 2、实验原理 ##

### 2.1 四级反馈队列调度策略实现 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70]  
  Geekos初始的调度算法为轮询算法，即所有进程根据优先级进入一个队列一次根据时间片运行。现要实现多级反馈调度策略。  
  当调度算法由时间片轮转改为多级反馈调度策略时，用四个准备运行队列代替时间片轮转的一个队列。四个队列有不同的优先级，最高为0级，最低为3级。新创建的进程被放入最高优先级的队列。进程每运行完一个时间但还未完成时会被放入下一级队列。等到第三级队列中也未完成时放入第0级队列。系统每次运行的都是调用优先级较高的进程运行。系统会有一个空闲进程IDLE，当队列中由其他进程时，它始终保持在最低级队列的尾部；当系统中仅有它一个进程时，系统就会调用它。  
  在Geekos中,进程调度是在时钟中断处理函数Time\_Interrupt\_Handle内实现的， 进程的Kernel\_Thread结构中有一个numTicks变量，在进程对象初始化时被初始化为零，之后每次时钟中断处理，进程的该变量都会加1，然后系统会检查进程执行的时间是否超过了系统规定的时间片g\_Quantum，如果超过，说明当前进程时间片已用完，系统应调度新的进程运行，于是将变量g\_needReschedule置为true，用以标志需要重新调度新进程运行。在时钟中断处理函数返回到Handle\_Interrupt后检查g\_needReschedule变量，如果true，就调Make\_RunnablE函数，将当前运行进程放入准备运行进程队列 s\_runQueue；之后再调用Get\_Next\_Runnable函数找到优先级最高的进程；最后返回 Handle\_Interrupt将g\_needReschedule返回为false，并切换到新进程运行，进程调度处理过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 1]

### 2.2 信号量操作 ###

通过Create\_Semaphone()函数先检查请求创建的信号量是否存在，若不存在，则分配内存给创建的信号量，并将当前线程加入到该信号量的队列中，设置注册线程数量为1，初始化信号量的名字、值、ID，并把信号量添加到系统信号量链表尾，并返回信号量ID；若存在，则将这个线程加入到该信号量的线程列表上。  
  线程P操作时，先检查信号量是否存在，接着检查线程是否注册在信号量队列中，若均存在则将信号量值减1，若信号量值小于0，则将该线程放入等待队列，若其一不存在，则返回错误。  
  线程V操作时，先检查信号量是否存在，接着检查线程是否注册在信号量队列中，若均存在则将信号量值加1，若信号量值仍小于等于0，则将信号量的等待队列中的一个线程唤醒。  
  通过Semaphone\_Destory()注销信号量。先检查传入信号量是否存在，再检查当前线程是否使用该信号量，若成功，则将该线程从该该信号量的线程队列中删除，并把注册线程数减1，若这个信号量注册线程数为0，则将这个信号量从信号量链表中删除；若检查未通过，则返回错误。

## 3、具体实现 ##

### 编辑源文件 ###

略，详见完整工程。

### 编辑Makefile文件 ###

TARGET_CC := $(TARGET_CC_PREFIX)gcc -m32
    HOST_CC := gcc -m32
    TARGET_LD := $(TARGET_CC_PREFIX)ld -m elf_i386
    GENERAL_OPTS := -O -Wall -fno-stack-protector $(EXTRA_C_OPTS)
    CC_GENERAL_OPTS := $(GENERAL_OPTS) #-Werror

### 编辑.bochsrc文件 ###

megs: 8
    boot: a
    floppya: 1_44=fd.img, status=inserted
    ata0-master: type=disk, path=diskc.img, mode=flat, cylinders=40, heads=8, spt=63

## 4、运行结果 ##

*  RR算法与MLF调度算法输出测试:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 2]
    
    从运行的测试结果来看，在schedtest测试用例中，因为RR算法和MLF算法都是基于时间片轮转，且时间片的长度都是一样的，所以输出数字1,2,3的数量是一样多的，然而RR算法的进程调度是没有优先级升降的调整，而MLF算法中有，所以使用两个算法输出的数字顺序会有些差别。进程的周转时间还包括进程切换的时间，所以同样的调度算法，同样的时间片，因为进程切换的时间可能不一样，所以程序执行的周转时间可能不一样，输出的结果也可能不一样。
 *  调度算法对比测试:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 3]
    
    Long 进程所做计算最多，且仅与“screen”信号量相关，需要的时间片最多，无论采用哪种调度策略，完成也最迟。在轮询策略中，Long 进程创建后，与父进程交替进行计算，Pong 进程在进行轮询后才完成，Ping 进程随着 Pong 进程完成后完成，父进程在等待 Long 进程完成后结束。在多级反馈调度策略中，Long 创建后运行完一个时间片后即进入次级队列，Ping 创建后在 0 级队列等待信号量，Pong 创建后，在 0 级队列完成任务，Ping 进程接收到信号量后被唤醒，完成任务，主进程等待 Long进程完成后结束。同时我们可以看到，在 workload 测试用例中，使用 RR 算法输出的结果与 MLF 算法输出的结果也有差别，因为 MLF 算法中有优先级升降的调整，而且因为MLF 算法中各个队列的时间片都是一样的，所以每个进程运行所花费的时间要比 RR 算法中的要少些，证明了 MLF 算法在进程调度上要比 RR 算法优秀。
 *  信号量和PV操作
    
     *  semtest  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 4]
     *  semtest1  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 5]
     *  semtest2  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 6]
    
    **semtest**是一个调用P和V操作，第一次创造信号量的return 1这个1是新建的信号量的id，最后return 结果为0说明信号量已被销毁。**semtest1**中即使p3进程较早的被创建，但因为信号量的原因，只有等p1、p2进程执行后，才能从信号量的等待进程队列中出来进入可执行队列。**semtest2**中程序会尝试对不存在的信号量作两次P操作，从而会显示两次`Error! Semaphore ID is Invalid`错误警告。后会对一个销毁了的信号量进行V操作会显示一次`Error! Connot Find Semaphore with SID=1`错误警告。

## 5、课后作业 ##

**1.GeekOS 系统原始的线程调度算法是什么？**

答：轮询调度算法

**2.在GeekOS 系统中，如何实现多级反馈队列调度算法？**

答：先要修改准备运行队列的数量，将Idle进程加入到最后一个队列尾，然后修改Make\_Runnable()函数实现将时间片用完的进程根据进程队列索引值加入相应的准备运行队列，修改Get\_Next\_Runnable()函数完成多级反馈队列的调度策略。

**3.在GeekOS 系统中，如何创建一个信号量？**

答：首先需要定义信号量结构体，以及信号量队列。然后通过Sys\_CreateSemaphore()函数创建信号量，Sys\_CreateSemaphore()函数功能实现，首先通过传入的参数获取信号量的名称，通过名称查找信号量是否在信号量队列，没有则创建信号量并加入队列。然后将进程注册加入到信号量的注册队列。这样进程就创建了一个信号量。

**4.在GeekOS系统中，如何通过信号量来实现进程同步？**

答：不同进程注册了同一个信号量之后，便可以通过PV操作实现进程间的同步关系，信号量的值只能由PV操作改变。P操作用于获得信号量，若信号量值小于等于0，则进程阻塞，若信号量值大于0，则信号量值减1，程序继续运行。V操作用于释放信号量，将信号量的值加1，若有进程等待该信号量，则唤醒等待队列首进程。具体的实现以生产消费者问题为例，可以是通过Shell执行一个用户程序，这个用户程序创建两个子进程执行另外两个用户程序，都注册名称相同的信号量，一个执行V操作作为生产者，另一个执行P操作作为消费者，这样就实现了一个简单的使用信号量PV操作解决进程同步的例子。

## 感谢阅读 ##

如果对你有帮助，点赞收藏再走呗。

[Link 1]: https://download.csdn.net/download/qq_38413498/20051683?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70]: /images/20221005/8127a5acd51e4b8db8d4c81c0cc67d17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 1]: /images/20221005/068aa9a0319b41e1837032c9d4ad245d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 2]: /images/20221005/92c0f3ec42b146eeaba8e42bc5cff3c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 3]: /images/20221005/b45835d9514f4a4a84b9087b6f5b3266.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 4]: /images/20221005/9ad288a6297f40cbbec59144473e67d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 5]: /images/20221005/345c33d232444f8c82b3a233623f9ce5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEzNDk4_size_16_color_FFFFFF_t_70 6]: /images/20221005/d6aacb4a25c346bab1b6f2266a1bdaba.png