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

精品文档操作系统实验报告专业名称：软件工程学生年级：2018级本科指导教师：课程性质：专业必修研修时间：20192020学年第1学期实验地点：软件学院2020年 1月 1日Pintos 实验统计l 请自评你的项目完成情况，在表中相应位置划。Pintos Project1内容完成情况完成圆满基本完成完成大部分还有很多没完成1. 消除忙等2. 优先级调度3. 高级调度Pintos Project2内容完成情况完成圆满基本完成完成大部分还有很多没完成1. 进程终止的终端提示2. 参数传递3. 系统调用4. 运行文件禁止写操作目 录摘 要4基础实践15基础实践26Pintos项目17Pintos项目210摘 要 基础实践1一、目的1) 掌握虚拟机安装方法2) 掌握Linux的基本使用方法 3) 掌握Pintos的安装方法4) 掌握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-studmakesudo make install安装和运行pintos：tar zxvf pintos2011.tar.gzcd pintos/src/tjreadsmakecd build././utils/pintos rum alarm-multiple五、实验总结实验的开端，安装，配置环境。六、附录基础实践2一、目的5) 巩固Ubutu系统命令； 6) 通过例程了解进程、线程的创建及主要函数的使用方法；7) 掌握用户程序的编辑、编译、调试程序的方法；8) 学会利用gdb跟踪程序的方法；9) 了解Pintos工程的结构，学会Pintos的跟踪方法。二、内容与设计思想1、编辑几个例程，了解进程、线程的创建及主要函数的使用方法。2、利用gdb对上述的进程、线程的基本例程进行调试和跟踪，学会断点设置和取消方法，学会在断点处观察变量的方法。3、了解Pintos工程的结构，学会Pintos的编译、运行及跟踪方法。三、使用环境Ubuntu 12，Pinos，gedit或vi，gdb四、实验过程与分析、调试过程1. tid_tthread_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 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 $ 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/utilsmakesudo cp squish-pty /usr/binsudo 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/buildgdb kernel.o 成功进入gdb，在(gdb)中输入target remote localhost:1234 continue，连接完成。3. pintos结构，包括内核device，文件调用filesys，库文件lib，线程使用threads，用户程序userprog等。五、实验总结实验了解了pintos的基本结构，了解了进程线程创建和初始化的方法等，为下面开始实验做了铺垫。六、附录Pintos项目1一、实验目的（1）了解Pintos操作系统的功能流程及内核的软件工程结构。（2）通过Pintos操作系统内核的剖析，了解现有Pintos操作系统在CPU调度功能中存在的问题。（3）学会用软件工程的方法分析、解决以上问题。（4）在实践中，通过消除Pintos操作系统调度问题，学会利用gdb跟踪策略对程序进行动态调试的方法。二、实验内容与设计思想（1）通过Pintos操作系统内核的剖析，了解其线程管理的机制。（2）了解现有Pintos操作系统的功能及线程调度中存在的问题。（3）在分析内核的基础上，分析忙等问题，设计算法，分步跟踪和调试，通过实践，有效解决忙等问题，并对实验结果进行分析。（4）在分析内核的基础上，分析现有CPU调度问题，设计利用优先级进行调度的策略，分步跟踪和调试，通过实践，验证抢占优先级调度算法的有效性，并对实验结果进行分析。（5）通过系统分析，设计有效的优先级翻转及多级反馈队列的CPU调度策略，分步跟踪和调试，通过实践，验证优先级翻转及多级反馈队列的CPU调度算法的有效性，并对实验结果进行分析。三、实验使用环境Ubuntu12.04操作系统环境，Pinto操作系统原型，gdb跟踪调试工具。四、实验过程与分析、调试过程（1）Pintos内核剖析（2）Pintos忙等问题分析及实践过程1. 在time.c中，有关于进程等待的函数timer_sleep()的实现函数的参数是操作系统指定的等待时间，没有返回值。在该函数第五行中，函数将timer_ticks()的返回值赋值给start。2. 找到timer_ticks()函数的实现枚举类型intr_level指定的是线程是否可以被中断。函数首先调用了intr_disable()，将其返回值赋值给枚举变量。3. 找到intr_disable()的函数实现函数调用了intr_get_level()，将其返回值赋值给一个枚举类型。4. 查看intr_get_level()的函数实现这里使用了汇编代码，由注释可以看出，函数返回的是线程当前是否可以被中断的状态。5. 回到intr_disable()中函数以old_level保存了当前线程是否可被中断的状态，然后使用汇编指令指定当前操作不能被中断，并返回线程先前是否可被中断的状态。6. 有以上结论我们可以知道： timer_ticks()第五行做了这么一件事情： 禁止当前行为被中断， 保存禁止被中断前的中断状态（用old_level储存）第六行以t存储全局变量ticks的值，这个t是函数的返回值。7. 全局变量ticks如下从pintos被启动开始， ticks就一直在计时， 代表着操作系统执行到现在的时间。8. 第七行调用intr_set_level()这个函数以参数level的值设置当前的中断状态。其中intr_disable()设置不可被中断，intr_enable()设置可以被中断。9. intr_enable()函数如下函数以old_level存储了线程的当前是否可被中断的状态并返回。第十二行使用汇编语言设置当前可以中断。10. ASSERT()调用了intr_context()函数这个函数返回in_external_intr，这个值是true如果中断为外中断(I/O中断)，值是false如果为内中断(进程切换)，这里intr_enable()第六行保证中断是一个进程或线程切换的中断。11. 回到timer_sleep()中第六行的作用是获取一个时间，这个时间是正在执行的线程开始停止的时间。第七行保证线程现在是可以中断的状态。12. 第八行调用了timer_elapsed()函数then是timer_sleep()中的start，即线程开始停止时间，函数调用timer_ticks()，这个函数在6，返回的是现在的时间，由此可知函数返回进程已经停止的时间。13. 当这个时间小于ticks（这里的ticks是函数的参数，代表线程要停止的时间）时，执行thread_yield()。14. 函数thread_yield()定义如下函数首先以cur指针指向thread结构体。15. 调用thread_current()函数函数以t为指针和返回值，调用running_thread()函数，该函数返回当前运行的线程地址。函数保证t指向的是一个线程并且线程状态是正在运行。16. 返回到thread_yield()中第六行得到了当前正在运行的线程，第九行保证线程中断是内中断，第11行将当前线程设置为不可中断并存储线程中断状态，第1214行如果线程不是一个空闲线程(就是正在运行被中断了)就把线程加到就绪队列中去，第15行调用schedule()，16行恢复先前的中断状态。17. schedule()如下cur指向当前运行线程，next是就绪队列中下一个要运行的线程，保证当前不可中断，当前运行线程状态不是运行（刚刚加入就绪队列），next是一个线程，19行如果cur和next不相同，就调用switch_threads切换，18. 将next进程开始执行若就绪队列空，设置空闲线程，否则调用lest_entry()使下一个线程执行。函数的返回值被赋值给prev，这时prev和cur指的是同一线程。schedule()最后一行调用19. thread_schedule_tail()thread_schedule_tail()其实就是获取当前线程， 分配恢复之前执行的状态和现场， 如果当前线程死了就清空资源。schedule()其实就是拿下一个线程切换过来继续run并进行上下文切换。thread_yield()其实就是把当前线程扔到就绪队列里， 然后重新schedule， 注意这里如果ready队列为空的话当前线程会继续在cpu执行。最后回溯到我们最顶层的函数逻辑： timer_sleep()就是在ticks时间内， 如果线程处于running状态就不断把他扔到就绪队列不让他执行。20. 操作系统的缺点很明显：线程依然不断在cpu就绪队列和running队列之间来回， 占用了cpu资源， 这并不是我们想要的， 我们希望用一种唤醒机制来实现这个函数。忙等待实现实现思路： 调用timer_sleep()的时候直接把线程阻塞掉，然后给线程结构体加一个成员ticks_blocked来记录这个线程被sleep了多少时间， 然后利用操作系统自身的时钟中断（每个tick会执行一次）加入对线程状态的检测， 每次检测将ticks_blocked减1, 如果减到0就唤醒这个线程。1. 修改thread(thread.h)结构体，加上一个ticks_blocked2. 修改thread_create()函数(在thread.c中)，使之初始化ticks_blicked为0。（截图中函数不完整）3. 修改中断处理函数timer_interrupt()(在timer.c中)，加入线程sleep时间的检测。4. 其中函数thread_foreach()已经定义在thread中： 函数的作用是对每一个就绪队列中的线程实现func()函数，这里的func()函数是blocked_thread_check()函数，用于检测是否有个线程停止等待进入执行5. 新函数blocked_thread_check()声明并定义在thread中作用是所有线程等待时间-1，若有线程阻塞时间为0，解除阻塞。6. 对timer_sleep()的修改（3）Pintos优先级调度问题分析及实践过程。1. 在thread.h中，已经为每个线程结构赋予一个优先级的值，即图中的8行。同时宏定义了priority的约束2. 优先级调度，指的是程序由就绪队列调度执行时依据优先级调度。就绪队列是一个优先级的队列，需要我们在将线程加入队列时加到合适的位置。下面的函数需要将线程加入就绪队列。它们都使用了list_push_back()函数(定义在list.c中)list_insert()如下：list_insert()是在队列中把elem放到before前面。list_push_back()是把elem放到队列尾巴的前面，即队列最后一个元素。三个函数都是简单地把线程放到队列尾部，没有按照优先级排列。3. 队列部分解释如下：结构体list_elem指定了队列上一个元素和下一个元素，结构体list是队列的头和尾，这个头和尾是空的。结构体thread包含list_elem。4. 阅读list.c，发现有这样一个函数：函数以less()为优先级比较方法的函数，从队列头遍历，找到插入点，将线程插入队列。需要我们完成less()函数的构造。5. 构造less()函数list_insert_ordered()最后调用了list_insert(e, elem)，将elem插入到e的前面，说明elem优先级更高，less()函数需要第一个参数elem比第二个参数e的优先级更高，在队列中，队列前面的优先级肯定是大于后面的的，因此e从头部开始遍历，逐渐变小，直到小于elem，合乎逻辑。构造的less()函数需要比较elem和e的优先级，当第一个参数大时返回true。由于a是结构体thread的元素，优先级priority也是结构体thread的元素，我们调用了宏定义list_entry()指定a的thread：6. 将三个函数的list_push_back()改为7. 观察测试样例test_priority_preempt()和test_priority_change()：这个样例先保证当前线程的优先级为PRI_DEFAULT，然后创建了一个优先级为PRI_DEFAULT+1的线程，这样新创建的线程应该抢占原来的线程。这个线程创建了一个优先级为PRI_DEFAULT+1的新线程，新线程抢占原线程，然后新线程优先级-1，又回到原来的线程中，然后原线程优先级-2，又回到新线程中，新线程终止，回到原线程，原线程终止。所以期望的输出为：分析这个测试行为我们得出的结论就是： 在设置一个线程优先级要立即重新考虑所有线程执行顺序， 重新安排执行顺序。要实现这个功能，我们可以在创建新线程和更改线程优先级的时候调用thread_yield()，直接将其丢入就绪队列中即可。更改如下：在thread_create()最后修改代码如下：8. 优先级捐赠。考虑下面一种情况，在这里ABC是三个进程，优先级分别为123（优先级越大先执行），线程 A 对一个互斥资源拥有线程锁。而此时, 高优先级的线程 C 也想要访问这个互斥资源, 线程 C 只好在这个资源上等待,不能进入就绪队列。当调度器开始调度时, 它只能从 A 和 B 中进行选择,根据优先级调度原理,线程 B 将会首先运行。这时就产生了一个问题, 即本来线程 C 优先级比线程 B 高, 但是线程 B 却先运行了,从而产生了优先级翻转问题。解决方法就是当发现高优先级的任务因为低优先级任务占用资源而阻塞时，就将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级，这里将A的优先级提升为3。9. 查看第一个案例test_priority_donate_one()： 原线程优先级为PRI_DEFAULT，它声明一个锁并获得这个锁，然后创建一个优先级为PRI_DEFAULT + 1的线程acquire1，这个线程需要获得锁，但是锁已经被原线程获取，所以线程acquire1等待。原线程创建一个优先级为PRI_DEFAULT+2的线程acquire2，这个线程执行的操作和acquire1一样，等待锁。原线程释放锁，然后应该是线程acquire2先执行并结束然后线程acquire1执行并结束，最后原线程终止。查看获得锁和释放锁的函数：函数在synch.c中结构体lock是一个拥有者一个信号量，信号量的结构是一个值一个等待队列。初始化锁的拥有者为null，信号量的值为参数(1)。函数lock_acquire()首先保证锁不被其他线程占有，否则等待。然后调用sema_down()即P操作，函数将线程放在信号量的等待队列中，等待唤醒，唤醒后value-，表示锁再次被占有。回到lock_acquire()中，设置锁的占有程序，回到进程。在lock_release()中首先保证锁被占有，然后调用sema_up()函数，如果信号的等待队列不为空则将队列首部的线程提出，并使value+。该样例希望的输出如下：在第7行和第8行中original_thread的优先级被捐赠了。实现思路是：在一个线程获取一个锁的时候， 如果拥有这个锁的线程优先级比自己低就提高它的优先级，然后在这个线程释放掉这个锁之后把原来拥有这个锁的线程改回原来的优先级。10. 分析样例test_priority_donate_multiple()原线程声明并获取了两个锁ab，创建优先级为PRI_DEFAULT + 1的线程a，a获取锁，等待，创建优先级为PRI_DEFAULT + 2的线程b，b获取锁b，等待。原线程释放锁b，线程b执行，结束，释放锁a，线程a执行，结束，原线程终止。期望的输出结果如下：在第7行，原线程被捐赠，优先级同线程a，在第8行，原线程被捐赠，优先级同线程b，第12行，线程b收回捐赠，第16行，线程a收回捐赠。这里测试的行为实际是： 多锁情况下优先级逻辑的正确性。那么我们对应的实现思路是： 释放一个锁的时候， 将该锁的拥有者改为该线程被捐赠的第二优先级，若没有其余捐赠者， 则恢复原始优先级。那么我们的线程必然需要一个数据结构来记录所有对这个线程有捐赠行为的线程。11. 分析样例test_priority_donate_multiple2():原线程创建锁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，结束，原线程终止。期望的输出如下：这里测试的依然是多锁情况下的优先级逻辑的正确性，前面分析过了。12. 查看样例test_priority_donate_nest()这里创建两个锁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。原线程释放锁a，线程medium抢占并执行，然后释放锁a释放锁b，线程high抢占，执行，结束，线程medium继续执行，结束，原线程执行并结束。期望结果如下：这个测试是一个优先级嵌套问题， 重点在于medium拥有的锁被low阻塞， 在这个前提下high再去获取medium的说阻塞的话， 优先级提升具有连环效应， 就是medium被提升了， 此时它被锁捆绑的low线程应该跟着一起提升。从实现的角度来说， 我们线程又需要加一个数据结构， 我们需要获取这个线程被锁于哪个线程，以提升对应线程的优先级。13. 实现样例test_priority_donate_sema():原线程声明一个结构体，这个结构体包含一个信号量一个锁。创建优先级为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，执行直到结束，回到原线程执行结束。这里的设计思想是为线程结构添加一个成员，标识信号占有的线程。14. test_priority_donate_lower()：原线程声明一个锁，获取这个锁，创建优先级为PRI_DEFAULT + 10的线程，这个线程试图获取锁，阻塞。原线程中将优先级修改为PRI_DEFAULT 10，这里如果修改了就会陷入死锁，所以实施策略是当捐赠行为被收回时更改优先级。所以原线程继续执行，释放锁同时修改优先级，新线程执行，结束，原线程执行，结束。15. test_priority_sema()原线程声明一个信号量并初始化为0，然后将自身优先级设置为PRI_MIN。使用一个循环，创建10个线程，线程名字为priority %d(优先级)，优先级分别为2130，所有线程都试图获取信号量，都阻塞。回到原线程，使用一个循环创建调用10次sema_up()，每次调用都会直接被优先级高的线程抢占，执行完后回到原线程中。期望输出结果如下：这里要实现的是，信号量的等待队列是优先级队列。16. test_priority_condvar()：这里condition里面装的是一个waiters队列， 看一下con_wait和cond_signal函数：cond_wait()是声明一个信号量等待队列，它声明一个waiter并使它进入cond的等待队列，释放锁，waiter信号量的值-1，获得锁；cond_signal()如果队列不为空则使队首的waiter信号量+1。回到原线程，设置原线程优先级为PRI_MIN，创建10个优先级分别为2130的线程，每个线程都获取锁，最终的结果是每个线程获得了锁，并调用cond_wait()，释放锁，进入等待队列试图获取信号量，但信号量为0，所以线程在这里等待（cond_wait第34行），回到原线程，创建下一个线程。创建了10个线程之后，原线程执行第二个循环，获取锁并执行cond_signal()，这里释放信号量，应该先释放优先级高的线程的信号量，该线程被唤醒并执行，释放锁，直到结束。所有线程结束后回到原线程，原线程结束。这里要求的是condition的waiters队列是优先级队列。17. test_priority_donate_chain()声明一个锁数组，声明一个包含两个lock指针的结构体lock_pairs，当前线程优先级设置为PRI_MIN。原线程获取锁0，设置一个循环，设置优先级依次递增，每个线程设置结构体lock_pairsi中前一个指针指向locksi，后一个指针指向locksi-1，创建线程抢占当前线程，若locksi存在则获取这个锁，试图获取locksi-1，但locksi-1被占有，所以等待。回到原线程，原线程创建第二个优先级为thread_priority-1的线程，由于原线程优先级被捐赠为thread_priority，所以这个线程不执行，直接进入下一个循环。循环执行结束后，原线程释放锁locks0，然后从头开始，按创建顺序执行所有被阻塞的线程，执行完成后释放locksi-1和locksi，直到所有阻塞线程执行完成。依次执行所有创建时优先级不够没有执行的线程，即调用函数interloper_thread_func()，执行完成后回到原线程，进程终止。这个测试其实就是一个链式优先级捐赠， 本质测试的还是多层优先级捐赠逻辑的正确性。值得注意的是释放一个锁时如果当前线程不被捐赠即马上改为原来的优先级以实现抢占式调度。18. 这里总结一下所有的逻辑：在一个线程获取一个锁的时候， 如果拥有这个锁的线程优先级比自己低就提高它的优先级，并且如果这个锁还被别的锁锁着， 将会递归地捐赠优先级， 然后在这个线程释放掉这个锁之后恢复未捐赠逻辑下的优先级。如果一个线程被多个线程捐赠， 维持当前优先级为捐赠优先级中的最大值（acquire和release之时）。在对一个线程进行优先级设置的时候， 如果这个线程处于被捐赠状态， 则对original_priority进行设置， 然后如果设置的优先级大于当前优先级， 则改变当前优先级， 否则在捐赠状态取消的时候恢复original_priority。在释放锁对一个锁优先级有改变的时候应考虑其余被捐赠优先级和当前优先级。将信号量的等待队列实现为优先级队列。将condition的waiters队列实现为优先级队列。释放锁的时候若优先级改变则可以发生抢占。19. 实现1）修改thread结构体，修改部分在最后三行：分别为优先级捐赠收回后应恢复的优先级，线程拥有的锁，线程等待的锁。2）修改lock结构体，增加了最后两行：分别为优先级捐赠的队列和想获得锁的最大优先级。3）修改lock_acquire()函数：如果锁被拥有，设置当前线程的lock_waiting为lock，并且比较当前线程的优先级和占有锁的线程的优先级，如果当前线程优先级大，则执行优先级捐赠，并且继续递归到锁的占有线程的等待队列，比较优先级并执行同样的操作，直到锁为空或不需优先级捐赠。得到锁之后，设置等待锁为空，设置锁的等待线程中的最大优先级为当前线程的优先级，设置当前线程占有锁并且锁为当前线程占有。在这个实现中，thread_donate_priority和thread_hold_the_lock是新的函数。4）实现thread_hold_the_lock():这个函数的作用是设置当前线程占有锁lock。实现是将锁加入线程拥有的锁的优先级队列中，如果锁的等待线程中最大的优先级大于当前线程的优先级，则实现优先级捐赠增大当前线程优先级，并将当前线程丢到就绪队列中重新执行。5）实现thread_donate_priority():这里要捐赠的线程t是锁的拥有者，先更新t的优先级，逻辑是如果t在就绪队列中，因为t的优先级改变，所以先则将t拿出来，再重新插回去。其中thread_cmp_priority()实现如下：6）在lock_release()中加入最后两行其中thread_remove_lock()实现如下：释放锁时收回优先级捐赠，更新线程的优先级，更新锁的等待队列。7）实现函数thread_update_priority()，用于释放锁时线程优先级可能的变化如果线程占有的锁的等待线程中有优先级比当前线程优先级大的，则将线程的优先级设置为较大的优先级。8）在init_thread中加入新变量的初始化。新变量的初始化在后面凸出来的3行.9）修改thread_set_priority():保存原先的的优先级到old_priority，设置base_priority为新的优先级，如果当前线程没有占有锁或新优先级大于原优先级，就设置优先级priority为新优先级并丢到就绪队列中。则当优先级捐赠被收回时设置priority为base_priarity。10）把condition的队列修改为优先级队列，修改cond_signal()函数：如果cond的等待队列不为空，按优先级排序并执行V操作。比较函数cond_sema_cmp_priority()如下：11）把信号量的等待队列实现为优先级队列。修改sema_up():信号等待队列不为空，则按优先级排序，并解除队列首部现成的阻塞。信号量+1，线程加入就绪队列中。修改sema_down()如下：至此，优先级调度完成。（4）Pintos高级调度的策略及实践过程。1. 阅读文献可知，每个线程有一个nice(-2020)，有一个优先级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加一， 虽然这里说的是维持64个优先级队列调度， 其本质还是优先级调度， 我们保留之前写的优先级调度代码即可， 去掉优先级捐赠（之前donate相关代码已经对需要的地方加了thread_mlfqs的判断了）。2. 实现1）浮点运算的实现，在fixed_point.h中：这里使用16位数FP_SHIFT_AMOUNT作为浮点数的小数部分，无论什么运算都要维持整数部分从第17位开始。aaaabbbbbbbbbbbbbbbb，a代表整数部分，b代表小数部分。2）修改timer_interrupt()加入一个thread_mlfqs即多级反馈调度成立的处理：如果要多级反馈调度，则执行三个函数。三个函数如下：这个函数将recent_cpu+1。如果ticks是TIMER_FREQ的整倍数，调用函数:每秒钟更新每个线程的recent_cpu和load_avg。如果ticks是4的整数倍，调用函数：更新优先级。3）在thread结构体中添加下面两个变量：在init_thread()中初始化两个变量：设置得到和更改nice、load_avg、recent_cpu的函数：在thread.c中加入全局变量并在thread_start中初始化：完成实现。五、实验结果及分析（1）Pintos忙等问题的实践结果及分析。通过将timer_sleep()线程的不断在就绪队列和CPU中来回移动改为线程阻塞，解决了以alarm开头的忙等待问题。（2）Pintos优先级调度问题实践结果及分析。通过赋予线程优先级并实现运行时的优先级调度，以及多线程情况下的优先级捐赠问题，解决了以priority开头的优先级调度问题。（3）Pintos高级调度策略的实践结果及分析。这里解决的是线程在运行过程中优先级动态变化，由此必须在变化的同时执行优先级调度，解决了以mlfqs开头的多级反馈调度问题。六、Pintos项目小结这个实验从开学开始做，兜兜转转做了半个学期才完成，完成日期是2019年11月22日。先前做的实验写的代码都是很小的一部分，而这个项目很大，需要在实现前阅读很多的代码，这造成了很大的困难。刚开始实现没有一点头绪，通过查阅相关资料帮助了解，到后面阅读代码逐渐顺利起来了。不管是最开始的配置环境，还是后面的修改代码，无论是自己解决还是上网查都走了很多弯路，从中培养了发现问题和解决问题的能力。实验最困难的优先级调度部分，采用的方法都是课上讲过的很基本的方法，但是将思想化为代码还是很困难，这也鼓励着我们不断实践和进取，探索新的世界。Pintos项目2一、实验目的（1）了解Pintos操作系统的功能流程及内核的软件工程结构。（2）通过Pintos操作系统内核的剖析，了解现有Pintos操作系统在处理用户程序方面中存在的参数传递问题，有效解决其参数传递的问题。（3）通过Pintos内核剖析，了解其中断处理的机制，学会操作系统中断功能的编写方法。（4）了解现有Pintos操作系统的系统调用功能，根据其中断机制，完善系统调用功能，使Pintos系统具有处理用户中断请求的功能。（5）通过Pintos内核剖析，解决现有Pintos操作系统中存在的进程终止时缺少终端提示的问题。（6）通过Pintos内核剖析，解决现有Pintos操作系统中存在的运行文件禁止写操作的问题。二、实验内容与设计思想（1）在分析内核的基础上，对 Pintos操作系统的参数传递问题提出有效的策略，设计算法，分步跟踪和调试，通过实践，有效解决参数传递问题，并对实验结果进行分析。（2）通过Pintos操作系统内核的剖析，了解其中断处理的机制，在此基础上，完善Pintos的系统调用功能，设计算法，分步跟踪和调试，通过测试分析完善的系统调用功能。（3）在分析内核的基础上，对现有Pintos操作系统进行完善，增加进程终止的终端提示功能，设计算法，分步跟踪和调试，通过实践，验证终端提示功的有效性。（4）在分析内核的基础上，对现有Pintos操作系统进行完善，增加运行文件禁止写操作的功能，设计算法，分步跟踪和调试，通过实践，验证禁止写操作功能的有效性。三、实验使用环境Ubuntu12.04操作系统环境，Pinto操作系统原型，gdb跟踪调试工具。四、实验过程与分析、调试过程l 准备用户程序，建立用户磁盘终端到src/examples，执行命令make生成echo文件。终端到src/userprog中，执行make，到build中执行pintos-mkdisk filesys.dsk filesys-size=2，由此创建了一个名为filesys.dsk的2M大小的磁盘。（1） 参数传递问题的分析及实践过程在string.h中有这样一个函数用于参数分离：函数参数中s是要分离的字符串，delimiters是分隔符，指定了参数以什么分离，也就是空格，save_ptr指定了分离好的参数存储的位置。示例如下：在process_execute()中，函数创建一个内核线程用以加载用户进程，因为thread_create()需要一个线程名，此时传递给它文件名，而传入的file_name是所有参数的字符串，需要分离。接下来，在start_process()中再次分离参数，函数将用户进程加载入内核执行：加载进程后，需要将用户进程的所有命令行参数压栈，实现需要在上述代码之后。在start_process()中有一个struct_intr_frame if_，这个结构体标识了用户进程的所有状态，其中的成员if_.esp是用户栈指针，在load()函数中为其赋值分配栈空间。调用strtok_r分离出一个个参数，把每个参数都复制到用户栈中，并把它在栈中的位置记录到一个数组arg中。栈向下增长。参数全部压栈完毕后，加入一个4位对齐，然后，将指针按照逆序放入栈中，放入argv的位置指针和argc，并让用户栈指针指向新的栈顶。Start_process()剩余部分如下：（2） 系统调用功能的分析、设计及实践过程在src/lib/syscall-nr.h中给出了所有系统调用的调用号在src/lib/user/syscall.h中给出了所有系统调用的形式（参数类型）。在src/userprog/syscall.h中声明这些系统调用处理函数，同时声明了CALL_PROC类型的pfn用于保存系统调用函数，将void 定义为