第一篇：北工《操作系統(tǒng)》作業(yè)考核試題參考答案

北京理工大學遠程教育學院2019-2020學年第二學期 《操作系統(tǒng)》期末試卷（A卷）應(yīng)用題（每題20分，共100分）1.試說明操作系統(tǒng)與硬件、其他系統(tǒng)軟件以及用戶之間的關(guān)系。

2.常見的進程調(diào)度算法包括先來先服務(wù)算法、短作業(yè)優(yōu)先調(diào)度算法、高優(yōu)先權(quán)優(yōu)先調(diào)度算法和基于時間片的輪轉(zhuǎn)調(diào)度算法，請簡述這幾個算法的調(diào)度思想。

3．操作系統(tǒng)的主要任務(wù)是什么？請論述其基本功能。

4．請論述基本分頁系統(tǒng)中將邏輯地址L轉(zhuǎn)化為物理地址的過程。

5.某工廠有一個可以存放設(shè)備的倉庫，總共有8個位置可以存放8臺設(shè)備。生產(chǎn)部門生產(chǎn)的每一臺設(shè)備都必須入庫。銷售部門可以從倉庫提出設(shè)備供應(yīng)客戶。設(shè)備的出庫和入庫都必須借助運輸工具?，F(xiàn)在只有一套運輸工具，每次只能運輸一臺設(shè)備，系統(tǒng)共使用三個信號量，S代表互斥信號量，表示運輸工具；

S1和S2均為同步信號量，S1表示倉庫中可以存放設(shè)備的空閑位置，S2表示倉庫中已經(jīng)被設(shè)備占用了的位置。請設(shè)計一個能協(xié)調(diào)工作的自動調(diào)度管理系統(tǒng)，并利用記錄型信號量寫出解決此問題的程序代碼，請注明信號量的初值。

(93)北京理工大學遠程教育學院2019-2020學年第二學期 《操作系統(tǒng)》期末試卷（A卷）答題紙

第二篇：福師《民法》作業(yè)考核參考試題答案

《民法》期末考試A卷

姓名：專業(yè)：

學號：學習中心：

成績：

一、簡答題（34分）

1、簡述抵押權(quán)的概念及含義。（6分）

2、簡述租賃合同的效力。（6分）

3、簡述遺囑的有效要件。（6分）

4、簡述意思自治原則的含義及主要體現(xiàn)。（8分）

5、簡述宣告失蹤的概念、條件及法律后果。（8分）

二、論述題（42分）

1、試述實現(xiàn)留置權(quán)的條件及程序。（10分）

2、試述建筑物區(qū)分所有權(quán)的概念及客體。（10分）

3、何為同時履行抗辯權(quán)？其構(gòu)成要件有哪些？（12分）

4、試述保證的主要特征。（10分）

三、案例分析題（24分）

楊某(男)與馬某(女)于1990年登記結(jié)婚。后因感情惡化，于2001年11月經(jīng)協(xié)商，雙方到婚姻登記機關(guān)辦理了離婚登記，并對夫妻共同財產(chǎn)進行了分割。2005年12月3日，馬某得知，楊某曾于2001年8月以10萬元購買一套房屋，在辦理離婚手續(xù)時并沒有告知馬某，致使這一本屬夫妻共同財產(chǎn)的房屋為楊某獨自占有，因而于2006年1月向人民法院起訴，要求重新分割這部分財產(chǎn)。楊某辯稱：當初離婚時，雙方已經(jīng)就夫妻共同財產(chǎn)進行了分割，現(xiàn)在已經(jīng)四年多，訴訟時效已過，馬某再來請求分割財產(chǎn)，沒有法律依據(jù)。

根據(jù)本案案情，回答下列問題，并說明理由：

1、馬某能否請求再次分割夫妻共同財產(chǎn)?（8分）

2、本案中，馬某請求權(quán)的訴訟時效從何時起算?是否已超過訴訟時效?（8分）

3、人民法院應(yīng)當如何處理這一案件?（8分）

第三篇：內(nèi)審員考核試題答案

實驗室資質(zhì)認定評審準則

內(nèi)審員考核試題答案

單位：

姓名

得分

一 判斷題（共20分，每題2分）計量認證和審查認可均屬于資質(zhì)評定

（√）

資質(zhì)評定的執(zhí)行主體是第三方

（×）

資質(zhì)評定是自愿行為

（×）

實驗室應(yīng)建立以過程為基礎(chǔ)的管理體系

（√）

實驗室應(yīng)通過實施糾正措施、預防措施等持續(xù)改進其管理體系

（√）

實驗室的監(jiān)督員就是內(nèi)審員

（×）

實驗室的授權(quán)簽字人必須是技術(shù)主管

（×）

為保證獨立性，實驗室不允許將其工作的一部分分包出去

（×）

校準證書必須給出測量不確定度，而檢測報告則不用給出

測量不確定度

（×）

10由于計量檢定機構(gòu)是國家法定的，所以其提供的檢定結(jié)果

肯定正確可靠，實驗室沒有必要再進行檢查確認

（×）二 填空題（共20分，每空2分）實驗室選擇檢測/校準方法時，應(yīng)優(yōu)先考慮-------A--------------A國家、行業(yè)標準、地方標準 B 客戶指定的方法C 實驗室自己制定的方法 D 非標準方法實驗室資質(zhì)認定評審準則主要依據(jù)-------D-----------------標準制定

A ISO9001 B GB/T15481-2000 C GB/T15481-1995 D ISO/IEC17025:2005 實驗室應(yīng)對從事抽樣、檢測和/或校準、簽發(fā)檢測/校準報告以及操作設(shè)備等工作的人員進行-------C----------------A 培訓考核

B 長期教育

C 資格確認并持證上崗

D 適當監(jiān)督對文件進行控制的目的是為了------A------------A 確保文件現(xiàn)行有效

B 可以檢索

C 方便查閱

D 接受審核 進行合同評審的時機是--------B----------A 合同簽訂以后

B合同簽訂以前

C按客戶要求

D內(nèi)審之前 實驗室應(yīng)具有檢測/校準樣品的-------B-----------A標識

B標識系統(tǒng)

C唯一性標識

D永久性標識 實驗室報告和證書應(yīng)當-------D-----------A 簡單明確

B用中英文兩種文字編寫

C統(tǒng)一一致

D保證數(shù)據(jù)和結(jié)果準確、客觀、真實 實驗室所用檢測/校準儀器的量值應(yīng)溯源到-----A------------A 國家基準

B 當?shù)赜嬃坎块T

C

CNAS

D 國際標準化組織 實驗室在以下情況時應(yīng)監(jiān)控、記錄環(huán)境條件-------D-----------A 相關(guān)的規(guī)范、方法和程序有要求

B對結(jié)果的質(zhì)量有影響

C當物品需要存放或在規(guī)定的環(huán)境條件下

D以上都需要

實驗室的職責是-------D-----------

A 從事檢測或校準B滿足客戶的需求C滿足法定管理機構(gòu)或認可組織的需求D以上都是

三 簡答題（共40分，每題4分）實驗室管理體系文件包括哪些內(nèi)容？

① 質(zhì)量手冊② 程序文件③作業(yè)指導書④記錄計劃表格

糾正和糾正措施有何區(qū)別？

糾正是對已經(jīng)產(chǎn)生的不符合的處置和補救，糾正措施是針對已經(jīng)產(chǎn)生的不符合的根本原因，為防止類似的不符合再次發(fā)生而采取的措施。

3沒有相關(guān)的技術(shù)規(guī)范或者標準時，實驗室應(yīng)如何制定抽樣計劃？

實驗室應(yīng)根據(jù)適當?shù)慕y(tǒng)計方法制定抽樣計劃

內(nèi)審員和監(jiān)督員有什么區(qū)別？

① 資格不同②數(shù)量不同③任務(wù)不同④執(zhí)行任務(wù)的時機不同⑤對象不通

什么情況下允許對檢測/校準方法的偏離？

須有相關(guān)技術(shù)單位驗證其可靠性或經(jīng)有關(guān)主管部門核準后，由實驗室負責人批準和客戶接受，并將該方法偏離進行文件規(guī)定。

為什么記錄要包含足夠的信息？

保證檢測（校準）工作能夠再現(xiàn) 實驗室發(fā)現(xiàn)所用儀器有缺陷時應(yīng)采取什么措施？

應(yīng)立即停止使用，并加以明顯標識，如可能應(yīng)將其儲存在規(guī)定的地方直至修復；修復的儀器設(shè)備必須經(jīng)檢定、校準等方式證明其功能指標已恢復。實驗室應(yīng)檢查這種缺陷對過去進行的檢測和/或校準所造成的影響。

期間核查與校準有何不同？

①目的不同②對象不同③方法不同④結(jié)果不同 有損實驗室判斷獨立性和檢測/校準誠信度的活動可能包括哪些？

以實驗室的名義①產(chǎn)品（工程）評優(yōu)②監(jiān)制、監(jiān)銷產(chǎn)品或監(jiān)理工程③推薦產(chǎn)品④不經(jīng)客戶同意向媒體公布檢測結(jié)果等 監(jiān)控檢測/校準有效性的措施可包括哪些內(nèi)容？

a)定期使用有證標準物質(zhì)（參考物質(zhì)）進行監(jiān)控和/或使用次級標準物質(zhì)（參考物質(zhì)）開展內(nèi)部質(zhì)量控制；

b)參加實驗室間的比對或能力驗證； c)使用相同或不同方法進行重復檢測或校準； d)對存留樣品進行再檢測或再校準； e)分析一個樣品不同特性結(jié)果的相關(guān)性。

四 場景題（共20分，每題5分）評審員發(fā)現(xiàn)實驗室正在使用的一臺儀器有某單位出具的校準證書，問儀器設(shè)備管理員該儀器是否滿足使用要求？儀器設(shè)備管理員回答說有校準證書當然能行了?；卮鹫_嗎？

不符合《評審準則》第4.5條 評審員在審核時詢問實驗室技術(shù)主管是否實施了質(zhì)量監(jiān)控？實驗室技術(shù)主管回答實施了，并取出質(zhì)量監(jiān)控的記錄。評審員又問質(zhì)量監(jiān)控的結(jié)果如何？實驗室技術(shù)主管回答：我們也不知道應(yīng)如何判斷結(jié)果，所以就沒判斷，你看我們做的還行把？。該情況是否符合評審準則規(guī)定？

不符合《評審準則》第5.7.2條 評審員在某實驗室審核時發(fā)現(xiàn)2005內(nèi)部審核只檢查了7個要素。問質(zhì)量主管其它要素為什么沒審核？質(zhì)量主管回答這7個要素對我們來說比較重要，其它要素與我們基本沒有關(guān)系，所以就不用審了。這樣做正確嗎？

不符合《評審準則》第4.10.條 評審員在某實驗室審核時發(fā)現(xiàn)沒有2005管理評審計劃,問實驗室主任為什么沒有？

實驗室主任回答管理評審已經(jīng)作了很多次了，每次討論的內(nèi)容都差不多，所以不用編計劃了?；卮鹫_嗎？

不符合《評審準則》第4.11條

第四篇：GRO考核試題答案

GRO考核試題

一、填空（每空1分，共30分）

1.酒店的客房分布在3—9樓，共有14種房型，其中3樓為藝術(shù)樓層，5、6、7樓為高級樓層，8樓為綠色無煙樓層，9樓為豪華樓層，總統(tǒng)套房位于9樓的988。

2.酒店餐飲包括中餐廳1個，西餐廳1個，特色中餐包房（16）個，韓餐廳1個。酒店以（魯菜）為主。宴會包房位于酒店的2樓，共有包間16個，其中6人包房（2）個，8人包房（5）個，10人包房（5）個，12人包房（3）個，16-20人包房（1）個。

3、酒店的健身房位于酒店的3樓，免費為客人提供服務(wù)，營業(yè)時間為（8:30-21:30）.棋牌室也位于3層，提供24小時服務(wù)，收費標準為每小時（50）元，（500）元/天，（6小時后按全天算）

4、多功能廳衣帽間內(nèi)線電話：8089，V2V3內(nèi)線：8085，音控室內(nèi)線：8087

5、酒店大庫辦公室電話：8100 電腦房：8123，前臺電話(任一個)812,禮賓電話8121, 客房中心電話（任一個）8600,餐飲預訂電話（任一個）8188，工程部電話8008，監(jiān)控室電話8111。

二、英文翻譯（每題6分 共30分）

1、請問您有預訂嗎？

Do you have a reservation？？

2、請問您怎么來支付押金呢？

How would you like to pay your deposit？

3、我們的早餐位于酒店二樓，開餐時間是上午的6：30---9:30.Our breakfast start from 6:30 to 9:30 on the second floor

4、請稍等（打電話）。Hold on , please

5、請問有什么可以幫您？

What can I do for you？

三、簡答題（每題10分，共40分）

1、酒店企業(yè)文化是什么？

我們尊重市場，尊總顧客，尊重團隊，統(tǒng)一目標，統(tǒng)一追求，統(tǒng)一理念，用信仰武裝頭腦，用毅力刻畫意志，用行動實踐諾言。

2、如果客人在客休區(qū)抽煙，你應(yīng)該如何制止？

端著煙灰缸過去禮貌的跟客人說：大堂是公共區(qū)域，這里是無煙區(qū)，是禁止吸煙的。請您諒解一下，麻煩您把煙熄滅吧。我給您倒杯熱水。謝謝您的配合。謝謝。

3、簡要概述一下如何介紹一個SK房間？

先生/小姐，您面前的這個衣柜是酒店專門為出差的商務(wù)人士設(shè)計的，時尚方便，順手打開衣櫥，這里面為您準備了各種材質(zhì)的衣架（手勢跟上），方便您晾掛不同的衣服。柜子的旁邊酒店還專門為您準備了電熨斗，燙衣板，當然酒店還可以為您提供洗衣服務(wù)，這是洗衣袋和洗衣單（手勢），接著下面這個是電子保險柜，您的貴重物品可以放在里面，密碼您可以

自己設(shè)定，按#號開啟。衣柜的旁邊為您配置了酒水吧臺，茶葉，咖啡等都是免費供您使用的，吧臺下面的柜子中的冰箱里還為您提供了酒水，軟飲，點心等，旁邊的消費菜單您可以自己填寫，非常方便。為了方便您的娛樂生活，您的房間接入了衛(wèi)星數(shù)字電視，電視節(jié)目非常的豐富，平板的高清頻顯示頻也非常方便您的觀看（順手打開電視），前面是酒店專門為您打造方便您使用的寫字臺，辦公用的便筏紙，信封，筆等一應(yīng)俱全，旁邊還為您接入了高速的寬帶插口（IP地址是自動獲取的），國際國內(nèi)直撥電話，為了方便你的使用，我們在您的房間里配備了三部電話，分別在寫字臺，床頭柜，和洗手間內(nèi)。在靠近床頭的床頭柜上酒店還為你準備了便筏，鉛筆，臺燈，保健用品等方便您的居住。酒店的床上用品都是按照國際四星級酒店標準配備的，非常的舒適，保證您健康的睡眠。酒店的衛(wèi)生間也是聘請名師專門設(shè)計，干濕分開的，方便您的使用！尊敬的先生小姐，您的房間已經(jīng)給您介紹完畢，您看還有其他需要給您介紹的嗎？我是酒店的賓客關(guān)系主任某某，這是我的名片（雙手遞上），很高興能為您提供服務(wù)！希望您下榻愉快！后退三步鞠躬和客人道別！

4、常用房型簡稱考核(請在英文簡稱后寫下他們的漢語稱謂)SK

DK

ST

DT

ES

高級大床

豪華大床

高級標準間

豪華標準間

藝術(shù)套房

AK

AES

SD

AS

AC

藝術(shù)大床房

藝術(shù)豪華套

高級單人間

藝術(shù)套房

藝術(shù)標準間

第五篇：北郵操作系統(tǒng)第二次實驗[模版]

北京郵電大學操作系統(tǒng)實驗實驗報告

班號：2011211314姓名：oneseven學號：

實驗日期： 2013.12.16 實驗名稱： 操作系統(tǒng)實驗

一、實驗目的

通過模擬實現(xiàn)內(nèi)存分配的伙伴算法和請求頁式存儲管理的幾種基本頁面置換算法，了解存儲技術(shù)的特點。掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。

二、實驗內(nèi)容

1.實現(xiàn)一個內(nèi)存管理的伙伴算法，實現(xiàn)內(nèi)存塊申請時的分配和釋放后的回收。

實驗準備

用隨機函數(shù)仿真進程進行內(nèi)存申請，并且以較為隨機的次序進行釋放。對其碎片進行統(tǒng)計，當申請分配內(nèi)存失敗時區(qū)分實際空間不足和由于碎片而不能滿足。

2.設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。

1)最佳置換算法（Optimal）

2)先進先出法（Fisrt In First Out）

3)最近最久未使用（Least Recently Used）4)最不經(jīng)常使用法（Least Frequently Used）

其中，命中率＝１－頁面失效次數(shù)／頁地址流長度。試對上述算法的性能加以較各：頁面?zhèn)€數(shù)和命中率間的關(guān)系；同樣情況下的命中率比較。

實驗準備

本實驗中主要的流程：首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。

實驗可先從一個具體的例子出發(fā)。

(1)通過隨機數(shù)產(chǎn)生一個指令序列，共2048條指令。指令的地址按下述原則生成： A：50%的指令是順序執(zhí)行的

B：25%的指令是均勻分布在前地址部分 C：25%的指令是均勻分布在后地址部分 具體的實施方法是：

A：在[0，1023]的指令地址之間隨機選取一起點m B：順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令

C：在前地址[0,m+1]中隨機選取一條指令并執(zhí)行，該指令的地址為m’ D：順序執(zhí)行一條指令，其地址為m’+1 E：在后地址[m’+2，2047]中隨機選取一條指令并執(zhí)行 F：重復步驟A-E，直到2048次指令(2)將指令序列變換為頁地址流 設(shè)：頁面大小為4K；

用戶內(nèi)存容量4頁到32頁； 用戶虛存容量為32K。

在用戶虛存中，按每K存放64條指令排列虛存地址，即2048條指令在虛存中的存放方式為：

第 0 條-第 63 條指令為第0頁（對應(yīng)虛存地址為[0，63]）第64條-第127條指令為第1頁（對應(yīng)虛存地址為[64，127]）

………………………………

－1－ 第1984條-第2047條指令為第31頁（對應(yīng)虛存地址為[1984，2047]）按以上方式，用戶指令可組成32頁。

以此為基礎(chǔ)，給出較為一般的情形：仿真內(nèi)存容量和虛存容量參數(shù)變化時的情形。

3.實現(xiàn)內(nèi)存的slab分配器：

其基本思想是：一次向內(nèi)核獲取整數(shù)頁，slab根據(jù)數(shù)據(jù)結(jié)構(gòu)的大小進行劃分為一個個小的數(shù)據(jù)結(jié)構(gòu)，當需要時直接從該鏈表上摘取一個返回應(yīng)用程序，當應(yīng)用程序釋放時，而非真正釋放，只需要該空間放回到鏈表中，當分散的一頁多塊又聚集一頁時，又會拼成一頁，同時判斷slab空閑的頁數(shù)，如果空閑頁超過一定的頁數(shù)，就會向系統(tǒng)釋放一定的頁數(shù)。一個slab分配器只能管理一個指定大小的數(shù)據(jù)結(jié)構(gòu)分配。

三、項目要求及分析

3.1實現(xiàn)一個內(nèi)存管理的伙伴算法，實現(xiàn)內(nèi)存塊申請時的分配和釋放后的回收。假設(shè)系統(tǒng)的可利用內(nèi)存空間容量為2m個字(地址從0到2m-1)，則在開始運行時，整個內(nèi)存區(qū)是一個大小為2m的空閑塊，在運行了一段時間之后，被分隔成若干占用塊和空閑塊。為了在分配時查找方便起見，我們將所有大小相同的空閑塊建于一張子表中。每個子表是一個雙重鏈表，這樣的鏈表可能有m+1個，將這m+1個表頭指針用向量結(jié)構(gòu)組織成一個表，這就是伙伴系統(tǒng)中的可利用空間表，如圖所示：

分配算法：

當用戶提出大小為n的內(nèi)存請求時，首先在可利用表上尋找結(jié)點大小與n相匹配的子表，若此子表非空，則將子表中任意一個結(jié)點分配之即可；若此子表為空，則需從結(jié)點更大的非空子表中去查找，直至找到一個空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中。

若2k-1 < n ≤ 2k-1，又第k+1個子表不空，則只要刪除此鏈表中第一個結(jié)點并分配給用戶即可；若 2k-2 < n ≤ 2k-1-1，此時由于結(jié)點大小為2k-1 的子表為空，則需從結(jié)點大小為2k 的子表中取出一塊，將其中一半分配給用戶，剩余的一半作為一個新結(jié)點插入在結(jié)點大小為2k-1的子表中，若2k-i-1 < n ≤ 2k-i-1(i為小于是的整數(shù))，并且所有結(jié)點小于2k的子表均為空，則同樣需從結(jié)點大小為2k的子表中取出一塊，將其中2k-i的一小部分分配給用戶，剩余部分分割成若干個結(jié)點分別插入在結(jié)點大小為2k-1、2k-

2、…、2k-i的子表中?；厥账惴ǎ?/p>

在用戶釋放不再使用的占用塊時，系統(tǒng)需將這新的空閑塊插入到可利用空間表中去。這里，同樣有一個地址相鄰的空閑塊歸并成大塊的問題。但是在伙伴系統(tǒng)中僅考慮互為“伙伴”的兩個空閑塊的歸并。

何謂“伙伴”?如前所述，在分配時經(jīng)常需要將一個大的空閑塊分裂成兩個大小相等的存

－2－ 儲區(qū)，這兩個由同一大塊分裂出來的小塊就稱之“互為伙伴”。例如：假設(shè)p為大小為pow(2,k)的空閑塊的初始地址，且p MOD pow(2,k+1)=0，則初始地址為p和p+pow(2,k)的兩個空閑塊互為伙伴。在伙伴系統(tǒng)中回收空閑塊時，只當其伙伴為空閑塊時才歸并成大塊。也就是說，若有兩個空閑塊，即使大小相同且地址相鄰，但不是由同一大塊分裂出來的，也不歸并在一起。

由此，在回收空閑塊時，應(yīng)首先判別其伙伴是否為空閑塊，若否，則只要將釋放的空閑塊簡單插入在相應(yīng)子表中即可；若是，則需在相應(yīng)子表中找到其伙伴并刪除之，然后再判別合并后的空閑塊的伙伴是否是空閑塊。依此重復，直到歸并所得空閑塊的伙伴不是空閑塊時，再插入到相應(yīng)的子表中去。

3.2.設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。

頁式虛擬存儲器實現(xiàn)的一個難點是設(shè)計頁面調(diào)度（置換）算法，即將新頁面調(diào)入內(nèi)存時，如果內(nèi)存中所有的物理頁都已經(jīng)分配出去，就要按某種策略來廢棄某個頁面，將其所占據(jù)的物理頁釋放出來，供新頁面使用。頁面替換算法主要用于如下幾個地方：

(1)虛擬存儲器中，主存頁面（或程序段）的替換。

(2)Cache中的塊替換。

(3)虛擬存儲器的快慢表中，快表的替換。

(4)虛擬存儲器中，用戶基地址寄存器的替換。

在虛擬存儲器中常用的頁面替換算法有如下幾種：

(1)最優(yōu)替換算法，即OPT算法（OPTimal replacement algorithm）。上面介紹的幾種頁面替換算法主要是以主存儲器中頁面調(diào)度情況的歷史信息為依據(jù)的，它假設(shè)將來主存儲器中的頁面調(diào)度情況與過去一段時間內(nèi)主存儲器中的頁面調(diào)度情況是相同的。顯然，這種假設(shè)不總是正確的。最好的算法應(yīng)該是選擇將來最久不被訪問的頁面作為被替換的頁面，這種替換算法的命中率一定是最高的，它就是最優(yōu)替換算法。

要實現(xiàn)OPT算法，唯一的辦法是讓程序先執(zhí)行一遍，記錄下實際的頁地址流情況。根據(jù)這個頁地址流才能找出當前要被替換的頁面。顯然，這樣做是不現(xiàn)實的。因此，OPT算法只是一種理想化的算法，然而，它也是一種很有用的算法。實際上，經(jīng)常把這種算法用來作為評價其它頁面替換算法好壞的標準。在其它條件相同的情況下，哪一種頁面替換算法的命中率與OPT算法最接近，那么，它就是一種比較好的頁面替換算法。(2)先進先出算法，即FIFO算法（First-In First-Out algorithm）。這種算法選擇最先調(diào)入主存儲器的頁面作為被替換的頁面。它的優(yōu)點是比較容易實現(xiàn)，能夠利用主存儲器中頁面調(diào)度情況的歷史信息，但是，沒有反映程序的局部性。因為最先調(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。

(3)最久沒有使用算法，即LRU算法（Least Recently Used algorithm）。這種算法把近期最久沒有被訪問過的頁面作為被替換的頁面。它把LFU算法中要記錄數(shù)量上的“多”與“少”簡化成判斷“有”與“無”，因此，實現(xiàn)起來比較容易。

(4)近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的算法，因為到目前為止最少使用的頁面，很可能也是將來最少訪問的頁面。該算法既充分利用了主存中頁面調(diào)度情況的歷史信息，又正確反映了程序的局部性。但是，這種算法實現(xiàn)起來非常困難，它要為每個頁面設(shè)置一個很長的計數(shù)器，并且要選擇一個固定的時鐘為每個計數(shù)器定時計數(shù)。在選擇被替換頁面時，要從所有計數(shù)器中找出一個計數(shù)值最大的計數(shù)器。因此，通常采用如下一種相 －3－ 對比較簡單的方法。

3.3實現(xiàn)內(nèi)存的slab分配器

slab描述符和空閑對象管理部分成為 slab的管理部分，也可以稱為slab頭

slab的頭可以放在slab自身，也可以放在 slab 之外。如果slab頭放在了slab 之外，那么用戶申請obj時，需要首先訪問 slab頭，slab頭提供未使用free obj的指針

然后再訪問這個free obj的地址。完成這項工作需要訪問2個頁塊。會帶來效率上的損失。slab頭始終位于slab 也存在問題，比如一個頁面只有4K，objsize = 2K，那么slab 頭在slab 上，就意味著，這個4K的頁面只能夠分配一個obj。造成了內(nèi)存的浪費。

如果 頁數(shù)太少，存放的 obj個數(shù)少，那么 增加管理開銷，同時 內(nèi)存使用率低，如果頁數(shù)太多對伙伴內(nèi)存系統(tǒng)不好，所以需要一定的策略妥協(xié)。

這個妥協(xié)過程是有calculate_slab_order 這個函數(shù)來實現(xiàn)的。從 0階（即一頁）到kmalloc的最高階 KMALLOC_MAX_ORDER，挨個嘗試，由cache_estimate這個函數(shù)計算 如果選用order 階，那么能分配 多少個 obj（num），剩余空間是多少（remainder）。所謂剩余空間，就是除去slab頭（如果有的話），除去 obj*num，剩下的邊角料空間是多少。需要分成兩種情況去計算，分成兩種情況的原因，很快就能看到 A)slab頭不在slab上，即 flag & CFLGS_OFF_SLAB == 1的時候 這種情況比較簡單，由于管理數(shù)據(jù)完全不在slab 上，size_tslab_size = PAGE_SIZE <

換句話，slab頭的大小取決于obj的個數(shù)，obj的個數(shù)取決于 slab頭的大小，四、具體實現(xiàn)

4.1實現(xiàn)一個內(nèi)存管理的伙伴算法，實現(xiàn)內(nèi)存塊申請時的分配和釋放后的回收。

程序：

#include #include #include

#define MIN_MOMORY_SIZE 536870912

//隨機產(chǎn)生的最小內(nèi)存空間 #define WORKTIME 1500

//系統(tǒng)工作時間

#define MAX_REQ_SIZE 268435456

//申請空閑內(nèi)存分配的最大容量：256M #define MIN_DUE 30

//使用內(nèi)存塊的最短時間 #define MAX_DUE 90

//使用內(nèi)存塊的最長時間 #define OCCUPY_INTERVAL 60

//每次分配的最大間隔 #define USED 1

//內(nèi)存塊被使用 #define UNUSED 0

//內(nèi)存塊未被使用

//內(nèi)存塊鏈表結(jié)點結(jié)構(gòu) typedefstructbuddy_node { int flag;

//標記空間是否被使用

－4－ int base;

//本塊兒內(nèi)存的基地址

int occupy;

//實際使用空間大小

int fragment;

//碎片大小

intduetime;

//使用時間

structbuddy_node *nextPtr;

//指向下一個結(jié)點 } Buddy, *BuddyPtr;

IndexTable table[INDEX_SIZE];//使用哈希表管理伙伴系統(tǒng) int ready = 0;

//需要分配內(nèi)存的時刻 intavailSpace;

//可分配空間大小 inttotalFragment = 0;

//總碎片大小

//函數(shù)：添加結(jié)點（形參為內(nèi)存塊結(jié)點的信息）

void insert_node(inti, intinbase, int f, intocc, int frag, int d){ BuddyPtrnewnodePtr = NULL, prePtr = NULL, curPtr = NULL;

newnodePtr =(BuddyPtr)malloc(sizeof(Buddy));//分配結(jié)點 newnodePtr->base = inbase;newnodePtr->flag = f;newnodePtr->occupy = occ;newnodePtr->fragment = frag;newnodePtr->duetime = d;newnodePtr->nextPtr = NULL;

if(table[i].headPtr == NULL)

table[i].headPtr = newnodePtr;

else { curPtr = table[i].headPtr;prePtr = NULL;

//按地址順序插入內(nèi)存塊

while(curPtr&&curPtr->base nextPtr;

}

if(prePtr == NULL){

//插在最前 newnodePtr->nextPtr = curPtr;

table[i].headPtr = newnodePtr;

}

else if(curPtr == NULL){

//插在最后 prePtr->nextPtr = newnodePtr;

}

else {

//插在中間 prePtr->nextPtr = newnodePtr;newnodePtr->nextPtr = curPtr;

－5－

}

} }

//函數(shù)：刪除結(jié)點

intdelete_node(inti, BuddyPtrdelPtr){ BuddyPtrprePtr = NULL, curPtr = NULL;intbasehold = delPtr->base;

curPtr = table[i].headPtr;

while(curPtr!= delPtr){ //尋找要刪除的結(jié)點的位置 prePtr = curPtr;curPtr = curPtr->nextPtr;

}

if(prePtr == NULL)

//要刪除的結(jié)點在最前

table[i].headPtr = curPtr->nextPtr;

else

//要刪除的結(jié)點不在鏈表的最前 prePtr->nextPtr = curPtr->nextPtr;

free(curPtr);

//釋放結(jié)點

return basehold;

//返回刪除的內(nèi)存塊結(jié)點的基地址 }

//函數(shù)：伙伴系統(tǒng)的分配算法 void buddy_allocate(inttime_slice){ inti, j, size, due;int state = 0;

//分配狀態(tài)：0為未分配，1為已分配 intinbase, basehold;BuddyPtrcurPtr = NULL;

if(ready == time_slice){ //到達分配內(nèi)存的時刻 printf(“Time %d:”, time_slice);

size = 1 + rand()% MAX_REQ_SIZE;

//申請使用內(nèi)存的大小

due = MIN_DUE + rand()%(MAX_DUEsize;curPtr->duetime = due + ready;

//修改可系統(tǒng)分配空間和碎片大小 availSpace-= table[i].nodesize;totalFragment += curPtr->fragment;

state = 1;//標記已分配

break;

}

//空閑塊的大小剛大于申請大小的2倍

else { basehold = delete_node(i, curPtr);//刪除較大的空閑塊并保留其基地址 inbase = basehold + table[i].nodesize;

j = i;

//分割空閑塊

do {

j--;inbase-= table[j].nodesize;

//設(shè)置要添加內(nèi)存塊結(jié)點的基地址 insert_node(j, inbase, UNUSED, 0, 0, 0);//添加較小的空閑塊 printf(“A block cut takes placen”);

} while(table[j].nodesize / size > 1);

//分配

insert_node(j, basehold, USED, size, table[j].nodesizesize;

state = 1;//標記已分配

}

}

//塊被占用，查看下一結(jié)點

else curPtr = curPtr->nextPtr;

}

}

} printf(“Allocated %d,Fragment %d,Due %dn”, size, totalFragment, ready+due);

－7－

}

else if((availSpace< size)&&((availSpace + totalFragment)>= size))printf(“Allocation failed because of fragment!n”);

else printf(“Allocation failed because of no enough unused space!n”);

ready +=(1 + rand()% OCCUPY_INTERVAL);//下次需要分配內(nèi)存的時刻

} }

//函數(shù)：伙伴系統(tǒng)的回收算法 void buddy_retrieve(inttime_slice){ inti, basehold, dif;int f = 0;intModnext=0;BuddyPtrcurPtr = NULL, todelPtr = NULL;

//依次查找，并回收需要回收的塊

for(i = 0;i< INDEX_SIZE;i ++){

if(table[i].headPtr){ curPtr = table[i].headPtr;

while(curPtr){

if((curPtr->flag == USED)&&(curPtr->duetime == time_slice)){//需要回收

//修改可系統(tǒng)分配空間和碎片大小 availSpace += table[i].nodesize;totalFragment-= curPtr->fragment;

//回收為空閑塊 curPtr->flag = UNUSED;curPtr->occupy = 0;curPtr->fragment = 0;curPtr->duetime = 0;printf(“Time %d:Retrieve %d,Fragment %dn”, time_slice, table[i].nodesize, totalFragment);

} curPtr = curPtr->nextPtr;

}

}

}

//合并空閑塊

for(i = 0;i< INDEX_SIZE;i ++){

if(table[i].headPtr){

－8－ curPtr = table[i].headPtr;

while(curPtr&&curPtr->nextPtr){

//將地址連續(xù)且都為空閑的塊合并后加入下一級的鏈表中

if(curPtr->flag == UNUSED &&(curPtr->nextPtr)->flag == UNUSED){ dif =(curPtr->nextPtr)->base-curPtr->base;

Modnext =((int)(curPtr->nextPtr->base))%(2*table[i].nodesize);

if((dif == table[i].nodesize)&&(Modnext==0)){

//刪除兩個結(jié)點 todelPtr = curPtr;curPtr = curPtr->nextPtr;basehold = delete_node(i, todelPtr);todelPtr = curPtr;curPtr = curPtr->nextPtr;delete_node(i, todelPtr);insert_node(i+1, basehold, UNUSED, 0, 0, 0);//添加合并后的結(jié)點 printf(“Two blocks mergen”);

}

else curPtr = curPtr->nextPtr;

}

else curPtr = curPtr->nextPtr;

}

}

} }

//函數(shù)：伙伴系統(tǒng)的處理過程 void buddy_system(void){ inttime_slice = 0;

//在每個時間片內(nèi)使用分配算法和回收算法

for(;time_slice< WORKTIME;time_slice ++){ buddy_allocate(time_slice);

//分配算法 buddy_retrieve(time_slice);

//回收算法

} }

int main(intargc, char *argv[]){ intmemory_size;

－9－ ini_index();

//初始化哈希索引表 srand(time(NULL));

//設(shè)置隨機數(shù)種子

//隨機產(chǎn)生需要管理的內(nèi)存大?。?12M ~ 1G

memory_size = MIN_MOMORY_SIZE + rand()% MIN_MOMORY_SIZE;printf(“The size of memory is:%dn”, memory_size);

int_system(memory_size);

//初始化伙伴系統(tǒng)

buddy_system();

//伙伴系統(tǒng)的處理過程

printf(“Time %d:System execution stops and the spaces are all freed.n”, WORKTIME);

free_system();

//釋放所有結(jié)點

system(“pause”);

return 0;}

4．2.設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。程序：

#include #include #include #define TRUE 1 #define FALSE 0 #define INVALID-1 #define NUL 0 #define total_instruction 320 //指令流長 #define total_vp 32

//虛頁長 #define clear_period 50

//清零周期

typedefstruct {

intpn;

//頁號 intpfn;

// 面號

int counter;

// 一個周期內(nèi)訪問該頁面的次數(shù) int time;

// time為訪問時間 }pl_type;pl_typepl[total_vp];//頁面結(jié)構(gòu)數(shù)組

structpfc_struct{

//頁面控制結(jié)構(gòu) intpn,pfn;structpfc_struct *next;};typedefstructpfc_structpfc_type;

－10－

pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];/*

Name: void Lprintf(void)

Achieve: 格式控制 */ void Lprintf(void){ inti,j;printf(“|”);

for(i = 1;i<=6;i++)

{

for(j = 1;j<=9;j++)printf(“-”);

if(i!=6)printf(“+”);

} printf(“|n”);

} /*

Name: void initialize(inttotal_pf)

Achieve:初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) */ void initialize(inttotal_pf){ inti;diseffect=0;

for(i=0;i

{ pl[i].pn=i;pl[i].pfn=INVALID;

//置頁面控制結(jié)構(gòu)中的頁號，頁面為空

pl[i].counter=0;pl[i].time=-1;//頁面控制結(jié)構(gòu)中的訪問次數(shù)為0，時間為-1

}

for(i=1;i

{ pfc[i-1 ].next=&pfc[i];pfc[i-1].pfn=i-1;//建立pfc[i-1]和pfc[i]之間的連接

}

pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0];

//頁面隊列的頭指針為pfc[0] } /*

－11－ Name:void FIFO(inttotal_pf)

Achieve:先進先出法（Fisrt In First Out）*/

void FIFO(inttotal_pf){ inti,j;pfc_type *p;//中間變量

initialize(total_pf);//初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)

busypf_head=busypf_tail=NULL;//忙頁面隊列頭，隊列尾鏈接

for(i=0;i

if(pl[page[i]].pfn==INVALID)

//頁面失效

{

diseffect+=1;//失效次數(shù)

if(freepf_head==NULL)//無空閑頁面

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head;//釋放忙頁面隊列的第一個頁面

freepf_head->next=NULL;//表明還是缺頁*/

busypf_head=p;

}

p=freepf_head->next;

freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

freepf_head->next=NULL;//使busy的尾為null

if(busypf_tail==NULL)

{

busypf_tail=busypf_head=freepf_head;

}

else

{

busypf_tail->next=freepf_head;

busypf_tail=freepf_head;

}

freepf_head=p;

} } printf(“%6.3f”,1-(float)diseffect/320);} /*

Name: void LRU(inttotal_pf)

Achieve: 最近最久未使用（Least Recently Used）*/

－12－ void LRU(inttotal_pf){ intmin,minj,i,j,present_time;//minj為最小值下標

initialize(total_pf);present_time=0;for(i=0;i

if(pl[page[i]].pfn==INVALID)//頁面失效

{

diseffect++;

if(freepf_head==NULL)//無空閑頁面

{

min=32767;//設(shè)置最大值

for(j=0;j

{

if(min>pl[j].time&&pl[j].pfn!=INVALID)

{

min=pl[j].time;

minj=j;

}

}

freepf_head=&pfc[pl[minj].pfn];

//空出一個單元

pl[minj].pfn=INVALID;

pl[minj].time=0;

freepf_head->next=NULL;

}

pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效

pl[page[i]].time=present_time;

freepf_head=freepf_head->next;//減少一個free 頁面

}

else

{

pl[page[i]].time=present_time;//命中則增加該單元的訪問次數(shù)

present_time++;

} } printf(“%6.3f”,1-(float)diseffect/320);} /* Name:void OPT(inttotal_pf)

Achieve:最佳置換算法（Optimal）*/ void OPT(inttotal_pf){

－13－ inti,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i

if(pl[page[i]].pfn==INVALID)

/*頁面失效*/

{

diseffect++;

if(freepf_head==NULL)

/*無空閑頁面*/

{

for(j=0;j

{

if(pl[j].pfn!=INVALID)

dist[j]=32767;

else

dist[j]=0;

}

for(j=0;j

{

if((pl[j].pfn!=INVALID)&&(dist[j]==32767))

{

dist[j]=j;

}

}

max=0;

for(j=0;j

if(max

{

max=dist[j];

maxpage=j;

}

freepf_head=&pfc[pl[maxpage].pfn];

freepf_head->next=NULL;

pl[maxpage].pfn=INVALID;

}

pl[page[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

} } printf(“%6.3f”,1-(float)diseffect/320);} /*

Name: vodi LFU(inttotal_pf)

Achieve:最不經(jīng)常使用法（Least Frequently Used）

－14－ */ void LFU(inttotal_pf)

{ inti,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i

if(pl[page[i]].pfn==INVALID)//頁面失效

{

diseffect++;

if(freepf_head==NULL)//無空閑頁面

{

min=32767;

//獲取counter的使用用頻率最小的內(nèi)存

for(j=0;j

{

if(min>pl[j].counter&&pl[j].pfn!=INVALID)

{

min=pl[j].counter;

minpage=j;

}

}

freepf_head=&pfc[pl[minpage].pfn];

pl[minpage].pfn=INVALID;

pl[minpage].counter=0;

freepf_head->next=NULL;

}

pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效

pl[page[i]].counter++;

freepf_head=freepf_head->next;//減少一個free 頁面

}

else

{

pl[page[i]].counter;

pl[page[i]].counter=pl[page[i]].counter+1;

} } printf(“%6.3f”,1-(float)diseffect/320);}

int main(int){

intS,i;

－15－ srand((int)getpid());

for(i=0;i

{

S=(int)rand()%320;

a[i]=S;

//任選一指令訪問點

a[i+1]=a[i]+1;//順序執(zhí)行一條指令

a[i+2]=(int)rand()%a[i+1];//執(zhí)行前地址指令m'

a[i+3]=a[i+2]+1;//順序執(zhí)行一條指令

a[i+4]=(int)rand()%(319-a[i+2]-1)+a[i+2]+2;//執(zhí)行后地址指令

} for(i=0;i

{

page[i]=a[i]/10;

offset[i]=a[i]%10;}

printf(“FrametOPTtFIFOtLRUtLFU n”);for(i=4;i<=32;i++)//用戶內(nèi)存工作區(qū)從4個頁面到32個頁面

{

printf(“%dt”,i);OPT(i);printf(“t”);

FIFO(i);printf(“t”);

LRU(i);

printf(“t”);

LFU(i);

printf(“n”);} system(“pause”);return 0;} 4.3 實現(xiàn)內(nèi)存的slab分配器 程序: #include #include #include using namespace std;－16－

－17－

}

五、調(diào)試運行結(jié)果

－18－ 5.1 實現(xiàn)一個內(nèi)存管理的伙伴算法

5.2設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。

－19－

5.3 實現(xiàn)內(nèi)存的slab分配器

六、所遇問題及解決方法

1.在寫第一個程序的時候，對樹的合并在之前的學習中，有比較多的學習，數(shù)據(jù)結(jié)構(gòu)中此程序有詳細的介紹，因此在編寫這個程序的時候，比較順利的完成了要求。但要求中需要產(chǎn)生一些隨機的數(shù)據(jù)，重新對隨機仿真函數(shù)進行回顧，最后較為順利的完成了程序。2.第二個程序，要求隨機產(chǎn)生一些數(shù)據(jù)，對srand()和rand()函數(shù)定義和產(chǎn)生指令序列，在進一步的學習中，完成了這些函數(shù)，仿真內(nèi)存容量和虛存容量參數(shù)變化時的情形，對此不太熟悉，四個算法對要求較高，在完成算法的學習后，完成了程序。

3.第三個程序因不太理解其要求，上網(wǎng)搜尋了一些代碼，但對其最后的結(jié)果依然沒有得出，為此詢問了同學，但不知是否正確。

－20－