操作系統實驗4

題目1：編寫頁面內存的LRU替換算法

在實驗3基礎上考慮，如果當前分配的內存或保存頁面的數據項已經被用完，這時再有新的網頁請求，需要對已在內存中的網頁數據進行替換，本實驗內容需要使用LRU算法來對內存中的網頁數據進行替換

題目2：編寫頁面內存的LFU替換算法

實現LFU（最少訪問頻率的頁面替換）算法來管理內存頁面

實驗報告要求：

實驗報告封面如下頁所示。

按照題目要求，完成相關實驗題目。

2.1報告中要包含完成此題目所查閱的一些關鍵技術材料。例如內存結構的設計、分配管理、回收方法等內容。

2.2 報告中有實現的關鍵技術點源代碼，源代碼書寫要有一定的規范，源代碼中有相關的注釋

2.3 作為擴展，在界面上能夠定時給出當前內存的占用情況。因此根據上面的題目，可以適當地增加對其它方面的信息監控。

?

?

?

?

?

?

操作系統實驗報告四

?

?

?

???????????????????????姓名：許愷

???????????????????????學號：2014011329

???????????????????????日期：12月7日

?

?

?

?

?

?

?

?

?

?

一．構思想法

題目1：編寫頁面內存的LRU替換算法

因為web4和3太像了，所以并沒有什么難度，我只需要將替換的頁面改一下就可以了，所以我加了一個屬性，就是這個頁面是第幾個被申請的，這樣既可以記錄網頁申請的流量，也可以將在內存中的數字最小的那個替換掉，也就是LRU算法所講的最久未被用的那個，然后加上時間函數計算出每次用的時間進行分析報告就可以了。

題目2：編寫頁面內存的LFU替換算法

其實我想說我web3用的就是LFU替換算法，老師可以看我的web3報告，或者這份報告也可以，這份報告會給出對于一串申請序列，兩種方法比較的時間分析。

?

二．源代碼以及結果貼圖和分析

題目1：編寫頁面內存的LRU替換算法

關鍵代碼（有修改）：

Webserver4.cpp： // webserver4.cpp : 定義控制臺應用程序的入口點。 // #include "stdafx.h" #include <iostream> #include <Winsock2.h> #include <windows.h> #include <string> #include <fstream> #include "PageMemo.h" PageMemo Mem; //初始化內存中的網頁 SOCKET socketconn; static string dir = "D:\\xukai\\學習\\操作系統實驗\\網頁"; //文件路徑 int num = 1; //請求網頁次數 #include "Thread.h" #include "CMyTask.h" #pragma comment(lib, "ws2_32.lib") using namespace std;void main(int argc, _TCHAR* argv[]) {CMyTask taskObj;CThreadPool threadPool(10);double alltime=0;//運行總時間 LARGE_INTEGER large_interger;double dff;__int64 c1, c2;QueryPerformanceFrequency(&large_interger);dff = large_interger.QuadPart;QueryPerformanceCounter(&large_interger);//初始化WinSock庫 WORD wVersionRequested;WSADATA wsaData;cout << "初始化庫成功" << endl;wVersionRequested = MAKEWORD(2, 2);int wsaret = WSAStartup(wVersionRequested, &wsaData);if (wsaret)return;//創建SOCKET SOCKET socketSrv;socketSrv = socket(AF_INET, SOCK_STREAM, 0);if (socketSrv == INVALID_SOCKET)return;cout << "創建socket成功" << endl;SOCKADDR_IN addrSrv;addrSrv.sin_addr.S_un.S_addr = htonl(INADDR_ANY);addrSrv.sin_family = AF_INET;addrSrv.sin_port = htons(80);//綁定套接字if (bind(socketSrv, (struct sockaddr*)&addrSrv, sizeof(SOCKADDR))){//關閉連接shutdown(socketSrv, 1);closesocket(socketSrv);WSACleanup();return;}cout << "綁定套接字成功！" << endl;//等待客戶端連接 SOCKADDR_IN addrCli;int len = sizeof(SOCKADDR);//監聽端口if (listen(socketSrv, 5) == SOCKET_ERROR){printf("監聽失敗!\n");}while (true){socketconn = accept(socketSrv, (SOCKADDR*)&addrCli, &len);//接受連接if (socketconn == SOCKET_ERROR){printf("接受連接失敗!\n");return;}cout << "連接成功" << endl;//用QueryPerformanceCounter()來計時 微秒 c1 = large_interger.QuadPart;taskObj.SetData((void*)0); //將任務內容設到對象里threadPool.AddTask(&taskObj); //將任務對象添加到線程池的任務隊列 CThreadPool::Threadfunction();QueryPerformanceCounter(&large_interger);c2 = large_interger.QuadPart;alltime = alltime + (c2 - c1) / dff;printf("本次用時%lf微秒\n", (c2 - c1) / dff);cout << "到現在為止共用時間：" << alltime << "微秒。" << endl;num++;}shutdown(socketSrv, 1);closesocket(socketSrv);//關閉連接 WSACleanup(); }PageMemo.h: #pragma once #include <string> #include <fstream> #include <iostream> using namespace std; /* 用來放網頁的內存結構類 */ class PageMemo { public:/****內存結構構造函數，建立10個頁面信息，從磁盤寫入內存10個網頁信息****/PageMemo(){//ifstream fp[10]; //用10個文件讀的對象//int i;//string which = "";//for (i = 0; i < 10; i++)//{// which = to_string(i);// file[i] = "D:\\xukai\\學習\\操作系統實驗\\網頁\\" + which + ".html ";// //cout << file[i] << endl;// fp[i].open(file[i], std::ios::binary);// //打開文件失敗// if (!fp[i].is_open())// {// cout << "請求文件" << which + ".html" << "不存在" << endl;// }// else//打開文件成功并讀取// {// char buffer[1024];// while (fp[i].good() && !fp[i].eof())// {// fp[i].getline(buffer, 1024);// //cout << buffer << endl;// //將讀取的內容追加入sendBuf中// Page[i].append(buffer);// //cout << Page[i] << endl;// buffer[0] = '\0';// }// }// fp[i].close();//} }~PageMemo(){}/*****LRU算法的函數，找出前面最久未使用的頁面替換*/int LRU(){int M = lru[0], X = 0;for (int i = 1; i < 10; i++) {if (lru[i] < M){X = i;M = lru[i];}}return X;}/****求出被用過次數最少的內存中的頁面，用的最普通的算法****/int Min(){int M = User_f[0], X = 0;for (int i = 1; i < 10; i++){if (User_f[i] < M){X = i;M = User_f[i];}}return X;}/****在屏幕上打印當前頁面的路徑信息和使用次數****/void print(){cout << "現在要輸出我當前的網頁的內存信息：" << endl;for (int i = 0; i < 10; i++){cout << " " << file[i] << " " << User_f[i]<<" "<<lru[i] << endl;}}//得到第i條路徑的內容string getfile(int i) { return file[i]; }//得到第i個頁面的內容string getPage(int i) { return Page[i]; }//得到第i個頁面使用次數int getUser_f(int i) { return User_f[i]; }//使用過一次這個網頁了，使用次數+1void plusone(int i) { User_f[i]++; }//修改file內容函數void writefile(int i, string f) { file[i] = f; }//修改Page內容函數void writePage(int i, string p) { Page[i] = p; }//修改User_f值的函數void writeUser_f(int i, int n) { User_f[i] = n; }//當網頁被使用，修改他的lru void writelru(int i, int n) { lru[i] = n; } private:string file[10]; //頁面路徑string Page[10]; //頁面信息int User_f[10] = { 0 }; //使用次數int lru[10] = { 0 }; //此網頁第幾個被使用，最小的就是最久沒被用的 };CMyTask.h: #pragma once #include "Thread.h" #include "windows.h" #include "PageMemo.h" class CMyTask : public CTask { public:CMyTask() {}inline int Run(){printf("Process startup!\n");//init WORD wVersionRequested;WSADATA wsaData;wVersionRequested = MAKEWORD(2, 2);WSAStartup(wVersionRequested, &wsaData);DWORD pid = ::GetCurrentProcessId();sockaddr_in sa;int add_len = sizeof(sa);if (socketconn != INVALID_SOCKET){getpeername(socketconn, (struct sockaddr *)&sa, &add_len);//while (1)//{//連接成功后與客戶端進行會話char recvBuff[10000];string sendBuf;string locDir;ifstream fp;//接收請求if (recv(socketconn, recvBuff, 10000, 0) == SOCKET_ERROR){printf("%d\n", socketconn);printf("error!");getchar();return 0;}//讀取http請求頭string recvBuffer = recvBuff;int posGet = recvBuffer.find("GET", 0);int posHttp = recvBuffer.find("HTTP", 0);//截取html文件路徑for (int pos = posGet + 4; pos < posHttp; pos++){if (recvBuffer[pos] == '/'){locDir.push_back('\\');continue;}locDir.push_back(recvBuffer[pos]);}locDir = dir + locDir;int i;//打開http請求文件進行讀取for (i = 0; i < 10; i++) //看看內存里有沒有現成的 {//cout << locDir << endl;//cout << Mem.getfile(i) << endl;if (strcmp(locDir.c_str(), Mem.getfile(i).c_str()) == 0) //匹配字符串 {cout << "在內存中找到相應的頁面信息啦！！！" << endl;Mem.plusone(i); //使用次數+1//cout << Mem.getPage(i) << endl;sendBuf = Mem.getPage(i);break;}}if (i == 10) //內存中沒有，從磁盤中調取 {cout << "555555,/(ㄒoㄒ)/~~還得從磁盤取~~" << endl;fp.open(locDir.c_str(), std::ios::binary);//打開文件失敗if (!fp.is_open()){cout << "請求文件" << locDir.c_str() << "不存在" << endl;}else//打開文件成功并讀取 {char buffer[1024];while (fp.good() && !fp.eof()){fp.getline(buffer, 1024);//將讀取的內容追加入sendBuf中 sendBuf.append(buffer);buffer[0] = '\0';}}fp.close();//int x = Mem.Min(); //找到最不經常用的頁int x = Mem.LRU(); //找到LRU算法的結果Mem.writefile(x, locDir); //把調用的頁的路徑也放內存里Mem.writePage(x, sendBuf); //把調用的頁放到內存里Mem.writeUser_f(x, 1); //將使用次數置為一 Mem.writelru(x, num);}Mem.print();//響應請求，將頁面信息發送到客戶端//cout << sendBuf << endl;if (send(socketconn, sendBuf.c_str(), sendBuf.length(), 0) == SOCKET_ERROR){return 0;}shutdown(socketconn, 1);//關閉連接i = 0; //重置計數的i closesocket(socketconn);}else{printf("[%d]fail accept:%d\n", pid, ::WSAGetLastError());}return 0;} };線程池（未修改）： Thread.h: #pragma once #ifndef __THREAD_H #define __THREAD_H #include "PageMemo.h" #include <vector> #include <string> #include <pthread.h> #pragma comment(lib,"x86/pthreadVC2.lib") using namespace std;/** * 執行任務的類，設置任務數據并執行 */ class CTask { protected:string m_strTaskName; /** 任務的名稱 */void* m_ptrData; /** 要執行的任務的具體數據 */ public:CTask() {}CTask(string taskName) //任務類的重載：設置任務名，設置任務內容為空 {m_strTaskName = taskName;m_ptrData = NULL;}virtual int Run() = 0; /*啟動任務的虛函數*/void SetData(void* data); /** 設置任務數據 */public:virtual ~CTask() {} //虛擬析構函數 };/** * 線程池管理類的實現 */ class CThreadPool { private:static vector<CTask*> m_vecTaskList; /** 任務列表 */static bool shutdown; /** 線程退出標志 */int m_iThreadNum; /** 線程池中啟動的線程數 */pthread_t *pthread_id;static pthread_mutex_t m_pthreadMutex; /** 線程同步鎖 */static pthread_cond_t m_pthreadCond; /** 線程同步的條件變量 */protected:static int MoveToIdle(pthread_t tid); /** 線程執行結束后，把自己放入到空閑線程中 */static int MoveToBusy(pthread_t tid); /** 移入到忙碌線程中去 */static void* ThreadFunc(void*); /** 新線程的線程回調函數 */int Create(); /** 創建線程池中的線程 */public:static void Threadfunction(); //在主函數中調用的任務函數CThreadPool(int threadNum = 10);int AddTask(CTask *task); /** 把任務添加到任務隊列中 */int StopAll(); /** 使線程池中的線程退出 */int getTaskSize(); /** 獲取當前任務隊列中的任務數 */ };#endifThread.cpp: #include "stdafx.h" #include "Thread.h" #include <iostream> void CTask::SetData(void * data) //設置任務的具體內容 {m_ptrData = data; }vector<CTask*> CThreadPool::m_vecTaskList; //任務列表 bool CThreadPool::shutdown = false; //設置關閉為0 pthread_mutex_t CThreadPool::m_pthreadMutex = PTHREAD_MUTEX_INITIALIZER; //設置變量值 pthread_cond_t CThreadPool::m_pthreadCond = PTHREAD_COND_INITIALIZER;/** * 線程池管理類構造函數 */ CThreadPool::CThreadPool(int threadNum) {this->m_iThreadNum = threadNum; //用參數設置線程數量cout << "I will create " << threadNum << " threads\n" << endl;Create(); //調用創建線程的函數 }/** * 線程回調函數 */ void* CThreadPool::ThreadFunc(void*) {return (void*)1; }void CThreadPool::Threadfunction() {pthread_t tid = pthread_self();printf("tid %lu run\n", tid);vector<CTask*>::iterator iter = m_vecTaskList.begin(); //添加迭代器從任務列表開頭 /** * 取出一個任務并處理之 */CTask* task = *iter;if (iter != m_vecTaskList.end()){task = *iter;m_vecTaskList.erase(iter);}pthread_mutex_unlock(&m_pthreadMutex);task->Run(); /** 執行任務 */printf("tid:%lu idle\n", tid);}int CThreadPool::MoveToIdle(pthread_t tid) {return 0; }int CThreadPool::MoveToBusy(pthread_t tid) {return 0; }/** * 往任務隊列里邊添加任務并發出線程同步信號 */ int CThreadPool::AddTask(CTask *task) {pthread_mutex_lock(&m_pthreadMutex);this->m_vecTaskList.push_back(task);pthread_mutex_unlock(&m_pthreadMutex);pthread_cond_signal(&m_pthreadCond);return 0; }/** * 創建線程 */ int CThreadPool::Create() {pthread_id = (pthread_t*)malloc(sizeof(pthread_t) * m_iThreadNum);for (int i = 0; i < m_iThreadNum; i++){pthread_create(&pthread_id[i], NULL, ThreadFunc, NULL);}return 0; }/** * 停止所有線程 */ int CThreadPool::StopAll() {/** 避免重復調用 */if (shutdown){return -1;}printf("Now I will end all threads!!\n");/** 喚醒所有等待線程，線程池要銷毀了 */shutdown = true;pthread_cond_broadcast(&m_pthreadCond);/** 阻塞等待線程退出，否則就成僵尸了 */for (int i = 0; i < m_iThreadNum; i++){pthread_join(pthread_id[i], NULL);}free(pthread_id);pthread_id = NULL;/** 銷毀條件變量和互斥體 */pthread_mutex_destroy(&m_pthreadMutex);pthread_cond_destroy(&m_pthreadCond);return 0; }/** * 獲取當前隊列中任務數 */ int CThreadPool::getTaskSize() {return m_vecTaskList.size(); }

?

?

結果貼圖：（因為我有10個內存頁面，當我輸入，第0，1,2,3,4,5,6,7,8,9,2，23,5，54,4，456,3,2，4,4356,9個頁面時的結果，LRU）

0，

?

。

。

。

9,

23,

?

54,

?

2，

?

456,

?

3,

?

4356,

?

3，

?

分析：我們發現從外存調入的大概會用到0.08微秒以上，而從內存中直接用的用時在0.07微秒左右或以下，可看出從內存中是快的，當然可能也跟文件的大小有關系，但是不影響大局。

?

?

LFU算法：

0，

?

。

。

9,

?

23,

?

54,

?

2，

?

456,

?

3,

?

4356,

?

3，

?

?

分析：LFU的算法時間就很明顯了，從外存拿的用時0.1微秒多，而從內存拿的只用了0.04微秒左右，總時間用了1.41638微秒，而LRU算法用了1.17903微秒，在這個序列上LRU算法要比LFU算法要快一些，雖然只實驗了一個序列，但是大部分序列LRU算法都是較好的一種算法。

三．查閱的文獻

1.http://blog.csdn.net/morewindows/article/details/6854764 時間函數集錦

四．體會感想

其實沒什么感想，因為和web3一樣，而且有很多同學web3就把這個做了，恩，就這樣，沒什么難度，時間函數也是一查就有。沒了。

轉載于:https://www.cnblogs.com/xukaiae86/p/6444985.html

總結

以上是生活随笔為你收集整理的操作系统实验报告四的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。