[开课学院]: 资电学院 [开课系所]: 资讯系 [课程名称]: 作业系统(一) [老师名称]: 戴婵玲 老师 [开课学期]: 981 [类型]: 98-1期末考 一、解释名词(25%) (a)Fragmentation (b)spin lock (c)atomic transaction (d)Belady's anomaly (e)TLB 二、问答题(75%) 1.Bakery演算法如下，请 (a)说明这个演算法。(5%) (b)列出解决临界区间(critical section)问题的三 个必要条件。(5%) (c)证明Bakery演算法满足 三个必要条件。(10%) do{ choosing[i]=true; number[i]=max(number[0],number[1],....,number[n-1])+1; choosing[i]=false; for(j=0;j<n;j++){ while(choosing[j]); while((number[j]!=0)&&(number[j],j<number[i],i)); } critical section number[i]=0; remainder section }while(1); 2.伺服器可针对同时连线的用户个数加以限制。例如，伺服器希望无论何时最多只 有N个socket connection。一但到达N个socket connection，伺服器就不接受再进 来的连线请求，除非任一个已经连线的用户端结束。 请写出此用来控制连线请求的假码(pseudo code)，并说明伺服器如何利用号志(sem aphore)来限制同时连线的socket个数? (10%) 3.请比较分页(paging)和分段(segmentation)记忆体管理模式，它们的逻辑位址转换 成实际位址的方法有何相似与相异之处? (10%) 4.请说明反转分页表(inverted page table)和一般分页表的建立方式有何差别？ 它们各自的优缺点为何？ (10%) 5.关於最佳换置法(Optimal algorithm) (10%) (a) 举例说明它的置换方式 (b) 为何它不适合实作?其主要目的为何? 6.当行程只分配到4个页框(frame)时，以下的分页取代法(page replacement algorithm) 会发生几次的分页失误(page fault)？请写出分页失误发生时的记忆体内容，并标示将 取代哪一个分页。(建议同学采用课本的方式作答。)参照字串(reference string)如下: (15%) １，２，３，４，５，６，２，１，２，３，７，６，３，２，１，２，３，６ (a)LRU(近来最少使用替换法) (b)LRU近似法中的Second Chance Algorithm(第二次机会替换法) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.170.119.76