《pitos参考资料.pdf》由会员分享，可在线阅读，更多相关《pitos参考资料.pdf（21页珍藏版）》请在金锄头文库上搜索。
1、OSOS 实践项目实践项目 1 1 设计与实现文档设计与实现文档 4p小组 10年11月11日 内容目录 1 小组人员组成与分工 1 1 1 小组成员 1 1 2 任务分工 1 1 3 版本控制 1 2 额外的参考资料 1 3 睡眠和唤醒 1 3 1 需求分析 1 3 2 数据结构 2 3 3 算法设计 3 3 4 调试 4 3 5 优化 5 3 6 题目完成程度 5 4 优先级调度 5 4 1 需求分析 5 4 2 数据结构 6 4 3 算法 7 4 4 解法描述 8 4 5 调试过程 11 4 6 题目完成程度 11 5 高级调度 11 5 1 需求分析 11 5 2 设计思想 11 5
2、3 数据结构 12 5 4 算法设计与函数实现 13 5 5 调试过程 16 5 6 题目完成程度 16 1小组人员组成与分工 1 1 小组人员组成与分工 1 1 小组成员 4p小组由4名08cs成员组成 列表如下 陈歌 C 李梦阳 L 王盛 W 肖天骏 X 开发代号是每人姓氏的首字母 1 2 任务分工 任务分工由一系列表格组成 并且有较强的松散自由度 日期内容人员结果 11 3实验环境搭建CLWX0 11 5阅读源码 理解调用关系CLWX0 11 7写完第一题代码CW延期11 9 11 9部署版本控制L完成 11 10完成代码提交和检查WL完成 11 13完成第二题代码L延期11 15 11
3、 16完成第三题代码X 11 17合并代码 提交版本LWX 11 18文档清理上传CLWX 11 19文档合并CL 1 3 版本控制 由于多人同时贡献代码 所以决定在项目中采用版本控制 代码托管于googlecode 采用SVN进行控制 可以在以下页面找到项目信息 2 额外的参考资料 在作业完成的过程中除了压缩包中的资料 还参考了 pintos 官方文档 http www scs stanford edu 10wics140 pintos minix3 源码 http www minix3 org source html 3 睡眠和唤醒 这一部分主要由LXW构思 W实现 L做出测试提出修改意见
4、 3睡眠和唤醒 2 3 1 需求分析 既有的线程挂起机制 通过在timer sleep 中执行while 循环实现 当前时间若不满足挂起的时 间要求 则调用thread yield 函数继续循环 如果满足则直接压紧就绪队列 实际上只存在两个态 Running和Ready 并没有真正意义上的睡眠与唤醒 如图 由于在while 循环中 不断的进行thread yield 操作 通过查看源代码中thread yield 函数 的注释 Yields the CPU The current thread is not put to sleep and may be scheduled again imm
5、ediately at the scheduler s whim 这也验证上面所说的线程并没有真正进入睡眠 且该线程有可能又一次立即被调度 这样的结果就是产 生了忙等待 我们需要实现的目标为 在timer sleep 函数中使线程进入Block态 系统运行一段时间后 睡眠 时间到 再对该线程进行唤醒 从Block态转入Ready态 改造后的机制为如图 3 2 数据结构 虽然在thread h 文件中的enum thread statues 已经提供了thread block 态 而且已 经存在ready list的链表 但中在源码中 并不存在一个叫做block list的list结构 故添加了
6、数据结构 static struct list block list 插图 1 睡眠与唤醒 插图 2 3态 3睡眠和唤醒 3 用于存储处于block态的thread 有了block list 就可以用来存储处于Block态的线程 而睡眠是有时间限制的 当睡眠时间到 之后 则应进行唤醒操作 但在struct thread 结构中 没有相关的变量来记录睡眠的时间 故在struct thread 进行改造 添加 int64 t wakeup ticks 用以记录执行唤醒操作的时间 当前时间大于某个线程的wakeup ticks时 应对线程唤醒 3 3 算法设计 现有的timer sleep 函数中
7、在while 循环中直接调用了thread yield 要避免忙等待 需使线程进入睡眠 睡眠之后紧跟的问题便是 如何来唤醒thread 更进一步的是何时来唤醒 仔细分析知 进入睡眠应该是在timer sleep 中实现 而进行唤醒的时间乍看之下似乎存在着不止一种选择 1 在每个tick之后 检查block list 当前时间大于wakeup ticks则进行唤醒 2 在有某个线程要释放cpu时进行唤醒 若在每个tick之后都进行唤醒检查block list 有可能出现所有的处于Block态的线程睡眠都没有 结束的情况 即使某些线程睡眠结束 进行了唤醒 若不进行调度 唤醒后的线程也没有机会转入
8、Running态 这样的效率过低 所以我们选择在进行线程调度之前检查block list 进行唤醒操作 在具体实现中 thread c中 thread sleep 函数使线程进入Block态 thread wakeup 函数检查block list 进行唤醒 归纳如下 插图 3 流程 3睡眠和唤醒 4 3 4 调试 在代码执行的过程中 当系统运行出错时 缺少必要的提示信息 这样就造成了调试时不便 为了进行调 试同时也为了弄清代码的执行过程 在调试阶段我们加入相当多的printf 语句 整个过程的具体步骤 如图所示 调试中遇到 插图 5 printf1 插图 6 printf2 3睡眠和唤醒 5
9、 的问题 在thread sleep 中实现对线程的阻塞后 继续进行检查block list 然后调用schedule 进行 线程调度 而忽略了一点 并不是只有在thread sleep 才调用schedule 进行调度 在 thread yield 中调用了schedule 函数 而我们没有在thread yield 函数中后检查 block list 进行唤醒 问题的解决就是在thread yield 中添加检查block list 进行唤醒的代码 对idle thread的理解 The idle thread is initially put on the ready list by t
10、hread start It will be scheduled once initially at which point it initializes idle thread up s the semaphore passed to it to enable thread start to continue and immediately blocks After that the idle thread never appears in the ready list It is returned by next thread to run as a special case when t
11、he ready list is empty idle thread只是在最初进入一次ready list 以后idle thread并不会出现在ready list中 起 初把它当作普通线程对待 在thread c文件中thread tick 中 如果当前线程为idle thread 执 行的操作仅仅为idle ticks 错误的对它进行改写为 idle ticks wakeup ticks时 执行唤 醒 事实上idle thread在thread start 之后根本不会进入ready list 自然也不会有睡眠与唤 醒这样的操作 3 5 优化 从最初正确可运行的代码到最终成型的代码 共进
12、行了两点优化 起初采用了thread block start与thread block ticks分别记录开始进入block态的时间 和thread处于block的时间 当时间运行到大于等于 thread block start thread block ticks即应该进行唤醒 所以此问题 可以直接简化为用 wakeup tick解决 减少一个变量 起初在每次thread从Running态进入Block态的时候 直接用执行入队列操作 插入到 block list的最后位置 而当唤醒的时候 每次又都要遍历block list 这样操作时间开销要大很多 若block list中的是按wakeup
13、 ticks 进行排列的 那么在唤醒操作的时候 则不需要每次都进行 遍历 当检查到某一线程的wakeup tick不满足唤醒条件时 则不继续对后续Block态的线程进行 检查 进行从而达到减少时间开销的目的 3 6 题目完成程度 pass tests threads mlfqs block pass tests threads alarm single pass tests threads alarm multiple pass tests threads alarm simultaneous FAIL tests threads alarm priority pass tests threa
14、ds alarm zero pass tests threads alarm negative 这里的FAIL是因为这里代码只有睡眠唤醒机制 带有优先级的唤醒机制将在第二题里实现 4优先级调度 6 4 优先级调度 这一部分主要由L构思 L实现 X测试并提出修改意见 4 1 需求分析 优先级调度要求实现一个基于优先级的调度策略 包括解决优先级授予和其他授予时的相关问题 优先级翻转描述如下 线程A B C 分别具有1 2 3 的优先级 数字越大说明优先级越高 线程A B 目前在就绪队列中等待调 度 线程A 对一个互斥资源拥有线程锁 而此时 高优先级的线程C 也想要访问这个互斥资源 线程C 只 好在
15、这个资源上等待 不能进入就绪队列 当调度器开始调度时 它只能从A 和B 中进行选择 根据优先 级调度原理 线程B 将会首先运行 这时就产生了一个问题 即本来线程C 的优先级比线程B 高 但是线程B 却先运行了 从而产生了优先级 翻转问题 4 2 数据结构 Synch h中添加 修改 锁本身 在原来锁的基础上添加了一个id 这个值用来区别各个锁 类似于tid struct lock L add an lid to identifer the lock int lid struct thread holder Thread holding lock for debugging struct sem
16、aphore semaphore Binary semaphore controlling access 锁链表的一个元素 这个链表保存着所有的可能引发donate 的锁 struct lock elem L lock id int lid struct lock lock This lock struct list elem elem List element 插图 7 优先级翻转 4优先级调度 7 锁列表的变量 struct list lock list threah h中添加 修改 struct thread int priority Priority int priority old L old priority stores the pri before donated struct list elem allelem List element for all threads list Owned by thread c unsigned magic Detects stack overflow 4 3 算法 上面的数据结构依赖于以下的函数实现 这里没有给出他们的代码 不过后
