操作系统实践报告-综合版

操作系统实验报告

专业名称： 软件工程 学生年级： 2018级本科 指导教师：

课程性质： 专业必修

研修时间： 2019～2020学年第1学期 实验地点：

软件学院 2020年 1月 1日

Pintos 实验统计

 请自评你的项目完成情况，在表中相应位置划√。

Pintos Project1

内容\\完成情况 完成 1. 消除忙等 2. 优先级调度 3. 高级调度

√ √ √ 基本 完成 完成 大部分 还有很多 没完成 Pintos Project2

内容\\完成情

完成 基本 2

完成 还有很多 况 1. 进程终止 的终端提示 2. 参数传递 3. 系统调用 完成 √ 大部分 没完成 √ √ 4. 运行文件√ 禁止写操作 目 录

摘 要 ................................................................ 4 基础实践1 ............................................................ 6 基础实践2 ............................................................ 7 Pintos项目1 ........................................................ 10 Pintos项目2 ........................................................ 79

3

摘 要

4

5

基础实践1

一、目的

1) 2) 3) 4)

掌握虚拟机安装方法

掌握Linux的基本使用方法 掌握Pintos的安装方法

掌握Pintos的编译、跟踪及动态调试方法

二、内容与设计思想

1、下载软件Vitualbox及虚拟机映像文件 2、安装虚拟机

3、熟悉Linux的基本命令和使用方法 4、学会使用Linux系统的常用命令

5、学会Pintos的编译、跟踪及动态调试方法 三、使用环境

Ubuntu 10.04，Pintos，C语言

四、实验过程与分析、调试过程

1. 下载Oracle VM VirtualBox，下载虚拟机映像文件，安装虚拟机 2.

3. 安装pintos：在官网下载bochs，bochs-2.6.7.tar.gz，下载pintos，pinots.tar.gz，移动到虚拟机中，执行tar zxvf bochs-2.6.7.tar.gz，执行tar zcvf pintos.tar.gz 更新一些脚本，$ sudo apt-get install buid-essential

$ sudo apt-get install xorg-dev $ sudo apt-get install bison $ sudo apt-get install libgtk2.0-dev

$ sudo apt-get install libc6:i386 libgcc1:i386 gcc-4.6-base:i386 libstdc++5:i386 libstdc++6:i386

$ sudo apt-get install libncurses5:i386 $ sudo apt-get install g++-multilib

安装bochs：cd bochs-2.6.7 ./configure – enable-gdb-stud make sudo make install

安装和运行pintos：tar zxvf pintos2011.tar.gz cd pintos/src/tjreads make cd build ../../utils/pintos – rum alarm-multiple

五、实验总结

实验的开端，安装，配置环境。

六、附录

6

基础实践2

7

一、目的

5) 6) 7) 8) 9)

巩固Ubutu系统命令；

通过例程了解进程、线程的创建及主要函数的使用方法； 掌握用户程序的编辑、编译、调试程序的方法； 学会利用gdb跟踪程序的方法；

了解Pintos工程的结构，学会Pintos的跟踪方法。

二、内容与设计思想

1、编辑几个例程，了解进程、线程的创建及主要函数的使用方法。

2、利用gdb对上述的进程、线程的基本例程进行调试和跟踪，学会断点设置和取消方法，学会在断点处观察变量的方法。

3、了解Pintos工程的结构，学会Pintos的编译、运行及跟踪方法。 三、使用环境

Ubuntu 12，Pinos，gedit或vi，gdb

四、实验过程与分析、调试过程

1. tid_t

thread_create (const char *name, int priority, thread_func *function, void *aux) {

struct thread *t;

struct kernel_thread_frame *kf; struct switch_entry_frame *ef; struct switch_threads_frame *sf; tid_t tid;

enum intr_level old_level;

ASSERT (function != NULL);

/* Allocate thread. */

t = palloc_get_page (PAL_ZERO); if (t == NULL) return TID_ERROR;

/* Initialize thread. */ init_thread (t, name, priority); tid = t->tid = allocate_tid ();

/* Prepare thread for first run by initializing its stack. Do this atomically so intermediate values for the 'stack'

8

member cannot be observed. */ old_level = intr_disable ();

/* Stack frame for kernel_thread(). */ kf = alloc_frame (t, sizeof *kf); kf->eip = NULL; kf->function = function; kf->aux = aux;

/* Stack frame for switch_entry(). */ ef = alloc_frame (t, sizeof *ef);

ef->eip = (void (*) (void)) kernel_thread;

/* Stack frame for switch_threads(). */ sf = alloc_frame (t, sizeof *sf); sf->eip = switch_entry; sf->ebp = 0;

intr_set_level (old_level);

/* Add to run queue. */ thread_unblock (t);

return tid; }

上面是进程线程创建，分配页面，初始化各参数，分配tid，各种指针，并将其开始运行。

2. 复制utils：# Copy utils

$ cd ̃/pintos/src/utils

$ sudo cp backtrace /usr/bin/ $ sudo cp pintos /usr/bin/ $ sudo cp pintos-gdb /usr/bin/ $ sudo cp pintos-mkdisk /usr/bin/ $ sudo cp Pintos.pm /usr/bin/

安装pintos-gdb：# Install pintos-gdb $ cd ̃/pintos/src/misc

$ sudo cp gdb-macros /usr/bin/ $ sudo vim /usr/bin/pintos-gdb

# Modify the 4th line: GDBMACROS=/usr/bin/gdb-macros

9

$ cd /usr/bin/

$ sudo chmod a+rx backtrace $ sudo chmod a+rx pintos* $ sudo chmod a+rx gdb-macros $ sudo chmod a+rx Pintos.pm $ test pintos-gdb

编译utils：cd ~/pintos/src/utils make sudo cp squish-pty /usr/bin sudo chmod a+rx /usr/bin/squish-pty

用gdb来调试pintos：cd /pintos/src/threads/build ../../utils/pintos –gdb –s – run alarm-multiple 在另一个终端输入cd pintos/src/threads/build gdb kernel.o 成功进入gdb，在(gdb)中输入target remote localhost:1234 continue，连接完成。

3. pintos结构，包括内核device，文件调用filesys，库文件lib，线程使用threads，用户程序userprog等。

五、实验总结

实验了解了pintos的基本结构，了解了进程线程创建和初始化的方法等，为下面开始实验做了铺垫。 六、附录

Pintos项目1

10

一、实验目的

（1）了解Pintos操作系统的功能流程及内核的软件工程结构。 （2）通过Pintos操作系统内核的剖析，了解现有Pintos操作系统在CPU调度功能中存在的问题。

（3）学会用软件工程的方法分析、解决以上问题。

（4）在实践中，通过消除Pintos操作系统调度问题，学会利用gdb跟踪策略对程序进行动态调试的方法。 二、实验内容与设计思想

（1）通过Pintos操作系统内核的剖析，了解其线程管理的机制。 （2）了解现有Pintos操作系统的功能及线程调度中存在的问题。

（3）在分析内核的基础上，分析忙等问题，设计算法，分步跟踪和调试，通过实践，有效解决忙等问题，并对实验结果进行分析。

（4）在分析内核的基础上，分析现有CPU调度问题，设计利用优先级进行调度的策略，分步跟踪和调试，通过实践，验证抢占优先级调度算法的有效性，并对实验结果进行分析。

（5）通过系统分析，设计有效的优先级翻转及多级反馈队列的CPU调度策略，分步跟踪和调试，通过实践，验证优先级翻转及多级反馈队列的CPU调度算法的有效性，并对实验结果进行分析。 三、实验使用环境

Ubuntu12.04操作系统环境，Pinto操作系统原型，gdb跟踪调试工具。

11

四、实验过程与分析、调试过程 （1）Pintos内核剖析

12

（2）Pintos忙等问题分析及实践过程

1. 在time.c中，有关于进程等待的函数timer_sleep()的实现

函数的参数是操作系统指定的等待时间，没有返回值。 在该函数第五行中，函数将timer_ticks()的返回值赋值给start。 2. 找到timer_ticks()函数的实现

枚举类型intr_level指定的是线程是否可以被中断。函数首先调用了intr_disable()，将其返回值赋值给枚举变量。 3. 找到intr_disable()的函数实现

13

函数调用了intr_get_level()，将其返回值赋值给一个枚举类型。 4. 查看intr_get_level()的函数实现

这里使用了汇编代码，由注释可以看出，函数返回的是线程当前是否可以被中断的状态。 5. 回到intr_disable()中

14

函数以old_level保存了当前线程是否可被中断的状态，然后使用汇编指令指定当前操作不能被中断，并返回线程先前是否可被中断的状态。

6. 有以上结论我们可以知道： timer_ticks()第五行做了这么一件事情： 禁止当前行为被中断， 保存禁止被中断前的中断状态（用old_level储存）

第六行以t存储全局变量ticks的值，这个t是函数的返回值。 7. 全局变量ticks如下

从pintos被启动开始， ticks就一直在计时， 代表着操作系统执

15

行到现在的时间。 8. 第七行调用intr_set_level()

这个函数以参数level的值设置当前的中断状态。其中intr_disable()设置不可被中断，intr_enable()设置可以被中断。 9. intr_enable()函数如下

函数以old_level存储了线程的当前是否可被中断的状态并返回。 第十二行使用汇编语言设置当前可以中断。 10. ASSERT()调用了intr_context()函数

16

这个函数返回in_external_intr，这个值是true如果中断为外中断(I/O中断)，值是false如果为内中断(进程切换)，这里intr_enable()第六行保证中断是一个进程或线程切换的中断。 11. 回到timer_sleep()中

第六行的作用是获取一个时间，这个时间是正在执行的线程开始停止的时间。

第七行保证线程现在是可以中断的状态。 12. 第八行调用了timer_elapsed()函数

then是timer_sleep()中的start，即线程开始停止时间，函数调用

17

timer_ticks()，这个函数在6，返回的是现在的时间，由此可知函数返回进程已经停止的时间。

13. 当这个时间小于ticks（这里的ticks是函数的参数，代表线程要停止的时间）时，执行thread_yield()。 14. 函数thread_yield()定义如下

函数首先以cur指针指向thread结构体。 15. 调用thread_current()函数

18

函数以t为指针和返回值，调用running_thread()函数，该函数返回当前运行的线程地址。函数保证t指向的是一个线程并且线程状态是正在运行。 16. 返回到thread_yield()中

19

第六行得到了当前正在运行的线程，第九行保证线程中断是内中断，第11行将当前线程设置为不可中断并存储线程中断状态，第12~14行如果线程不是一个空闲线程(就是正在运行被中断了)就把线程加到就绪队列中去，第15行调用schedule()，16行恢复先前的中断状态。 17. schedule()如下

cur指向当前运行线程，next是就绪队列中下一个要运行的线程，保证当前不可中断，当前运行线程状态不是运行（刚刚加入就绪队列），next是一个线程，19行如果cur和next不相同，就调用switch_threads切换， 18. 将next进程开始执行

20

若就绪队列空，设置空闲线程，否则调用lest_entry()使下一个线程执行。函数的返回值被赋值给prev，这时prev和cur指的是同一线程。

21

schedule()最后一行调用 19. thread_schedule_tail()

22

thread_schedule_tail()其实就是获取当前线程， 分配恢复之前执行的状态和现场， 如果当前线程死了就清空资源。

schedule()其实就是拿下一个线程切换过来继续run并进行上下文切换。

thread_yield()其实就是把当前线程扔到就绪队列里， 然后重新schedule， 注意这里如果ready队列为空的话当前线程会继续在cpu执行。

最后回溯到我们最顶层的函数逻辑： timer_sleep()就是在ticks时间内， 如果线程处于running状态就不断把他扔到就绪队列不让他执行。

20. 操作系统的缺点很明显：

线程依然不断在cpu就绪队列和running队列之间来回， 占用了cpu资源， 这并不是我们想要的， 我们希望用一种唤醒机制来

23

实现这个函数。 忙等待实现

实现思路： 调用timer_sleep()的时候直接把线程阻塞掉，然后给线程结构体加一个成员ticks_blocked来记录这个线程被sleep了多少时间， 然后利用操作系统自身的时钟中断（每个tick会执行一次）加入对线程状态的检测， 每次检测将ticks_blocked减1, 如果减到0就唤醒这个线程。

1. 修改thread(thread.h)结构体，加上一个ticks_blocked

2. 修改thread_create()函数(在thread.c中)，使之初始化ticks_blicked为0。（截图中函数不完整）

24

3. 修改中断处理函数timer_interrupt()(在timer.c中)，加入线程sleep时间的检测。

4. 其中函数thread_foreach()已经定义在thread中：

函数的作用是对每一个就绪队列中的线程实现func()函数，这里的

25

func()函数是blocked_thread_check()函数，用于检测是否有个线程停止等待进入执行

5. 新函数blocked_thread_check()声明并定义在thread中

作用是所有线程等待时间-1，若有线程阻塞时间为0，解除阻塞。 6. 对timer_sleep()的修改

26

（3）Pintos优先级调度问题分析及实践过程。

1. 在thread.h中，已经为每个线程结构赋予一个优先级的值，即图中的8行。

同时宏定义了priority的约束

2. 优先级调度，指的是程序由就绪队列调度执行时依据优先级调度。

27

就绪队列是一个优先级的队列，需要我们在将线程加入队列时加到合适的位置。下面的函数需要将线程加入就绪队列。

28

它们都使用了list_push_back()函数(定义在list.c中)

list_insert()如下：

list_insert()是在队列中把elem放到before前面。

29

list_push_back()是把elem放到队列尾巴的前面，即队列最后一个元素。

三个函数都是简单地把线程放到队列尾部，没有按照优先级排列。 3. 队列部分解释如下：

结构体list_elem指定了队列上一个元素和下一个元素，结构体list是队列的头和尾，这个头和尾是空的。结构体thread包含list_elem。 4. 阅读list.c，发现有这样一个函数：

30

函数以less()为优先级比较方法的函数，从队列头遍历，找到插入点，将线程插入队列。需要我们完成less()函数的构造。 5. 构造less()函数

list_insert_ordered()最后调用了list_insert(e, elem)，将elem插入到e的前面，说明elem优先级更高，less()函数需要第一个参数elem比第二个参数e的优先级更高，在队列中，队列前面的优先级肯定是大于后面的的，因此e从头部开始遍历，逐渐变小，直到小于elem，合乎逻辑。

构造的less()函数需要比较elem和e的优先级，当第一个参数大时

返

回

true

。

31

由于a是结构体thread的元素，优先级priority也是结构体thread的元素，我们调用了宏定义list_entry()指定a的thread：

6. 将三个函数的list_push_back()改为

7. 观察测试样例test_priority_preempt()和test_priority_change()：

32

这个样例先保证当前线程的优先级为PRI_DEFAULT，然后创建了一个优先级为PRI_DEFAULT+1的线程，这样新创建的线程应该抢占原来的线程。

33

这个线程创建了一个优先级为PRI_DEFAULT+1的新线程，新线程抢占原线程，然后新线程优先级-1，又回到原来的线程中，然后原线程优先级-2，又回到新线程中，新线程终止，回到原线程，原线程终止。所以期望的输出为：

分析这个测试行为我们得出的结论就是： 在设置一个线程优先级要立即重新考虑所有线程执行顺序， 重新安排执行顺序。要实现这个功能，我们可以在创建新线程和更改线程优先级的时候调用thread_yield()，直接将其丢入就绪队列中即可。更改如下：

34

在thread_create()最后修改代码如下：

8. 优先级捐赠。考虑下面一种情况，

在这里ABC是三个进程，优先级分别为123（优先级越大先执行），线程 A 对一个互斥资源拥有线程锁。而此时, 高优先级的线程 C 也想要访问这个互斥资源, 线程 C 只好在这个资源上等待,不能进入就绪队列。当调度器开始调度时, 它只能从 A 和 B 中进行

35

选择,根据优先级调度原理,线程 B 将会首先运行。这时就产生了一个问题, 即本来线程 C 优先级比线程 B 高, 但是线程 B 却先运行了,从而产生了优先级翻转问题。

解决方法就是当发现高优先级的任务因为低优先级任务占用资源而阻塞时，就将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级，这里将A的优先级提升为3。 9. 查看第一个案例test_priority_donate_one()：

36

原线程优先级为PRI_DEFAULT，它声明一个锁并获得这个锁，然后创建一个优先级为PRI_DEFAULT + 1的线程acquire1，这个线程需要获得锁，但是锁已经被原线程获取，所以线程acquire1等待。原线程创建一个优先级为PRI_DEFAULT+2的线程acquire2，这个线程执行的操作和acquire1一样，等待锁。原线程释放锁，然后应该是线程acquire2先执行并结束然后线程acquire1执行并结束，最后原线程终止。

查看获得锁和释放锁的函数：函数在synch.c中

37

结构体lock是一个拥有者一个信号量，信号量的结构是一个值一个等待队列。

初始化锁的拥有者为null，信号量的值为参数(1)。

38

函数lock_acquire()首先保证锁不被其他线程占有，否则等待。然

39

后调用sema_down()即P操作，函数将线程放在信号量的等待队列中，等待唤醒，唤醒后value--，表示锁再次被占有。回到lock_acquire()中，设置锁的占有程序，回到进程。

在lock_release()中首先保证锁被占有，然后调用sema_up()函数，如果信号的等待队列不为空则将队列首部的线程提出，并使

40

value++。该样例希望的输出如下：

在第7行和第8行中original_thread的优先级被捐赠了。实现思路是：在一个线程获取一个锁的时候， 如果拥有这个锁的线程优先级比自己低就提高它的优先级，然后在这个线程释放掉这个锁之后把原来拥有这个锁的线程改回原来的优先级。 10. 分析样例test_priority_donate_multiple()

41

42

原线程声明并获取了两个锁ab，创建优先级为PRI_DEFAULT + 1的线程a，a获取锁，等待，创建优先级为PRI_DEFAULT + 2的线程b，b获取锁b，等待。原线程释放锁b，线程b执行，结束，释放锁a，线程a执行，结束，原线程终止。期望的输出结果如下：

43

在第7行，原线程被捐赠，优先级同线程a，在第8行，原线程被捐赠，优先级同线程b，第12行，线程b收回捐赠，第16行，线程a收回捐赠。这里测试的行为实际是： 多锁情况下优先级逻辑的正确性。那么我们对应的实现思路是： 释放一个锁的时候， 将该锁的拥有者改为该线程被捐赠的第二优先级，若没有其余捐赠者， 则恢复原始优先级。那么我们的线程必然需要一个数据结构来记录所有对这个线程有捐赠行为的线程。 11. 分析样例test_priority_donate_multiple2():

44

45

原线程创建锁ab，获取锁，创建线程a，设置优先级为PRI_DEFAULT + 3，a线程试图获取锁a，等待；原线程创建线程c并设置优先级为PRI_DEFAULT + 1，这里因为原线程被捐赠（PRI_DEFAULT + 3）所以并没有调用线程c的函数，原线程创建线程b，b试图获取锁b，等待。原线程释放锁a，但由于此时原线程优先级被捐赠（PRI_DEFAULT + 5），所以不执行线程a的函数，继续执行原线程，原线程释放锁b，执行线程b，结束，执行线程a，结束，执行线程c，结束，原线程终止。 期望的输出如下：

46

这里测试的依然是多锁情况下的优先级逻辑的正确性，前面分析过了。

12. 查看样例test_priority_donate_nest()

47

48

这里创建两个锁ab，创建一个包含两个锁ab的结构体locks，原进程获取锁a，创建线程medium并设置优先级为PRI_DEFAULT + 1，线程medium获取锁b，试图获取锁a，等待。原线程被捐赠优先级(PRI_DEFAULT + 1)并移入就绪队列，创建线程high并设置优先级为PRI_DEFAULT + 2，线程high试图获取锁b，发现锁b被线程medium占有，于是捐赠线程medium的优先级为PRI_DEFAULT + 2，同时原线程的优先级也为PRI_DEFAULT + 2。

49

原线程释放锁a，线程medium抢占并执行，然后释放锁a释放锁b，线程high抢占，执行，结束，线程medium继续执行，结束，原线程执行并结束。期望结果如下：

这个测试是一个优先级嵌套问题， 重点在于medium拥有的锁被low阻塞， 在这个前提下high再去获取medium的说阻塞的话， 优先级提升具有连环效应， 就是medium被提升了， 此时它被锁捆绑的low线程应该跟着一起提升。从实现的角度来说， 我们线程又需要加一个数据结构， 我们需要获取这个线程被锁于哪个线程，以提升对应线程的优先级。 13. 实现样例test_priority_donate_sema():

50

51

原线程声明一个结构体，这个结构体包含一个信号量一个锁。创建优先级为PRI_DEFAULT + 1的线程low，这个线程获取锁，试图获取信号量，但因为信号量初始化为0，所以线程在这里阻塞。回到原线程(优先级为PRI_DEFAULT + 1)，创建一个优先级为PRI_DEFAULT + 3的线程med，这个线程也试图获取信号量，阻塞。回到原线程（优先级为PRI_DEFAULT + 3），创建优先级为PRI_DEFAULT + 5的线程high，该线程试图获取锁，但发现锁已经被low占有，阻塞。到这里，由于优先级捐赠，原线程、low、high的优先级为PRI_DEFAULT + 5，med的优先级为PRI_DEFAULT + 3。原线程递增信号量，直接转到线程low，获取信号量，执行，释放锁。转到线程high，执行直到结束。转到线程med，执行直到结束，转到线程low，执行直到结束，回到原线程执行结束。

52

这里的设计思想是为线程结构添加一个成员，标识信号占有的线程。

14. test_priority_donate_lower()：

53

原线程声明一个锁，获取这个锁，创建优先级为PRI_DEFAULT + 10的线程，这个线程试图获取锁，阻塞。原线程中将优先级修改为PRI_DEFAULT – 10，这里如果修改了就会陷入死锁，所以实

施策略是当捐赠行为被收回时更改优先级。所以原线程继续执行，释放锁同时修改优先级，新线程执行，结束，原线程执行，结束。 15. test_priority_sema()

原线程声明一个信号量并初始化为0，然后将自身优先级设置为PRI_MIN。使用一个循环，创建10个线程，线程名字为priority %d(优先级)，优先级分别为21~30，所有线程都试图获取信号量，都阻塞。回到原线程，使用一个循环创建调用10次

55

sema_up()，每次调用都会直接被优先级高的线程抢占，执行完后回到原线程中。期望输出结果如下：

这里要实现的是，信号量的等待队列是优先级队列。 16. test_priority_condvar()：

56

这里condition里面装的是一个waiters队列， 看一下con_wait和

57

cond_signal函数：

cond_wait()是声明一个信号量等待队列，它声明一个waiter并使它进入cond的等待队列，释放锁，waiter信号量的值-1，获得锁；cond_signal()如果队列不为空则使队首的waiter信号量+1。 回到原线程，设置原线程优先级为PRI_MIN，创建10个优先级分别为21~30的线程，每个线程都获取锁，最终的结果是每个线程获得了锁，并调用cond_wait()，释放锁，进入等待队列试图获

58

取信号量，但信号量为0，所以线程在这里等待（cond_wait第34行），回到原线程，创建下一个线程。创建了10个线程之后，原线程执行第二个循环，获取锁并执行cond_signal()，这里释放信号量，应该先释放优先级高的线程的信号量，该线程被唤醒并执行，释放锁，直到结束。所有线程结束后回到原线程，原线程结束。

这里要求的是condition的waiters队列是优先级队列。59

17. test_priority_donate_chain()

60

声明一个锁数组，声明一个包含两个lock指针的结构体lock_pairs，当前线程优先级设置为PRI_MIN。原线程获取锁0，设置一个循环，设置优先级依次递增，每个线程设置结构体lock_pairs[i]中前一个指针指向locks[i]，后一个指针指向locks[i-1]，创建线程抢占当前线程，若locks[i]存在则获取这个锁，试图获取locks[i-1]，但locks[i-1]被占有，所以等待。回到原线程，原线程创建第二个优先级为thread_priority-1的线程，由于原线程优先级被捐赠为thread_priority，所以这个线程不执行，直接进入

61

下一个循环。循环执行结束后，原线程释放锁locks[0]，然后从头开始，按创建顺序执行所有被阻塞的线程，执行完成后释放locks[i-1]和locks[i]，直到所有阻塞线程执行完成。依次执行所有创建时优先级不够没有执行的线程，即调用函数interloper_thread_func()，执行完成后回到原线程，进程终止。 这个测试其实就是一个链式优先级捐赠， 本质测试的还是多层优先级捐赠逻辑的正确性。值得注意的是释放一个锁时如果当前线程不被捐赠即马上改为原来的优先级以实现抢占式调度。 18. 这里总结一下所有的逻辑：

在一个线程获取一个锁的时候， 如果拥有这个锁的线程优先级比自己低就提高它的优先级，并且如果这个锁还被别的锁锁着， 将会递归地捐赠优先级， 然后在这个线程释放掉这个锁之后恢复未捐赠逻辑下的优先级。

如果一个线程被多个线程捐赠， 维持当前优先级为捐赠优先级中的最大值（acquire和release之时）。

在对一个线程进行优先级设置的时候， 如果这个线程处于被捐赠状态， 则对original_priority进行设置， 然后如果设置的优先级大于当前优先级， 则改变当前优先级， 否则在捐赠状态取消的时候恢复original_priority。

在释放锁对一个锁优先级有改变的时候应考虑其余被捐赠优先级和当前优先级。

将信号量的等待队列实现为优先级队列。

62

将condition的waiters队列实现为优先级队列。 释放锁的时候若优先级改变则可以发生抢占。 19. 实现

1）修改thread结构体，修改部分在最后三行：

分别为优先级捐赠收回后应恢复的优先级，线程拥有的锁，线程等待的锁。

2）修改lock结构体，增加了最后两行：

分别为优先级捐赠的队列和想获得锁的最大优先级。 3）修改lock_acquire()函数：

63

如果锁被拥有，设置当前线程的lock_waiting为lock，并且比较当前线程的优先级和占有锁的线程的优先级，如果当前线程优先级大，则执行优先级捐赠，并且继续递归到锁的占有线程的等待队列，比较优先级并执行同样的操作，直到锁为空或不需优先级捐赠。

得到锁之后，设置等待锁为空，设置锁的等待线程中的最大优先

级为当前线程的优先级，设置当前线程占有锁并且锁为当前线程占有。

在这个实现中，thread_donate_priority和thread_hold_the_lock是新的函数。

4）实现thread_hold_the_lock():

这个函数的作用是设置当前线程占有锁lock。实现是将锁加入线程拥有的锁的优先级队列中，如果锁的等待线程中最大的优先级大于当前线程的优先级，则实现优先级捐赠增大当前线程优先级，并将当前线程丢到就绪队列中重新执行。 5）实现thread_donate_priority():

65

这里要捐赠的线程t是锁的拥有者，先更新t的优先级，逻辑是如果t在就绪队列中，因为t的优先级改变，所以先则将t拿出来，再重新插回去。

其中thread_cmp_priority()实现如下：

6）在lock_release()中加入最后两行

其中thread_remove_lock()实现如下：

66

释放锁时收回优先级捐赠，更新线程的优先级，更新锁的等待队列。

7）实现函数thread_update_priority()，用于释放锁时线程优先级可能的变化

如果线程占有的锁的等待线程中有优先级比当前线程优先级大的，则将线程的优先级设置为较大的优先级。 8）在init_thread中加入新变量的初始化。

67

新变量的初始化在后面凸出来的3行. 9）修改thread_set_priority():

保存原先的的优先级到old_priority，设置base_priority为新的优先级，如果当前线程没有占有锁或新优先级大于原优先级，就设置优先级priority为新优先级并丢到就绪队列中。则当优先级捐赠

68

被收回时设置priority为base_priarity。

10）把condition的队列修改为优先级队列，修改cond_signal()函数：

如果cond的等待队列不为空，按优先级排序并执行V操作。比较函数cond_sema_cmp_priority()如下：

11）把信号量的等待队列实现为优先级队列。修改sema_up():

69

信号等待队列不为空，则按优先级排序，并解除队列首部现成的阻塞。信号量+1，线程加入就绪队列中。修改sema_down()如下：

至此，优先级调度完成。

70

（4）Pintos高级调度的策略及实践过程。

1. 阅读文献可知，每个线程有一个nice(-20~20)，有一个优先级priority(PRI_MIN 0 ~ PRI_MAX 63)，优先级的计算公式为

，其中recent_cpu初始化为

1，然后每秒都会以下面的公式更新

，其中load_avg

是就绪队列中的平均线程数量，它初始化为0，每秒都以下面的公式更新

， 其中

ready_thread是当前的正在运行的线程和就绪队列的线程数目的和。

文献指出，pintos没有设置浮点运算，但给出了规则，所有的浮点数运算由我们实现。

实现思路： 在timer_interrupt中固定一段时间计算更新线程的优先级，这里是每TIMER_FREQ时间更新一次系统load_avg和所有线程的recent_cpu， 每4个timer_ticks更新一次线程优先级， 每个timer_tick running线程的recent_cpu加一， 虽然这里说的是维持个优先级队列调度， 其本质还是优先级调度， 我们保留之前写的优先级调度代码即可， 去掉优先级捐赠（之前donate相关代码已经对需要的地方加了thread_mlfqs的判断了）。 2. 实现

71

1）浮点运算的实现，在fixed_point.h中：

这里使用16位数FP_SHIFT_AMOUNT作为浮点数的小数部分，无论什么运算都要维持整数部分从第17位开始。aaaabbbbbbbbbbbbbbbb，a代表整数部分，b代表小数部分。 2）修改timer_interrupt()加入一个thread_mlfqs即多级反馈调度成立的处理：

72

如果要多级反馈调度，则执行三个函数。三个函数如下：

这个函数将recent_cpu+1。

如果ticks是TIMER_FREQ的整倍数，调用函数:

73

每秒钟更新每个线程的recent_cpu和load_avg。 如果ticks是4的整数倍，调用函数：

更新优先级。

3）在thread结构体中添加下面两个变量：

在init_thread()中初始化两个变量：

设置得到和更改nice、load_avg、recent_cpu的函数：

74

在thread.c中加入全局变量

并在thread_start中初始化：

75

完成实现。

76

五、实验结果及分析

（1）Pintos忙等问题的实践结果及分析。

通过将timer_sleep()线程的不断在就绪队列和CPU中来回移动改为线程阻塞，解决了以alarm开头的忙等待问题。 （2）Pintos优先级调度问题实践结果及分析。

通过赋予线程优先级并实现运行时的优先级调度，以及多线程情况下的优先级捐赠问题，解决了以priority开头的优先级调度问题。 （3）Pintos高级调度策略的实践结果及分析。

这里解决的是线程在运行过程中优先级动态变化，由此必须在变化的同时执行优先级调度，解决了以mlfqs开头的多级反馈调度问题。

77

六、Pintos项目１小结

这个实验从开学开始做，兜兜转转做了半个学期才完成，完成日期是2019年11月22日。先前做的实验写的代码都是很小的一部分，而这个项目很大，需要在实现前阅读很多的代码，这造成了很大的困难。刚开始实现没有一点头绪，通过查阅相关资料帮助了解，到后面阅读代码逐渐顺利起来了。不管是最开始的配置环境，还是后面的修改代码，无论是自己解决还是上网查都走了很多弯路，从中培养了发现问题和解决问题的能力。实验最困难的优先级调度部分，采用的方法都是课上讲过的很基本的方法，但是将思想化为代码还是很困难，这也鼓励着我们不断实践和进取，探索新的世界。

78

Pintos项目2

一、实验目的

（1）了解Pintos操作系统的功能流程及内核的软件工程结构。 （2）通过Pintos操作系统内核的剖析，了解现有Pintos操作系统在处理用户程序方面中存在的参数传递问题，有效解决其参数传递的问题。

（3）通过Pintos内核剖析，了解其中断处理的机制，学会操作系统中断功能的编写方法。

（4）了解现有Pintos操作系统的系统调用功能，根据其中断机制，完善系统调用功能，使Pintos系统具有处理用户中断请求的功能。

（5）通过Pintos内核剖析，解决现有Pintos操作系统中存在的进程终止时缺少终端提示的问题。

（6）通过Pintos内核剖析，解决现有Pintos操作系统中存在的运行文件禁止写操作的问题。 二、实验内容与设计思想

（1）在分析内核的基础上，对 Pintos操作系统的参数传递问题提出有效的策略，设计算法，分步跟踪和调试，通过实践，有效解决参数传递问题，并对实验结果进行分析。

（2）通过Pintos操作系统内核的剖析，了解其中断处理的机制，

79

在此基础上，完善Pintos的系统调用功能，设计算法，分步跟踪和调试，通过测试分析完善的系统调用功能。

（3）在分析内核的基础上，对现有Pintos操作系统进行完善，增加进程终止的终端提示功能，设计算法，分步跟踪和调试，通过实践，验证终端提示功的有效性。

（4）在分析内核的基础上，对现有Pintos操作系统进行完善，增加运行文件禁止写操作的功能，设计算法，分步跟踪和调试，通过实践，验证禁止写操作功能的有效性。 三、实验使用环境

Ubuntu12.04操作系统环境，Pinto操作系统原型，gdb跟踪调试工具。

四、实验过程与分析、调试过程  准备用户程序，建立用户磁盘

终端到src/examples，执行命令make生成echo文件。

终端到src/userprog中，执行make，到build中执行pintos-mkdisk filesys.dsk –filesys-size=2，由此创建了一个名为filesys.dsk的2M大小的磁盘。

（1） 参数传递问题的分析及实践过程 在string.h中有这样一个函数用于参数分离：

80

函数参数中s是要分离的字符串，delimiters是分隔符，指定了参数以什么分离，也就是空格，save_ptr指定了分离好的参数存储的位置。示例如下：

81

在process_execute()中，函数创建一个内核线程用以加载用户进程，因为thread_create()需要一个线程名，此时传递给它文件名，而传入的file_name是所有参数的字符串，需要分离。

接下来，在start_process()中再次分离参数，函数将用户进程加载入内核执行：

82

加载进程后，需要将用户进程的所有命令行参数压栈，实现需要在上述代码之后。在start_process()中有一个struct_intr_frame if_，这个结构体标识了用户进程的所有状态，其中的成员if_.esp是用户栈指针，在load()函数中为其赋值分配栈空间。

调用strtok_r分离出一个个参数，把每个参数都复制到用户栈中，并把它在栈中的位置记录到一个数组arg中。栈向下增长。参数全部压栈完毕后，加入一个4位对齐，然后，将指针按照逆序放入栈中，放入argv的位置指针和argc，并让用户栈指针指向新的栈顶。Start_process()剩余部分如下：

83

（2） 系统调用功能的分析、设计及实践过程

在src/lib/syscall-nr.h中给出了所有系统调用的调用号

84

在src/lib/user/syscall.h中给出了所有系统调用的形式（参数类型）。

在src/userprog/syscall.h中声明这些系统调用处理函数，同时声明了CALL_PROC类型的pfn用于保存系统调用函数，将void 定义为零一类型。

85

在src/userprog/syscall.c中的实现：

首先在syscall_init()中保存各函数名，数组pfn下标是系统调用号，其他设置为NULL。

在syscall_handler()函数中依据系统调用号调用相应函数。

86

其中ExitStatus()函数用于非正常情况下的进程终止，在后面实现。 1) SYS_WRITE，写操作，调用函数向标准输出或文件写，首先从用户栈中获取三个参数，即标准输出或文件句柄fd，写的内容buffer，写的大小size，然后依据fd实现写操作。

87

其中GetFile()函数和file_node结构体在后面实现。

2) SYS_EXIT，是用户正常退出时的系统调用，需要取出返回值保存到进程控制块的ret变量中，调用thread_exit()函数退出进程。 这里同样实现了非正常退出的ExitStatus()函数。

3) SYS_CREATE，创建文件，从用户栈中取出参数文件名和文件大小，调用filesys_create()函数创建文件。

4) SYS_OPEN，打开文件，这里需要为每个进程维护一个打开文件表，记录打开文件的数量，打开文件后还要为每个文件分配一个句柄号唯一标识文件。在struct thread结构中加入：

88

在src/filesys/file.h中加入关联文件句柄和文件指针的结构体

有了以上准备，每打开一个文件就要新建一个file_node结构体，分配文件句柄，递增FileNum，并把file_node加入文件打开队列，最后返回文件句柄。

5) SYS_CLOSE关闭文件，从用户栈中获取要关闭文件的句柄，从用户打开文件列表中找到文件，得到文件指针，调用file_close()关闭文件，释放struct file_node。

定义了一个函数CloseFile()，依据参数的不同关闭某个文件或所有文件。

6) SYS_READ，读文件，从用户栈中获得fd、buffer和size三个参数，如果fd是标准输入，则调用input_getc()，是文件则找到文件指针，调用file_read()读取数据。

90

这里定义了一个新的函数GetFile()

7) SYS_FILESIZE，获取文件大小，从用户栈中获得文件句柄fd，由

91

fd找到文件指针，调用file_length()得到文件大小。

8) SYS_EXEC，加载用户程序，用户程序通过这个系统调用创建子进程。在IExec()函数中，分配一个页，复制一份用户提供的用户名，否则后来分离参数时，加入’\\0’会出现核心线程写入用户内存空间的页错误。父进程调用process_execute()创建子进程，然后调用start_process()加载该子进程，但start_process()函数可能因找不到程序文件或内存不足等问题加载失败，所以父进程调用process_execute()后不能立刻返回，要在信号量上等待，直到start_process()返回后再激活父进程，激活父进程前子进程应该挂起自己，父进程获取子进程状态信息后，再激活子进程。如果不这样做，当父进程创建了一个优先级高的子进程时，子进程执行完成后父进程才恢复，这样就得不到子进程的状态了。如果子进程创建成功则返回pid，否则返回-1。为了实现信号量等待，在struct thread结构中加入semaphore信号量并初始化。

92

实现

修改start_process()函数，在load()之后修改：

IExec()中的GetThreadFromTid()如下：

93

由于all_list定义在src/threads/thread.c中且声明为static list变量，所以该函数定义在thread.c中。 9) SYS_WAIT，父进程等待子进程结束。

主进程创建子进程后，出于它与子进程优先级一样，这样二者交替执行，主进程可能先结束而无法获得子进程的返回状态，由此加入该系统调用。

系统调用需要父进程创建子进程后要等待子进程结束，process_wait()返回子进程的返回值。情况有两种，若父进程调用process_wait()时子进程还未结束，就将父进程挂起，等待子进程结束后父进程唤醒，由此父进程获取了子进程的返回值；若父进程调用process_wait()时子进程已经结束，要求子进程结束后应该把返回值保存到父进程的进程控制块中。

在struct thread中加入一个链表，struct list sons_ret，加入一个保存返回值的结构struct ret_data，每当一个子进程终止，就将返回值保存到struct ret_data中，这个结构体进入链表即可。

在struct thread结构中加入bool bWait，表示进程本身有没有

94

被父进程等待；加入bool SaveData，如果子进程已经把返回值保存到了父进程就设为ture，该项应初始化为false；加入struct thread *father，表示父进程。

进程的等待由信号量实现。在struct thread结构中加入semaphore SemaWait，这里选择在父进程的SemaWait上等待，这个等待会把父进程的进程控制块插入到SemaWait的list上去。 父进程执行process_wait(chile_pid)后，可以由child_pid得到子进程的进程指针t，这通过遍历all_list比较pid实现，如果在all_list没有发现子进程的进程控制块或子进程已经把返回值保存到了父进程或子进程已经终止，直接从sons_ret链表中找到子进程的返回值就可。如果子进程还在运行，执行

sema_down(t->father->SemaWait)把自己挂起，子进程执行完后，发现bWait==ture，自己被父进程等待了，释放父进程sema_up(SemaWait)，如果bWait==false，则不用唤醒父进程。父进程唤醒后，从sons_ret链表中得到子进程返回值。 一个进程结束时，在process_exit()函数中要释放自己打开的所有文件，保存返回值到父进程，输出退出信息，如果有父进程在等他就唤醒父进程，释放子进程链表。 在struct thread中加入下面的成员:

95

在init_thread()中初始化如下:

定义结构体struct ret_data:

96

修改process_exit()函数:

97

其中的record_ret实现如下:

10)

SYS_SEEK移动文件指针，从用户栈中去除文件句柄fd和要移

动的距离，调用file_seek()移动即可。

11)

SYS_REMOVE删除文件，取出要删除的文件名，调用

filesys_remove()删除文件。

98

12)

SYS_TELL返回文件指针当前位置，从用户栈中去除文件句柄

fd，转为文件指针，调用file_tell()得到指针位置。

13)

SYS_HALT关机，调用shutdown_power_off()关机。

（3） 进程终止的终端提示问题的分析、设计及实践过程 要求在进程结束时输出退出的main函数的返回值。 既然要打印返回值，就需要一个变量保存返回值，在struct thread结构中加入一个ret变量，在init_thread()中初始化为0。

99

为ret赋值的操作留到系统调用的EXIT中实现。每个线程结束后，都要调用thread_exit()函数，如果是加载了的用户线程，thread_exit()还要调用process_exit()函数，

在process_exit()中，如果是用户进程，那么其页表一定不为NULL，而核心进程页表一定为NULL，所以在if(!=NULL)成立时加入打印退出值的语句。

100

（4）运行文件禁止写操作问题的分析、设计及实践过程 在struct thread结构中添加FileSelf变量

这里的可执行文件主要指的是用户进程的子进程，即用户进程加载子进程时不能修改子进程。

在start_process()函数加入不能写的:

在process_exit()函数中解除

五、实验结果及分析

（1）参数传递问题问题的实践结果及分析。

在没有分离参数之前，通过命令行输入的一系列参数都被看作一个整体字符串传递给函数执行，这显然是的。分离参数采用了string.h中的函数strtok_r()，并且这里还设计了一个栈结构，将参数、参数指针等条目压栈，供后面取用。 （2）完善系统调用功能的实践结果及分析。

系统调用是用户程序和内核交流的接口，通过实现各种系统调用

101

实现了读写、开关、删改、移动等操作，这一步除了调用操作系统的中断处理函数外，还使用了先前分离的参数和栈的内容，以及进程的加载、开始、等待、终止等内容。

（3）进程终止的终端提示问题的实践结果及分析。 在进程结束时调用printf打印返回值等即可。 （4）运行文件禁止写操作问题的实践结果及分析。

在运行和执行文件时，加载中要实现禁止写操作，终止后实现解除禁止。 运行结果:

六、Pintos项目2小结

这个项目在十六周才完成。操作系统作为底层用户和计算机交互的接口，为用户使用计算机提供了服务。这里主要实现了用户程序的参数分离，用户程序系统调用的处理，以及后面的终端提示和禁止运行时写等操作。在这一个工程中最困难的部分是系统调用，和前一个工程相比，我们更少地去阅读代码，而是更多去实现新的功能。通过学习，我对栈的结构，包括参数的位置和栈各部分的组成等有了更清晰的认识；系统调用的加载和等待两个内容复习了之前学习的内容；同时对文件的处理页开启了新的世界。

102