*** 作系统课程设计报告2021-2022——pintos_随笔

*** 作系统课程设计报告2021-2022——pintos *** 作系统课程设计报告 2021-2022

*** 作系统课程设计报告 2021-2022第一章实验项目介绍环境配置

（一）、 Ubuntu 服务器搭建

图形界面搭建（二）、 Pintos 系统配置（三）、 git环境搭建实验三线程管理

一、实验概述

1.Alarm Clock

算法: 数据结构

增加部分:需要的函数: 2.Priority Scheduling

算法: 数据结构

增加部分:需要的函数:修改部分: 3.Advanced Scheduler

算法: 数据结构

增加部分：需要的函数:修改部分: 二、实验内容

1. pintos 线程管理框架2. Alarm Clock

1 、任务描述2 、实验过程 3. Priority Scheduling

1 、任务描述2 、实验过程 4. Advanced Scheduler

1 、任务描述2 、实验过程错误点整理总结及展望

第一章实验项目介绍

本章是关于pintos的配置，结合了b站的视频与StackOverflow社区的问答教程

环境配置（一）、 Ubuntu 服务器搭建

我租的是阿里云的轻量级应用服务器，学生机很便宜，选用的是ubuntu18.04系统镜像

图形界面搭建

sudo su root
apt-get update    //更换软件源
apt install gnome-panel gnome-settings-daemon metacity nautilus gnome-terminal ubuntu-desktop    //安装桌面环境所需的软件包
apt-get install gcc
apt-get install g++
apt-get install libncurses5-dev    //git所需
apt-get install libx11-dev    //git所需
apt-get install libxrandr-dev    //git所需
apt-get install binutils
apt-get install perl
apt-get install make    //必备
apt-get install qemu    //qemu模拟器
apt-get install git    //gitlab配置所需
reboot    //重启

（二）、 Pintos 系统配置

Pintos配置教程如下

（三）、 git环境搭建

打开老师发的gitlab官网，进行账号的注册。
创建项目之后，将看到一系列关于添加SSH密钥和上传的说明。这些指令很重要，可以通过比较文档找到较小的错误。

在桌面新建了ljh文件夹用来放置pintos文件，以便上传，登录课程网站创建自己的项目，并在本地克隆它，因为它是空的，因此目录中没有任何东西。
找到你的本地项目路径，文件夹上右键—>git bash here,
输入命令：

git init

来初始化仓库，该项目的根目录下会自动创建.git的文件

接着输入：

git add .

将项目所有文件添加到缓存区

提交缓冲区：

git commit -m “备注信息”

将项目添加到远程仓库：

git remote add origin [email protected]:osd20f/chy.git

origin后面的路径为gitlab服务端创建的project的路径地址，可从服务器复制

将项目提交到远程仓库：

git push origin master

下一步是将本机SSH密钥添加到gitLab的用户设置中
具体教程源自gitlab官网
在Ubuntu中，输入以下命令生成SSH密钥，然后按Enter键，最后生成密钥。SSH密钥在.ssh文件夹。

ssh-keygen -t rsa -b 4096 -C "[email protected]"

使用以下命令将公共SSH密钥复制到剪贴板

pbcopy < ~/.ssh/id_ed25519.pub    //MacOS系统下

通过以下方式将您的公共SSH密钥添加到您的GitLab帐户：
单击右上角的头像，然后选择“设置”。
导航到SSH密钥，并将公钥粘贴到密钥字段中。
测试SSH密钥是否添加正确，在终端中运行以下命令

ssh -T [email protected]

接下来就可以开始进行实战 *** 作了。

实验三线程管理一、实验概述

任务1：Alarm Clock任务2：Priority Scheduling（优先级调度）任务3：Advanced Scheduler（多级反馈调度） 1.Alarm Clock 算法:

当调用timer_sleep时，线程被阻塞，ticks_blocked被添加到线程结构中，以跟踪线程被休眠了多长时间。然后使用 *** 作系统自己的时钟中断(每滴答执行一次)进行检查。每次检查Ticks_blocked都会减少1，如果减少到0，线程就会被唤醒。
原始的Timer_sleep函数的工作方式是这样的:首先，获得当前OS计时变量ticks作为开始时间，而timer_Elapsed将返回THEN之后的经过时间。确保在ticks时间内以及允许中断的情况下，如果线程不被允许执行，但它正在运行，它将被扔到就绪队列中，不再执行。
显然这是不合理的，线程仍然在CPU就绪队列和运行队列之间切换，消耗CPU资源，这不是我们想要的，我们想要一个唤醒机制来做这个。
添加一个新状态:Blocked。timer_sleep函数取消了休眠线程在就绪和运行状态之间来回切换的方式。修改函数直接阻塞线程，并添加ticks_blocked记录线程被阻塞的时间。

数据结构增加部分:

threads/thread:

int64_t ticks_blocked； //跟踪这个线程已经休眠了多长时间
void blocked_thread_check (struct thread *t, void *aux UNUSED);// 通过在thread.h中声明并在c文件中定义来检测线程是否被阻塞。

需要的函数:

void thread_foreach (thread_action_func *func, void *func);//对各个线程都执行的函数，需要用这个函数对各个线程执行。
void thread_block (void);// 设置当前运行的线程休眠。
void thread_unblock (struct thread *t);// 将参数thread放入就绪队列继续运行。
void timer_sleep (int64_t ticks);//取消之前休眠线程在ready和running状态之间反复切换的方式。 修改函数让线程直接阻塞，增加ticks_blocked记录线程阻塞的时间。

2.Priority Scheduling 算法:

查看线程的结构，我们发现在设计时已经添加了优先级作为优先级标记，将线程添加到就绪队列有三个 *** 作：thread_unblock、thread_yield和thread_init。
只要保证按队列优先级排序，从上面的thread_unblock函数中可以看出，当使用list_PUSH_back将其放入就绪队列时，会导致线程直接被添加到队列的末尾，也就是不是我想要的。
但是，当我查看 pintos 的队列结构和成员函数时，发现它内置了 list_insert_ordered 函数，可以直接将线程按一定的顺序插入队列中，使用这个可以确定规则和顺序功能。 List_push_back 是 list_insert_ordered，thread_cmp_priority 是从上到下。
测试线程thread1创建了一个优先级高于它的内核线程thread2，所以线程执行应该切换到thread2，让thread1阻塞。 Thread1 具有更高的优先级，thread2 阻塞，Thread1 将其优先级更改为高于 thread2。于是我们、再次执行thread2，输出thread1的MSG。
重新排列执行顺序，因为设置线程优先级不会重新考虑所有线程的执行顺序。解决方案是在线程设置为优先级时调用thread_yield。这会将当前线程放回就绪队列以继续执行，确保执行顺序。此外，在线程创建期间，如果新创建的线程的优先级高于主线程，则调用 thread_yield。

数据结构增加部分:

int base_priority;// 表示初始优先级。
struct list locks;// 线程持有的锁列表。
struct lock *lock_waiting;// 这个指针指向线程正在等待的锁。
struct list_elem elem;// 优先捐赠的线程列表项。
int max_priority;// 表示有锁的线程的最大优先级。
void thread_hold_the_lock(struct lock *lock)// 实现线程的优先捐赠。
void thread_donate_priority (struct thread *t)//捐赠优先级时授予锁。
bool thread_cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)//线程优先级比较函数。

需要的函数:

void thread_remove_lock (struct lock *lock)// 让线程释放锁的函数。
void thread_update_priority (struct thread *t)//更新线程的优先级函数。
bool lock_cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);//锁队列排序函数。
void list_insert_ordered(struct list *list, struct list_elem *elem,list_less_func *less, void *aux);//根据参数函数的规则，让插入线程队列的线程有一定的顺序，实现优先队列 。

修改部分:

static void init_thread(struct thread *, const char *name, int priority);//增加优先级调度时初始化代码。
void thread_set_priority(int new_priority)//根据优先级调度的逻辑修改优先级设置函数。
void lock_acquire (struct lock *lock)//在P *** 作之前递归实现优先捐赠，然后在被唤醒后成为锁的拥有者（此时线程已经拥有锁）。
void lock_release(struct lock *lock)//如果不是多级反馈调度，添加一条语句让线程释放锁。
void sema_up (struct semaphore *sema);
void sema_down (struct semaphore *sema);

3.Advanced Scheduler 算法:

多级反馈队列实现需要维护64个队列，每个队列的优先级从PRI_MIN到PRI_MAX不等。然后可以使用一些公式计算线程的当前优先级。当系统被调度时，将从高优先级队列中选择线程执行，该队列的优先级随着 *** 作系统的 *** 作数据动态变化。

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2).
recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice.
load_avg = (59/60)*load_avg + (1/60)*ready_threads.

利用这三个公式，可以计算出线程所属的队列等数据，并进行多级反馈调度。

数据结构增加部分：

typedef int fixed_t; // 用于多级反馈计算公式的浮点数。
诠释好;
fixed_t recent_cpu； // 正在运行的线程运行的次数 timer_tick。
fixed_t load_avg； // 浮点记录的全局变量。
void thread_mlfqs_increase_recent_cpu_by_one； // 将recent_CPU 添加到用于调度多级反馈的线程。
void thread_mlfqs_update_load_avg_and_recent_cpu； // 每单位时间更新所有进程的recent_CPU 和load_avg。
void thread_set_nice (int nice); // 将当前线程的 nice 值设置为系统 nice 值。
int thread_get_nice (void); //返回nice。
int thread_get_load_avg (void); // 返回平均系统负载的 100 倍。
int thread_get_recent_cpu (void); // 返回当前 timer_tick 计数的 100 倍。

需要的函数:

void thread_mlfqs_update_priority (struct thread *t); // 更新多级反馈队列中线程的优先级，在队列之间切换。

修改部分:

void thread_start (void);// 初始化 load_avg 值。
static void timer_interrupt (struct intr_frame *args UNUSED)
所有线程的系统load_AVg和recent_CPU每TIMER_FREQ时间更新一次，线程优先级每4个周期更新一次，运行线程的recent_CPU为 每个周期增加一。

二、实验内容 1. pintos 线程管理框架

Pintos的线程管理功能是在src的thread文件夹中实现的。在thread.h中定义了线程的结构，包括线程的状态、线程名称、线程的优先级等。其他一些文件是线程管理程序的基本 *** 作。，比如中断程序，io *** 作，以及互斥和同步信息等。
系统中的进程调度会导致忙等待问题，虽然系统中已经定义了优先级等数据结构成员，但是高级调度方法并没有实现。

2. Alarm Clock 1 、任务描述

通过改变devices中的定时器，取消忙等待，再通过阻塞线程的休眠并添加变量记录时间来实现定时器。

2 、实验过程

当调用timer_sleep时，线程被阻塞，Ticks_blocked被添加到线程结构中，以跟踪线程已经休眠了多长时间。然后使用 *** 作系统自己的时钟中断(每次一个滴答)来检查。每次检查Ticks_blocked时，它都会减少1，如果减少到0，线程就会被唤醒。

原来的timer_sleep函数的工作原理如下:首先，获取当前的OS计时变量ticks作为开始时间。Timer_Elapsed返回经过的时间。如果线程不允许执行但正在运行，它将被抛出到就绪队列中，并允许滴答时间和中断。不要让它执行。

显然，这是不合理的。线程还在CPU就绪队列和运行队列之间不断地来回切换，消耗CPU资源。这不是我们想要的。我们想用一种唤醒机制来做这件事。

具体实现思路如下：添加一个新状态:ticks_blocked成员首先被添加到线程结构中，以记录线程休眠了多长时间。当timer_sleep被调用时，线程直接被阻塞，并且 *** 作系统自己的时钟中断(每滴答执行一次)被用来检测线程状态。每次检测时，Ticks _blocked将减少1，当该值减少到0时，线程将被唤醒。

首先，成员变量ticks_blocked被添加到线程结构中，以记录进程何时被阻塞。在线程_create函数中，ticks_blocked在创建线程时被初始化为0。

在thread中添加blocked_thread_check方法，检查进程是否被阻塞。它在thread.h中声明，然后在c文件中定义。它用于每次检测减少1个滴答_blocked。当达到0时，线程被唤醒和阻塞 _thread_check使用thread_foreach对每个线程执行。线程_unblock被抛出到就绪队列中。

具体见代码文件。

3. Priority Scheduling 1 、任务描述

为线程实现优先级调度。当优先级高于当前运行线程的线程被添加到就绪列表时，当前线程应该立即将处理器分配给新线程。

原有的优先级更改的情况下面没有考虑到捐赠的情况，仅仅只是改变更改了当前线程的优先级，更别说恢复原本优先级了，所以不能通过任何有关捐赠的test。

原有的获得互斥锁和释放互斥锁的时候，仅仅是对信号量做一个简单的PV *** 作，获得互斥锁的时候应当考虑该锁当前是否被别的线程持有和优先级如何是否该被阻塞，释放互斥锁的时候也差不多同理，因此不能通过test。

原有的信号量 *** 作仅仅是简单的加减，没有考虑信号量在不同值的情况下阻塞和唤醒的情况设计，因此不能通过test。

信号量的等待队列理应设计为优先队列。
释放锁时应该运行发生优先级抢占行为。

重新设计优先级更改的情况

单独捐赠的情况：
当高优先级线程因为低优先级线程占用资源而阻塞时，应将低优先级线程的优先级提升到等待它所占有的资源的最高优先级线程的优先级。即将优先级较高的线程的优先级 donate 给持有资源的优先级的进程，让其先执行。

多重捐赠的情况：
struct thread 中的 list locks, 还有 struct locks 中的 lock_priority，两者配合使用,应对 multiple-donate 的情况。由于每次 donate 的时候都是因为优先级高的一个进程需要申请一个握在优先级比较低的线程手中的,因此锁在涉及到 priority-donate 的时候维护一个lock_priority,记录获得这个锁的线程此时的优先级,因为存在 multiple-donate,线程可能会接受几个不同的优先级,因此需要在锁中,而不是在线程的结构中维护这样一个信息,以在释放锁,undonate 的时候能够将线程优先级恢复到正确的值。

嵌套捐赠的情况：
通过检测被捐赠的线程是否已经获得了所需要的全部锁来判断是否出现嵌套捐赠的情况，如是则设置好参数来进行下一轮的优先级捐赠。和情况一差不多，也就是多捐赠一次，知道被捐赠线程获得了所需要的全部的锁。

2 、实验过程

检查线程的结构，发现在设计中添加了优先级作为优先级标记。将线程添加到就绪队列有三个 *** 作：thread_unblock、thread_yield 和 thread_init。

只要保证放入就绪队列时按优先顺序排列，从上图中的thread_unblock函数可以看出，放入时使用list_push_back函数就绪队列，这将导致线程被直接添加到队列的末尾。，这不是我们想要的。

但是在查看pintos的队列结构和成员函数的时候，发现它有自己的list_insert_ordered函数，可以直接按照一定的顺序将线程插入队列，并且可以通过函数确定规则和顺序，所以 list 将 _push_back 改为 list_insert_ordered 函数，然后按照优先级从大到小的规则实现比较函数thread_cmp_priority，这样就可以对thread_unblock的优先级调度达到。

同理，通过将thread_yield和thread_init中的list_push_back修改为list_insert_ordered函数，即可实现所有优先级调度。

但是在测试过程中，发现priority-change和priority-preempt任务无法通过。测试线程thread1创建了一个内核线程thread2，其优先级比它高，所以线程执行要切换到thread2，并让thread1阻塞，thread2执行时调用changeing_thread，将自己的优先级调整为比它低一个线程1。此时thread1的优先级较大，thread2被阻塞。然后 thread1 将其优先级更改为比 thread2 高 1，因此它再次执行。 thread2，最后输出thread1的msg。

由于设置线程优先级不会重新考虑所有线程的执行顺序，因此重新排列执行顺序。因此，测试样本中有失败提示。解决方法是在线程设置优先级时直接调用thread_yield。这样，当前线程被扔回就绪队列继续执行，保证了执行顺序。另外，在创建线程时，如果新创建的线程的优先级高于主线程，也应该调用thread_yield。

优先调度测试样本中也存在一些优先捐赠问题。当高优先级线程因为低优先级线程占用资源而阻塞时，应提高低优先级线程的优先级等待其占用的资源。最高优先级线程的优先级。即把优先级较高的线程的优先级捐赠给持有资源优先级的进程，让其先执行。

首先，在priority-donate-one测试例子中，original_thread所拥有的锁被acquire1获取后，由于acquire1线程阻塞在这个锁上，那么acquire1的执行必须继续由original_thread执行要释放锁，从优先级来看，应该将original_thread的优先级提升到acquire1的优先级，因为original_thread的执行本身就包含acquire1执行的阻塞，所以此时acquire1对 original_thread 进行了捐赠，并且提到的优先级 PRI _DEFAULT+1，acquire2 的行为类似。

实现的具体思路是，当一个线程获取锁时，如果拥有锁的线程的优先级低于自己，就会增加自己的优先级，然后在线程释放锁后，改变拥有锁的线程原本拥有的锁回来。原来的优先级。

其余5个测试样本问题也与优先捐赠有关。 priority-donte-multiple 的重点是 original_thread 的优先级变化。第一个输出是正常的，priority-donate-one 已经测试过这个逻辑。这里比较特别的是 original_thread 有两个锁，分别被两个线程 a 和 b 占用。 b释放后，original_thread的优先级恢复为32，即当前线程的优先级仍然由a的优先级捐赠，a释放后又恢复到原来的优先级。

priority-donte-multiple2和它类似，也是测试的是多锁情况下优先级逻辑的正确性。

值得一提的是，在多重捐赠的情况下，优先化逻辑的有效性。相应的实现思想是释放一个锁，将锁所有者更改为所捐赠线程的第二个优先级，如果没有其他捐赠线程，则恢复原来的优先级。可以使用一个新的数据结构来记录参与该线程的所有线程。

priority - donor -nest测试是一个优先级的嵌套问题。关键是Medium拥有的锁被Low阻塞了。在此前提下，如果High再次获得medium的锁定，优先级提升具有连锁效应，即medium被提升。此时，它锁定的低线程应该与它一起提升。线程可以添加一个数据结构来获取它锁定的线程。

priority - donor -sema混合了信号量和锁触发器，它们实际上是信号量，因为锁是由信号量生成的。优先级-捐赠-较低测试的逻辑是改变捐赠线程优先级时行为的正确性。priority -sema创建10个线程来阻塞P，然后使用一个称为V的循环来唤醒最高优先级的线程，也就是说，信号量队列是优先级队列。

优先级- condvar中的条件有一个等待队列，因此cond _WAIT和cond _Signal释放锁，等待信号唤醒，然后重新获得锁。该条件的waitqueue是一个优先队列。代码的逻辑是创建10个线程，在每个线程被调用时获取锁，然后调用cond_wait来释放锁，阻塞cond_signal来唤醒，然后循环cond_signal 10次。优先级-捐赠-链检验是一个优先级捐赠链，其本质是检验多层优先级捐赠逻辑的正确性。

4. Advanced Scheduler 1 、任务描述

实现多级反馈队列调度程序，以减少系统上运行作业的平均响应时间。64个队列被维护，每个队列的优先级从PRI_MIN到PRI_MAX。线程的当前优先级可以通过一些公式计算出来。在系统调度过程中，线程将从优先级高的队列中选择执行。线程的优先级将随着 *** 作系统运行数据的变化而动态变化。

在多级反馈队列调度器中，线程的优先级是通过下面的公式动态计算的：
priority = PRI_MAX - (recent_cpu/4) - (nice * 2)
recent_cpu = (2load_avg)/(2load_avg + 1)*recent_cpu + nice
load_avg= (59/60)*load_avg + (1/60)*ready_threads

priority即为线程的优先级，每4个timer tick，按上式计算一次。
nice为线程属性，取值[-20,+20]，越大表示该线程出让更多的CPU时间。
recent_cpu表示线程消耗的timer tick，每一次timer tick中断，该值加1，每一秒，recent_cpu按照上式计算一次。
load_avg表示过去的一分钟内处于就绪状态的线程数，初始值为0，每一秒按上式计算一次。
公式计算的过程中，需要小数的支持，而pintos不支持浮点数运算，所以我们需要实现定点小数的运算。

2 、实验过程

多级反馈队列实现需要维护64个队列，每个队列对应一个优先级，从PRI_MIN到PRI_MAX。然后通过一些公式计算来计算线程当前的优先级。系统调度时，会从高优先级队列中选择要执行的线程。这里，线程的优先级随着 *** 作系统的运行数据而动态变化。

在timer_interrupt中计算固定时间更新线程的优先级，这里是每隔TIMER_FREQ时间更新系统load_avg和所有线程的recent_cpu，每次timer_ticks更新线程优先级，每timer_tick后正在运行的线程的recent_cpu加一。虽然维护了64个优先级队列调度，但其本质是优先级调度，所以只需要对之前的优先级调度进行改进即可。

thread_tick()函数每个timer tick被调用一次，所以我们在其中完成：
当前线程recent_cpu++
每一秒，更新recent_cpu和load_avg
每4个ticks，更新所有线程的priority
需要注意的是，计算涉及浮点运算。 Pintos 本身不实现浮点运算。需要引入浮点运算库函数来实现。浮点算术逻辑在 fixed_point.h 中实现，使用 16 位数字。作为浮点数的小数部分，它始终保持从第 17 位开始的整数部分。

先实现timer_interrupt的逻辑，加上if判断，使用thread_mlfqs_increase_recent_cpu_by_one和thread_mlfqs_update函数增加线程的recent_cpu（个数最近对 cpu 的访问）。 _load_avg_and_recent_cpu 用于更新单位时间内所有进程的最近_cpu和load_avg，在thread.c中实现。

将thread_mlfqs_update_load_avg_and_recent_cpu函数中提到的thread_mlfqs_update_priority也写在thread.c中，该函数用于更新多个优先级队列类中的优先级。

线程结构添加了以下nice和recent_cpu数据成员，并在init_thread中初始化线程时初始化这两个新成员。
需要注意的是设置nice值后线程的优先级发生了改变，需要重新计算优先级并调度。

至此，threads全部27个测试通过。

错误点整理

每次建立新的仓库，提交的时总会出现这样的错误。Updates were rejected because the remote contains work that you do

错误的git 提交的步骤：

git init //初始化仓库
git add .(文件name) //添加文件到本地仓库
git commit -m “first commit” //添加文件描述信息
git remote add origin + 远程仓库地址 //链接远程仓库，创建主分支
git push -u origin master //把本地仓库的文件推送到远程仓库

这样就会出现问题：

remote:
remote:
remote:
remote: Internal API unreachable
remote:
remote:
remote:
fatal: Could not read from remote repository.

经过查资料发现是因为我们在本地新建库后，与远程仓库的内容不一致导致的。为此在我向远程库推送的时候，要先进行pull，让本地新建的库和远程库进行同步。
正确步骤：

git init //初始化仓库
git add .(文件name) //添加文件到本地仓库
git commit -m “first commit” //添加文件描述信息
git remote add origin + 远程仓库地址 //链接远程仓库，创建主分支
git pull origin master // 把本地仓库的变化连接到远程仓库主分支
git push -u origin master //把本地仓库的文件推送到远程仓库

git中failed to push some refs to git问题
可以通过以下方式解决
git pull --rebase origin master
执行后可以看到本地代码中多了README.md文件
再次执行git push origin master即可完成代码上传

总结及展望

由于对于自身有充分的认知，只完成了线程部分的课设，但也是在经过查阅了大量的资料与询问了众多的同学的情况下好不容易做完的。基本都是跟着教程做，不论是ubuntu的安装。
由于我是使用的M1芯片的Macbook，导致我的虚拟机无法使用pintos，发现这个问题就用了两天时间，之后迫不得已改用阿里云服务器，然后阿里云的服务器配置也花费了很多时间。再之后开始pintos的配置，跟着b站和csdn的教程顺利配置完成后。被未知的下一步困住了，不知道从何下手。后来找到了博客园的一篇教程（据我所知大部分同学也是参考的这一篇），慢慢地跟着做下去。并且做的过程中询问了大四的学长部分内容。花了几个时间也磕磕绊绊的做完了。到现在写报告的时候也是似懂非懂，大部分都是网上的资料，但至少不是一周前当初一点儿也不理解的我了。
本身对于 *** 作系统还是有一定热情的，希望在之后的学习中能渐渐把这些底层的东西搞懂！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5714723.html

*** 作系统课程设计报告2021-2022——pintos

发表评论

评论列表（0条）