课后练习
匿名2023/07/31 19:49:11提问
    lecture1lecture2lecture3lecture4
405

lec21-23

===============

1 完成Simple File System的功能,支持应用程序的一般文件操作。具体帮助和要求信息请看sfs-homework (https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab8/sfs-homework.md)

2 (不用提交)理解文件访问的执行过程,即在ucore运行过程中通过cprintf函数来完整地展现出来读一个文件在ucore中的整个执行过程。可自行编程实现。

3 (不用提交) ZFS、YAFFS这两种文件系统中选一种,分析它的文件卷结构、目录结构、文件分配方式,以及它的变种。

4 (不用提交)理解下列磁盘调度算法的工作原理,并能够用下列算法进行推演

    先进先出(FIFO)磁盘调度算法
    最短寻道时间优先(SSTF)磁盘调度算法
    扫描(SCAN)磁盘调度算法
    循环扫描(C-SCAN)磁盘调度算法
    C-LOOK磁盘调度算法
    N步扫描(N-step-SCAN)磁盘调度算法
    双队列扫描(FSCAN)磁盘调度算法

5 完成磁盘访问与磁盘寻道算法的作业,具体帮助和要求信息请看disksim指导信息(https://github.com/chyyuu/ucore_os_lab/blob/master/related_info/lab8/disksim-homework.md)和disksim参考代码(https://github.com/chyyuu/ucore_os_lab/blob/master/related_info/lab8/disksim-homework.py)

6 (不用提交)    磁盘缓存的作用是什么?
    请描述单缓存(Single Buffer Cache)的工作原理
    请描述双缓存(Double Buffer Cache)的工作原理
    请描述访问频率置换算法(Frequency-based Replacement)的基本原理

lec20

===============

1  用python实现银行家算法(https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab7/deadlock/bankers-homework.py)。大致输出可参考参考输出(https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab7/deadlock/example-output.txt)。除了YOUR CODE部分需要填写代码外,在算法的具体实现上,效率也不高,可进一步改进执行效率。

2  描述signal, pipe的实现机制,描述signal的三种处理方式。编写一个Linux app:父进程创建了3个子进程,3个子进程通过pipe机制给父进程分别发送了3个128Byte的数据,父进程在收到这3个数据后,通过signal机制分别通知子进程,子进程/OS分别用signal的三种处理方式来响应。

Linux的pipe, signal等相关编程/原理信息在网上有很多,下面是一些参考:
https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab7/ipc/signal-ex1.c
http://blog.csdn.net/vc0051127833/article/details/7658799
http://www.cnblogs.com/taobataoma/archive/2007/08/30/875743.html
https://www.hitoy.org/pipe-aplication-in-linux.html
http://ryanstutorials.net/linuxtutorial/piping.php

lec19

===============

请每人按时认真独立完成如下网页中的习题
https://github.com/chyyuu/os_course_exercises/blob/master/all/07-2-spoc-pv-problems.md

下面是列出的题号和要独立完成的学生名单。要求用C语言,基于semaphore和monitor两种方式实现同步互斥问题,并提供测试用例和README,说明你实现的设计和结果分析
一个可以参考的实现例子请看 https://github.com/chyyuu/os_tutorial_lab/tree/master/knowledge_points/semaphore-vs-monitor

lec18

===============

注意:下面的问题不需要提交,但需要认真理解和完成.

1. 信号量在ucore中的具体实现与课程上的原理实现的差别在哪里?请给出差异性分析
2. 信号量在实现软件同步和软件互斥上的一般使用模式(pattern)是什么?
3. 管程的组成包括哪几部分?入口队列和条件变量等待队列的作用是什么?
4. 请描述管程条件变量的三种释放处理方式的区别是什么?条件判断中while和if是如何影响释放处理中的顺序的?
5. 请理解管程和信号量在实现生产者-消费者问题上的差异。
6. 对于 https://github.com/chyyuu/os_course_exercises/blob/master/all/07-2-spoc-pv-problems.md 中的同步互斥问题,使用C++或python语言用信号量和管程两种手段分别实现。建议一个班的同学每人做两题,并组织讨论交流,这样班上同学可实现对这些问题的全覆盖。

lec17

===============

1  在报告中通过枚举和分类方法或反证法说明Peterson算法的正确性。

参考:
https://en.wikipedia.org/wiki/Peterson%27s_algorithm
https://en.wikipedia.org/wiki/Dekker%27s_algorithm

2  在报告中准确描述Eisenberg同步算法,并通过枚举和分类方法或反证法说明说明Eisenberg同步算法的正确性。用C或PYTHON实现Eisenberg同步算法和测试用例。在报告中给出测试结果简单描述。

参考:
https://en.wikipedia.org/wiki/Eisenberg_%26_McGuire_algorithm
https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
piazza.com的本课程网页中,搜索“Eisenberg”,可看到3个相关帖子集合

下面的练习不用提交,但请通过个人或同学间讨论等形式认真完成:
https://chyyuu.gitbooks.io/os_course_exercises/content/all/07-1-quiz.html
https://chyyuu.gitbooks.io/os_course_exercises/content/all/07-1-spoc-discussion.html 中的“17.4 基于软件的同步方法”小节中的4~12题。

lec16

===============

1  请描述stride调度算法的目标,思路和算法设计(要求写出伪代码),并分析stride调度算法只采用整数运算是如何避免stride计算溢出问题的。
1. (扩展,感兴趣的同学可试试)分析/理解/运行/测试 https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep10-lottery.md https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep10-lottery.py 写出你的实验过程和你对其设计实现的理解。尝试实现stride.py并给出实现说明  
 
2(不用提交) 理解一个操作系统调度的时机有哪些。
3(不用提交) 理解课堂讲述的调度算法哪些是可抢占的,哪些是不可抢占的。
4(不用提交) 理解课堂讲述的调度算法哪些是动态调度算法,哪些是静态调度算法。
5(不用提交) 思考如何实现MLFQ?特别是如何动态调整进程优先级?
6(不用提交) FIFO调度算法的实现是否需要中断机制?其他调度算法呢?
7(不用提交) 理解在存在两个用户进程的情况下,ucore的调度时机和进程切换的完整过程
8(不用提交) 理解实时操作系统的特征,实时调度算法的基本思路,特点
9(不用提交) 理解优先级反置问题和解决方法。火星探路者碰到的类似问题是啥?如何发现和解决的?
10(不用提交)  理解ucore调度算法支撑框架的执行过程
11(不用提交) 理解SMP,AMP, MC的含义与区别

lec15

===============

1 请证明短进程优先算法具有最小平均周转时间。
 
2(不用提交) 通过观察FIFO、SJF和RR调度算法的模拟程序(https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep8-scheduler.py)运行结果及其描述文档(https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep8-scheduler.md),理解其工作原理和算法特征。

3(不用提交) 通过观察MLFQ调度算法的模拟程序(https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep9-mlfq.py)运行结果及其描述文档(https://github.com/chyyuu/os_tutorial_lab/blob/master/ostep/ostep9-mlfq.md),理解其工作原理和算法特征。

lec13&14

===============

https://github.com/chyyuu/os_course_exercises/blob/master/all/05-4-lab5-spoc-discussion.md
中的小组练习与思考题 第二题
(2)(spoc) 理解用户进程的生命周期。
需写练习报告和简单编码,完成后放到网络学堂
要求提供代码和报告

lec12

=============

1(不用回答)理解 孤儿进程和僵死进程的含义
http://www.cnblogs.com/xiehongfeng100/p/4619913.html
http://www.cnblogs.com/Anker/p/3271773.html
https://piazza.com/class/i5j09fnsl7k5x0?cid=753

2(不用回答)理解ucore进程控制块proc_struct数据结构内容和大致含义

3(不用回答)理解fork和execv的实现机制

4(不用回答)理解COW的实现机制
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601655.html

5 请仔细阅读https://chyyuu.gitbooks.io/os_course_exercises/content/all/05-2-spoc-discussion.html 中的小组思考题

设计一个简化的进程管理子系统,可以管理并调度如下简化进程.给出了参考代码(https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab5/process-cpuio-homework.py),请理解代码,并完成"YOUR CODE"部分的内容.

lec10&11

=============

1 以lab3为例,说明虚拟页与磁盘后备页面的对应关系是什么?
2 (不用回答)以lab4为例,理解保存现场和恢复现场: lab4/kern/process/switch.S
3 (不用回答)理解进程的各种状态和各种状态间的转换的起因。
4 由于何种原因,可出现进程的何种状态转到退出状态?
5 请设计一个简化的进程管理子系统,可以管理并调度如下简化进程.给出了参考代码(https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab4/process-concept-homework.py),请理解代码,并完成"YOUR CODE"部分的内容。
6 (不用回答)请了解实际操作系统Linux的各种状态和各种状态间的转换的起因。
7 (不用回答)请了解实际操作系统Linux的进程控制块PCB数据结构 task_struct

lec9

=============

1. 物理页帧数量为3,且初始时没有对应的虚拟页。虚拟页访问序列为 0,1,2,0,1,3,0,3,1,0,3,请问采用最优置换算法的缺页次数为()

2. 物理页帧数量为3,且初始时没有对应的虚拟页。虚拟页访问序列为 0,1,2,0,1,3,0,3,1,0,3,请问采用FIFO置换算法的缺页次数为()

3.物理页帧数量为4,且初始时没有对应的虚拟页。虚拟页访问序列为 0,3,2,0,1,3,4,3,1,0,3,2,1,3,4 ,请问采用CLOCK置换算法(用1个bit表示存在时间)的缺页次数为()

4. 物理页帧数量为4,且初始时没有对应的虚拟页。虚拟页访问序列为 0,3,2,0,1,3,4,3,1,0,3,2,1,3,4 ,请问采用CLOCK置换算法(用2个关联,bit表示存在时间,可以表示4,)的缺页次数为()

https://github.com/chyyuu/os_course_exercises/blob/master/all/04-2-spoc-discussion.md#小组思考题目
的第一和第二道题目

5.(spoc)根据你的学号 mod 4的结果值,确定选择四种页面置换算法(0:LRU置换算法,1:改进的clock 页置换算法,2:工作集页置换算法,3:缺页率置换算法)中的一种来设计一个应用程序(可基于python, ruby, C, C++,LISP等)模拟实现,并给出测试用例和测试结果。请参考如python代码或独自实现。

页置换算法实现的参考实例 ( https://github.com/chyyuu/ucore_lab/blob/master/related_info/lab3/page-replacement-policy.py )

6. 请判断OPT、LRU、FIFO、Clock和LFU等各页面置换算法是否存在Belady现象?如果存在,给出实例;如果不存在,给出证明。

lec8

=============
04-1-spoc-discussion.md
的个人思考题,小组思考题(1)(2)(3)

回答(0
    推荐问答
      Simple Empty
      暂无数据