生成网站有吗免费的,附近旅游团地址电话怎么搜索,自助建个人网站哪个好,阿里巴巴国际站怎么运营页面置换算法 在进程运行过程中#xff0c;若需要访问的物理块不在内存中#xff0c;就需要通过一定的方式来将页面载入内存#xff0c;而此时内存很可能已无空闲空间#xff0c;因此就需要一定的算法来选择内存中要被置换的页面#xff0c;这种算法就被称为页面置换算法。…页面置换算法
在进程运行过程中若需要访问的物理块不在内存中就需要通过一定的方式来将页面载入内存而此时内存很可能已无空闲空间因此就需要一定的算法来选择内存中要被置换的页面这种算法就被称为页面置换算法。页面置换算法的好坏将直接影响系统的性能。
一个好的页面置换算法应做到减少页面置换的频率。尽量将以后不会用到的或较长时间不会使用的页面给置换出。
下面介绍几种常用的页面置换算法。 1. 最佳置换算法
该算法是一种理想化的算法具有非常好的性能但是由于目前无法预知未来因此难以实现。
该算法选择淘汰的页面是未来永远不会再使用的页面 or 未来最长时间不再被访问的页面。该算法保证了可以获得最低缺页率但无法预知未来页面的使用情况因此目前无法实现但通常用来评价其他算法。
例假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 进程运行时,先将 7,0,1 三个页面装入内存。以后,当进程要访问页面 2 时,将会产生缺页中断。此时 OS 根据最佳置换算法,将选择页面 7 予以淘汰。这是因为页面 0 将作为第 5 个被访问的页面,页面 1 是第 14 个被访问的页面,而页面 7 则要在第 18 次页面访问时才需调入。下次访问页面 0 时,因它已在内存而不必产生缺页中断。当进程访问页面 3时,又将引起页面 1 被淘汰;因为,它在现有的 1,2,0 三个页面中,将是以后最晚才被访问的。图 4-26 示出了采用最佳置换算法时的置换图。由图可看出,采用最佳置换算法发生了 6 次页面置换。 2. 先进先出FIFO页面置换算法
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
例同上。当进程第一次访问页面 2 时,将把第 7 页换出,因为它是最先被调入内存的;在第一次访问页面 3 时,又将把第 0 页换出, 因为它在现有的 2, 0, 1 三个页面中是最老的页。 由图 4-27 可以看出,利用 FIFO 算法时进行了 12 次页面置换,比最佳置换算法正好多一倍。 3. 最近最久未使用(LRU)算法
该算法以过去预测未来选择之前最长时间未使用的页面置换。但是由于利用“过去”作为“未来”的近似这一做法并非完全可靠因此有时会造成缺页率非常高导致效率会非常低。
例同上。当进程第一次对页面 2 进行访问时,由于页面 7 是最近最久未被访问的,故将它置换出去。当进程第一次对页面 3进行访问时,第 1 页成为最近最久未使用的页,将它换出。由图可以看出,前 5 个时间的图像与最佳置换算法时的相同,但这并非是必然的结果。因为,最佳置换算法是从“向后看”的观点出发的,即它是依据以后各页的使用情况;而 LRU 算法则“向前看”的,即根据各页以前的使用情况来判断,而页面过去和未来的走向之间并无必然的联系。 4. 代码实现
该部分代码使用vector来实现未使用链表。
/************************************************************************* 测试数据 20 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 3************************************************************************/#include iostream
#include algorithm
#include vector
#include map
using namespace std;class PageReplacement {
private:vectorint page;int page_num; //物理内存块数
public:PageReplacement() : page_num(0) {}void create();void print();void physical_block_print( const vectorint );bool isfind( const vectorint, int ); //查找是否已在内存物理块中void FIFO(); //FIFO页面置换算法void LRU(); //LRU页面置换算法void OPT(); //OPT页面置换算法
};void PageReplacement::create() {cout 请输入页面个数: ;int n, t;cin n;cout 请输入页面串\n;while( n-- ) {cin t;page.push_back( t );}cout 请输入内存物理块数: ;cin page_num;
}void PageReplacement::print() {int n page.size();cout 页面串:\n;for( int i 0; i n; i ) {cout page[i] ;}cout endl;
}void PageReplacement::physical_block_print( const vectorint t ) {int n t.size();for( int i 0; i n; i ) {cout t[i] ;}cout endl;
}bool PageReplacement::isfind( const vectorint block, int t ) {if ( find( block.begin(), block.end(), t ) ! block.end() ) {return true;}return false;
}/* FIFO页面置换算法 */
void PageReplacement::FIFO() {vectorint physical_block( page_num, -1 );int n page.size(), cur 0;int not_found 0;cout FIFO页面置换情况:\n;for( int i 0; i n; i ) {if( !isfind( physical_block, page[i] ) ) {physical_block[cur] page[i]; //页面置换cur (cur1)%page_num;not_found;}physical_block_print( physical_block ); //输出每个物理块信息}cout 缺页次数 not_found endl;
}/* LRU页面置换算法 */
void PageReplacement::LRU() {vectorint physical_block( page_num, -1 );mapint, int page_time;int n page.size();int not_found 0;for( int i 0; i n; i ) {if ( !isfind( physical_block, page[i] ) ) { //当前页不在为物理块中if ( page_time.size() page_num ) { //物理块未放满physical_block[i] page[i];page_time[page[i]] i;} else { //物理块放满进行页面置换mapint, int::iterator it page_time.begin(), t it;for( it; it ! page_time.end(); it ) {if ( t-second it-second ) {t it;}}int index;for( index 0; index page_num physical_block[index]!t-first; index );physical_block[index] page[i];page_time.erase( t );page_time[page[i]] i;}not_found;} else { //在物理块中更新页面最后使用时间page_time[page[i]] i;}physical_block_print( physical_block );}cout 缺页次数 not_found endl;
}/* OPT页面置换算法 */
void PageReplacement::OPT() {vectorint physical_block( page_num, -1 );int n page.size();int not_found 0;for( int i 0; i n; i ) {if( !isfind( physical_block, page[i] ) ) { //当前页不在物理块中if( i page_num ) { //物理块未放满physical_block[i] page[i];} else { //物理块放满,进行页面置换mapint, int page_time;int k, j;/* 获取物理块中页面此后的最先使用时间 */for( j 0; j page_num; j ) { //遍历physical_blockfor( k i1; k n; k ) { //遍历pageif( physical_block[j] page[k] ) {page_time[page[k]] k;break;}}if( k n ) {page_time[physical_block[j]] k;}}/* 寻找可以置换的页面 */mapint, int::iterator it page_time.begin(), t it;for( ; it ! page_time.end(); it ) {if ( t-second it-second ) {t it;}}/* 获取被置换页面在物理块的下标 */int index 0;for( ; index page_num physical_block[index] ! t-first; index );physical_block[index] page[i];}not_found;}physical_block_print( physical_block );}cout 缺页次数 not_found endl;
}int main() {PageReplacement t;t.create();// t.FIFO();t.LRU();// t.OPT();return 0;
}
