ucorelab3

LAB 3

The experiment purpose

• Learn about virtual memory Page Fault Exception handling implementation
• Understand the implementation of page replacement algorithm in the operating system

Experimental content

This experiment is based on Experiment 2 , With the help of the page table mechanism and the interrupt exception handling mechanism involved in Experiment 1 , complete Page Fault Exception handling and FIFO Implementation of page replacement algorithm , Combined with the cache space provided by the disk , Thus, virtual storage management can be supported , Provide a larger than the actual physical memory space “ Bigger ” Virtual memory space for the system to use . This experiment is simpler than the implementation in the actual operating system , However, you need to understand the specific implementation of Experiment 1 and Experiment 2 . The design and implementation of virtual memory management in actual operating system is quite complex , Related to the process management system 、 Cross access to file systems, etc . If you have spare time , You can try to complete the extension exercise , Realization extended　clock Page replacement algorithm .

practice

practice 0： Fill in the existing experiment

This experiment relies on experiments 1/2. Please take your experiment 1/2 Fill in the code in this experiment. There are “LAB1”,“LAB2” The corresponding part of the notes .

Explain ： Use here meld take lab2 Modified default_pmm.c and pmm.c Move the annotated part in lab3 Corresponding position in , At the same time lab1 Modified in debug.c,trap.c as well as init.c Move the annotated part in lab3 The corresponding position in .

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-3vQjGKG2-1652150932796)(C:\Users\zhaolv\AppData\Roaming\Typora\typora-user-images\image-20220508223041924.png)]

practice 1： Map physical pages to unmapped addresses （ You need to program ）

complete do_pgfault（mm/vmm.c） function , Map physical pages to unmapped addresses . When setting access permissions, you need to refer to the page VMA Authority , At the same time, you should pay attention to the memory control when mapping physical pages Structure , Instead of the kernel page table . Be careful ： stay LAB3 EXERCISE 1 Fill in the code at . perform

make　qemu

after , If you pass check_pgfault After the test of the function , There will be “check_pgfault() succeeded!” Output , Means to practice 1 Basically right .

Please briefly describe your design and implementation process in the experimental report . Please answer the following questions ：

• Please describe the page directory entry （Page Directory Entry） And page table entries （Page Table Entry） The middle part is right ucore The potential use of implementing page replacement algorithms .
• If ucore The missing page service routine of accesses memory during execution , Page access exception occurred , What does the hardware do ？

Explain ： First , We need to know about page exceptions ：

Page exception ：

When the paging mechanism is started , If the physical page frame corresponding to the virtual address of an instruction or data is not in memory or the access type is wrong （ For example, write a read-only page or user mode program to access kernel mode data, etc ）, A page error exception will occur . The main reasons for page exceptions are :

The target page does not exist （ Page table entries are all 0, That is, the mapping between the linear address and the physical address has not been established or has been revoked ）, The corresponding physical page is not in memory （ Page table entry is not empty , but Present Sign a =0, For example swap Partition or disk file , Access permissions do not match （ At this time, the page table item P sign =1, For example, trying to write a read-only page ）.

When one of the above occurs , Then there will be a page page fault（#PF） abnormal .CPU Will store the linear address of the exception in CR2 in , And put the value representing the page access exception type （ Page access exception error code for short ,errorCode） Save in interrupt stack .

Key data structure and correlation function analysis ：

In Experiment 2, the data structure and related operations of memory are directly aimed at the actual resources – Management of physical memory space , There is no memory from general applications “ demand ” consider , That is, relevant data structures and operations are needed to reflect the impact of general applications on virtual memory “ demand ”. The virtual memory of general applications “ demand ” With physical memory space “ supply ” There is no direct correspondence ,ucore It's through page fault Exception handling to indirectly complete the connection between the two .

page_fault The function doesn't know what is “ legal ” The virtual page of , as a result of ucore There is also a lack of data structure to describe this kind of data that is not in physical memory “ legal ” Virtual page . So ucore Through establishment mm_struct and vma_struct data structure , It describes ucore Simulate the legal memory space required by the application to run . When accessing memory, a page fault When abnormal , How to get access to memory （ Read or write ） And the specific virtual memory address , such ucore You can query this address , See if it belongs to vma_struct The legal address range described in the data structure , If in , You can request page adjustment according to specific conditions / Page in / out processing （ This is practice 2 The part involved ）; If not , False report .mm_struct and vma_struct The schematic diagram of data structure combined with page table to represent virtual address space and physical address space is as follows ：

stay ucore Describes the application's response to virtual memory “ demand ” The data structure is vma_struct（ It's defined in vmm.h in ）, And aiming at vma_struct Function operation of . Here's a vma_struct The variable of structure is abbreviated as vma Variable .vma_struct Is defined as follows ：

struct vma_struct {
      
        struct mm_struct *vm_mm;  // Point to a ratio vma_struct Data structures at higher levels of abstraction mm_struct 
        uintptr_t vm_start;      //vma Start address of 
        uintptr_t vm_end;      // vma The end address of 
        uint32_t vm_flags;     //  Properties of virtual memory space 
        list_entry_t list_link;  // Double linked list , Link the virtual memory space from small to large 
   };  

vm_start and vm_end Describes the starting and ending positions of a virtual memory space with consecutive addresses , Both values should be PGSIZE The alignment of the , And it describes a reasonable address space range （ That is, strictly ensure vm_start < vm_end The relationship between ）;list_link It's a two-way list , Use a series from small to large vma_struct Represents the virtual memory space linked together , And also requires these linked vma_struct It should be disjoint , namely vma There is no intersection between the address spaces ;vm_flags Represents the properties of this virtual memory space , Current properties include ：

#define VM_READ 0x00000001 // read-only 
#define VM_WRITE 0x00000002 // read-write 
#define VM_EXEC 0x00000004 // Executable 

vm_mm It's a pointer , Point to a ratio vma_struct Data structures at higher levels of abstraction mm_struct, Here's a mm_struct The variable of structure is abbreviated as mm Variable . This data structure represents the common attributes of all virtual memory spaces , The specific definitions are as follows ：

struct mm_struct {
      
        list_entry_t mmap_list;  // Two way chain header , All virtual memory spaces belonging to the same page directory table are linked 
        struct vma_struct *mmap_cache;  // Point to the virtual memory space currently in use 
        pde_t *pgdir; // It points to  mm_struct The page table maintained by the data structure 
        int map_count; // Record mmap_list Inside the link vma_struct The number of 
        void *sm_priv; // Point to the chain header used to link and record page access 
 };  

mmap_list It is a bidirectional chain header , All virtual memory spaces belonging to the same page directory table are linked ,mmap_cache It refers to the virtual memory space currently in use , Due to the “ Locality ” principle , The virtual memory space currently being used may be used in the next operation , At this time, there is no need to look up the linked list , Instead, you can directly use this pointer to find the next virtual memory space to be used .pgdir The point is mm_struct The page table maintained by the data structure . By visiting pgdir You can find out whether the page entry corresponding to a virtual address exists and the properties of the page entry .map_count Record mmap_list Inside the link vma_struct The number of .sm_priv Point to the chain header used to link and record page access , This establishes mm_struct And what we will talk about later swap_manager The connection between .

Processing mechanism after page exception ：

trap–> trap_dispatch–>pgfault_handler–>do_pgfault

The following needs to be analyzed in detail do_pgfault function .do_pgfault The calling relationship of is shown in the following figure ：

After page access exception is generated ,CPU Load the linear address causing the page access exception into the register CR2 in , And give the error code errorCode, Describes the type of page access exception .ucore OS Will save this value in struct trapframe in tf_err In the member variable . The interrupt service routine will call the page access exception handler do_pgfault Carry out specific treatment . The page access exception handling here is to realize on-demand paging 、 The key of the page in and out mechanism .

ucore in do_pgfault Function is the main function to handle page access exceptions , It is based on CPU Control register of CR2 The physical address of the page access exception obtained in and according to errorCode To find out whether this address is in a VMA And whether the correct read and write permissions are met , If within this range and the permissions are correct , This is considered a legitimate visit , But there is no correspondence between the actual and the actual . So you need to allocate a free memory page , And modify the page table to complete the mapping from virtual address to physical address , Refresh TLB, And then call iret interrupt , Return to the instruction that generated the page access exception and re execute the instruction . If the virtual address is not in a VMA Within the scope of , Is considered an illegal visit .

Next, let's explain in detail do_pgfult Implementation process of ：
appear page fault after , There will be an interrupt status pointer tf, to trap() In dealing with ：

void
trap(struct trapframe *tf) {
    
    // dispatch based on what type of trap occurred
    trap_dispatch(tf);
}

trap Called in trap_dispatch function ：

static void
trap_dispatch(struct trapframe *tf) {
    
    char c;

    int ret;

    switch (tf->tf_trapno) {
    
    case T_PGFLT:  //page fault
        if ((ret = pgfault_handler(tf)) != 0) {
    
            print_trapframe(tf);
            panic("handle pgfault failed. %e\n", ret);
        }
        break;

Because it should be page fault, So call pgfault_handler()：

static int
pgfault_handler(struct trapframe *tf) {
    
    extern struct mm_struct *check_mm_struct;
    print_pgfault(tf);
    if (check_mm_struct != NULL) {
    
        return do_pgfault(check_mm_struct, tf->tf_err, rcr2());
    }
    panic("unhandled page fault.\n");
}

Finally called. do_pgfault() function ：

do_pgfault() function :

First of all to see do_pgfault The function prototype ：

int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr)

The three parameters passed in are

• mm: Application virtual storage manager
• error_code: Wrong type
• addr: Specific error virtual address

The specific function code is ：

int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    
    int ret = -E_INVAL; 
 /* Judge the virtual address , If the range of virtual addresses exceeds the limit ,  Or the virtual address cannot be found , That is to say, the address is illegal ,  Made an illegal visit , Then you can report an error directly .*/
    // Try to find including addr Of vma
    struct vma_struct *vma = find_vma(mm, addr);
    pgfault_num++;
    // Judge addr Whether in vma In the range of 
    if (vma == NULL || vma->vm_start > addr) {
    
        cprintf("not valid addr %x, and can not find it in vma\n", addr);
        goto failed;
    }
    // Error type check 
    /* Low error code 2 The positions are ：P sign （ position 0） Its lowest ： Indicates that the current error is   Because there is no page （0） cause , Or because of access violation （1） cause . W / R sign （ position 1）： Indicates that the current error is due to a read operation （0）  Cause or write （1） cause .*/
    switch (error_code & 3) {
    
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
    case 2: /*  Apply for write operation , Physical memory does not exist , And the content of the corresponding address is not allowed to be written */
        if (!(vma->vm_flags & VM_WRITE)) {
    
            cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
            goto failed;
        }
        break;
    case 1: /*  Apply for read operation , And in physical memory （ Therefore, an error has been reported , So the permission is insufficient ） */
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0: /*  Read operation is requested but does not exist in physical memory , And the address data is not allowed to be read or loaded */ 
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
    
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    uint32_t perm = PTE_U;//prem: Intermediate variables that give permissions to physical pages 
    if (vma->vm_flags & VM_WRITE) {
    
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);
    ret = -E_NO_MEM;
    pte_t *ptep=NULL;
    
    // Modification part 
    // Find the page directory , If it does not exist, it will fail 
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
    
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    if (*ptep == 0) {
     //  If it is a newly created secondary page table .
        // Initialize and establish the mapping relationship between the virtual address and the physical page 
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
    
            // If initialization fails, report an error and exit .
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
   // Exercise 2 realize  
   // Page table entry is not empty , Try switching to a page 
    else {
     
   
        if(swap_init_ok) {
    
            struct Page *page=NULL;
	    // according to mm The structure and addr Address , Try to switch the contents of the hard disk into page in 
            if ((ret = swap_in(mm, addr, &page)) != 0) {
    
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }    
            page_insert(mm->pgdir, page, addr, perm);
	    // Establish the correspondence between the virtual address and the physical address ,perm Set physical page permissions , In order to ensure the consistency with its corresponding virtual page permissions 
            swap_map_swappable(mm, addr, page, 1);// Make this page exchangeable  , It is also added to the order queue maintained by the algorithm 
	    page->pra_vaddr = addr;		// Set the virtual address corresponding to the page 
        }
        else {
    
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
/*################# Modification part #######################*/
   ret = 0;
failed:
    return ret;
}

The final result of the run is ：

You can see , adopt check_pgfault Testing of functions , practice 1 adopt .

The answer to the question ：

• Please describe the page directory entry （Pag Director Entry） And page tables （Page Table Entry） The middle part is right ucore The potential use of implementing page replacement algorithms .

Implementation of paging mechanism , Ensure the correspondence between virtual address and physical address , One side , Find out whether the virtual address exists in the first and second level page table , It is easy to find out whether the address is legal , At the same time, the page replacement operation can be realized by modifying the mapping relationship . On the other hand , When implementing page replacement, it involves changing in and out ： When switching in, you need to read a page of the disk corresponding to a virtual address into memory , When swapping out, you need to write the contents of a virtual page to a location on the disk .

in addition , The address segmentation operation is realized based on the page table , ad locum , Different bits of a physical address , Will store a series of different information , such as ,pg_fault This operation is used to determine the permission in the function , Observe the macro definition in the code , We get the meaning of some marker bits as follows ：

/* page table/directory entry flags */
#define PTE_P 0x001 // Present
#define PTE_W 0x002 // Writeable
#define PTE_U 0x004 // User
#define PTE_PWT 0x008 // Write-Through
#define PTE_PCD 0x010 // Cache-Disable
#define PTE_A 0x020 // Accessed
#define PTE_D 0x040 // Dirty
#define PTE_PS 0x080 // Page Size
#define PTE_MBZ 0x180 // Bits must be zero
#define PTE_AVAIL 0xE00 // Available for software use
                                                // The PTE_AVAIL bits aren't used by the kernel or interpreted by the
                                                // hardware, so user processes are allowed to set them arbitrarily.

#define PTE_USER (PTE_U | PTE_W | PTE_P)

Whether it is a page directory item or a page table item , All items in the table are reserved 3 Bits for the operating system , It can support the implementation of some page replacement algorithms .

• If ucore The missing page service routine of accesses memory during execution , Page access exception occurred , What does the hardware do ？

CPU Will store the linear address of the exception in CR2 In the register , And the page access exception type error Code Save in interrupt stack . Then through the above analysis trap–> trap_dispatch–>pgfault_handler–>do_pgfault Call relationship , Deal with it step by step .

practice 2： Supplementary completion is based on FIFO Page replacement algorithm （ You need to program ）

complete vmm.c Medium do_pgfault function , And in the implementation FIFO Algorithm swap_fifo.c Finish in map_swappable and swap_out_victim function . Through to swap Test of . Be careful ： stay LAB3 EXERCISE 2 Fill in the code at . perform

make　qemu

after , If you pass check_swap After the test of the function , There will be “check_swap() succeeded!” Output , Means to practice 2 Basically right .

Please briefly describe your design and implementation process in the experimental report .

Please answer the following questions in the experiment report ：

• If you want to in ucore Implemented on "extended clock Page replacement algorithm " Please give me your design , The existing swap_manager Whether the framework is sufficient to support in ucore To implement this algorithm ？ If it is , Please give me your design . If not , Please provide your new extension and the design scheme based on this extension . And you need to answer the following questions
  • What are the characteristics of the page that needs to be swapped out ？
  • stay ucore How to judge a page with such characteristics in ？
  • When to perform a swap in and swap out operation ？

Explain ： The experimental instruction is based on ：

Because the operating system provides a virtual for user mode applications “ The large capacity ” Memory space , The actual physical memory space is not that large . So the operating system is “ Keep it a secret ” Applications , Only in the application “ Commonly used ” The data and code are stored in physical memory , The data and code that are not commonly used are put on the storage medium such as the hard disk . But when the application accesses these uncommon data and code , Because the page is saved in swap Area or disk , Will cause page error exception , So we should solve this problem through page replacement algorithm .

And Practice 1 The connection here lies in ： Page replacement is mainly divided into two aspects , Page out and page in . practice 1 The realization is page switching , Mainly in the above do_pgfault() Function implementation ; And Practice 2 The main implementation here , Page out , Mainly in the swap_out_vistim() function . in addition , In practice 1 There is also a function called swappable, Represents setting the page as exchangeable . therefore , practice 2 Mainly for the implementation of these two functions .

Page switch in part ：

do_pgfault() Part of the code in the function ：

else {
      // Page table entry is not empty , Try switching to a page  
        if(swap_init_ok) {
    
            struct Page *page=NULL; // according to mm The structure and addr Address , Try to switch the contents of the hard disk into page in 
            if ((ret = swap_in(mm, addr, &page)) != 0) {
    
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }    
            page_insert(mm->pgdir, page, addr, perm); // Establish the correspondence between the virtual address and the physical address  
            swap_map_swappable(mm, addr, page, 1); // Make this page exchangeable  
            page->pra_vaddr = addr;
        }
        else {
    
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
   ret = 0;
failed:
    return ret;
}

When switching in , You need to check whether the address generating the access exception belongs to a vma Represents the legal virtual address , And saved on the hard disk swap In file （ Corresponding PTE The height of 24 Not for 0）. If you meet the above highlights , execute swap_in() Function switch to page .

Page swap out part ：

The timing of changing pages is relatively complicated , There are different opportunities for different strategies .ucore At present, there are roughly two strategies , That is, positive swap out strategy and negative swap out strategy . An active swap out strategy means that the operating system periodically （ Or when the system is not busy ） Take the initiative to think that “ Not commonly used ” Page out to the hard disk , To ensure that there are always a certain number of free pages in the system , So when you need a free page , Basically, it can meet the demand in time ; A negative swap out strategy is , Just when trying to get free pages , It is found that there are currently no free physical pages available for allocation , Only then did I begin to search “ Not commonly used ” page , And swap one or more of these pages out to the hard disk .

meanwhile , The second strategy mentioned above is used in the basic experiment of this experiment .

The whole page replacement strategy adopts FIFO Strategy ：

fifo (First In First Out, FIFO) Page replacement algorithm ： The algorithm always knocks out the first page that enters memory , That is, select the page that has stayed in memory for the longest time to be eliminated . Just link the pages that have been called into memory during the execution of an application into a queue in order , The queue header points to the oldest page in memory , The end of the queue points to the page that was recently called into memory . When you need to weed out pages , It is easy to find the pages that need to be eliminated from the queue header .FIFO The algorithm only works well when the application accesses the address space in a linear order , Otherwise, the efficiency is not high . Because those pages that are often visited , It often stays in memory for the longest time , As a result, they changed “ The old ” And have to be replaced .FIFO Another drawback of the algorithm is , It has an anomaly （Belady The phenomenon ）, That is, when the page frame for placing the page is increased , Instead, it increases the number of page access exceptions .

Class framework swap_manager

In order to realize various page replacement algorithms , We design a class framework of page replacement algorithm swap_manager:

struct swap_manager  
{
      
    const char *name;  
    /* Global initialization for the swap manager */  
    int (*init) (void);  
    /* Initialize the priv data inside mm_struct */  
    int (*init_mm) (struct mm_struct *mm);  
    /* Called when tick interrupt occured */  
    int (*tick_event) (struct mm_struct *mm);  
    /* Called when map a swappable page into the mm_struct */  
    int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);   
    /* When a page is marked as shared, this routine is called to delete the addr entry from the swap manager */
    int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);  
    /* Try to swap out a page, return then victim */  
    int (*swap_out_victim) (struct mm_struct *mm, struct Page *ptr_page, int in_tick);  
    /* check the page relpacement algorithm */  
    int (*check\_swap)(void);   
};

The two key function pointers here are map_swappable and swap_out_vistim, The previous function is used to record the properties related to page access , The latter function is used to select the page to be swapped out . Obviously, the second function depends on the page access recorded by the first function .tick_event Function pointers are also important , Interrupt generated in combination with timing , Can achieve a positive page change strategy .

Realization ：

First of all FiFO The initialization ：

list_entry_t pra_list_head;
/* * (2) _fifo_init_mm: init pra_list_head and let mm->sm_priv point to the addr of pra_list_head. * Now, From the memory control struct mm_struct, we can access FIFO PRA */
static int
_fifo_init_mm(struct mm_struct *mm)
{
         
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     //cprintf(" mm->sm_priv %x in fifo_init_mm\n",mm->sm_priv);
     return 0;
}
// Empty , The header points to the head of the queue 

call _fifo_map_swappable() function ：

Add the most recently used pages to the order queue maintained by the algorithm . Here, create a pointer to the most recently used page , Then create a new null pointer in the list , Add the most recently used pages to the end of the sequence .

/* * (3)_fifo_map_swappable: According FIFO PRA, we should link the most recent arrival page at the back of pra_list_head qeueue */
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
    list_entry_t *entry=&(page->pra_page_link);
 
    assert(entry != NULL && head != NULL);
    //record the page access situlation
    /*LAB3 EXERCISE 2: YOUR CODE*/ 
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head, entry);// Add a new... After the header page
    return 0;
}

_fifo_swap_out_victim() function ：

_fifo_swap_out_victim() The function is used to query which page needs to be swapped out , Its main function is to query which page needs to be replaced . Use linked list operation , Delete the page you first entered , And according to the comments, give this page to the incoming parameters ptr_page.

static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
    
     list_entry_t *head=(list_entry_t*) mm->sm_priv;
     assert(head != NULL);
     assert(in_tick==0);
     list_entry_t *le = head->prev;// use le Indicates the page that needs to be swapped out 
     assert(head!=le);
     struct Page *p = le2page(le, pra_page_link//le2page The macro can obtain the corresponding... According to the linked list elements Page The pointer p 
     list_del(le); // Remove the oldest page from the queue 
     assert(p !=NULL);
     *ptr_page = p; // Remove the oldest page from the queue 
     return 0;
}

experimental result ：

Question answering ：

If you want to in ucore Implemented on "extended clock Page replacement algorithm " Please give me your design , The existing swap_manager Whether the framework is sufficient to support in ucore To implement this algorithm ？ If it is , Please give me your design . If not , Please provide your new extension and the design scheme based on this extension . And you need to answer the following questions

• What are the characteristics of the page that needs to be swapped out ？
• stay ucore How to judge a page with such characteristics in ？
• When to perform a swap in and swap out operation ？

Explain ：

First , We need to understand extended clock Specific representation of page replacement algorithm ：

In the clock replacement algorithm , When weeding out a page, we only consider whether the page has been visited , But in reality , You should also consider whether the obsolete pages have been modified . Because the modified pages need to be written back to the hard disk , Make its replacement cost greater than that of unmodified pages , So give priority to the pages that have not been modified , Reduce the number of disk operations . The improved clock replacement algorithm not only considers the access of the page , You also need to consider the modification of the page . That is, the algorithm not only hopes to eliminate the pages that have not been used recently , And we also hope that the pages that are eliminated have not been modified during the stay of main memory .

This requires adding a reference bit and a modification bit to the corresponding page table item content of each page .

When the page is accessed ,CPU Medium MMU The hardware will access the location “1”. When the page is “ Write ” when ,CPU Medium MMU The hardware will change the position “1”. In this way, there are four possible combinations of these two ：

• （0,0） Indicates that it has not been referenced or modified recently , First select this page to eliminate ;
• （0,1） Not used recently , But it was modified , Second, choose ;
• （1,0） Recently used but not modified , Choose... Again ;
• （1,1） Recently used and modified , The final choice .

This algorithm is compared with the clock algorithm , It can further reduce the I/O Operating frequency , But in order to find a page that is suitable for elimination as much as possible , It may need to be scanned many times , It increases the execution cost of the algorithm itself .

Next , Question answering ：

1、 What are the characteristics of the page that needs to be swapped out ？

1. The physical page has not been accessed before the last sweep of the current pointer ;
2. The content of the physical page is consistent with the data saved in the external memory ,.（ That is, it has not been modified ）

2、 stay ucore How to judge a page with such characteristics in ？

The first one scanned by the pointer dirty bit by 0 Pages that have not been visited .

3、 When to perform a swap in and swap out operation ？

When the page to be called is not in the page table , And when the page table is full , May trigger PageFault, At this time, you need to perform the operation of changing in and out . Specifically, when the memory saved in the disk needs to be accessed , You need to perform a swap operation ; When the memory in the physical page box is selected by the page replacement algorithm , Exchange operation is required .

Extended exercises Challenge 1： Achieve recognition dirty bit Of extended clock Page replacement algorithm （ You need to program ）

Prepare knowledge ：

The clock page replacement algorithm organizes each page into a circular linked list , Like the surface of a clock . Then put a pointer （ Short for current pointer ） Point to the oldest page , That is, the most advanced page . in addition , The clock algorithm needs to be in the page table entry （PTE） An access bit is set in to indicate whether the page corresponding to this page table item has been accessed . When the page is accessed ,CPU Medium MMU The hardware will access the location “1”. When the operating system needs to eliminate pages , Query the page table item corresponding to the page pointed to by the current pointer , If the access bit is “0”, Then eliminate this page , If the page has been written , Then you have to change it out to the hard disk ; If the access bit is “1”, Then this position of the table item on the page “0”, Continue to the next page .

To implement this algorithm is to traverse along the linked list , Swap pages that have not been accessed and modified recently out of memory .

Insert ：

If the circular linked list is empty , Then this page is the whole linked list , Point the pointer to this page . otherwise , Just insert the page before the page pointed to by the pointer .

Swap out ：

This function finds a physical page that can be used for swapping out , You only need to traverse four times at most ：

• First , Find mark as <0,0> The page of ;
• If not found in the previous step , Find Tags <0,1>, And clear the access bit of the visited page ;
• If not found in the previous step , Find again marked <0,0> The page of ;
• If not found in the previous step , Find again marked <0,1> The page of ;

take PTE Medium PTE_A After removal , Need to call tlb_invalidate Refresh TLB, Otherwise, when the page is accessed again ,PTE Medium PTE_A Will not be set .

The implementation is as follows ：

kern/mm/mmu.h The document has the following definitions ：

#define PTE_A 0x020 // Accessed
#define PTE_D 0x040 // Dirty

PTE_A Is the flag bit indicating access ,PTE_D Is the flag bit indicating modification

list_entry_t pra_list_head;

static int
_clock_init_mm(struct mm_struct *mm)
{
         
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     return 0;
}
// Here and FIFO The initialization method of is the same 

static int
_clock_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    
    // The position of the incoming page in the linked list does not affect , So insert it at the end of the linked list .
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
    list_entry_t *entry=&(page->pra_page_link);

    assert(entry != NULL && head != NULL);//  Insert the new page at the end of the linked list 
    list_add(head -> prev, entry);//  Newly inserted page dirty bit Marked as 0.
    struct Page *ptr = le2page(entry, pra_page_link);
    pte_t *pte = get_pte(mm -> pgdir, ptr -> pra_vaddr, 0);
    *pte &= ~PTE_D;
    return 0;
}

static int
_clock_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
    
     list_entry_t *head=(list_entry_t*) mm->sm_priv;
     assert(head != NULL);
     assert(in_tick==0);

     list_entry_t *p = head;
     while (1) {
    
         p = list_next(p);
         if (p == head) {
    
             p = list_next(p);
         }
         struct Page *ptr = le2page(p, pra_page_link);
         pte_t *pte = get_pte(mm -> pgdir, ptr -> pra_vaddr, 0);
         // Get page table entry 
         if ((*pte & PTE_D) == 1) {
    //  If dirty bit by 1, Change it to 0
             *pte &= ~PTE_D;
         } 
         else 
         {
    //  If dirty bit by 0, Then it is marked as a page out 
             *ptr_page = ptr;
             list_del(p);
             break;
         }
     }
     return 0;
}

Modelled on the swap_fifo.c Medium _fifo_check_swap, To write _clock_check_swap:

static int
_clock_check_swap(void) {
    
    cprintf("write Virt Page c in clock_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;
    assert(pgfault_num==4);
    cprintf("write Virt Page a in clock_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==4);
    cprintf("write Virt Page d in clock_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==4);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==4);
    cprintf("write Virt Page e in clock_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e;
    assert(pgfault_num==5);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==5);
    cprintf("write Virt Page a in clock_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==6);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==7);
    cprintf("write Virt Page c in clock_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;
    assert(pgfault_num==8);
    cprintf("write Virt Page d in clock_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==9);
    cprintf("write Virt Page e in clock_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e;
    assert(pgfault_num==10);
    cprintf("write Virt Page a in clock_check_swap\n");
    assert(*(unsigned char *)0x1000 == 0x0a);
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==11);
    return 0;
}

These are also imitated ：

static int
_clock_init(void)
{
    
    return 0;
}

static int
_clock_set_unswappable(struct mm_struct *mm, uintptr_t addr)
{
    
    return 0;
}

static int
_clock_tick_event(struct mm_struct *mm)
{
     return 0; }

Finally, swap_manager_clock To initialize ：

struct swap_manager swap_manager_clock =
{
    
     .name            = "extend_clock swap manager",
     .init            = &_clock_init,
     .init_mm         = &_clock_init_mm,
     .tick_event      = &_clock_tick_event,
     .map_swappable   = &_clock_map_swappable,
     .set_unswappable = &_clock_set_unswappable,
     .swap_out_victim = &_clock_swap_out_victim,
     .check_swap      = &_clock_check_swap,
};

That's all extended clcok Implementation of page replacement algorithm . But here you need to call swap_manager_clock To verify whether the code is written correctly . In order to call extended clock Algorithm , take swap.c in swap_init Functional sm = &swap_manager_fifo;** Change to **sm = &swap_manager_clock;

Here are the experimental results ：

Extended exercises Challenge 2： Implementation does not consider implementation overhead and efficiency LRU Page replacement algorithm （ You need to program ）

challenge Part is not necessary , However, in the end, we will add points as appropriate . Need to write a detailed design 、 Experimental report of analysis and test . You can get appropriate bonus points if you finish excellent .

Refer to the answer analysis

It is almost the same as the reference answer .

The knowledge points involved in the experiment are listed

The knowledge points involved in this experiment are ：

• The basic concept and principle of virtual memory management ;
• page fault Exception handling process ;
• Page replacement algorithm ;
• Management of physical memory ;

The corresponding knowledge points in the operating system are ：

• Implementation of virtual memory mechanism in operating system ;
• The implementation of a specific page replacement algorithm in the operating system ;
• Interrupt handling mechanism in operating system ;

The relationship between them is , The knowledge points of the former provide a theoretical basis for the specific implementation of the operating system in the latter ( For example, the page replacement algorithm is OS The concrete implementation of swap out The mechanism provides the basis );

Experience and experience ：

This experiment is compared with lab1 and lab2 experiment , Generally speaking, the content of the experiment is less , But the knowledge needed is more in-depth . I learned about the page replacement strategy and other knowledge points that I would not touch at ordinary times , I feel very rewarding .