页面置换算法实验报告.doc

1 操作系统课程设计报告 课课程程名名称称 操操作作系系统统课课程程设设计计 课程设计题目课程设计题目 页面置换算法页面置换算法 学院 学院 计算机科学与技术学院计算机科学与技术学院 专专业业 科科技技 小小组组成成员员 庞庞思思慧慧 E E0 01 11 11 14 40 08 81 1 王王蒙蒙 E E0 01 11 11 14 41 16 61 1 姚姚慧慧乔乔 E E0 01 11 11 14 43 34 49 9 朱朱潮潮潮潮 E E0 01 11 11 14 44 40 08 8 指导老师 指导老师 邱剑锋邱剑锋 2 目录目录 1实验目的实验目的 3 2实验要求实验要求 3 3实验内容与步骤实验内容与步骤 3 4算法思想算法思想 4 5模块设计模块设计 4 6程序设计程序设计 5 7测试结果测试结果 7 8结果分析结果分析 9 9程序代码程序代码 9 10课程设计小结课程设计小结 24 3 页面置换算法模拟设计页面置换算法模拟设计 1 1 实验目的实验目的 1 通过模拟实现几种基本页面置换的算法 了解虚拟存储技术的特点 2 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想 并至少用三种 算法来模拟实现 3 通过对几种置换算法命中率的比较 来对比他们的优缺点 2 2 实验要求实验要求 计算并输出下述各种算法在不同内存容量下的命中率 A A 先进先出的算法 FIFO B B 最近最少使用算法 LRU C C 最佳淘汰算法 OPT 3 3 实验内容与步骤实验内容与步骤 1 通过随机数产生一个指令序列 共 320 条指令 具体的实施方法是 A 0 319 的指令地址之间随机选取一起点 M B 顺序执行一条指令 即执行地址为 M 1 的指令 C 在前地址 0 M 1 中随机选取一条指令并执行 该指令的地址为 M D 顺序执行一条指令 其地址为 M 1 E 在后地址 M 2 319 中随机选取一条指令并执行 F 重复 A E 直到执行 320 次指令 2 指令序列变换成页地址流 A 页面大小为 1K B 用户内存容量为 4 页到 32 页 4 C 用户虚存容量为 32K 在用户虚存中 按每 K 存放 10 条指令排列虚存地址 即 320 条指令在虚存中的 存放方式为 第 0 条 第 9 条指令为第 0 页 对应虚存地址为 0 9 第 10 条 第 19 条指令为第 1 页 对应虚存地址为 10 19 第 310 条 第 319 条指令为第 31 页 对应虚存地址为 310 319 3 计算并输出上述各种算法在不同内存容量下的命中率 命中率 1 缺页次数 页地址流长度 4 4 算法思想算法思想 在进程运行过程中 若其所要访问的页面不在内存而需把它们调入内存 但内存已无 空闲空间时 为了保证该进程能正常运行 系统必须从内存中调出一页程序或数据 送磁 盘的对换区中 但应将哪 个页面调出 须根据一定的算法来确定 通常 把选择换出页面 的算法称为页面置换算法 一个好的页面置换算法 应具有较低的页面更换频率 从理论 上讲 应将那些以后不再会访问的页面换出 或将那些在较长时间内不会再访问的页面调 出 1 先进先出算法 FIFO 这是最早出现的置换算法 该算法总是淘汰最先进入内存的页面 即选择在内存中驻留 时间最久的页面予以淘汰 该算法实现简单只需把一个进程已调入内存的页面 按先后次 序链接成一个队列 并设置一个指针 称为替换指针 使它总是指向最老的页面 2 最近最久未使用算法 LRU least recently used 算法的基本思想 当需要淘汰某一页时 选择离当前时间最近的一段时间内最久没有使用 过的页先淘汰 该算法的主要出发点是 如果某页被访问了 则它可能马上还被访问 或 者反过来说 如果某页很长时间未被访问 则它在最近一段时间不会被访问 3 最佳淘汰算法 OPT 其所选择的被淘汰的页面将是以后永不使用 或许是未来最长时间内不使用的页面 该算 法可保证获得最低的淘汰率 但在实际运用中无法实现 可用来评价其他算法的命中率 5 5 模块设计模块设计 5 入口 产生随机数 要调入的页面 离现在处理时间最长的页面 最长的页面 初始化页面情况 t1 N 根据选择的算法进行 置换 缺页数加 1 计算缺页率 并输出数 据 结束 Y N 直接存入内存 开始 输入内存数 调用各种置换算法 并显示地址流 页面流 页面置换过程和命中率 命中率比较 结束结束 总模块图总模块图 主程序图 6 6 6 程序设计程序设计 struct Pro 内存页的结构体 int num 记录页面号 int time 页面从未被利用的时间 define M 320 定义指令条数 Pro P M 产生的随机指令数组 void Input 产生随机数 int s 随机数 int i srand time 0 s rand M cout n 随机产生指令流 n for i 0 i M i 4 产生指令队列 p i num s 任选一指令访问点 m p i 1 num p i num 1 顺序执行一条指令 p i 2 num int float p i num rand RAND MAX 1 0 执行前地址指令 m p i 3 num p i 2 num 1 顺序执行一条指令 s int float 319 p i 2 num rand RAND MAX 1 0 p i 2 num for i 0 i M i p i time 0 int Search int e Pro page1 int N 查找内存中是否存在要调入的页面 int t Pro page new Pro N page page1 for int i 0 i N i t e 10 if t page i num return i 7 return 1 int Max Pro page1 int N 查找最久最久未被使用的页面 Pro page new Pro N page page1 int e page 0 time i 0 while i N if e page i time e page i time 找最长时间 i for i 0 i N i if e page i time return i 找最长时间的下标 return 1 int Compfu Pro page1 int i int t Pro p M 找到最久不使用的页面 Pro page new Pro N page page1 int count 0 for int j i jLRU CLOCK FIFO 实际上 在内存页面数较少 4 5 页面 时 3 种算法的命中率差别不大 可是 50 左右 在内存页 面为 7 25 个页面之间时 3 种算法的访内命中率大致在 52 至 87 之间变化 在内存页面 10 为 25 32 个页面时 由于用户进程的所有指令基本上都已装入内存 从而命中率已较大 从而算法之间的差别不大 9 9 程序代码程序代码 页面置换算法模拟设计 Dlg cpp implementation file include stdafx h include 页面置换算法模拟设计 h include 页面置换算法模拟设计 Dlg h ifdef DEBUG define new DEBUG NEW undef THIS FILE static char THIS FILE FILE endif CMyDlg dialog CMyDlg CMyDlg CWnd pParent NULL CDialog CMyDlg IDD pParent AFX DATA INIT CMyDlg m iFifo 0 N 0 MZL 0 0 AFX DATA INIT Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m hIcon AfxGetApp LoadIcon IDR MAINFRAME void CMyDlg DoDataExchange CDataExchange pDX CDialog DoDataExchange pDX AFX DATA MAP CMyDlg DDX Control pDX IDC EDIT4 m suiji2 DDX Control pDX IDC EDIT5 m yemian DDX Control pDX IDC EDIT3 m suiji DDX Radio pDX IDC RADIO1 m iFifo DDX Text pDX IDC EDIT1 N DDX Text pDX IDC EDIT2 MZL AFX DATA MAP 11 BEGIN MESSAGE MAP CMyDlg CDialog AFX MSG MAP CMyDlg ON WM PAINT ON WM QUERYDRAGICON ON BN CLICKED IDC BUTTON1 OnButton1 ON BN CLICKED IDC RADIO1 OnRadio1 ON BN CLICKED IDC RADIO2 OnRadio2 ON BN CLICKED IDC RADIO3 OnRadio3 ON EN CHANGE IDC EDIT2 OnChangeEdit2 ON BN CLICKED IDC BUTTON2 OnButton2 ON BN CLICKED IDC BUTTON3 OnButton3 AFX MSG MAP END MESSAGE MAP CMyDlg message handlers BOOL CMyDlg OnInitDialog CDialog OnInitDialog 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 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 CMyDlg OnPaint if IsIconic CPaintDC dc this device context for painting 12 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 int x rect Width cxIcon 1 2 int y rect Height cyIcon 1 2 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 CMyDlg OnQueryDragIcon return HCURSOR m hIcon include include include define M 320 int N struct Pro 内存页的结构体 int num time Pro p M 13 void Input 输入函数 输入实际页号和实际页数 int s 随机数 inti srand time 0 每次运行时进程号不同 用来作为初始化随机数队列的种子 s rand M cout n 随机产生指令流 n for i 0 i M i 4 产生指令队列 p i num s 任选一指令访问点 m p i 1 num p i num 1 顺序执行一条指令 p i 2 num int float p i num rand RAND MAX 1 0 执行前地址指令 m p i 3 num p i 2 num 1 顺序执行一条指令 s int float 319 p i 2 num rand RAND MAX 1 0 p i 2 num for i 0 i M i p i time 0 p 0 num 10 p 1 num 22 p 2 num 33 p 3 num 44 p 4 num 50 p 5 num 13 p 6 num 32 p 7 num 22 测试数 据 1 2 3 4 5 1 3 2 fifo 5 1 2 4 LRU 5 1 3 2 opt 置换 1 2 3 5 int Search int e Pro page1 int N 查找内存中是否存在要调入的页面 int t Pro page new Pro N page page1 14 for int i 0 i N i t e 10 if t page i num return i return 1 int Max Pro page1 int N 找出离现在时间最长的页面 Pro page new Pro N page page1 int e page 0 time i 0 while i N if e page i time e page i time 找最长时间 i for i 0 i N i if e page i time return i 找最长时间的下标 return 1 int Compfu Pro page1 int i int t Pro p M 找到最久不使用的页面 Pro page new Pro N page page1 int count 0 for int j i j M j if page t num p j num 10 break 当前页面开始往后查找在内存中的页帧号 else count return count 15 void CMyDlg OnButton1 TODO Add your control notification handler code here UpdateData true Input 地址流 CString str1 tmp1 tmp1 str1 int k 0 t 0 i 0 for i 0 i M i tmp1 Format 4d p i num str1 tmp1 k if k 16 0 str1 n r n r n r m suiji SetWindowText T str1 页面流 CString str2 tmp2 tmp2 str2 for i 0 i M i tmp2 Format 4d p i num 10 str2 tmp2 k if k 16 0 str2 n r n r n r m suiji2 SetWindowText T str2 Pro page new Pro N for int j 0 j N j 初始化页面基本情况 page j num 1 16 page j time j if m iFifo 0 FIFO 页面置换 float n 0 记录缺页数 int i 0 CString str3 tmp3 str3 m yemian SetWindowText T str3 while i 0 i 找到相同的页面 else n page t num p i num 10 如果没有找到相同的页 则进行页面 替换 缺页数加一 tmp3 m yemian GetWindowText T str3 for int i 0 i N i if page i num 1 tmp3 Format s str3 tmp3 else tmp3 Format 4d page i num str3 tmp3 str3 n r n r n r m yemian SetWindowText T str3 t t N 17 MZL 1 n M if m iFifo 1 LRU 页面置换 int p2 float n 0 记录缺页数 int i 0 int t1 t 0 CString str3 tmp3 str3 m yemian SetWindowText T str3 while i 0 page k time 0 for p2 0 p2 N p2 if p2 k page p2 time else if t1 N n page t num p i num 10 如果没有找到相同的页 则进行 页面替换 缺页数加一 t1 t page t time 0 tmp3 m yemian GetWindowText T str3 for int i 0 i N i if page i num 1 18 tmp3 Format s str3 tmp3 else tmp3 Format 4d page i num str3 tmp3 str3 n r n r n r m yemian SetWindowText T str3 else n t Max page N page t num p i num 10 page t time 0 tmp3 m yemian GetWindowText T str3 for int i 0 i N i if page i num 1 tmp3 Format s str3 tmp3 else tmp3 Format 4d page i num str3 tmp3 str3 n r n r n r m yemian SetWindowText T str3 for p2 0 p2 N p2 if p2 t page p2 time 19 i MZL 1 n M if m iFifo 2 OPT 页面置换 int i 0 float n 0 记录缺页数 int t 0 t1 0 CString str3 tmp3 str3 m yemian SetWindowText T str3 while i 0 i else if t1 N n page t num p i num 10 如果没有找到相同的页 则进行页面替换 缺页数加 1 t1 t i tmp3 m yemian GetWindowText T str3 for int i 0 i N int temp 1 cn for t 0 t N t 查找下次访问距离最远的那个页面 if temp Compfu page i t p temp Compfu page i t p 下次命中经历的页面计数 cn t 最远的页面号 page cn num p i num 10 n tmp3 m yemian GetWindowText T str3 for int i 0 i N i if page i num 1 tmp3 Format s str3 tmp3 else tmp3 Format 4d page i num str3 tmp3 str3 n r n r n r m yemian SetWindowText T str3 i else break MZL 1 n M 21 UpdateData false void CMyDlg OnRadio1 TODO Add your control notification handler code here void CMyDlg OnRadio2 TODO Add your control notification handler code here void CMyDlg OnRadio3 TODO Add your control notification handler code here void CMyDlg OnChangeEdit2 TODO If this is a RICHEDIT control the control will not send this notification unless you override the CDialog OnInitDialog function and call CRichEditCtrl SetEventMask with the ENM CHANGE flag ORed into the mask TODO Add your control notification handler code here void CMyDlg OnButton2 TODO Add your control notification handler code here MessageBox T 确认退出 ExitProcess 0 void CMyDlg OnButton3 UpdateData true 22 Input Pro page new Pro N for int j 0 j N j 初始化页面基本情况 page j num 1 page j time j int t1 0 int i1 0 float n1 0 float s1 s2 s3 FIFO 页面置换 n1 0 记录缺页数 while i1 0 i1 找到相同的页面 else n1 page t