精华内容
下载资源
问答
  • lru页面替换算法_LRU页面替换算法分析和Belady异常
    千次阅读
    2020-06-23 21:47:44

    lru页面替换算法

    Problem statement:

    问题陈述:

    Write a program to simulate Least Recently Used (LRU) page replacement algorithm for the following page reference string: 9, 10, 11, 7, 12, 8, 7, 6, 12, 5, 4, 3, 10, 11, 12, 4, 5, 6, 9, 4, 5.

    编写程序以模拟以下页面引用字符串的最近最少使用(LRU)页面替换算法 :9,10,11,7,12,12,8,7,6,12,5,5,4,3,10,11,12 ,4、5、6、9、4、5。

    Consider (i) 4 frames and (ii) 5 frames. Compare the results...

    考虑(i)4帧和(ii)5帧。 比较结果...

    Solution

    LRU页面替换算法 (LRU Page replacement algorithm)

    1. Set page_fault=0 & frame_size to the value given as input.

      将page_fault = 0和frame_size设置为输入值。

    2. Start traversing the pages.

      开始遍历页面。

      If

      如果

      1. Page_set holds less pages than frame_size. Insert pages one by one until the size of page_set reaches frame_size or all page references are processed. Simultaneously maintain the recent occurred counter (which has come most recently or least recently) of each page in a map called page_counter.
      2. Page_set容纳的页面少于frame_size 。 一页一页地插入页面,直到page_set的大小达到frame_size或处理所有页面引用为止。 同时在称为page_counter的映射中维护每个页面的最近发生的计数器 (最近或最近出现的计数器 )。
      3. Increment page_fault.
      4. 增加page_fault 。

      Else

      其他

      If current page is present in page_set
          Continue;
      Else
      
      
      1. Find the page in the set that was least recently used. We find it using the map we created. We basically need to replace the page with minimum counter.
      2. 在集合中找到使用最少的页面。 我们使用创建的地图找到它。 我们基本上需要用最小计数器替换页面。
      3. Replace the page having the least counter value with current page.
      4. 用当前页面替换计数器值最小的页面。
      5. Increment page_fault.
      6. 增加page_fault 。
      7. Update counter of current page.
      8. 更新当前页面的计数器 。
    3. Return page_fault.

      返回page_fault 。

    LRU页面替换算法和Belady异常的C ++实现 (C++ implementation of LRU page replacement algorithm and Belady's anomaly)

    #include <bits/stdc++.h>
    using namespace std;
    
    int page_faults(int page[],int n, int frame_size){
    	//STL set to hold current pages,max size=frame_size
    	unordered_set<int> page_set ; 
    	//STL map to store counter of each referenced pages 
    	unordered_map<int,int> page_counter;
    	int page_fault=0;
    	//for each memory reference
    	for(int i=0;i<n;i++){ 
    		//frame_size =max set size 
    		cout<<"processing request page no "<<page[i]<<endl;
    		//when all frames are not allocated
    		if(page_set.size()<frame_size){ 
    			//if page is not present in memory
    			if(page_set.find(page[i])==page_set.end()){ 
    				page_set.insert(page[i]); //insert pages
    				page_fault++; //increase page-fault
    			}
    			//update counter value of the referenced page
    			page_counter[page[i]]=i; 
    		}
    		//when all frames are allocated
    		else{ 
    			//if referenced page is not present
    			if(page_set.find(page[i])==page_set.end()){ 
    				int lru=INT_MAX,val;
    				for(auto it=page_set.begin();it!=page_set.end();it++){
    					//find the least recently used page
    					if(page_counter[*it]<lru){  
    						lru=page_counter[*it];
    						val=*it;
    					}
    				}
    				//erase the least recently used page
    				page_set.erase(val); 
    				//insert the current page
    				page_set.insert(page[i]); 
    				//increase page fault
    				page_fault++; 
    			}
    			//update counter value of current page
    			page_counter[page[i]]=i; 
    		}
    		//display existing pages in the frames 
    		//after each page request processed
    		cout<<"pages in the frames are: ";    
    		for(auto it=page_set.begin();it!=page_set.end();it++)
    			cout<<*it<<" ";
    		cout<<endl;
    	}
    }
    
    int main(){
    	//page reference requests
    	int page[]={9, 10, 11, 7, 12, 8, 7, 6, 12, 5, 4, 3, 10, 11, 12, 4, 5, 6, 9, 4, 5}; 
    	int n=sizeof(page)/sizeof(int);
    	//total no of frames in memory
    	int frame_size;   
    	//input frame_size
    	cout<<"enter no of frames"<<endl; 
    	cin>>frame_size;
    	//compute memory value
    	cout<<"no of page faults for "<<frame_size<<" frames are: "<<page_faults(page,n,frame_size)<<endl; 
    
    	return 0;
    }
    
    
    

    Output (first run)

    输出(首次运行)

    enter no of frames 
    4
    processing page no 9 
    pages in the frames are: 9 
    processing page no 10
    pages in the frames are: 10 9
    processing page no 11
    pages in the frames are: 11 9 10 
    processing page no 7 
    pages in the frames are: 7 11 9 10 
    processing page no 12
    pages in the frames are: 12 7 11 10
    processing page no 8 
    pages in the frames are: 8 12 7 11 
    processing page no 7 
    pages in the frames are: 8 12 7 11 
    processing page no 6 
    pages in the frames are: 6 8 12 7
    processing page no 12
    pages in the frames are: 6 8 12 7
    processing page no 5 
    pages in the frames are: 6 5 12 7
    processing page no 4 
    pages in the frames are: 4 6 5 12
    processing page no 3 
    pages in the frames are: 3 4 5 12
    processing page no 10
    pages in the frames are: 10 3 4 5
    processing page no 11
    pages in the frames are: 10 3 11 4 
    processing page no 12
    pages in the frames are: 12 10 3 11
    processing page no 4 
    pages in the frames are: 12 10 4 11
    processing page no 5 
    pages in the frames are: 5 12 4 11 
    processing page no 6 
    pages in the frames are: 6 5 12 4
    processing page no 9 
    pages in the frames are: 9 6 5 4 
    processing page no 4 
    pages in the frames are: 9 6 5 4 
    processing page no 5 
    pages in the frames are: 9 6 5 4 
    ...........no of page faults for 4 frames are: 17........ 
    
    
    

    Output (second run)

    输出(第二次运行)

    enter no of frames 
    5
    processing page no 9 
    pages in the frames are: 9 
    processing page no 10
    pages in the frames are: 10 9
    processing page no 11
    pages in the frames are: 11 9 10 
    processing page no 7 
    pages in the frames are: 7 11 9 10 
    processing page no 12
    pages in the frames are: 12 7 11 9 10
    processing page no 8 
    pages in the frames are: 8 12 7 11 10
    processing page no 7 
    pages in the frames are: 8 12 7 11 10
    processing page no 6 
    pages in the frames are: 6 8 12 7 11 
    processing page no 12
    pages in the frames are: 6 8 12 7 11 
    processing page no 5 
    pages in the frames are: 6 8 5 12 7
    processing page no 4 
    pages in the frames are: 4 6 5 12 7
    processing page no 3 
    pages in the frames are: 3 4 6 5 12
    processing page no 10
    pages in the frames are: 10 3 4 5 12 
    processing page no 11
    pages in the frames are: 10 3 11 4 5 
    processing page no 12
    pages in the frames are: 12 10 3 11 4
    processing page no 4 
    pages in the frames are: 12 10 3 11 4
    processing page no 5 
    pages in the frames are: 5 12 10 11 4
    processing page no 6 
    pages in the frames are: 6 5 12 11 4 
    processing page no 9 
    pages in the frames are: 9 6 5 12 4
    processing page no 4 
    pages in the frames are: 9 6 5 12 4
    processing page no 5 
    pages in the frames are: 9 6 5 12 4
    ...........no of page faults for 5 frames are: 16........
    
    

    Comparison of result

    结果比较

    The outputs show that the no of page fault for 4 frames are 17 while the no of page fault for 5 frames are 16. That means no of page faults has decreased with the increase in frame number.

    输出显示4帧的页面错误数为17,而5帧的页面错误数为16。这意味着,随着帧数的增加,页面错误数也没有减少。

    Comment

    评论

    This phenomenon is an example of Belady's anomaly. Belady's anomaly states that increasing number of frames will never increase number of page faults if LRU page replacement algorithm is used. Using LRU page replacement algo, no. of page fault may decrease or remain same if no of frame is increased. This is so because LRU is a stack algorithm.

    这种现象是贝拉迪异常现象的一个例子贝拉迪的异常状态表明,如果使用LRU页面替换算法,则增加帧数将永远不会增加页面错误数。 使用LRU页面替换算法 ,否。 如果不增加帧数,页面错误的数量可能会减少或保持不变。 之所以如此,是因为LRU是一个堆栈算法

    翻译自: https://www.includehelp.com/algorithms/analysis-of-lru-page-replacement-algorithm-and-beladys-anomaly.aspx

    lru页面替换算法

    更多相关内容
  • 页面替换算法

    2017-12-10 20:19:54
    理解页面替换算法的作用和不同的页面替换算法确定被替换页面的原则
  • Here you will get program for lru page ... 在这里,您将获得C语言中的lru页面替换算法的程序。 Least Recently Used (LRU) page replacement algorithm works on the concept that the pages that are heavil...

    lru页面替换算法

    Here you will get program for lru page replacement algorithm in C.

    在这里,您将获得C语言中的lru页面替换算法的程序。

    Least Recently Used (LRU) page replacement algorithm works on the concept that the pages that are heavily used in previous instructions are likely to be used heavily in next instructions. And the page that are used very less are likely to be used less in future. Whenever a page fault occurs, the page that is least recently used is removed from the memory frames. Page fault occurs when a referenced page in not found in the memory frames.

    最近最少使用(LRU)页面替换算法的工作原理是,先前指令中大量使用的页面很可能在下一指令中大量使用。 而且,很少使用的页面将来可能会更少使用。 每当发生页面错误时,都会从内存帧中删除最近使用最少的页面。 当在存储框架中找不到引用的页面时,将发生页面错误。

    Also Read: LRU Page Replacement Algorithm in C

    另请参见:C语言中的LRU页面替换算法

    Below program shows how to implement this algorithm in C.

    下面的程序显示了如何在C中实现此算法。

    C语言中的LRU页面替换算法程序 (Program for LRU Page Replacement Algorithm in C)

    #include<stdio.h>
     
    int findLRU(int time[], int n){
    	int i, minimum = time[0], pos = 0;
     
    	for(i = 1; i < n; ++i){
    		if(time[i] < minimum){
    			minimum = time[i];
    			pos = i;
    		}
    	}
    	
    	return pos;
    }
     
    int main()
    {
        int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10], flag1, flag2, i, j, pos, faults = 0;
    	printf("Enter number of frames: ");
    	scanf("%d", &no_of_frames);
    	
    	printf("Enter number of pages: ");
    	scanf("%d", &no_of_pages);
    	
    	printf("Enter reference string: ");
    	
        for(i = 0; i < no_of_pages; ++i){
        	scanf("%d", &pages[i]);
        }
        
    	for(i = 0; i < no_of_frames; ++i){
        	frames[i] = -1;
        }
        
        for(i = 0; i < no_of_pages; ++i){
        	flag1 = flag2 = 0;
        	
        	for(j = 0; j < no_of_frames; ++j){
        		if(frames[j] == pages[i]){
    	    		counter++;
    	    		time[j] = counter;
    	   			flag1 = flag2 = 1;
    	   			break;
       			}
        	}
        	
        	if(flag1 == 0){
    			for(j = 0; j < no_of_frames; ++j){
    	    		if(frames[j] == -1){
    	    			counter++;
    	    			faults++;
    	    			frames[j] = pages[i];
    	    			time[j] = counter;
    	    			flag2 = 1;
    	    			break;
    	    		}
        		}	
        	}
        	
        	if(flag2 == 0){
        		pos = findLRU(time, no_of_frames);
        		counter++;
        		faults++;
        		frames[pos] = pages[i];
        		time[pos] = counter;
        	}
        	
        	printf("\n");
        	
        	for(j = 0; j < no_of_frames; ++j){
        		printf("%d\t", frames[j]);
        	}
    	}
    	
    	printf("\n\nTotal Page Faults = %d", faults);
        
        return 0;
    }

    Output

    输出量

    Enter number of frames: 3 Enter number of pages: 6 Enter reference string: 5 7 5 6 7 3

    输入帧数:3 输入页数:6 输入参考字符串:5 7 5 6 7 3

    5 -1 -1 5 7 -1 5 7 -1 5 7 6 5 7 6 3 7 6

    5 -1 -1 5 7 -1 5 7 -1 5 7 6 5 7 6 3 7 6

    Total Page Faults = 4

    总页面错误数= 4

    Video Tutorial

    影片教学

    Comment below if you have doubts or found anything incorrect in above lru page replacement algorithm in C.

    如果您对以上C语言中的lru页面替换算法有疑问或发现任何错误,请在下面评论。

    翻译自: https://www.thecrazyprogrammer.com/2016/11/lru-page-replacement-algorithm-c.html

    lru页面替换算法

    展开全文
  • 页面替换算法的仿真 任务是执行不同内存页面替换算法的蒙特卡洛模拟,并测量页面错误的数量。 内存页替换算法为FIFO(先进先出),LRU(最近最少使用)和CLOCK。 然后,假定模拟数据可用于创建页面错误与分配的帧...
  • 页面替换算法,LRU和FIFO。 输入结构 该程序获得三行输入: 一个整数,其中包含页数 一个字符串,其中包含参考字符串 一个字符串,其中包含帧的大小和我们要使用的算法 范例一: 10 0 1 2 0 3 1 4 0 1 4 3 FIFO ...
  • 页面替换算法在实现此内存设置方面发挥着重要作用,旨在实现更少的页面错误、高命中率和最小的开销。 多年来,人们设计并提出了许多页面替换算法。 随着内存类型和程序设计方法的改进,改进算法的需求作为一种需要...
  • 本程序主要用于模拟LRU算法(内存单元在10个以内);支持动态输入数字 和内存单元个数;输出结果为每步的内存存储情况及缺页统计情况。
  • 操作系统 页面替换算法(OPT最佳置换算法与LRU最近最久未使用算法)
  • 操作系统中页面替换算法的Java代码 复杂度分析 时间复杂度: 空间复杂度: 什么是分页? 在计算机操作系统中,分页是一种内存管理方案,计算机可以通过它来存储和从辅助存储器中检索数据,以供在主存储器中...

    目录

    什么是分页?

    什么是内存管理?

    什么是页面替换?

    先进先出(FIFO)

    贝拉迪的异常

    最佳页面替换

    LRU(最近最少使用)

    FIFO先进先出的实现

    Java实现代码:

    C++实现代码:

    复杂度分析

    时间复杂度:

    空间复杂度:


    什么是分页?

            在计算机操作系统中,分页是一种内存管理方案,计算机可以通过它来存储和从辅助存储器中检索数据,以供在主存储器中使用。在这种方案中,操作系统从二级存储中以相同大小的块称为page检索数据。分页是现代操作系统中虚拟内存实现的重要组成部分,它使用二级存储来使程序超出可用物理内存的大小。

            为简单起见,主存储器称为“ RAM”(“随机存储器”的缩写),辅助存储器称为“磁盘”(“硬盘存储器,或固态存储器”的简写),但是概念并不取决于这些术语是否从字面上适用于特定的计算机系统。

    什么是内存管理?

            内存管理是应用于计算机内存的一种资源管理形式。内存管理的基本要求是提供一种方法,可以根据它们的请求为程序动态分配内存的一部分,并在不再需要时释放它们以供重用。这对于任何随时可能进行多个进程的高级计算机系统都是至关重要的。

            已经设计出几种方法来提高存储器管理的有效性。虚拟内存系统将进程使用的内存地址与实际物理地址分开,从而允许进程分离,并使用分页或交换到辅助存储来增加虚拟地址空间的大小,使其超出可用的RAM数量。虚拟内存管理器的质量可能会对整体系统性能产生广泛影响。

    什么是页面替换?

            现代操作系统使用分页进行内存管理,并且很多时候需要页面替换。页面替换是将内存中当前存在的页面替换为需要但内存中不存在的页面的过程。这种情况称为页面错误。关于百科详细解释如下:

            在计算机操作系统使用分页的虚拟化内存管理,页面置换算法决定哪些内存页页出,有时也被称为换出,或写入到磁盘上,当一个页面被分配的内存需求。当请求的页面不在内存中时发生页面替换(页面错误),并且空闲页面不能用于满足分配,这是因为没有页面,或者空闲页面的数量低于某个阈值。

            当再次选择被替换的页面并调出页面时,必须将其调入页面(从磁盘读入),这需要等待I / O完成。这决定了页面替换算法的质量:等待页面插入的时间越短,算法越好。页面替换算法查看有关硬件提供的页面访问的有限信息,并尝试猜测应该替换哪些页面以最大程度地减少页面遗漏的总次数,同时平衡此操作的成本(主存储和处理器时间)算法本身。 从竞争分析的角度来看,页面替换问题是一个典型的在线问题,从某种意义上说,最佳确定性算法是已知的。

            页面替换算法的目标是减少页面错误的数量,从而提高整体性能。有许多用于页面替换的算法。我们在这里讨论一些。

    先进先出(FIFO)

    先进先出页面替换算法是最简单的页面替换算法。它维护一个队列以跟踪所有页面。我们总是将新页面添加到队列的末尾。当队列已满并且出现页面错误时,我们将删除队列前面的页面,并在队列末尾添加一个新页面。
    通过这种方式,我们将保持先进先出的技术,即,首先从内存中删除首先插入内存的页面。

     令页面引用字符串为{1、0、1、2、5、7、3、4、3、4、1},总共有4个页面槽。然后,

    贝拉迪的异常

    Belady证明,某些页面参考字符串可能会增加页面槽,从而导致更多的页面错误。

    示例
    考虑具有3个页面插槽和4个页面插槽的页面引用字符串{3,2,1,0,3,2,4,3,2,1,1,0,4}。
    具有3个页面插槽的页面错误= 3

    具有4个页面插槽的页面错误= 4

    最佳页面替换

    该算法表示,如果我们知道将来要使用哪个页面,则可以优化页面替换技术。
    根据最佳页面替换算法,始终最好替换将来将最少使用的页面。

    例  令页面引用字符串为{2,3,4,2,1,3,7,5,5,4,3},共有3个页面槽。然后,

    LRU(最近最少使用)

    该算法基于缓存技术。该算法表示替换最近最少使用的页面。

      令页面参考字符串为{1、2、3、4、1、2、5、1、2、3、4},总共有3个页面槽。然后,

    FIFO先进先出的实现

    Java实现代码:

    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    class FirstInFirstOutPageReplacement {
        private static int pageFaults(int[] pageString, int pageSlots) {
            int faults = 0;
            // Set to store the elements present in queue, used to check if a page is present or not
            HashSet<Integer> set = new HashSet<>();
            // Queue to maintain the order of insertion
            Queue<Integer> queue = new LinkedList<>();
            // traverse the page string
            for (int i = 0; i < pageString.length; i++) {
                // if there are some empty slots
                if (queue.size() < pageSlots) {
                    if (!set.contains(pageString[i])) {
                        // and the current page is missing
                        // add the page to set
                        set.add(pageString[i]);
                        // add the page to queue
                        queue.add(pageString[i]);
                        // it is a page fault, increment faults
                        faults++;
                    }
                } else {
                    // there are no empty slots and if current page is absent
                    if (!set.contains(pageString[i])) {
                        // remove the first page in queue
                        int removedPage = queue.poll();
                        // remove the page from set
                        set.remove(removedPage);
                        // add the new page to set
                        set.add(pageString[i]);
                        // add the new page to queue
                        queue.add(pageString[i]);
                        // it is page fault, increment faults
                        faults++;
                    }
                }
            }
            // return total number of page faults
            return faults;
        }
        public static void main(String[] args) {
            // Example
            int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
            int pageSlots = 4;
            System.out.println(pageFaults(pageString, pageSlots));
        }
    }

    输入:

    Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
    Page Slots = 4

    输出:

    8

    C++实现代码:

    #include <bits/stdc++.h> 
    using namespace std; 
    int pageFaults(int *pageString, int pageSlots, int n) {
        int faults = 0;
        
        // Set to store the elements present in queue, used to check if a page is present or not
        unordered_set<int> set;
        // Queue to maintain the order of insertion
        queue<int> q;
        
        // traverse the page string
        for (int i = 0; i < n; i++) {
            // if there are some empty slots
            if (q.size() < pageSlots) {
                if (set.find(pageString[i]) == set.end()) {
                    // and the current page is missing
                    // add the page to set
                    set.insert(pageString[i]);
                    // add the page to queue
                    q.push(pageString[i]);
                    // it is a page fault, increment faults
                    faults++;
                }
            } else {
                // there are no empty slots and if current page is absent
                if (set.find(pageString[i]) == set.end()) {
                    // remove the first page in queue
                    int removedPage = q.front();
                    q.pop();
                    // remove the page from set
                    set.erase(removedPage);
                    
                    // add the new page to set
                    set.insert(pageString[i]);
                    // add the new page to queue
                    q.push(pageString[i]);
                    
                    // it is page fault, increment faults
                    faults++;
                }
            }
        }
        
        return faults;
    }
    int main() {
        // Example
        int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
        int pageSlots = 4;
        cout<<pageFaults(pageString, pageSlots, sizeof(pageString) / sizeof(pageString[0]))<<endl;
        
        return 0;
    }
    

    输入:

    Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
    Page Slots = 4

    输出:

    8

    复杂度分析

    时间复杂度:

            使用HashSet允许我们在线性时间内运行给定算法。因此,该算法具有线性时间复杂度O(N)

    空间复杂度:

            O(pageSlots),我们一直只保留pageSlots队列中的页面数。因此,空间复杂度取决于pageSlots。

     

    展开全文
  • 页面替换算法opt+fifo+lru+clock页面替换算法opt+fifo+lru+clock
  • 闪存感知页面替换算法
  • 文章目录模拟实现请求分页虚存页面替换算法1. 需求分析2. 数据结构设计3. 程序设计3.1 页面替换算法基本思路3.2 请求页面队列3.3 主存块队列3.4 进程3.5 主存3.6 主存队列的维护3.7 OPT3.8 FIFO3.9 LRU4. 页面替换...

    模拟实现请求分页虚存页面替换算法

    1. 需求分析

    请求分页虚存管理在地址映射过程中,若页表中发现所要访问的页不在主存,则产生缺页异常,操作系统接到此信号后,就调出缺页异常处理程序,根据页表中给出的磁盘地址,将该页面调入主存,是作业继续运行下去。如果主存中有空闲块,则分配一个页框,将新调入页面装入,并修改页表中相应页表项的驻留位及相应的主存块号;若此时主存中没有空闲块,则要淘汰某页面,若该页在此期间被修改过,要将其先写回磁盘,这个过程就是页面替换。

    页面替换算法是虚拟存储管理实现的关键,好的算法能够减少和避免“颠簸”现象,本程序在模拟实现FIFO,LRU和OPT几种经典页面替换算法的基础上,比较各种替换算法的效率及优缺点,从而了解虚拟存储实现的过程,理解内存页面调度的机制。

    2. 数据结构设计

    • 在请求分页虚存页面替换算法中,为实现从请求页到主存块的替换,需要在模拟程序中维护两个数据结构,即请求页面队列和主存块队列。
    • 请求页面队列为进程所用,记录当前进程请求的页面块信息。
    • 主存队列由系统维护,该队列保存当前系统中各主存块的状态(包括最后访问时间、闲忙状态等)。
    • 以这两个数据结构为基础,实现各种替换算法,在系统中为用户请求寻找物理块。
    • 本程序设计含有以下功能:
      • 接收用户输入参数,包括程序长度(页面数)、页框个数及页面访问序列。
      • 程序结果采用不同的标志区分命中、替换及直接加入空闲块。
      • 实现OPT、FIFO、LRU等替换算法,并显示算法对应替换页面的过程
      • 计算各种页面替换算法的缺页中断率。

    3. 程序设计

    3.1 页面替换算法基本思路

    本程序并没有进入系统空间对实际进程页面进行控制,而是在用户空间用线性表的连续存储方式对进程页面替换进行模拟。

    1. 最佳页面替换算法(OPT)

      淘汰以后不再需要的或者最远的将来才会用到的页面。

    2. 先进先出页面替换算法(FIFO)

      淘汰最先调入主存的页面,或者说在主存中驻留时间最长的那一页。

    3. 最近最少使用页面替换算法(LRU)

      淘汰在最近一段时间里较久未被访问的页面。它是根据程序执行时所具有的局部性来考虑的,即那些刚被使用过的页面可能马上还要被使用,而那些在较长时间里未被使用的页面一般可能不会马上使用。

    3.2 请求页面队列

    typedef struct _Page { // 页面
        int pageID;     //页号
    } Page;
    typedef struct _PageQueue { //页面队列
        Page page;
        struct _PageQueue *next; //下一页面
    } PageQueue;
    typedef struct process { // 进程结构
        PageQueue pages; //页面
        unsigned int pageLength; // 页面数
    } process;//进程
    

    3.3 主存块队列

    typedef struct _Block { //块记录结构
        Page *page; //页面
        long time; //最后访问时间
        int state; //页块是否空闲
    } Block;
    typedef struct _BlockQueue { //块队列
        Block block;
        struct _BlockQueue *next;
    } BlockQueue;
    

    3.4 进程

    初始化进程以及进程需要访问的页面的序列,这里仅仅展示了进程接收输入序列作为页面访问序列的代码,本程序还提供了由系统自动生成的页面访问序列,可以指定访问页面的最大序号。

    PageQueue *InitializePageQueueWithInput(unsigned int pageLength) {
        //初始化页面,把首地址返回。如果分配失败,返回NULL
        PageQueue *head = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < pageLength; i++) {
            p = (PageQueue *) malloc(sizeof(PageQueue));
            p->page.pageID = pages[i];
            p->next = NULL;
            printf("%d ", p->page.pageID);
            if (head == NULL) head = p;
            else q->next = p;
            q = p;
        }
        printf("\n");
        return head;
    }
    
    void InitializeProcessWithInput(process *proc, unsigned int pageSize) {
        //初始化进程,接收手动输入的页面访问序列
        printf("进程初始化:\n");
        proc->pageLength = pageSize;
        proc->pages.next = InitializePageQueueWithInput(pageSize);
    }
    

    随机生成页面访问序列

    PageQueue *InitializePageQueue(unsigned int pageLength, int maxPageID) {
        //初始化页面,把首地址返回。如果分配失败,返回NULL
        srand(100);
        PageQueue *head = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < pageLength; i++) {
            p = (PageQueue *) malloc(sizeof(PageQueue));
            p->page.pageID = rand() % (maxPageID + 1);
            p->next = NULL;
            printf("%d ", p->page.pageID);
            if (head == NULL) head = p;
            else q->next = p;
            q = p;
        }
        printf("\n");
        return head;
    }
    

    3.5 主存

    接收用户输入参数,作为初始化主存的块数,也即页框数,使用一个单向链表模拟实现主存。

    BlockQueue *InitializeBlockQueue(unsigned int size) {
        //初始化主存块,把首地址返回,如果分配失败返回NULL
        BlockQueue *block = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < size; i++) {
            p = (BlockQueue *) malloc(sizeof(BlockQueue));
            p->block.time = 0;
            p->block.state = 0;
            p->block.page = NULL;
            p->next = NULL;
            if (block == NULL) block = p;
            else q->next = p;
            q = p;
        }
        return block;
    }
    

    3.6 主存队列的维护

    这里只展示主存队列一些重要操作的代码。

    BlockQueue *SearchPage(BlockQueue *blockQueue, Page page) {
        //搜索特定页面,根据页面ID进行匹配
        BlockQueue *p = blockQueue;
        while (p != NULL) {
            if (p->block.page != NULL) {
                if (p->block.page->pageID == page.pageID)
                    return p;
            }
            p = p->next;
        }
        return NULL;
    }
    
    BlockQueue *SearchIdleBlock(BlockQueue *blockQueue) {
        //搜索空闲块
        BlockQueue *p = blockQueue;
        while (p != NULL) {
            if (p->block.state == IDLE) return p;
            else p = p->next;
        }
        return NULL;
    }
    
    BlockQueue *GetOldestBlock(BlockQueue *blockQueue) {
        //取得主存中停留最久的页面,返回它的地址
        BlockQueue *p = blockQueue, *oldestAddr;
        if (p == NULL) return p;
        long oldest = p->block.time;
        oldestAddr = p;
        while (p != NULL) {
            if (p->block.time < oldest) {
                oldest = p->block.time;
                oldestAddr = p;
            }
            p = p->next;
        }
        return oldestAddr;
    }
    
    BlockQueue *GetLongestWithoutAccess(BlockQueue *blockQueue, PageQueue *currentPage){
        //获取主存中最长时间将不会被访问的页面,返回其地址
        BlockQueue *p = blockQueue, *longestAddr;
        PageQueue *q = currentPage->next;
        if (p == NULL) return p;
        longestAddr = p;
        int max_count = 0;
        while (p != NULL){
            int count = 0;
            while(q != NULL){
                count++;
                if(p->block.page->pageID == q->page.pageID) break;
                q = q->next;
            }
            if(count > max_count){
                max_count = count;
                longestAddr = p;
            }
            q = currentPage->next;
            p = p->next;
        }
        return longestAddr;
    }
    

    3.7 OPT

    void OPT(BlockQueue *blockQueue,process *proc){
        //最佳页面替换算法
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            if (SearchPage(blockQueue, currentPage->page) != NULL) {
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetLongestWithoutAccess(blockQueue,currentPage);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    

    3.8 FIFO

    void FIFO(BlockQueue *blockQueue, process *proc) {
        //先进先出算法
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            if (SearchPage(blockQueue, currentPage->page) != NULL) {
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetOldestBlock(blockQueue);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    

    3.9 LRU

    void LRU(BlockQueue *blockQueue, process *proc) {
        //最近最少使用
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            BlockQueue *searchedBlock = SearchPage(blockQueue, currentPage->page);
            if (searchedBlock != NULL) {
                searchedBlock->block.time = Time++;
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetOldestBlock(blockQueue);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    

    4. 页面替换算法测试

    测试页面访问序列(页框数为3)

    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

    在这里插入图片描述

    4.1 OPT

    运行结果

    ---------------------------------------------------------
    页框1 |  7  |  缺页! 主存不存在该页面,载入空闲页框1
    页框2 |     |
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |  缺页! 主存不存在该页面,载入空闲页框2
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |
    页框3 |  1  |  缺页! 主存不存在该页面,载入空闲页框3
    ---------------------------------------------------------
    页框1 |  2  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  0  |
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |
    页框3 |  3  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  4  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  2  |  命中! 主存已存在该页面,位于页框1
    页框2 |  4  |
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  4  |
    页框3 |  3  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |
    页框3 |  3  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  2  |  命中! 主存已存在该页面,位于页框1
    页框2 |  0  |
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |
    页框3 |  1  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  2  |  命中! 主存已存在该页面,位于页框1
    页框2 |  0  |
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |
    页框3 |  1  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  7  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  0  |
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |
    页框3 |  1  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    缺页中断率为:45.00%
    

    运行结果部分截图

    在这里插入图片描述

    对比准确数据

    在这里插入图片描述

    4.2 FIFO

    ---------------------------------------------------------
    页框1 |  7  |  缺页! 主存不存在该页面,载入空闲页框1
    页框2 |     |
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |  缺页! 主存不存在该页面,载入空闲页框2
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |
    页框3 |  1  |  缺页! 主存不存在该页面,载入空闲页框3
    ---------------------------------------------------------
    页框1 |  2  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  0  |
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  3  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  3  |
    页框3 |  0  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  4  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  3  |
    页框3 |  0  |
    ---------------------------------------------------------
    页框1 |  4  |
    页框2 |  2  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  0  |
    ---------------------------------------------------------
    页框1 |  4  |
    页框2 |  2  |
    页框3 |  3  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  0  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  2  |
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  2  |
    页框3 |  3  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  2  |  命中! 主存已存在该页面,位于页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  1  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  1  |
    页框3 |  2  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  0  |  命中! 主存已存在该页面,位于页框1
    页框2 |  1  |
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  1  |  命中! 主存已存在该页面,位于页框2
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  7  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  1  |
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |
    页框3 |  1  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    缺页中断率为:75.00%
    

    运行结果部分截图

    在这里插入图片描述

    对比准确数据

    在这里插入图片描述

    4.3 LRU

    ---------------------------------------------------------
    页框1 |  7  |  缺页! 主存不存在该页面,载入空闲页框1
    页框2 |     |
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |  缺页! 主存不存在该页面,载入空闲页框2
    页框3 |     |
    ---------------------------------------------------------
    页框1 |  7  |
    页框2 |  0  |
    页框3 |  1  |  缺页! 主存不存在该页面,载入空闲页框3
    ---------------------------------------------------------
    页框1 |  2  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  0  |
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  1  |
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |
    页框3 |  3  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  2  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  4  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  0  |
    页框3 |  3  |
    ---------------------------------------------------------
    页框1 |  4  |
    页框2 |  0  |
    页框3 |  2  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  4  |
    页框2 |  3  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  0  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  3  |
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  3  |  命中! 主存已存在该页面,位于页框2
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  0  |
    页框2 |  3  |
    页框3 |  2  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  1  |  缺页! 主存不存在该页面,替换页框1
    页框2 |  3  |
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  1  |
    页框2 |  3  |
    页框3 |  2  |  命中! 主存已存在该页面,位于页框3
    ---------------------------------------------------------
    页框1 |  1  |
    页框2 |  0  |  缺页! 主存不存在该页面,替换页框2
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  1  |  命中! 主存已存在该页面,位于页框1
    页框2 |  0  |
    页框3 |  2  |
    ---------------------------------------------------------
    页框1 |  1  |
    页框2 |  0  |
    页框3 |  7  |  缺页! 主存不存在该页面,替换页框3
    ---------------------------------------------------------
    页框1 |  1  |
    页框2 |  0  |  命中! 主存已存在该页面,位于页框2
    页框3 |  7  |
    ---------------------------------------------------------
    页框1 |  1  |  命中! 主存已存在该页面,位于页框1
    页框2 |  0  |
    页框3 |  7  |
    ---------------------------------------------------------
    缺页中断率为:60.00%
    

    运行结果部分截图

    在这里插入图片描述

    对比准确数据

    在这里插入图片描述

    5. 总结

    分页虚拟存储管理既有优点又有缺点,优点是作业的程序和数据可按页分散存放在主存中,有效解决了碎片问题; 既有利于改进主存利用率,又有利于多道程序运行。缺点是要有硬件支持,要进行缺页中断处理,机器成本增加,系统开销加大。缺页中断率小是虚拟存储管理目标之一,而影响缺页中断率的因素主要有:主存页框数、页面大小、页面分配机制,替换算法、程序的局部性。好的页面替换算法能够降低缺页中断率。

    6. 完整源码

    //
    // Created by wylu on 2018/1/6.
    //
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<ctype.h>
    #include<sys/time.h>
    #include<unistd.h>
    #include<stdlib.h>
    
    #define BUSY 1
    #define IDLE 0
    
    #define COLOR_Exist 0
    #define COLOR_NotExist_IDLE 1
    #define COLOR_NotExist_NoIDLE 2
    
    double hitCount = 0;
    int pages[100];
    
    typedef struct _Page { // 页面
        int pageID;     //页号
    } Page;
    typedef struct _PageQueue { //页面队列
        Page page;
        struct _PageQueue *next; //下一页面
    } PageQueue;
    typedef struct _Block { //块记录结构
        Page *page; //页面
        long time; //最后访问时间
        int state; //页块是否空闲
    } Block;
    typedef struct _BlockQueue { //块队列
        Block block;
        struct _BlockQueue *next;
    } BlockQueue;
    typedef struct process { // 进程结构
        PageQueue pages; //页面
        unsigned int pageLength; // 页面数
    } process;//进程
    
    int Time = 0;
    
    long GetSystemUtime() {
        //获取系统当前时间的微秒数
        struct timeval nowit;
        gettimeofday(&nowit, NULL);
        return 1000000 * nowit.tv_sec + nowit.tv_usec;;
    }
    
    BlockQueue *InitializeBlockQueue(unsigned int size) {
        //初始化主存块,把首地址返回,如果分配失败返回NULL
        BlockQueue *block = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < size; i++) {
            p = (BlockQueue *) malloc(sizeof(BlockQueue));
            p->block.time = 0;
            p->block.state = 0;
            p->block.page = NULL;
            p->next = NULL;
            if (block == NULL) block = p;
            else q->next = p;
            q = p;
        }
        return block;
    }
    
    int GetBlockQueueSize(BlockQueue *blockQueue) {
        //获取块长度
        BlockQueue *presentBlock = blockQueue;
        int blockQueueSize = 0;
        while (presentBlock != NULL) {
            blockQueueSize++;
            presentBlock = presentBlock->next;
        }
        return blockQueueSize;
    }
    
    void ResetBlockQueue(BlockQueue *blockQueue) {
        //清空块内容
        BlockQueue *presentBlock = blockQueue;
        while (presentBlock != NULL) {
            presentBlock->block.page = NULL;
            presentBlock->block.state = IDLE;
            presentBlock->block.time = 0;
            presentBlock = presentBlock->next;
        }
    }
    
    PageQueue *InitializePageQueue(unsigned int pageLength, int maxPageID) {
        //初始化页面,把首地址返回。如果分配失败,返回NULL
        srand(100);
        PageQueue *head = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < pageLength; i++) {
            p = (PageQueue *) malloc(sizeof(PageQueue));
            p->page.pageID = rand() % (maxPageID + 1);
            p->next = NULL;
            printf("%d ", p->page.pageID);
            if (head == NULL) head = p;
            else q->next = p;
            q = p;
        }
        printf("\n");
        return head;
    }
    
    PageQueue *InitializePageQueueWithInput(unsigned int pageLength) {
        //初始化页面,把首地址返回。如果分配失败,返回NULL
        PageQueue *head = NULL, *p = NULL, *q = NULL;
        for (int i = 0; i < pageLength; i++) {
            p = (PageQueue *) malloc(sizeof(PageQueue));
            p->page.pageID = pages[i];
            p->next = NULL;
            printf("%d ", p->page.pageID);
            if (head == NULL) head = p;
            else q->next = p;
            q = p;
        }
        printf("\n");
        return head;
    }
    
    void InitializeProcess(process *proc, unsigned int pageSize, unsigned int maxPageID) {
        //初始化进程,随机生成进程页面访问序列
        printf("进程初始化:\n");
        proc->pageLength = pageSize;
        proc->pages.next = InitializePageQueue(pageSize, maxPageID);
    }
    
    void InitializeProcessWithInput(process *proc, unsigned int pageSize) {
        //初始化进程,接收手动输入的页面访问序列
        printf("进程初始化:\n");
        proc->pageLength = pageSize;
        proc->pages.next = InitializePageQueueWithInput(pageSize);
    }
    
    BlockQueue *SearchPage(BlockQueue *blockQueue, Page page) {
        //搜索特定页面
        BlockQueue *p = blockQueue;
        while (p != NULL) {
            if (p->block.page != NULL) {
                if (p->block.page->pageID == page.pageID)
                    return p;
            }
            p = p->next;
        }
        return NULL;
    }
    
    BlockQueue *SearchIdleBlock(BlockQueue *blockQueue) {
        //搜索空闲块
        BlockQueue *p = blockQueue;
        while (p != NULL) {
            if (p->block.state == IDLE) return p;
            else p = p->next;
        }
        return NULL;
    }
    
    int GetBlockLable(BlockQueue *blockQueue, BlockQueue *goalBlock) {
        //返回块号,编号从1开始
        BlockQueue *p = blockQueue;
        int count = 1;
        while (p != goalBlock) {
            p = p->next;
            count++;
        }
        return count;
    }
    
    BlockQueue *GetOldestBlock(BlockQueue *blockQueue) {
        //取得主存中停留最久的页面,返回它的地址
        BlockQueue *p = blockQueue, *oldestAddr;
        if (p == NULL) return p;
        long oldest = p->block.time;
        oldestAddr = p;
        while (p != NULL) {
            if (p->block.time < oldest) {
                oldest = p->block.time;
                oldestAddr = p;
            }
            p = p->next;
        }
        return oldestAddr;
    }
    
    BlockQueue *GetLongestWithoutAccess(BlockQueue *blockQueue, PageQueue *currentPage){
        //获取主存中最长时间将不会被访问的页面,返回其地址
        BlockQueue *p = blockQueue, *longestAddr;
        PageQueue *q = currentPage->next;
        if (p == NULL) return p;
        longestAddr = p;
        int max_count = 0;
        while (p != NULL){
            int count = 0;
            while(q != NULL){
                count++;
                if(p->block.page->pageID == q->page.pageID) break;
                q = q->next;
            }
            if(count > max_count){
                max_count = count;
                longestAddr = p;
            }
            q = currentPage->next;
            p = p->next;
        }
        return longestAddr;
    }
    
    void PrintBlockList(BlockQueue *blockQueue, int pageID, int color) {
        //打印块信息
        BlockQueue *presentBlock = blockQueue;
        for (int i = 0; i < GetBlockQueueSize(blockQueue); i++) {
            if (presentBlock == NULL) break;
            printf("页框%d ", i + 1);
            if (presentBlock->block.state == IDLE) {
                printf("|     |\n");
            } else {
                if (presentBlock->block.page->pageID != pageID) {
                    printf("|  %d  |\n", presentBlock->block.page->pageID);
                } else {
                    switch (color) {
                        case COLOR_Exist:
                            printf("|  %d  |  命中! 主存已存在该页面,位于页框%d\n", 
                                   pageID, GetBlockLable(blockQueue, presentBlock));
                            hitCount++;
                            break;
                        case COLOR_NotExist_IDLE:
                            printf("|  %d  |  缺页! 主存不存在该页面,载入空闲页框%d\n", 
                                   pageID, GetBlockLable(blockQueue, presentBlock));
                            break;
                        case COLOR_NotExist_NoIDLE:
                            printf("|  %d  |  缺页! 主存不存在该页面,替换页框%d\n", 
                                   pageID, GetBlockLable(blockQueue, presentBlock));
                            break;
                        default:
                            break;
                    }
                }
            }
            presentBlock = presentBlock->next;
        }
        printf("---------------------------------------------------------\n");
    }
    
    void FIFO(BlockQueue *blockQueue, process *proc) {
        //先进先出算法
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            if (SearchPage(blockQueue, currentPage->page) != NULL) {
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetOldestBlock(blockQueue);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    
    void LRU(BlockQueue *blockQueue, process *proc) {
        //最近最少使用
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            BlockQueue *searchedBlock = SearchPage(blockQueue, currentPage->page);
            if (searchedBlock != NULL) {
                searchedBlock->block.time = Time++;
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetOldestBlock(blockQueue);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    
    void OPT(BlockQueue *blockQueue, process *proc){
        //最佳页面替换算法
        PageQueue *currentPage = proc->pages.next;
        while (currentPage != NULL) {
            if (SearchPage(blockQueue, currentPage->page) != NULL) {
                PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
            } else {
                BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
                if (idleBlock != NULL) {
                    idleBlock->block.state = BUSY;
                    idleBlock->block.time = Time++;
                    idleBlock->block.page = (Page *) malloc(sizeof(Page));
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_IDLE);
                } else {
                    idleBlock = GetLongestWithoutAccess(blockQueue,currentPage);
                    idleBlock->block.time = Time++;
                    idleBlock->block.page->pageID = currentPage->page.pageID;
                    PrintBlockList(blockQueue, 
                                   currentPage->page.pageID, COLOR_NotExist_NoIDLE);
                }
            }
            currentPage = currentPage->next;
        }
    }
    
    void SelectAlgorithm(){
        printf("\n========================================================\n");
        printf("\t1.OPT\t2.FIFO\t3.LRU\t0.exit\n");
        printf("========================================================\n");
    }
    
    int main() {
        bool isGoOn = true;
        while (isGoOn){
            //主存块数,即页框数
            unsigned int blockNumber;
            //进程页面数
            unsigned int pageNumber;
            printf("请输入主存块数(即页框数):");
            scanf("%u", &blockNumber);
            printf("请输入进程页面数:");
            scanf("%u", &pageNumber);
            printf("========================================================\n");
            printf("\t主存页框数: %u, 进程页面数: %u\n", blockNumber, pageNumber);
            printf("========================================================\n");
    
            BlockQueue *blocks;
            process proc;
            printf("是否手动输入访问序列? y/n\n");
            getchar();
            if (getchar() == 'y'){
                printf("请输入访问序列:");
                for (int i = 0; i < pageNumber; ++i) {
                    scanf("%d",&pages[i]);
                }
                InitializeProcessWithInput(&proc,pageNumber);
            } else{
                InitializeProcess(&proc, pageNumber, 10);
            }
            blocks = InitializeBlockQueue(blockNumber);
    
            SelectAlgorithm();
            int oper;
            while (scanf("%d",&oper)){
                int flag = 0;
                printf("\n---------------------------------------------------------\n");
                hitCount = 0;
                switch (oper){
                    case 1:
                        OPT(blocks, &proc);
                        break;
                    case 2:
                        FIFO(blocks, &proc);
                        break;
                    case 3:
                        LRU(blocks, &proc);
                        break;
                    case 0:
                        flag = 1;
                        break;
                    default:
                        SelectAlgorithm();
                        printf("非法输入!请重新输入:");
                        break;
                }
                if (flag == 1) break;
                printf("缺页中断率为:%.2lf%%\n",(1-(hitCount/pageNumber))*100);
                ResetBlockQueue(blocks);
                SelectAlgorithm();
            }
            printf("是否重新输入访问序列? y/n\n");
            getchar();
            if(getchar() != 'y') isGoOn = false;
            system("cls");
        }
    }
    
    展开全文
  • 操作系统实验报告,内含4个实验,页面替换算法,作业调度,进程调度,spooling技术。实验报告写得比较简单,都分为3块,1实验介绍 2,程序流程图 3实现过程。
  • NAND闪存的高效页面替换算法
  • 操作系统第三次实验报告_页面替换算法.docx
  • CLRU:基于NAND闪存的消费电子产品的新页面替换算法
  • ** 今天老师在讲操作系统-虚拟存储管理全局页面替换算法,局部页面替换算法,其中也讲到了一些比较底层的知识,听到深处仿佛来到一个新世界,但又恍惚而不知路在何方,故整理记录如下:** 一、全局页面替换算法 1...
  • 而用来选择淘汰哪一页的规则叫做页面置换算法。 1.最佳置换算法(OPT)(理想置换算法) 从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不...
  • 页替换 这是 CSC 4103 的一个项目,它实现了操作系统使用的页面替换算法
  • b: 先进先出算法(FIFO):淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。 c:最近最久未使用算法(LRU):淘汰最近最久未被使用的页面。 (3)程序采用人工的方法选择,依次换策略选择一个可置换...
  • 3.3 引用串的生成实验三页面替换算法 • LRU 算法则需要一个尺寸为F 的数组,该数组用来实现排队功能: 每次处理一个新的页面引用时,则把该页放置在队列的末尾。这样, 每当需要淘汰一个页面时,从队首取到的即最长...
  • 页面替换算法FIFO,OPT,LRU的js实现

    千次阅读 2018-11-22 09:40:51
    OPT,FIFO,LRU页面置换算法的JS实现一.FIFO算法二. LRU算法三.Optimal算法:四.运行截图五.代码: 一.FIFO算法 1.1 先进先出算法基本思想: 淘汰最先进入的页面,选择在内存中驻留最久的页面的予以淘汰。 基本...
  • 操作系统实验--页面替换算法

    千次阅读 2016-05-26 07:00:03
    操作系统实验4–页面替换算法基本数据结构 变量名 意义 pageNum 总页面数 rsLen 引用串长度 frameNum 物理内存长度 rs[] 保存引用串的数组 frameArr[] 保存物理内存的数组 XXModeCounter XX算法的缺页...
  • typedef struct _Page{ // 页面 int pageID; //页号 }Page; typedef struct _PageQueue{ //页面队列 Page page; struct _PageQueue* next; //下一页面 }PageQueue; typedef struct _Block{ //块记录结构
  • page-replacement-algorithms:2021年Spring在NTNUÅlesund的操作系统与系统编程[IDATA2305]课程的一部分,分配任务以Java编写最佳页面替换算法
  • pageReplacementGUI 这是一个小组项目,我们使用Python Tkinter为使用Bélády的Anomaly的页面替换算法准备了GUI。它由FIFO,SC,RP,OPR和LIFO组成。 (08/2020-12/2020)
  • (1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响 。 (2)实现对FIFO,LRU算法的模拟

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 74,462
精华内容 29,784
关键字:

页面替换算法

友情链接: Notepad.zip