Written at the top: This article is reproduced from https://blog.csdn.net/weixin_52760656/article/details/127715747?spm=1001.2014.3001.5502

Before writing this article, allow me to say a few words. This article is the code I learned from another blogger when I was writing the operating system experiment. The problems I found and my own problems in writing code are shared with you as experience. This note is my first note. If there is any mistake, please point it out in the comment area, and I can discuss it with you. the

The code for this experiment is at the end of the article.

Experimental environment: vscode.

Set up a table:

Status 1 means that the page is in memory, and status 0 means that the page is not in memory;

Suppose a physical block size is 1K, which is 1024B;

Uses a first-in-first-out page replacement algorithm.

Define the number of pages PN, page size PAGESIZE;

#define PN 7//Number of pages
#define PAGESIZE 1024//page size: 1K

Define the structure;

typedef struct 
{
    int P;//presence sign
    int M;//modify flag
    int pno;//page number
    int bno;//physical block number
    int place;//displacement
}PAGETAB;

Define the structure array in the main function to store the page table PAGETAB s[];

void main(){
    PAGETAB s[PN];
    int i,sel;
    int flag=1;
    for(i=0;i<PN;i++){
        s[i].pno=i;
        if(i<3){
            s[i].P=1;
        }
        else{
            s[i].bno=0;
            s[i].P=0;
        }
    }
    s[0].bno=9;
    s[1].bno=5;
    s[2].bno=4;
}

FIFO page replacement algorithm;

void change(PAGETAB s[]){
    int flag=1;
    int a,p;//a is the logical address, p is the page number
    int x=0,i=0;
    int weiyi,place;//displacement, physical address
    int found=0;
    char st;//Fault status
    while(flag==1){
        st='N';
        printf("Please enter the logical address:");
        scanf("%d",&a);
        p=a/PAGESIZE;
        weiyi=a%PAGESIZE;
        if(p>=PN){
            printf("Logical address is illegal!\n");
        }
        else{
            for(i=0;i<PN;i++){
                if(s[i].pno==p){//Use the page number p to find the corresponding page
                    break;
                }
            }
            if(s[i].P==0){//status is 0
                st='Y';//Description missing page
                for(x;x<PN;x++){//s page
                    if(s[x].P==1){
                       found=1;
                       break; 
                    }
                }//Indicates that there is a table with status 1 in page s, skip the following if
                if(found=0){//Indicates that there is no table with status 1 in page s, execute this if
                    for(x=0;x<PN;x++){
                        if(s[x].P==1){
                            break;
                        }
                    }
                }
                found=0;
                s[x].P=0;//s page status changed to 0
                s[i].bno=s[x].bno;//The physical block number of the p page is recorded as the physical block number of the s page
                s[x].bno=0;//s page block number is changed to 0
                s[i].P=1;//p page status changed to 1
            }   
            place=s[i].bno*PAGESIZE+weiyi;//Physical address = physical block number * page size + page displacement
            printf("Logical address:%d\n Page number:%d\n In-page displacement:%d\n Is there a page fault:%c\n Physical block:%d\n Physical address:%d\n",a,p,weiyi,st,s[i].bno,place);
        }
        printf("Whether to continue?(1:is 0:no):");
        scanf("%d",&flag);
    }
}

Display the current page table;

void show(PAGETAB s[]){
    int i;
    for(i=0;i<PN;i++){
        printf("Page number:%d\n state:%d\n Physical block number:%d\n",s[i].pno,s[i].P,s[i].bno);
    }
}

Screenshot of the experiment running result:

 Obviously, when the input logical address is 2546, the page number is 2. At this time, in the page table, the page status of page number 2 is 1. In the change function, skip if(s[i].P= =0), direct output;

When the input logical address is 5456, the page number is 5. At this time, in the page table, the state of the page with page number 5 is 0, and enter if(s[i].P==0);

if(s[i].P==0){//At this time, the page number i is 5, and the state is 0
                st='Y';//Fault status is set to 'Y'
                for(x;x<PN;x++){
                    if(s[x].P==1){//Find the first page with status 1
                       found=1;
                       break; //break out of the for loop
                    }
                }//At this point found is 1, skip the following if
                if(found=0){
                    for(x=0;x<PN;x++){
                        if(s[x].P==1){
                            break;
                        }
                    }
                }
                found=0;//Set found to 0
                s[x].P=0;//Change the found page status to 0
                s[i].bno=s[x].bno;//The physical block number of the i-th page (that is, the 5th page) is recorded as the physical block number where the page is found
                s[x].bno=0;//The page block number is changed to 0
                s[i].P=1;//i page status changed to 1
            }   

Because the input logical address is 5456, the page with page number 0 is eliminated and transferred to the page with page number 5;

When the input logical address is 9867, the page number is 9, which exceeds the length of the page table, and an error is output.

if(p>=PN){
            printf("Logical address is illegal!\n");
        }

Problems encountered in this experiment:

1: When reposting the code written by the original blogger, he made a mistake:

place = s[i].bno*PAGESIZE+place;

Here it should be written as:

place=s[i].bno*PAGESIZE+weiyi;

place is the physical address, physical address = physical block number * page size + page displacement

2: The experimental code written by me is different from the original blogger: page fault status. The original blogger used int st=0 to represent missing pages, and st=1 to represent no missing pages. In fact, st=0 means that there is no page fault, and st=1 means that the page is faulty. And I use char st='N' to represent no missing pages, and 'Y' to represent missing pages. One more thing to say about char is that in printf, %c is used to output. I started using %s, and found that the program crashed. Later, I found it to be %c. This is because I am not familiar with C language. It's best if it helps you, and if it doesn't help, have fun.

3: When referring to the code of the original blogger, I found that an int M is defined in the structure, but M does not appear in the following code, so I think this M can be deleted, and I did not delete it because I was lazy.

4: There are some mistakes in my code comments, if you don't understand, you can tell them in the comment area, and I will try my best to explain.

The complete code of this experiment:

#include<stdio.h>
#define PN 7//Number of pages
#define PAGESIZE 1024//page size: 1K

typedef struct 
{
    int P;//presence sign
    int M;//modify flag
    int pno;//page number
    int bno;//physical block number
    int place;//displacement
}PAGETAB;

void change(PAGETAB s[]){
    int flag=1;
    int a,p;//a is the logical address, p is the page number
    int x=0,i=0;
    int weiyi,place;//displacement, physical address
    int found=0;
    char st;//Fault status
    while(flag==1){
        st='N';
        printf("Please enter the logical address:");
        scanf("%d",&a);
        p=a/PAGESIZE;
        weiyi=a%PAGESIZE;
        if(p>=PN){
            printf("Logical address is illegal!\n");
        }
        else{
            for(i=0;i<PN;i++){
                if(s[i].pno==p){//Use the page number p to find the corresponding page
                    break;
                }
            }
            if(s[i].P==0){//status is 0
                st='Y';//Description missing page
                for(x;x<PN;x++){//s page
                    if(s[x].P==1){
                       found=1;
                       break; 
                    }
                }//Indicates that there is a table with status 1 in page s, skip the following if
                if(found=0){//Indicates that there is no table with status 1 in page s, execute this if
                    for(x=0;x<PN;x++){
                        if(s[x].P==1){
                            break;
                        }
                    }
                }
                found=0;
                s[x].P=0;//s page status changed to 0
                s[i].bno=s[x].bno;//The physical block number of the p page is recorded as the physical block number of the s page
                s[x].bno=0;//s page block number is changed to 0
                s[i].P=1;//p page status changed to 1
            }   
            place=s[i].bno*PAGESIZE+weiyi;//Physical address = physical block number * page size + page displacement
            printf("Logical address:%d\n Page number:%d\n In-page displacement:%d\n Is there a page fault:%c\n Physical block:%d\n Physical address:%d\n",a,p,weiyi,st,s[i].bno,place);
        }
        printf("Whether to continue?(1:is 0:no):");
        scanf("%d",&flag);
    }
}

void show(PAGETAB s[]){
    int i;
    for(i=0;i<PN;i++){
        printf("Page number:%d\n state:%d\n Physical block number:%d\n",s[i].pno,s[i].P,s[i].bno);
    }
}

void main(){
    PAGETAB s[PN];
    int i,sel;
    int flag=1;
    for(i=0;i<PN;i++){
        s[i].pno=i;
        if(i<3){
            s[i].P=1;
        }
        else{
            s[i].bno=0;
            s[i].P=0;
        }
    }
    s[0].bno=9;
    s[1].bno=5;
    s[2].bno=4;

    while(flag==1){
        printf("************system menu************\n");
        printf("***********1: change***********\n");
        printf("***********2: show  ***********\n");
        printf("***********0: exit  ***********\n");
        printf("*******************************\n");
        printf("enter your choice(0-2): ");
        scanf("%d",&sel);

        switch (sel)
        {
        case 1:change(s);break;
        case 2:show(s);break;
        case 0:flag=0;break;
        
        default:printf("input error!");break;
        }
    }
}

Thank you for watching, please give more valuable comments, thank you!