请问你怎么看待这种改进的观点?
8-9.下面的程序使用院子加载和存入操作来实现互斥:
//全局变量
blocked[0]=false;
blocked[0]=false;
turn=0;
//Thread0
While
(1){
blocked[0]=true;
while(turn!
=0)do;
turn=0}
//triticalesection
Blocked[0]=false;
}
//Thread1
While
(1){
Blocked[1]=true;
While(turn!
=1){
While(blocked[0])do;
Turn=1;}
//criticalsection
Blocked[1]=false;
}
请问该实现正确吗?
如果正确,请证明。
否则,请给出反例。
8-11.共享卫生间。
某单位为节省经费,决定建造男女共用的单性卫生间。
为满足社会风化要求,卫生间的使用需求需要满足如下条件:
在任何时候不同性别的人不能同时在卫生间里。
任务就是写一个程序来模拟卫生间的使用。
可以使用的工具是Mesa管理。
需要编写下述4个函数:
Woman_wants_to_enter()
Man_wants_to_enter()
Woman_leaves()
Man_leaves()
在这些函数里面可以使用原语lock()、unlock(),signal(),wait()和broadcast()来控制对卫生间的使用。
假定同一性别的人进入卫生间的数量不受限制。
8-12.第2个版本的卫生间共享
重做第十题的卫生间共享问题,这次把优先级赋予当前使用卫生间的性别。
例如,如果卫生间里面已经有女士在使用,新来的女士即可以直接进入,即使有男士在卫生间外面等待。
8-13.第3个版本的卫生间共享
这次需要保证公平,并防止饥饿:
如果女士在卫生间,则只要没有男士等待在外面,新来的女士皆可以进入卫生间。
如果有男士等待,则新来的女士就不能进去,而必须等待在男士后面。
当卫生间的最后一位女士离开时,等待的男士可全部进入。
第九章P183
9-3.忽略死锁似乎不像一个好的策略,但它在商业操作系统中得到了广泛的应用,为什么?
因为防止死锁的代价太高,比重启一百次的代价还高,发生死锁死机还不如直接重启。
9-6.死锁的根本基础是什么?
计算机系统有可能完全杜绝死锁么?
根本基础是资源有限,持有等待,不能抢占,循环等待条件。
计算机不可能完全杜绝死锁。
9-7.银行家算法在现实生活中经常使用,为什么使用类似策略的死锁应对策略在操作系统中却无法行使呢?
银行家算法是一个动态避免死锁算法,它的缺陷是需要知道将来需要什么,而在操作系统中并没有什么有效的办法计算出一个线程所需的资源额度,所以在操作系统无法行使该策略。
9-8.睡觉理发师问题:
一个理发店有一个理发师,一张理发椅子,N张等待椅子(N>1)。
当没有顾客的时候,理发师就睡觉。
当一个顾客来到店里时,如理发师在睡觉,则叫醒理发师,如果理发师正在给人理发,则坐在等待椅子上等待;如果等待的椅子都满了,则顾客就离开理发店而不理发了。
请问这种安排有发生死锁的可能么?
如果不能请予以证明。
如果可能,什么情况下会发生死锁?
请设计一个避免死锁的方案。
你采取的是哪种死锁应对策略?
理发师检查没有顾客,准备睡觉——挂起
顾客发现理发师没睡,等待——挂起
理发师睡觉——死锁
避免死锁方案,在理发师检查没有顾客和睡觉过程加锁。
两个动作要么全都做,要么一个都不做。
采取的是静态防止中的杜绝保持并等待。
9-9.四方恋爱问题:
假如我们有两男:
尤尔、夏士,两女:
左怡、尚珊。
左怡尚珊都喜欢玫瑰,谁送她们玫瑰,她们就和谁谈恋爱,尤尔和夏士都喜欢名表,谁送他们名表,他们就跟谁谈恋爱。
如果两位男士给同一位女士送玫瑰,或者一位女士同时给两位男士送名表,则两位男士大打出手(死锁)。
如果两位女士同时给一位男士送名表,后者一位男士同时给两位女士玫瑰,则两位女士将大打出手(死锁),请你帮助他们建立一对一的恋情关系,并在建立过程中防止大打出手(死锁)
Inti尤=0,i夏=0,i左=0,i尚
While(i尤==0)
{lock();
If(左怡送){i尤++;i左++;}
Unlock();
Lock();
If(尚珊送){i尤++;i尚++;}
Unclock();
lock();
If(送左怡){i尤++;i左++;}
Unlock();
Clock();
If(送尚珊){i尤++;i尚++;}
Unclock();}
9-11.本章讨论的哲学家就餐问题多个解决方案,请给出一个不同于书中解答的方案
9-12.本章给出的则学家就餐问题解决方案是否为最优方案?
请说明理由
9-13.有同学提出,本章给出的则学家就餐问题解决方案可能导致饥饿,即某个或某些哲学家永远得不到足够的筷子来就餐。
你同意该同学的看法吗?
如果你同意,那么本解决方案是否公平?
如果你不同意,请说明你的理由。
第十章P198
10-1.你能否用加载和存入原子指令实现锁?
请给出答案
内存加载和存入
Lock()
{load;
While(walue!
=FREE)
{store;
Bad;}
Value=BUSY;
Store;}
Unclock{load;
Value=FREE;
Store;
}
测试与设置
Clock(){while(test_and_set(value)==1){}}
Unclock(){value=0;}
10-2.lock()
{disableinterrupts;
While(value!
=FREE)
{enableinterrupts;
Disableinterrupts;}
Value=BUSY;
Enableinterrupts;
}
在如上所示的锁的实现中,enableinterrupts和disableinterrupts两条指令紧邻似乎是无聊之举,因为它们的效果互相取笑。
真的是这样吗?
不是,enableinterrupts:
是打开终端,让其他线程有机会通过中断被CPU调度,释放value,使进程获得value,紧接的disableinterrupts是将打开的中断关闭。
10-3.一同学认为用在切换时将中断保持为禁止状态(图10-9)的办法来解决图10-7所面临的问题太过复杂,不如干脆如图10-7中切换语句删除,留待操作系统的调度程序进行切换。
这样就不存在在何处启用中断的难题。
即将上锁程序变为如下:
Lock()
{disableinterrupts;
If(value==FREE){
Value=BUSY;}
Else{addthreadtoqueueofthreadswaitingforthislock;
}
Enableinterrupts;
}
请问,上述锁的实现是否可行。
如果可行,证明其可行性。
如果不可行,给出反例。
不可行,因为disableinterrupts关断中断以后,进程一直占用CPU,别的线程没有机会被CPU调度,如果此时value=BUSY的话,那线程就无法向前推进,从而造成死帧。
10-4.一个同学提出一个解决使用测试与设置命令、非繁忙等待实现锁时(图10-10)所面临的一个线程同时存在两个状态的问题。
该方法非常简单,即让操作系统调度器在取得控制权后,检查一下刚刚被中断的线程是否在锁的系统调用里面,如果是,则不予切换线程,即将控制权再交回给被中断线程,使其可以继续执行下一句指令,从而切换到别的线程。
请问这种方法能奏效么?
如果能,它有什么缺点?
如果不能,它存在什么问题?
能,但是时间复杂度增大。
10-7.有人提出另一种使用测试与设置来实现锁的方法如下:
Lock()
While(test_and_set(guard)){}
If(value==FREE){
Value==BUSY;}
Else{
Addthreadtoqueueofthreadswaitingforthislock;
Switchtonextrunnablethread;
}
Guard=0
}
Unlock()
{value=FREE;
If(anythreadiswaitingforthislock)
{movewaitingthreadfromwaitingqueuetoreadyqueue;
Value=BUSY;
}
}
这种实现的特点是在unlock里不对guard进行厕所遇设置,而是直接对value进行操作。
请问:
这种实现方式能否正确运行,为什么?
unclock中value=FREE,这个赋值语句不是原子操作,所以需要保护,否则FREE可能在传往value的途中被■掉,造成锁的释放失败。
第十一章P222
11-5.有同学提出,在固定分区的多道编程的内存管理下,只需要在编译时给出一个参数,即该程序将被加载的内存分区,便可以通过编译器来事先计算出每个程序虚地址的物理地址。
这样在加载后,就不在需要动态地址翻译了。
请问该建议怎么样?
该建议不可行,因为每加载一个程序都要给出一个参数,这样效率很低。
11-6.固定分区管理模式下,使用静态地址翻译能否满足地址独立的目标?
地址保护呢?
在固定分区管理模式下,使用静态地址翻译不能满足地址独立和地址保护。
11-7.固定分区时如何达到内存管理的两个抽象:
地址独立和地址保护?
请详细说明
地址独立:
是要程序发出的地址与物理地址无关,而固定分区管理中,每个程序的地址都不一样。
地址保护:
要求进程之间相互没有访问。
11-11.在多道编程下,我们说过需要动态地址翻译。
因为编译器不知道该程序将被加载到何地址上。
但有学生提出,可以使用加载器进行静态地址翻译,因为加载的时候我们已经知道加载的起始地址了。
请问这种做法行得通么?
行不通,没实现地址保护。
11-13.使用位图和链表来管理限制内存空间在时间效率上孰优孰劣?
为什么?
如果程序数量很少,那么链表比较好,因为链表的数量小。
位图表示法的空间成本是固定的,它不依赖于内存中程序的数量。
位图表示法没有容错能力
时间成本上,位图表示图在修改时简单
第十二章P243
12-1.与基本内存管理模式比较,分页管理模式的最大优点是什么?
最大优点是可以有效减少内存空间的外部碎片。
12-2.在一个页式内存系统下,一个程序能达到的最大尺寸是多大?
最大尺寸=硬盘尺寸—操作系统尺寸
12-5.设有一个32位寻址的分页系统,页面大小为16KB,假定页面号处于最左面,页面偏移值处于最右面,请问该系统需要多少位来表示页面号和页内号偏移值?
该系统能访问的最大虚拟页面号是多少?
18位,14位。
12-8.有人建议使用一个代数公式来进行虚拟页面到物理页面的映射,从而无须使用页表而节省页表而节省页表所占的内存空间。
请问你对这种建议做何评价?
这种建议不可行,因为物理内存比较小,而页面数比较多,可能会导致多个虚拟页面号指向同一个物理页面。
12-11.比莱迪异常出现的原因是什么?
它是一个悖论么?
比莱迪异常的原因是:
页面更换策略的不合理。
比莱迪异常不是悖论,它不是一种常见现象,而是一种异常现象。
它并不能说明我们不能给进程增加物理页面数或者增加物理页面数就一定会导致缺页中断。
12-13.多级页表策略是否会造成内存访问效率下降?
解决办法是什么?
会,解决方法:
使用翻译快表TLB。
第十三章P266
13-1.页面替换算法的根本追求是什么?
降低随后发生缺页中断的次数或者概率。
最理想的情况是选择一个再也不会被访问的页面进行替换。
13-2.提出最优页面替换算法的意义是什么?
为了定义一个标杆,以此来评判其他算法的优劣。
13-5.考虑一个460字的程序的下述内存访问序列:
10,11,104,170,309,185,245,246,434,458,364
假定采用页式虚拟内存管理,页面大小为100字,内存中有2个物理页面可供程序使用,且在开始时物理页面没有被任何进程占用。
1)若采用FIFO替换算法,那么有关访问序列的缺页中断次数是多少?
2)若采用LRU替换算法,那么有关该访问序列的缺页中断次数是多少?
460/100=4…6要用到5个页面0-99100-199200-299300-399400-459
(1)FIFO(中断次数6)
要访问的序列101110417073309185245246434458364
物理页面1000003333444
物理页面21111122223
中断标记√√√√√√
(2)URL(中断次数7)
要访问的序列101110417073309185245246434458364
物理页面1000000122222
物理页面21113331443
中断标记√√√√√√√
13-6.在工作集算法里,每个页面的最后使用时间是在每次访问时都设置呢,还是只在却也中断被扫描到时才设置呢?
为什么?
在工作集算法里,每个页面的最后使用时间是指在缺页中断被扫描到时才设置。
因为工作集有时空局域性,如果时间都发生变化,那么就没有工作集了。
所以它在某段时间比较固定,不每一次访问都设置。
13-7.比较各种页面替换算法,说明为什么工作集时钟算法最受人们青睐。
因为工作集时钟算法继承了时钟算法以及工作集算法的优点。
时间更快,效率更好,公平性更佳。
13-10.工作集算法的提出时因为我们在观念上实现了突破,请问这种观念图片是什么?
这种观念的突破是没必要记录每个页面的访问的记录
13-11.虽然本章讨论了10种页面替换算法,但页面替换算法还有很多,例如,有一种成为“栈算法”的页面替换算法。
该算法的替换策略就是栈的操作策略:
后进先出。
即每次替换页面时,选择最后进入内存的页面进行替换。
试分析这种策略的优劣,并重做第五题。
使用栈算法的缺页中断次数是多少?
栈算法:
存在时间最长不一定访问次数最多,每次都