2013操作系统实验指导书

操作系统 实验指导书 适用专业 计算机科学与技术 网络工程 软件工程 太原科技大学计算机科学与技术学院 2013年 3 月 前前 言言 操作系统是计算机的核心和灵魂 操作系统软件的设计对整个计算机的功能和性能起着 至关重要的作用 所以此门课也是必不可少的 是面向计算机科学与技术 网络工程 软件 工程等大多数计算机专业本科生开设的一门计算机专业课程 操作系统是计算机系统的核心 操作系统 课程是计算机科学与技术专业的重要必修 课 本课程的目的是使学生掌握现代计算机操作系统的基本原理 基本设计方法及实现技术 具有分析现行操作系统和设计 开发实际操作系统的基本能力 操作系统实验是操作系统课程的重要组成部分 属于学科基础实验范畴 作为与相关教 学内容配合的实践性教学环节 应在操作系统理论课教学过程中开设 操作系统是计算机科学与技术专业必修的专业基础课程 操作系统实验的作用是 理解 操作系统的设计和实现思路 掌握典型算法 基本要求是 理解进程的概念 理解死锁 掌 握银行家算法 掌握请求页式存储管理的实现原理及页面置换算法 学生应具有高级语言编 程能力 具有数据结构等基础知识 目目 录录 实验一 windows 进程的创建 1 实验二 windows 并发多线程的应用 4 实验三 P V 操作的模拟实现 7 实验四 银行家算法模拟 13 实验五 虚拟存储管理中页面置换算法模拟 16 1 实验一实验一 windows 进程的创建进程的创建 实验学时 2 实验类型 验证 实验要求 必修 一 实验目的一 实验目的 本课题实习的目的是 加深对 wiundows 进程概念及进程管理各部分内容的理解 熟悉 windows 进程管理 API 的使用 二 实验要求二 实验要求 1 将源程序编译 链接后形成 master exe 和 slave exe 文件 2 在命令行方式下输入 master slave 回车 将在 master 进程中创建 slave 进程 观 察程序运行的结果 3 自己设计一个小程序 完成在 master 进程中启动该程序的操作 4 撰写上机报告 三 实验内容三 实验内容 下面程序是两个简单的控制台应用程序 第一个程序 MASTER 运行第二个程序 SLAVE 并进入睡眠 SLAVE 程序从命令行读取 MASTER 程序的进程 ID PID 并等 待 MASTER 程序终止之后 SLAVE 做了一些事情之后 也结束 这些程序用到了以下几 个重要技术 1 使用 CreateProcess CreateProcess 函数 函数原型 BOOL CreateProcess LPCTSTR lpApplicationName LPTSTR lpCommandLine LPSECURITY ATTRIBUTES lpProcessAttributes LPSECURITY ATTRIBUTES lpThreadAttributes BOOL bInheritHandles DWORD dwCreationFlags LPVOID lpEnvironment LPCTSTR lpCurrentDirectory LPSTARTUPINFO lpStartupInfo LPPROCESS INFORMATION lpProcessInformation 参数 lpApplicationName 指向一个以空结尾的串 他指定了要执行的模块 lpCommandLine 指向一个以空结尾的串 该串定义了要执行的命令行 lpProcessAttributes 指向一个 SECURITY ATTRIBUTES 结构 该结构决定了返回的句柄 是否可被子进程继承 lpThreadAttributes 指向一个 SECURITY ATTRIBUTES 结构 该结构决定了返回的句柄 是否可被子进程继承 2 bInheritHandles 表明新进程是否从调用进程继承句柄 dwCreationFlags 定义控制优先类和进程创建的附加标志 lpEnvironment 指向一个新进程的环境块 lpCurrentDirectory 指向一个以空结尾的串 该串定义了子进程的当前驱动器和当前目录 lpStartupInfo 指向一个 STARTUPINFO 结构 该结构定义了新进程的主窗口将如何显示 lpProcessInformation 指向 PROCESS INFORMATION 结构 该结构接受关于新进程的表 示信息 返回值 若函数调用成功 则返回值不为 0 若函数调用失败 返回值为 0 在上述参数中 参数 lpStartupInfo 是 STARTUPINFO 结构 可以用来设置控台的标题 新 窗口的的初始大小和位置 及重定向标准输入和输出 新程序通常可以忽略多数这些数据项 如果选择那样做的话 可以规定该结构体中的标志 已表明要设置的数据段 有时 不想设 置任何信息 也必须传递一个有效的指针给空结构 确定设置大小到 cb 及设置 dwFlags 成员为 0 参数 lpProcessInformation 返回进程和线程句柄 还包括进程和线程 ID 这 些句柄拥有在参数 lpProcessAttributes 和 lpThreadAttributes 中规定的访问 要注意 针对 CreateProcess 的一些参数对控制台应用程序是特定的 而其它参数则对各种 应用程序有用 大多数情况下 并不一定要填入 STARTUPINFO 结构 但无论如何必须提 供它 其返回值是布尔型的 而真正感兴趣的返回值发生于作为参数传送的结构中 PROCESS INFORMATION CreateProcess 返回该结构中的进程 ID 及其句柄 以及初 始线程 ID 及其句柄 可以将 ID 发送到其它进程 或使用句柄来控制新进程 2 使用 WaitForSingleObject WaitForSingleObject 的目的是要确定句柄是否处于发送信号的状态 当进程结束时 进程句 柄发出信号 当调用 WaitForSingleObject 时 就规定进程句柄和超时值 如果超时为 0 则该命令就立刻返回 且能够确定进程的状态 如果超时是常数 INFINITE 则命令就不返 回 直到目标进程退出为止 当然 还可以规定超时值 其导致该命令等待要结束的进程一 段时间 如果进程在超时届满前结束 该命令就返回 并指出句柄在发射信号状态 否则 就返回一个负值 不管句柄在何种状态 WaitForSingleObject 将成功返回 没有错误发生 要确定进程的状态 就必须比较返回值为 WAIT OBJECT 0 已发信号的 和 WAIT TIMEOUT 未发信号的 真正的错误返回值为 WAIT FAILED 另外可能的返回 值是 WAIT ABANDONED 是不会看到何时处理进程 要等待一个进程 就必须带有 SYNCHRONIZE 特权的打开局柄 这里要注意 进程 ID 与进程句柄不同 不能简单地在进程之间传送句柄 这意味着除非有 句柄 否则不能从外部进程直接操纵一个进程 不过 OpenProcess 命令将允许任何程序 有 足够的安全特权 将进程标示符 可以用来于其它进程通信 变换为进程句柄 通过调用 GetCurrentProcessId 还可以了解当前进程标示符 如果要想与其他无关的进程共享 以使 能够打开进程句柄 这是非常有用的 但调用 OpenProcess 时 可以请求对进程的访问 对 每种进程的访问 也许有或也许没有访问要打开进程的安全性 于是试图请求是仅仅需要的 例如 如果要了解进程的返回代码 就需要 PROCESS QUERY INFORMATION 的访问 要终止进程 就必须有 PROCESS TERMINATE 的访问 3 3 源程序清单 master cpp include include include include void main int argc char argv char cmd 128 if argc 1 strcpy cmd argv 1 else strcpy cmd slave exe int pid GetCurrentProcessId cout process ID pid endl cout Master 准备启动 cmd n sprintf cmd strlen cmd d pid cout flush STARTUPINFO info memset info cb sizeof info PROCESS INFORMATION pinfo if CreateProcess NULL cmd NULL NULL FALSE NORMAL PRIORITY CLASS NULL NULL cout Master 重新输入从进程名 n cout Master 睡觉去喽 n cout flush Sleep 10000 for int i 1 i 5 i cout 睡醒了 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n cout Master 刷牙 洗脸 吃饭 n cout Master 结束 n exit 0 slave cpp include include include 4 void main int argc char argv if argc 2 cout Slave 请重新运行 MASTER EXE n exit 1 int pid atoi argv 1 HANDLE process OpenProcess PROCESS QUERY INFORMATION SYNCHRONIZE FALSE pid if process cout Slave Error opening process n cout Slave 我要等 Master 起床 n cout flush if WaitForSingleObject process INFINITE WAIT OBJECT 0 cout Slave Master 结束了 该我玩了 n else cout Slave 出什么错了 n for int i 1 i 5 i cout i 我好高兴好高兴 n cout Slave 我也该结束了 拜拜 n exit 0 实验二实验二 windows 并发多线程的应用并发多线程的应用 实验学时 4 实验类型 设计 实验要求 必修 1 实验目的实验目的 本课题实习的目的是 加深对 wiundows 线程概念及线程同步管理各部分内容的理解 熟悉 windows 线程管理 API 的使用 二 实验要求二 实验要求 1 通过上网查阅资料 了解 windows 线程同步函数 写出本程序中出现的 API 函数的定义 2 阅读案例程序 给出程序的详细注解 3 运行程序 分析程序结果 4 改写程序实现 至少选其中两个项目实现 1 苹果桔子问题 5 桌上有一只盘子 每次只能放入一只水果 爸爸专向盘子中放苹果 apple 妈妈专向盘 子中放桔于 orange 一个儿子专等吃盘子中的桔子 一个女儿专等吃盘子里的苹果 2 在一个盒子里混装了数量相等的黑白围棋子 现在用自动分拣系统把黑白子分开 设 分拣系统有两个线程 P1 P2 其中 P1 拣白子 P2 拣黑子 当一个线程在拣时 不允许另 一个线程去拣 当一个线程拣了一子后 必须让另一线程去拣 试写出两个线程能并发正确 执行的程序 3 设有线程 A B C 分别调用过程 get copy 和 put 对缓冲区 S 和 T 进行操作 其中 get 负责把数据块输入缓冲区 S copy 负责从 S 中提取数据块并复制到缓冲区 T 中 put 负责 从缓冲区 T 中取出信息打印 如图所示 编程序实现 get copy 和 put 并发的操作过程 4 编程序实现生产者 消费者问题 5 撰写上机报告 3 实验内容实验内容 苹果香蕉问题苹果香蕉问题 范例范例 以下程序实现多线程同步 其关系如下 父亲 儿子 女儿三人和一个盘子 当盘子空 时 父亲往盘中随机放苹果或香蕉 儿子只从盘中拿苹果 女儿只从盘中拿香蕉 include using namespace std include include int k HANDLE Apple HANDLE Banana CRITICAL SECTION mmutex DWORD WINAPI Son LPVOID n HANDLE Apple CRITICAL SECTION mmutex int i 1 OpenSemaphore MUTEX ALL ACCESS false Apple while 1 WaitForSingleObject Apple INFINITE 等苹果 cout Son eats i apples endl LeaveCriticalSection i CloseHandle Apple return 0 DWORD WINAPI Daughter LPVOID n 6 int i 1 HANDLE Banana CRITICAL SECTION mmutex OpenSemaphore MUTEX ALL ACCESS false Banana while 1 WaitForSingleObject Banana INFINITE 等香蕉 cout Daughter eats i bananas endl LeaveCriticalSection i CloseHandle Banana return 0 DWORD WINAPI Father LPVOID n UINT fruit CRITICAL SECTION mmutex EnterCriticalSection fruit rand 2 if fruit 0 盘中放入苹果 cout k 1 father produce an apple endl k k 1 ReleaseSemaphore Apple 1 NULL else 盘中放入香蕉 cout k 1 father produce a banana endl k k 1 ReleaseSemaphore Banana 1 NULL return 0 int main int j k 0 HANDLE Father 20 Apple CreateSemaphore NULL 0 1 apple Banana CreateSemaphore NULL 0 1 banana InitializeCriticalSection srand time NULL for j 0 j 0 11 当进程 process2 访问 x 时 若 x 0 66 当进程 process1 访问 x 时 若 x 0 66 则分别认为各进程的执行时间片到限 产生 时间片中断 而转入低就绪态 t 进程调度算法采用剥夺式最高优先数法 各进程的优先数通过键盘输入予以静态设置 调度程序每次总是选择优先数量小 优先权最高 的就绪态进程投入执行 先从 r 状态进程 中选择 再从 t 状态进程中选择 当现行进程唤醒某个等待进程 而被唤醒进程的优先数小 于现行进程时 则剥夺现行进程的执行权 各进程在使用临界资源 S1 和 S2 时 通过调用信号量 sem1 和 sem2 上的 P V 操作来实 现同步 阻塞和唤醒操作和负责完成从进程的执行态到等待态以及从等待态到就绪态的转换 糸统启动后 在完成必要的糸统初始化后便执行进程调度程序 当执行进程因 时间片 中断 或被排斥使用临界资源 或唤醒某个等待进程时 立即进行进程调度 当 1 个进程 都处于完成状态后 糸统退出运行 图 1 和图 2 分别示出了糸统主控程序和进程调度程序的大致流程 9 Main 初始化 Secheduler 有执行进程 exe NTL 进程 2进程 1进程 3 END 1 数据结构 1 每个进程有一个进程控制块 PCB 内容包括 Id 进程标识数 id 0 1 2 Status 进程状态 可为 e r t w c Priority 进程优先数 Nextwr 等待链指针 指示在同一信号量上等待的下一个进程的标识数 2 信号量 semaphore 对应于临界资源 s1 和 s2 分别有 sem1 和 sem2 均为互斥信号量 内容 包括 Value 信号量值 初值为 1 Firstwr 等待链首指针 指示该信号量上第一个等待进程的标识数 1 现场保留区 用数组 savearea 1 3 表示 即每个进程都有一个大小为 3 个单元的保 留区 用来保存被 中断 时的现场信息 如通用寄存器的内容和断点地址等 此外 糸统中还用到下列主要全程变量 Exe 执行进程指针 其值为进程标识数 I 用来模拟一个通用寄存器 五 程序源代码五 程序源代码 10 include define TRUE 1 define FALSE 0 define MAXPRI 100 define NIL 1 struct int id char status int nextwr int priority pcb 1 struct int value int firstwr sem 2 char savearea 1 3 addr int i s1 s2 seed exe NIL init int j for j 0 j 1 j pcb j id j pcb j status r pcb j nextwr NIL printf n process d priority j 1 scanf d pcb j priority i sem 0 value 1 sem 0 firstwr NIL sem 1 value 1 sem 1 firstwr NIL for i 1 i 1 i for j 0 j 3 j savearea i j 0 float random int m if seed 0 m seed else m seed seed 24151 seed 11839 64416 return m 12565 0 timeint char addr float x x random if x 0 11 if x 0 66 if x 1 0 savearea exe 0 i savearea exe 1 addr pcb exe status t printf Times silce interrupt nprocess d enter into ready n exe 1 exe NIL return TRUE find int j pd NIL w MAXPRI for j 0 j 1 j if pcb j status r if pcb j priority w w pcb j priority pd j if pd NIL for j 0 j 1 j if pcb j status t if pcb j priority w w pcb j priority pd j return pd scheduler int pd if pd find NIL 11 if pd NIL if exe NIL pcb pd status e exe pd printf process d is executing n exe 1 else if pcb pd priority 0 return FALSE block se savearea exe 0 i savearea exe 1 ad exe NIL return TRUE wakeup int se int w w sem se firstwr if w NIL sem se firstwr pcb w nextwr pcb w status r printf process d is waken up n w 1 v int se char ad if sem se value 0 return FALSE wakeup se savearea exe 1 ad savearea exe 0 i return TRUE eexit int n pcb n status c printf process d is completed n n 1 exe NIL processl if addr a goto a1 if addr b goto b1 if addr c goto c1 if addr d goto d1 if addr e goto e1 if addr f goto f1 for i 1 i 6 i printf process1 calls P on the semaphore1 n if p 0 a break a1 printf process1 is executing in the cretical section 1 n 12 if timeint b break b1 printf s1 d n s1 printf process1 calls V on semaphorel and quit cretical section1 n if v 0 c break c1 printf process1 calls P on esemaphorel 2 n if p 1 d break d1 printf process1 is execting cretical section 2 n if timeint e break e1 printf s2 d n s2 printf process1 calls V on semaphore2 and quit cretical section2 n if v 1 f break f1 printf process1 cycle count d n i if i 6 return eexit 0 process2 if addr a goto a2 if addr b goto b2 if addr c goto c2 if addr d goto d2 if addr e goto e2 if addr f goto f2 for i 1 i 6 i printf process2 calls P on the semaphore2 n if p 1 a break a2 printf process2 is executing in the cretical section2 n if timeint b break b2 printf s2 d n s2 printf process2 calls V on semaphore2 and quit cretical section2 n if v 1 c break c2 printf process2 calls P on esemaphore1 n if p 0 d break d2 printf process2 is execting cretical section1 n if timeint e break e2 printf s1 d n s1 printf process2 calls V on semaphore1 and quit cretical section1 n if v 0 f break f2 printf process2 cycle count d n i if i 6 return eexit 1 process1 if addr a goto a1 if addr b goto b1 if addr c goto c1 for i 1 i 6 i printf process1 calls P on semaphore2 n if p 1 a break process 1 is biocked a1 printf process 1 is execcuting on its cretical section n if timeint b break b1 printf s2 d n s2 printf process1 calls V on semapore2 and quit cretical section n if v 1 c break wake up a biocked process c1 printf process1 cycien count d n i if i 6 return eexit 2 main int k printf process management n n init printf s1 d s2 d n s1 s2 printf process1 process2 process1 are all in ready n for if k scheduler NIL switch k case 0 process1 break 13 case 1 process2 break case 2 process1 break default printf process identifer error n break else break printf s1 d s2 d n s1 s2 printf n END n 六 思考六 思考 1 如何修改 P 操作 使之能一次申请多个信号量 2 在某个时刻 一个进程最多可以等待多少个信号量 实验四实验四 银行家算法模拟银行家算法模拟 实验学时 2 实验类型 设计 实验要求 必修 一 实验目的一 实验目的 1 进一步理解利用银行家算法避免死锁的问题 2 在了解和掌握银行家算法的基础上 编制银行家算法通用程序 将调试结果显示在 计算机屏幕上 再检测和笔算的一致性 3 理解和掌握安全序列 安全性算法 二 实验内容二 实验内容 1 了解和理解死锁 2 理解利用银行家算法避免死锁的原理 3 会使用某种编程语言 4 撰写上机报告 三 实验原理三 实验原理 一 安全状态 指系统能按照某种顺序如 称为序列为安全序列 为每个进 程分配所需的资源 直至最大需求 使得每个进程都能顺利完成 二 银行家算法 假设在进程并发执行时进程 i 提出请求 j 类资源 k 个后 表示为 Requesti j k 系统按下 述步骤进行安全检查 1 如果 Requesti Needi 则继续以下检查 否则显示需求申请超出最大需求值的错误 2 如果 Requesti Available 则继续以下检查 否则显示系统无足够资源 Pi 阻塞等待 3 系统试探着把资源分配给进程 Pi 并修改下面数据结构中的数值 14 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正 式将资源分配给进程 Pi 以完成本次分配 否则 将本次的试探分配作废 恢复原来的资 源分配状态 让进程 Pi 等待 三 安全性算法 1 设置两个向量 工作向量 Work 它表示系统可提供给进程继续运行所需的各类资源数目 它含有 m 个元素 在执行安全算法开始时 Work Available Finish 它表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做 Finish i false 当有足够资源分配给进程时 再令 Finish i true 2 从进程集合中找到一个能满足下述条件的进程 Finish i false Need i j Work j 若找到 执行步骤 3 否则 执行步骤 4 3 当进程 Pi 获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 Work j Work i Allocation i j Finish i true go to step 2 4 如果所有进程的 Finish i true 都满足 则表示系统处于安全状态 否则 系统处于 不安全状态 四 实验算法四 实验算法 1 参考图 1 1 所示流程图编写安全性算法 2 编写统一的输出格式 每次提出申请之后输出申请成功与否的结果 如果成功还需要输出变化前后的各种数据 并且输出安全序列 3 参考图 1 2 所示流程图编写银行家算法 4 编写主函数来循环调用银行家算法 15 五 思考题五 思考题 1 在编程中遇到了哪些问题 你是如何解决的 2 在安全性算法中 为什么不用变量Available 而又定义一个临时变量 work 结束 否是 申请失败 以上分配作废 恢复原来的分配状态 Available j Available j Request i j Allocation i j Allocation i j Request i j Need i j Need i j Request i j N Y N Y Request i j Need i j 出错返回 return error Request i j Available j 出错返回 进程阻 塞 return error Available j Available j Request i j Allocation i j Allocation i j Request i j Need i j Need i j Request i j 假定分配 输入初始参数 资 源分配及请求情况 开始 假定分配之后 系统安 全吗 申请成功 输出各种 数据的变化 图 1 2 银行家算法流程图 16 实验五实验五 虚拟存储管理中页面置换算法模拟虚拟存储管理中页面置换算法模拟 实验学时 2 实验类型 设计 实验要求 必修 一 实验目的一 实验目的 1 了解内存分页管理策略 2 掌握调页策略 3 掌握一般常用的调度算法 4 学会各种存储分配算法的实现方法 5 了解页面大小和内存实际容量对命中率的影响 二 实验内容二 实验内容 1 采用页式分配存储方案 通过分别计算不同算法的命中率来比较算法的优劣 同 时也考虑页面大小及内存实际容量对命中率的影响 2 实现 OPT 算法 最优置换算法 LRU 算法 Least Recently FIFO 算法 First IN First Out 的模拟 3 会使用某种编程语言 4 撰写实验报告 三 实验原理三 实验原理 分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片 称为页面或页 在进程运行过程中 若其所要访问的页面不在内存而需把它们调入内存 但内存已无空 闲空间时 为了保证该进程能正常运行 系统必须从内存中调出一页程序或数据 送磁盘的 对换区中 但应将哪 个页面调出 须根据一定的算法来确定 通常 把选择换出页面的算 法称为页面置换算法 Page Replacement Algorithms 一个好的页面置换算法 应具有较低的页面更换频率 从理论上讲 应将那些以后不再 会访问的页面换出 或将那些在较长时间内不会再访问的页面调出 1 最佳置换算法 最佳置换算法