<4D F736F F F696E74202D20B2D9D7F7CFB5CDB3CFB0CCE2BFCE202D20D6DCC8FD2E BBCE6C8DDC4A3CABD5D>

Size: px

Start display at page:

Download "<4D6963726F736F667420506F776572506F696E74202D20B2D9D7F7CFB5CDB3CFB0CCE2BFCE202D20D6DCC8FD2E707074205BBCE6C8DDC4A3CABD5D>"

阐戈
7 years ago
Views:

1 操作系统习题课习题一 : 多道程序 1

2 习题一 : 多道程序第 (1) 问 :Turn around 时间作业从投入到完成所需时间 J1:110ms J2:90ms J3:110ms 第 (2)(3) 问 : 计算 CPU 和 I/O 设备的利用率 CPU 的利用率为 :(110-30)/110=72.7% 的利用率为 :(110-30)/110=72.7% 的利用率为 :(110-20)/110=81.8% 习题一 : 课堂练习 (2013 阿里招聘试题 ) 假设在内存中有 P1 P2 P3 三道程序, 并按照 P1 P2 P3 的优先次序运行, 其内部计算和 I/O 操作时间由下给出 : P1: 计算 60ms I/O 操作 80ms 计算 20ms P2: 计算 120ms I/O 操作 40ms 计算 40ms P3: 计算 40ms I/O 操作 80ms 计算 40ms 调度程序的时间忽略不计, 完成者三道程序比单道运行节省的时间是 ( ) A 80ms B 120ms C 160ms D 200ms 2

8% 习题一 : 课堂练习 (2013 阿里招聘试题 ) 假设在内存中有 P1 P2 P3 三道程序, 并按照 P1 P2 P3 的优先次序运行, 其内部计算和 I/O 操作时间由下给出 : P1:

3 习题一 : 课堂练习单道所需时间 :520ms 多道所需时间 : =360ms 故节省的时间为 160ms 答案为 C 习题二 :CPU 调度 3

4 习题二 :CPU 调度第一问 : 采用优先级调度算法, 其执行顺序为 B E A C D 如下表 : 作业运行时间等待时间周转时间带权周转时间 B /6=1 E /8=1.75 A /10=2.4 C /2=13 D /4=7.5 作业平均周转时间 T=( )/5=20 作业平均带权周转时间 W=( )/5=5.13 习题二 :CPU 调度第二问 : 采用先来先服务, 其执行顺序为 A B C D E 如下表 : 作业运行时间等待时间周转时间带权周转时间 A /10=1 B /6=2.66 C /2=9 D /4=5.5 E /8=3.75 作业平均周转时间 T=( )/5=19.2 作业平均带全周转时间 W=( )/5=4.38 4

13 习题二 :CPU 调度第二问 : 采用先来先服务, 其执行顺序为 A B C D E 如下表 : 作业运行时间等待时间周转时间带权周转时间 A 10 0 10 10/10=1 B 6 10 16 16/6=2.

5 习题二 :CPU 调度第三问 : 采用短作业优先调度算法, 其执行顺序为 C D B E A 如下表 : 作业运行时间等待时间周转时间带权周转时间 C /2=1 D /4=1.5 B /6=2 E /8=2.5 A /10=3 作业平均周转时间 T=( )/5=14 作业平均带权周转时间 W=( )/5=2 习题二 :CPU 调度思考 : 通过计算时间片轮转 (t=2) 算法的平均等待时间, 周转时间, 比较其与前三种算法的区别 5

5 A 10 20 30 30/10=3 作业平均周转时间 T=(2+6+12+20+30)/5=14 作业平均带权周转时间 W=(1+1.5+2+2.

6 习题三 : 哲学家就餐习题三 : 课堂练习京东掌门和奶茶妹妹近日京东掌门证实了和奶茶妹妹的恋情, 京东依靠着财大气粗, 可以源源不断的生产奶茶, 这样奶茶妹妹就可以尽情享用女神最爱的奶茶了可是京东的库存不给力, 只能储存 N 杯奶茶, 当库存满时京东就不再生产奶茶了, 当没有库存时, 奶茶妹妹就没奶茶喝了, 只能呵呵了请用信号量 P,V(wait,signed) 操作实现京东掌门和奶茶妹妹的互斥和同步, 要求写出完整的过程 ; 并指出所用信号量的含义和初值 6

存 N 杯奶茶, 当库存满时京东就不再生产奶茶了, 当没有库存时, 奶茶妹妹就没奶茶喝了, 只能呵呵了请用信号量

7 习题三 : 课堂练习京东掌门和奶茶妹妹信号量 : Semaphore empty=n; // 表示库存空余 Semaphore full=0; // 表示库存已满 Semaphore mutex=1; // 库存互斥信号京东奶茶妹妹 generant(){ consumer(){ P(mutex); (1) P(mutex); (1) P(empty); P(full); P(mutex); (2) P(mutex); (2) generate();// 生产奶茶 consume();// 喝奶茶 V(mutex); (2) V(mutex); (2) V(full); V(empty); V(mutex); (1) V(mutex); (1) 问题 : 1. 如果库存是一个互斥资源, 京东掌门和奶茶妹妹不能同时访问库存, 该如何实现? 2. 互斥信号量应该放哪儿? 先同步, 后互斥习题三 : 课堂练习 2009 年计算机考研题三个进程 P1 P2 P3 互斥使用一个包含 N(N>0) 个单元的缓冲区 P1 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中 ;P2 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数 ;P3 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数请用信号量机制实现这三个进程的同步与互斥活动, 并说明所定义的信号量的含义要求用伪代码描述 7

如果库存是一个互斥资源, 京东掌门和奶茶妹妹不能同时访问库存, 该如何实现? 2. 互斥信号量应该放哪儿?

8 习题三 : 课堂练习 2009 年计算机考研题同学们课下思考 :( 几点提示 ) 1. 有几种关系?(P1 和 P2 的奇数同步关系,P1 和 P3 的偶数同步关系,P1 和 (P2,P3) 的生产者 - 消费者同步关系,(P1,P2,P3) 的缓冲区互斥关系 ) 2. 需要几个信号量?( 每个关系一个信号量 ) 3. 信号量的初值分别怎么赋值? 习题三 : 课堂练习一个司机与售票员在公共汽车上, 为保证乘客的安全, 司机和售票员应协调工作 : 停车后才能开门, 关车门后才能行车用 PV 操作来实现他们之间的协调 8

区互斥关系 ) 2. 需要几个信号量?( 每个关系一个信号量 ) 3. 信号量的初值分别怎么赋值?

9 习题三 : 课堂练习一个司机与售票员信号量 : Semaphore s1=0;// 是否允许启动汽车 Semaphore s2=0;// 是否允许开门司机 driver(){ P(s1);// 请求启动汽车 start(); drive(); stop(); V(s2);// 允许打开车门售票员 busman(){ shutdown();// 关车门 V(s1);// 允许开车 selling();// 售票 P(s2);// 请求开门 open();// 开车门 discharge_or_takein();// 上下乘客习题三 : 课堂练习水果盘当水果盘空时, 父亲可以放香蕉或者母亲可以放苹果, 但盘中已有水果时, 就不能放, 父母等待当盘中有香蕉时, 女儿可吃香蕉, 否则, 女儿等待 ; 当盘中有苹果时, 儿子可吃, 否则, 儿子等待 9

票 P(s2);// 请求开门 open();// 开车门 discharge_or_takein();// 上下乘客习题三 : 课堂练习水果盘当水果盘空时, 父亲可以放香蕉或者母亲可

10 习题三 : 课堂练习水果盘信号量 : Semaphore empty=1;// 空盘子 Semaphore apple=0;// 放了苹果的盘子 Semaphore banana=0;// 放了香蕉的盘子父亲 father(){ peelingb();// 剥香蕉 P(empty); set();// 放香蕉 V(banana);// 允许吃母亲 mother(){ peelinga();// 剥苹果 P(empty); set();// 放苹果 V(apple);// 允许吃儿子 son(){ P(apple); geta();// 拿苹果 V(empty); eat();// 吃女儿 daughter(){ P(banana); getb();// 拿香蕉 V(empty); eat();// 吃习题三 : 课堂练习生产者消费者扩展多缓冲区一个从键盘输入到打印机输出的数据处理流程图如图所示其中键盘输入进程通过缓冲区 bufa 把数绝传送给计算进程, 计算进程把处理结果通过 bufb 传送给打印进程假设上述两个缓冲区的大小分别为 a 和 b, 试写出键盘输入进程计算进程及打印进程间的同步算法 Input Buffer A Calculate Buffer B Print out 10

daughter(){ P(banana); getb();// 拿香蕉 V(empty); eat();// 吃习题三 : 课堂练习生产者消费者扩展多缓冲区一个从键盘输入到打印机输出的数据处理流程图如图所示其中键盘输入进程通过缓冲区

11 习题三 : 课堂练习生产者消费者扩展多缓冲区信号量 : Semaphore emptya=a;//buffer a 的缓冲区大小 Semaphore emptyb=b;//buffer b 的缓冲区大小 Semaphore fulla=0;//a 缓冲区已用数量 Semaphore fullb=0;//b 缓冲区已用数量 Semaphore mutexa=1;// 访问 buffer a 时互斥 Semaphore mutexb=1;// 访问 buffer b 时互斥 input(){ inputdata(); 输入数据 P(emptya); P(mutexa); puta();// 向 A 中输入 V(mutexa); V(emptya); print(){ P(fullb); P(mutexb); getb();// 从 B 中读入 V(mutexb); V(emptyb); printdata();// 输出 caculate(){ P(fulla); P(mutexa); geta();// 从 A 中读入 V(mutexa); V(fulla); caculate();// 计算 P(emptyb); P(mutexb); putb();// 向 B 中输入 V(mutextb); V(fullb); Input Buffer A Calculate Buffer B Print out 习题三 : 哲学家吃面伪代码 : semaphore chopstick[5]={1;// 筷子信号量 int i;// 表示位置 philosopher(int i){ think();// 思考 p(chopstick[i]);// 申请右边的筷子 p(chopstick[(i+1)mod5]);// 申请左边的筷子 eat();// 吃面 v(chopstick[i]);// 释放右边的筷子 v(chopstick[(i+1)mod5]);// 释放左边的筷子思考 : 五个哲学家同时拿起右边的筷子, 会出现什么情况? 死锁 11

P(mutexb); getb();// 从 B 中读入 V(mutexb); V(emptyb); printdata();// 输出 caculate(){ P(fulla); P(mutexa); geta();// 从 A 中读入 V(mutexa); V(fulla); caculate();// 计算 P(emptyb); P(mutexb); putb();// 向 B

12 4 习题三 : 哲学家吃面伪代码 : semaphore chopstick[5]={1;// 筷子信号量 semaphore room=4;// 同时最多允许 4 人 int i;// 表示位置 philosopher(int i){ think();// 思考 p(room); p(chopstick[i]);// 申请右边的筷子 p(chopstick[(i+1)mod5]);// 申请左边的筷子 eat();// 吃面 v(chopstick[i]);// 释放右边的筷子 v(chopstick[(i+1)mod5]);// 释放左边的筷子 v(room);// 释放空间习题三 : 哲学家吃面其他解决方案 : 1. 仅当哲学家的左右两支筷子都可用时, 才允许他拿起筷子进餐 (AND 型信号量 ) 2. 规定奇数号的哲学家先拿起他左边的筷子, 然后再去拿他右边的筷子 ; 而偶数号的哲学家则相反 12

v(chopstick[i]);// 释放右边的筷子 v(chopstick[(i+1)mod5]);// 释放左边的筷子 v(room);// 释放空间习题三 : 哲学家吃面其他解决方案 : 1.

13 习题四 : 死锁问题习题四 : 死锁问题 (1) 计算得到时刻的资源分配表如下, 剩余单元数为 150-( )=40 此时 40 不小于进程请求的单元数 25 进程 Max Allocation Need Available

14 习题四 : 死锁问题 (1) 计算得到时刻的资源分配表如下, 剩余单元数为 150-( )=40 此时 40 不小于进程请求的单元数 25 进程 Max Allocation Need Available 习题四 : 死锁问题将 25 分配给进程, 还剩余 15 个单元, 将其分配给进程, 此时结果如下表, 得到安全序列 {,,, 进程 Max Work Need Allocation Work+Allocation Finish True True True True 14

给进程, 还剩余 15 个单元, 将其分配给进程, 此时结果如下表, 得到安全序列 {,,, 进程 Max Work Need Allocation

15 习题四 : 死锁问题 (2) 此时的剩余单元数 150-( )=40 此时 40 不小于进程请求的单元数 35, 将其 35 个单元分配给进程, 余下 5 个单元, 其资源分配如下,4 个进程都不够分配, 找不到安全序列, 故为不安全状态进程 Max Allocation Need Available Thanks! 15

2016 年计算机专业基础综合考试真题思路分析 C180,500,200,450 D180,200,500,450 8 S abaabaabacacaabaabcc t abaabc KMP (s[i]t[j]) i=j=5i j Ai=1,j=0 Bi=5,j=0

2016 年计算机专业基础综合考试真题思路分析 C180,500,200,450 D180,200,500,450 8 S abaabaabacacaabaabcc t abaabc KMP (s[i]t[j]) i=j=5i j Ai=1,j=0 Bi=5,j=0 2015 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一单项选择题 : 第 140 小题, 每小题 2 分, 共 80 分下列每题给出的四个选项中, 只有一个选项最符合试题要求 1 int S(int n) { return