2019操作系统课程设计:OS算法分析及Hyper-OS实现

在本页面维护操作系统课程设计大实验"xxxx"的相关信息。老师、助教和选做课程设计的同学可修改该页面的内容。

课程设计目标:

  1. 阅读论文,了解比较新的内存分配算法研究,在模拟环境下实现一些算法并测试性能
  2. 通过已有算法的结合和改进,提出一些优化策略
  3. 在ucore或rcore上实现上面学习或提出的算法
  4. (未定)在rcore上利用真实应用对算法性能进行分析

实验参与者信息

姓名

学号

电子邮箱

GitHub 账户

杨天祺

tqyangoi1@gmai.com

tqyaaaaang

李嘉图

ljt12138@qq.com

ljt12138

算法分析相关实验代码仓库:

Hyper-OS 实验仓库:

13周实验报告:

16周实验报告:

已有工作参考

其它已有工作依赖

实验分工

杨天祺:

李嘉图:

日志 第1-4周

学习了mooc课程,并完成了ucorelab 1-8

下面用ljt12138代指李嘉图,用tqyaaaaang代指杨天祺

日志 第5周

ljt12138:主要工作是编写测试环境、进行简单测试

[Repo] 页面置换相关内容在仓库https://github.com/os-algorithm/page-replacement-simulator 中

[Code] 完成了一个简单的页面置换算法模拟框架 。实现了OPT算法、随机置换算法、FIFO算法、LRU算法和带写标记的CLOCK算法;可以从文件中读取访存序列,或生成随机序列测试算法。

[Code] 使用随机数据测试了缺页率和物理页面数的关系。已得到一些数据,但还未分析。预计于第七周研究全局页面置换时分析。

[Paper] 大致阅读了[1]中Belady的早期研究,但未精读。

[Docs] 阅读了网上的一些资料,完成了调研报告中关于确定性算法竞争比的分析。调研报告在 https://github.com/os-algorithm/page-replacement-simulator/blob/dev/docs/page_replacement.pdf 。主要工作是证明了两个引理:

  1. 任何确定性算法不会优于k-Competitive
  2. 任何标记算法是k-Competitive的

LRU是k-Competitive的可以看作2的推论。

tqyaaaaang:主要工作是查阅了 Slab Allocator 相关文献

[Paper] 精读了 Jeff Bonwick 关于 Slab Allocator 的论文 [6]

[Code] 完成了个简单了连续内存分配的框架,但暂未向其中添入内存分配算法

日志 第6周

ljt12138: 主要工作是了解随机置换算法和竞争性分析

[Paper] 阅读了 wikipedia 中页面置换算法的资料,其中关于标记算法和随机标记算法的描述含糊且缺乏引用,查阅了其他资料。其中不错的有:

[Paper] 阅读了[2]中关于随机标记算法的工作。论文中直接研究了页面置换问题的一个超集:k-server问题,并说明了随机标记算法在k-server问题上是2logk-Competitive的,从而页面置换问题上随机标记算法也是2logk-Competitive的。同时说明了任何随机置换策略的竞争比的下界是logk-Competitive,从而说明了随机标记算法的“最优性”。

[Docs] 完成了调研报告中随机标记算法的部分,整理了[2]中的证明并补完了一些不清晰的细节。

[Code] 实现了一个方便直接编码测试的库,现在可以直接不需要生成trace,直接编写访存代码来测试竞争比了。

tqyaaaaang:主要工作是研究了 Belady 在 1966 年参考文献 [1] 中提出的关于页面置换算法的 MIN 算法

[Paper] 阅读了 Belady 在 1966 年关于页面置换算法的论文,主要关注其中的最优算法 MIN 算法,由于论文中的表述不清楚,图和解释不符合,因此无法得到准确的算法描述

[Code] 尝试在 ljt12138 的框架中实现 MIN 算法

日志 第7周

ljt12138: 主要工作是了解几种程序访存模型,并完成设计报告。

[Docs] 补充了调研报告中关于竞争比下界的证明。主要思路是使用Yao's Minimax Principle,构造某种随机访存序列的分布,使得任何确定性算法的期望却也次数都达到1/2log(k+1)。这个漂亮的证明思路来自[5]的最后部分。

[Paper] 阅读了综述 Albers S, Leonardi S. On-line algorithms[J]. ACM Computing Surveys, 1999, 31(3). 和页面置换有关的部分。从中了解了[5]中基于访存图的分析;计划阅读[4], [5]。

[Docs] 完成了设计报告。

tqyaaaaang:主要工作集中在连续内存分配的最优算法

[Proof] 尝试证明连续内存分配的离线情况是 NP-Hard 的,提出了一个基于构造的证明方法。

[Code] 采用程序验证确认了上述证明的正确性

[Paper] 大致阅读了 J. M. Robson 的证明连续内存分配的离线情况是 NP-Hard 的论文 [7],但论文中给出的证明方法不如我们提出的基于构造的方法简洁

[Paper] 大致了解了离线情况的近似算法 [8] [9],存在可被证明较优的近似算法

[Docs] 大致完成对连续内存分配算法调研的报告 https://github.com/os-algorithm/memory-allocation/blob/dev/docs/report.pdf

[Paper] 了解 Linux Kernel 中的 zram、zswap 和 zcache,以及它们所需要使用的 zbud、zsmalloc等,查阅了 zswap、zsmalloc 对应 commit 的 mailing list

[Paper] 查阅 Linux Kernel Documentation 中对 zsmalloc 的介绍

[Docs] 完成设计报告

日志 第9~10周

考虑到对 OS 的分析缺少较好的模拟环境,在陈渝老师的建议下,将实验方向转向对 OS 的模拟环境的设计和实现。

完成 Hyper-OS 的思路设计,代码仓库:https://github.com/tqyaaaaang/Hyper-OS/ ,主要工作在 dev 分支完成。

tqyaaaaang:主要完成了 Hyper-OS 中的中断相关工作

ljt12138:主要完成了 Hyper-OS 中物理内存管理的相关工作

日志 第11-12周

tqyaaaaang:主要完成了Hyper-OS的中断机制和外部设备

ljt12138:主要完成了Hyper-OS的Kernel和应用程序格式

日志 第13周

[踩坑记录]:中断不规范,进程两行泪。

[情况]:在实现shell程序时,在shell中继续执行shell出现出错,大致逻辑如下:

然而时而出现多个进程同时执行,时而出现子进程等待而父进程继续运行。

[调试过程]:

  1. 将时钟中断调为5s一次,不再出现错误;调为1s一次,错误率显著低于默认(200ms一次)。
  2. 修改了系统调用等待的逻辑,解决了潜在的竞争问题,未果。
  3. 阅读log,发现wait时而停止了父进程,时而停止了子进程

[问题原因]:未设置中断优先级,从而以下情况可能出现:

  1. 进程A创建了进程B
  2. 进程A发出wait系统调用,但由于还有时钟中断在队列中,系统调用未被立刻执行
  3. 时钟中断处理中,A的时间片用完,切换到进程B
  4. B开始执行,堆在队列中的系统调用执行,B“被”休眠了。

[解决方案]

[关键提交]:

[问题后续]:

在进行如上处理后,又出现了多个shell同时输出信息,即有一个shell在系统调用后没有停下来,并且系统调用又让另一个shell跑了起来

[问题原因]:

由于需要判断是否在一个内部中断的时候将当且用户进程阻塞,为每个CPU core记录了一个当且中断处理例程栈的深度,但是这个深度是在释放了CPU的锁之后才修改。这样可能导致如下问题:

在某一个外部中断(比如时钟中断)处理到释放CPU锁和修改栈深之间时,第一个shell发出系统调用 CreateProcess,创建第二个shell。

但由于当前有一个时钟中断未处理完,中断栈深度依然是1,因此这个系统调用不会将自己阻塞,第一个shell继续执行。而会有第二个shell在系统调用中被创建,因此会出现两个shell同时运行的情况

[解决方案]:

将修改栈深的操作用CPU锁保护,则一定会在第一个shell执行系统调用(运行需要CPU锁)之前将栈深修改到合适的值。

[关键提交]:

日志 第14-16周

主要完善了用户体验:

OS2019spring/projects/g10 (last edited 2019-06-18 09:02:20 by 杨天祺)

MoinMoin Appliance - Powered by TurnKey Linux