天津科技大学操作系统实验报告

2015-2016学年第一学期

计算机操作系统实验报告

专 业：计算机科学与技术

班 级：

学 号： 姓 名： 日 期：

实验一 Windows多线程

【开发语言及实现平台或实验环境】

C++/C#

Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET

【实验目的】

(1) 进一步理解操作系统的并发性；

(2) 了解Windows线程创建方法，并通过查阅资料理解各参数的含义； (3) 了解多线程程序设计方法，并进行简单应用。

【实验要求】

(1) 逐程序进行简要分析、运行各程序并仔细阅读注释；

(2) 查阅MSDN或其他资料，掌握相关系统调用使用方法和参数含义； (3) 完成实验报告。

【实验结果与分析】 （1）1-1.cpp程序 运行1-1.cpp结果：

将main函数中注释掉的Sleep语句让其可用，运行结果为：

1

分析原因：

Sleep（0）的作用为语句可观察线程1和主线程并发执行。输出结果“main thread is running /thread1 is running”。没有添加的线程1运行结束只输出“main thread is running”。

（2）1-2.cpp程序 运行1-2.cpp结果：

分析原因：

1-2.cpp文件使用的是时间片轮转方法调度的主线程、线程1、线程2.因此不需要sleep语句就可将主线程调度。因为在两个线程中存在共享变量，因此执行结果出现不可再现性。

（3）1-3.cpp程序 运行1-3.cpp结果：

2

将main函数中注释掉的Sleep语句让其可用，运行结果为：

将两个子函数中注释掉的Sleep语句让其可用，运行结果：

3

分析原因：

加入两个sleep（1）后，有可能到thread1 is sell tickets:时间片就停了，tickets没--,还可以运行thread2 is sell tickets:\"<【实验思考及总结】 ………………………

（1）加入循环，使得两个进程可以交替执行。 （2）Sleep是阻塞线程函数。它会在当前语句阻塞一段时间，参数是以1/1000秒为单位的。 （3）线程也有父子关系。父进程退出后子进程也会退出。

（4）不可再现性：两个进程同时迈出同一部步，两个进程中存在共享变量。 .

4

实验二 Windows线程同步机制

【开发语言及实现平台或实验环境】

C++/C#

Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET

【实验目的】

(1) 了解Windows线程同步机制；

(2) 了解互斥体，并通过查阅资料理解互斥体对象的使用方法； (3) 了解事件，并通过查阅资料理解事件对象的使用方法； (4) 了解关键区，并通过查阅资料理解关键区对象的使用方法； (5) 了解信号量，并通过查阅资料理解信号量对象的使用方法； (6) 利用Windows线程同步机制，模拟生产者消费者问题。

【实验要求】

(1) 逐程序进行简要分析、运行各程序并仔细阅读注释；

(2) 查阅MSDN或其他资料，掌握相关系统调用使用方法和参数含义；(3) 完成实验报告。

【实验结果与分析】 （1）2-1(mutex).cpp 程序

运行2-1(mutex).cpp 结果：

5

将两个子函数中注释掉的Sleep语句让其可用，运行结果：

6

（2）2-2(event).cpp 程序 运行2-2(event).cpp 结果：

7

将两个子函数中注释掉的Sleep语句让其可用，运行结果：

8

（3）2-3(critical_section).cpp 程序 运行2-3(critical_section).cpp 结果：

9

将两个子函数中注释掉的Sleep语句让其可用，运行结果：

10

分析原因：

2-1(mutex).cpp 、2-2(event).cpp、2-3(critical_section).cpp的处理方式相同，不会出现销售出0号票的情况原因相同：

修改之前，在指定暂停的时间Sleep(1000)内，thread1和thread2随机售票，出现多种情况；将两个子函数中注释掉的Sleep（1）语句让其可用后，thread1和thread2交替售票，即thread1在其暂停的时间Sleep(1)内，thread2获得了对共享对象hMutex的所有权，开始售票，同理当thread2在其暂停的时间Sleep(1)内，thread1获得了对共享对象hMutex的所有权，开始售票，这样thread1和thread2就实现了交替售票，不会出现销售出0号票的情况。

11

（4）2-4(Producer_Consumer).cpp 程序 运行2-4(Producer_Consumer).cpp 结果：

将两个子函数中注释掉的while语句让其可用，运行结果：

12

分析原因：

修改之前，在指定暂停时间sleep（20）内，producer和consumer只能执行一次；将两个子函数中注释掉的while语句让其可用后，producer和consumer在指定暂停时间sleep（20）内，随机循环获得共享对象的所有权，进行生产或消费，从而出现多种结果。

（5）2-4(Producer_Consumer)1.cpp 程序 运行2-4(Producer_Consumer)1.cpp 结果：

13

【实验思考及总结】 ………………………

（1）Sleep(10)使当前线程放弃目前的时间片，并且在10ms内不会被再次调度。 （2）进程也有父子关系。父进程退出后子进程也会退出。

（3）线程之间的同步使用一些核心对象：如thread, process, evnet, mutex, semaphore.。 在线程之间使用等待函数如WaitForSingleObjects, WaitForMultipleObjects.

（4）等待函数使用核心对象的handle作为参数，如果handle被激发，则执行下一步。 handle被激发的条件： (handle是一段内存指针，为了掩藏内部实现而做的一个类型转化指针）激发：－－－资源未被占用。未激发： －－－资源正在被占用。 eg：

1) thread, process被终止，则激发。

2) event: 要通过它的API来手动激发，是最灵活的激发方式，可被所有线程使用。 3) mutex: 没被任何线程所拥有，则激发。

14

实验三 Windows线程通信

【开发语言及实现平台或实验环境】

C++/C#

Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET

【实验目的】

(1) 了解Window线程通信方法；

(2) 了解匿名管道，并通过查阅资料理解匿名管道的使用方法； (3) 了解命名管道，并通过查阅资料理解命名管道的使用方法；

【实验要求】

(1) 逐程序进行简要分析、运行各程序并仔细阅读注释；

(2) 查阅MSDN或其他资料，掌握相关系统调用使用方法和参数含义； (3) 完成实验报告。

【实验结果与分析】

(1)匿名管道：先编译Child工程，然后运行Parent工程，再在Parent中创建管道和子进程，然后双方即可通过管道通信。如下图所示：

15

(2)命名管道：Server和Client各自运行，再在Server中创建命名管道，然后在Client中连接管道，最后双方即可通过管道通信。如下图所示：

注：相关代码在*View.cpp中

16

（3）(实验三选做题目)：在客户端输入数据a和b，然后发送到服务器并计算a+b,然后把计算结果发送到客户端。可以多个客户端与同一个服务器并行通信。

相关代码： 客户端：

// CDlg.cpp : implementation file //

#include \"stdafx.h\" #include \"C.h\" #include \"CDlg.h\"

#ifdef _DEBUG

#define new DEBUG_NEW #undef THIS_FILE

static char THIS_FILE[] = __FILE__; #endif

///////////////////////////////////////////////////////////////////////////// // CAboutDlg dialog used for App About

class CAboutDlg : public CDialog {

public: CAboutDlg();

// Dialog Data //{{AFX_DATA(CAboutDlg) enum { IDD = IDD_ABOUTBOX };

17

//}}AFX_DATA // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL

// Implementation protected: //{{AFX_MSG(CAboutDlg) //}}AFX_MSG DECLARE_MESSAGE_MAP() };

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) { //{{AFX_DATA_INIT(CAboutDlg) //}}AFX_DATA_INIT }

void CAboutDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CAboutDlg) //}}AFX_DATA_MAP }

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAP END_MESSAGE_MAP()

///////////////////////////////////////////////////////////////////////////// // CCDlg dialog

CCDlg::CCDlg(CWnd* pParent /*=NULL*/) : CDialog(CCDlg::IDD, pParent) { //{{AFX_DATA_INIT(CCDlg) // NOTE: the ClassWizard will add member initialization here //}}AFX_DATA_INIT // Note that LoadIcon does not require a subsequent DestroyIcon in Win32

18

m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); }

void CCDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CCDlg) // NOTE: the ClassWizard will add DDX and DDV calls here //}}AFX_DATA_MAP }

BEGIN_MESSAGE_MAP(CCDlg, CDialog) //{{AFX_MSG_MAP(CCDlg) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() //}}AFX_MSG_MAP END_MESSAGE_MAP()

///////////////////////////////////////////////////////////////////////////// // CCDlg message handlers

BOOL CCDlg::OnInitDialog() { CDialog::OnInitDialog(); // Add \"About...\" menu item to system menu. // IDM_ABOUTBOX must be in the system command range. ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX); ASSERT(IDM_ABOUTBOX < 0xF000); CMenu* pSysMenu = GetSystemMenu(FALSE); if (pSysMenu != NULL) { CString strAboutMenu; strAboutMenu.LoadString(IDS_ABOUTBOX); if (!strAboutMenu.IsEmpty()) { pSysMenu->AppendMenu(MF_SEPARATOR); pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

} }

19

// Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon(m_hIcon, TRUE); // Set big icon SetIcon(m_hIcon, FALSE); // Set small icon // TODO: Add extra initialization here return TRUE; // return TRUE unless you set the focus to a control }

void CCDlg::OnSysCommand(UINT nID, LPARAM lParam) { if ((nID & 0xFFF0) == IDM_ABOUTBOX) { CAboutDlg dlgAbout; dlgAbout.DoModal(); } else { CDialog::OnSysCommand(nID, lParam); } }

// If you add a minimize button to your dialog, you will need the code below // to draw the icon. For MFC applications using the document/view model, // this is automatically done for you by the framework.

void CCDlg::OnPaint() { if (IsIconic()) { CPaintDC dc(this); // device context for painting SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); // Center icon in client rectangle int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSystemMetrics(SM_CYICON); CRect rect; GetClientRect(&rect); int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - cyIcon + 1) / 2;

20

// Draw the icon dc.DrawIcon(x, y, m_hIcon); } else { CDialog::OnPaint(); } }

// The system calls this to obtain the cursor to display while the user drags // the minimized window.

HCURSOR CCDlg::OnQueryDragIcon() { return (HCURSOR) m_hIcon; }

服务端：

// SDlg.cpp : implementation file //

#include \"stdafx.h\" #include \"S.h\" #include \"SDlg.h\"

#ifdef _DEBUG

#define new DEBUG_NEW #undef THIS_FILE

static char THIS_FILE[] = __FILE__; #endif

///////////////////////////////////////////////////////////////////////////// // CAboutDlg dialog used for App About

class CAboutDlg : public CDialog {

public: CAboutDlg();

// Dialog Data //{{AFX_DATA(CAboutDlg) enum { IDD = IDD_ABOUTBOX }; //}}AFX_DATA

21

// ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL

// Implementation protected: //{{AFX_MSG(CAboutDlg) //}}AFX_MSG DECLARE_MESSAGE_MAP() };

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) { //{{AFX_DATA_INIT(CAboutDlg) //}}AFX_DATA_INIT }

void CAboutDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CAboutDlg) //}}AFX_DATA_MAP }

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAP END_MESSAGE_MAP()

///////////////////////////////////////////////////////////////////////////// // CSDlg dialog

CSDlg::CSDlg(CWnd* pParent /*=NULL*/) : CDialog(CSDlg::IDD, pParent) { //{{AFX_DATA_INIT(CSDlg) // NOTE: the ClassWizard will add member initialization here //}}AFX_DATA_INIT // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

22

}

void CSDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CSDlg) // NOTE: the ClassWizard will add DDX and DDV calls here //}}AFX_DATA_MAP }

BEGIN_MESSAGE_MAP(CSDlg, CDialog) //{{AFX_MSG_MAP(CSDlg) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() //}}AFX_MSG_MAP END_MESSAGE_MAP()

///////////////////////////////////////////////////////////////////////////// // CSDlg message handlers

BOOL CSDlg::OnInitDialog() { CDialog::OnInitDialog(); // Add \"About...\" menu item to system menu. // IDM_ABOUTBOX must be in the system command range. ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX); ASSERT(IDM_ABOUTBOX < 0xF000); CMenu* pSysMenu = GetSystemMenu(FALSE); if (pSysMenu != NULL) { CString strAboutMenu; strAboutMenu.LoadString(IDS_ABOUTBOX); if (!strAboutMenu.IsEmpty()) { pSysMenu->AppendMenu(MF_SEPARATOR); pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

} }

23

// Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon(m_hIcon, TRUE); // Set big icon SetIcon(m_hIcon, FALSE); // Set small icon // TODO: Add extra initialization here return TRUE; // return TRUE unless you set the focus to a control }

void CSDlg::OnSysCommand(UINT nID, LPARAM lParam) { if ((nID & 0xFFF0) == IDM_ABOUTBOX) { CAboutDlg dlgAbout; dlgAbout.DoModal(); } else { CDialog::OnSysCommand(nID, lParam); } }

// If you add a minimize button to your dialog, you will need the code below // to draw the icon. For MFC applications using the document/view model, // this is automatically done for you by the framework.

void CSDlg::OnPaint() { if (IsIconic()) { CPaintDC dc(this); // device context for painting SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); // Center icon in client rectangle int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSystemMetrics(SM_CYICON); CRect rect; GetClientRect(&rect); int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - cyIcon + 1) / 2; // Draw the icon

24

dc.DrawIcon(x, y, m_hIcon); } else { CDialog::OnPaint(); } }

// The system calls this to obtain the cursor to display while the user drags // the minimized window.

HCURSOR CSDlg::OnQueryDragIcon() { return (HCURSOR) m_hIcon; }

运行结果如下图：

【实验思考及总结】 ………………………

（1）在VC++6.0中open已经编译好的程序，选择所有文件，线程之间通信的两个基

本问题是互斥和同步。

线程同步是指线程之间所具有的一种制约关系，一个线程的执行依赖另一个线程的消息，当它没有得到另一个线程的消息时应等待，直到消息到达时才被唤醒。

线程互斥是指对于共享的操作系统资源（指的是广义的\"资源\"，而不是Windows的.res

25

文件，譬如全局变量就是一种共享资源），在各线程访问时的排它性。当有若干个线程都要使用某一共享资源时，任何时刻最多只允许一个线程去使用，其它要使用该资源的线程必须等待，直到占用资源者释放该资源。 线程互斥是一种特殊的线程同步。

（2）互斥和同步对应着线程间通信发生的两种情况： 1） 当有多个线程访问共享资源而不使资源被破坏时；

2） 当一个线程需要将某个任务已经完成的情况通知另外一个或多个线程时。 （3）在WIN32中，同步机制主要有以下几种： 1） 事件(Event);

2） 信号量(semaphore); 3） 互斥量(mutex);

4） 临界区(Critical section)。 （4）全局变量

因为进程中的所有线程均可以访问所有的全局变量，因而全局变量成为Win32多线程通信的最简单方式。

26

实验四 银行家算法模拟

【开发语言及实现平台或实验环境】 C++/C#

Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003

【实验目的】

（1）进一步理解利用银行家算法避免死锁的问题； （2）在了解和掌握银行家算法。

（3）理解和掌握安全序列、安全性算法

【实验内容】

（1）编写安全性算法；

（2）编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

【源代码】

#include #include

#define M 3 //资源的种类数 #define N 5 //进程的个数

void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]); //统一的输出格式

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);

void main() {

int i,j;

//当前可用每类资源的资源数 int iAvailable[M]={3,3,2};

//系统中N个进程中的每一个进程对M类资源的最大需求 int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; //iNeed[N][M]每一个进程尚需的各类资源数

//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数 int

iNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};

//进程名

char cName[N]={'a','b','c','d','e'}; bool bExitFlag=true; //退出标记 char ch; //接收选择是否继续提出申请时传进来的值 bool bSafe; //存放安全与否的标志

27

//计算iNeed[N][M]的值 for(i=0;ioutput(iMax,iAllocation,iNeed,iAvailable,cName); //判断当前状态是否安全

bSafe=safety(iAllocation,iNeed,iAvailable,cName); //是否继续提出申请 while(bExitFlag) { cout<<\"\\n\"<<\"继续提出申请？\\ny为是；n为否。\\n\"; cin>>ch; switch(ch) { case 'y':

//cout<<\"调用银行家算法\"; bSafe=banker(iAllocation,iNeed,iAvailable,cName); if (bSafe) //安全，则输出变化后的数据 output(iMax,iAllocation,iNeed,iAvailable,cName); break; case 'n': cout<<\"退出。\\n\"; bExitFlag=false; break; default: cout<<\"输入有误，请重新输入：\\n\"; } } }

//输出

void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

int i,j;

cout<<\"\\n\ Max \Allocation\ Need \ Available\"<cout<<\"\A B C\A B C\A B C\ A B C\"<28

cout<//安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返回false，并输出不安全的提示；

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

int i,j,flag,x=0; char Name[N]; int Work[M];

bool Finish[N]; for(j=0;jwhile(true) { flag=0; for(i=0;i=iNeed[i][0] && Work[1]>=iNeed[i][1] && Work[2]>=iNeed[i][2])

{ for(j=0;j29

{ if(Finish[i]==false) { i=i; break; } } if(i==5) { cout<<\"\\n\"; cout<<\"当前时刻系统的一个安全序列为：\"; for(x=0;xreturn true; }

//安全返回true，不安全返回false

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; int i,j,Request[M],check[M]; bool f=true;

char x; while(f) { cout<<\"请输入进程名：\"; cin>>x;

for(i=0;iif (cName[i]==x) { i=i; break; } if (i==5) cout<<\"\\n您输入的进程名有误！请重新输入\";

30

else f=false; }

cout<<\"请输入申请各类资源数量：\\n\"; for(j=0;j>Request[j];

for(j=0;jfor(j=0;jif((iMax[i][j]-check[j])<0) {

cout<<\"\\n资源申请超过最大需求量！！！\\n\"; return false; } }

for(j=0;jif((iAvailable[j]-Request[j])<0) {

cout<<\"\\n不能满足进程！！！\\n\"; return false; } }

for(j=0;jiAvailable[j]-=Request[j]; iAllocation[i][j]+=Request[j]; iNeed[i][j]-=Request[j]; }

safety(iAllocation,iNeed,iAvailable,cName); return true; }

31

【实验结果与分析】

【实验思考及总结】 ………………………

银行家算法的安全算法不唯一，我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源

32

的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

33

实验五 页面置换算法模拟

【开发语言及实现平台或实验环境】 C++/C#

Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003

【实验目的】

（1）进一步理解利用页面调度算法实现虚拟内存的问题；

（2）通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点。

（3）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

（4）了解页面大小和内存实际容量对命中率的影响。

【实验内容】

（1）在了解和掌握页面调度算法的基础上，编制先进先出的算法（FIFO）、最近最少使用算法（LRU）、最佳淘汰算法（OPT）等各种页面置换算法。将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

（2）理解和掌握命中率的问题 （3）会使用某种编程语言。

【源代码】

#include #define M 3 #define N 20

using namespace std;

struct block { int iPageNum; //物理块里存储的页面号 int iBlockFlag; //在三种算法中用到的标记。例如在FIFO中为在内存中的时间 };

//算法模拟移位寄存器原理

void FIFO(int iTempPage[N],int flag[N],block myBlock[M]); void Optimal(int iTempPage[N],int flag[N],block myBlock[M]); void LRU(int iTempPage[N],int flag[N],block myBlock[M]); int PageNum(int array[]);

void main() { block myBlock[M];

34

int iPageString[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; //页面引用串 int flag[N]; //缺页标记；1为缺页，0为不缺页,在统计缺页次数时用 int i; bool bExitFlag=true; //退出标记 char ch; //接收选择算法时传进来的值 while(bExitFlag) { cout<<\"\\n\"<<\"请选择页面置换算法：\\n\"; cout<<\"f:FIFO置换算法\o:OPT置换算法\l:LRU置换算法\x:退出置换算法程序.\\n\"; cin>>ch; //初始化数据 if((ch=='f')||(ch=='o')||(ch=='l')) { for(i=0;icout<<\"LRU置换算法的结果是：\\n\"; LRU(iPageString,flag,myBlock); cout<<\"\\n缺页次数为\"<35

bExitFlag=false; break; default: cout<<\"输入有误，请重新选择置换算法：\\n\"; } } }

//对数组中的数累加，用来统计缺页次数时用 int PageNum(int array[]) { int num=0; for(int j=0;j//定位函数，在最佳算法中用于定位；

//定位物理块中的某一个页面在引用串中还未访问串中页面的位置 int allocate(int iPage,int iLoc,int iTempPage[N]) { int i; for(i=iLoc;i//找数组中最大值所在的下标，返回最大值在数组中的位置（下标），三种算法中都用到 int max(block array[M]) { int j,loc; int temp=array[0].iBlockFlag; loc=0; for(j=1;j36

} } return loc; }

//输出数据

void output(int iPage,int flag,block myBlock[M],int blockNum) { int j; //如果缺页则输出缺页标志，否则不输出 if (flag==1) cout<<\"\\n \"<//初始化物理块的内容，因任一种算法在物理块内容为空时，结果都一样的 //同时将目前物理块中的内容输出

void InitialBlock(int iTempPage[N],int flag[N],block myBlock[M]) { int i; for(i=0;i//FIFO置换算法

void FIFO(int iTempPage[N],int flag[N],block myBlock[M]) { int i,j,k,loc;

37

//初始化物理块的内容，因任一种算法在物理块内容为空时，结果都一样的 //同时将目前物理块中的内容输出 InitialBlock(iTempPage,flag,myBlock); //从引用串中的第4个页面开始 for(i=3;i//Optimal置换算法

void Optimal(int iTempPage[N],int flag[N],block myBlock[M])

38

{ int i,j,loc; //初始化物理块的内容，因任一种算法在物理块内容为空时，结果都一样的 //同时将目前物理块中的内容输出 InitialBlock(iTempPage,flag,myBlock); //从引用串中的第4个页面开始 for(i=3;i//LRU置换算法

void LRU(int iTempPage[N],int flag[N],block myBlock[M]) { int i,j,k,loc;

39

//初始化物理块的内容，因任一种算法在物理块内容为空时，结果都一样的 //同时将目前物理块中的内容输出 InitialBlock(iTempPage,flag,myBlock); //从引用串中的第4个页面开始 for(i=3;iif(j==M) { //查找最近最久未使用的页面，也就是block中iBlockFlag最大的物理块 loc=max(myBlock); myBlock[loc].iPageNum=iTempPage[i]; //置缺页标志

flag[i]=1;

//模拟移位寄存器 for(k=0;kcout<}

40

【实验结果与分析】 （1）FIFO置换算法：

（2）OPT置换算法：

（3）LRU置换算法：

41

（4）退出置换算法

【实验思考及总结】 ………………………

首先，我们需要清楚一个概念：缺页——我要装的程序的页，内存中没有该页就叫缺页。 （1）先进先出页面置换算法(FIFO)：

42

概念：往内存的3个页中先后装入程序的3个页（这三个的程序页号是不一样的），再装入程序的下一个页时，先判断内存中有无此页，有就不用再次装入；内存中没有此页时，就把先进入内存中的程序页给弄到虚拟内存上，然后，装入要装入的，以后，以此类推。 特点：哪个页面先进来，哪个页面先出去，不管该页面是不是最近又被访问了一次还是没有。

（2） 最佳置换算法（OPT）：

概念：往内存的3个页中先后装入程序的3个页（这三个的程序页号是不一样的），再装入程序的下一个页时，先判断内存中有无此页，有就不用再次装入；内存中没有此页时，该算法会把之后要装入内存的程序页号查一遍，并且要计算出，此时内存中的三个页号在之后谁是被最晚再次装入的页号，然后，把该页号给弄到虚拟内存上，然后，装入该装入的程序页号，最佳置换算法是这几种算法中最好的算法。

特点：置换页面的时候，看一下以后要进来的页面，把那个最晚再次进入内存的页面（这些页面必须是内存中存在的那些）置换出来。 （3）最近最久未使用置换算法(LRU)：

概念：往内存的3个页中先后装入程序的3个页（这三个的程序页号是不一样的），再装入程序的下一个页时，先判断内存中有无此页，有就不用再次装入；内存中没有此页时，就把内存中那个隔得时间最长没有运行的程序页给弄到虚拟内存上，然后，装入要装入的，以后，以此类推。这个开始时和先进先出页面置换算法的结果时一样的，但是，往后运行一段后，就不一样了。

特点：页面置换时，不管页面谁先进来，只管的是从这些页面当中选择一个从最后一次被访问到现在，时间最长的那个页面。

43