clock_page_replacement/

lib.rs

//! A simple (improved) clock page replacement algorithm.
//!
//! This algorithm utilizes the 'A' (Accessed) and 'D' (Dirty) bits in the PTE (Page Table Entry) to determine which page to replace. We maintain a circular pointer to the page in the memory and evict current page if it is neither accessed nor dirty. Otherwise, we clear the first one of 'A' and 'D' bit and move to the next page.

#![no_std]

extern crate alloc;

use alloc::collections::VecDeque;

/// A page with 'A' and 'D' bits.
pub trait Page {
    /// Check if the page is valid.
    fn is_valid(&self) -> bool;

    /// Check if the page is accessed.
    fn is_accessed(&self) -> bool;

    /// Check if the page is dirty.
    fn is_dirty(&self) -> bool;

    /// Set the 'A' bit.
    fn set_accessed(&mut self);

    /// Set the 'D' bit.
    fn set_dirty(&mut self);

    /// Clear the 'A' bit.
    fn clear_accessed(&mut self);

    /// Clear the 'D' bit.
    fn clear_dirty(&mut self);
}

/// A page replacer based on the clock page replacement algorithm.
///
/// # Usage
///
/// Every time you allocate a physical memory page, you should call
/// [`register`] to register it to the replacer.
///
/// You don't need to unregister a page when it's evicted from the
/// physical memory, because the replacer will automatically remove it
/// when it becomes invalid.
///
/// When you need to replace a page, call the `replace` method to get the
/// page to replace. The page is automatically removed from the replacer.
///
/// [`register`]: ClockPageReplacer::register
#[derive(Default)]
pub struct ClockPageReplacer<T: Page> {
    pages: VecDeque<T>,
}

impl<T: Page> ClockPageReplacer<T> {
    /// Create a new [`ClockPageReplacer`].
    pub fn new() -> Self {
        Self {
            pages: VecDeque::new(),
        }
    }

    /// Register a page to the replacer.
    pub fn register(&mut self, page: T) {
        self.pages.push_back(page);
    }

    /// Find a page to replace.
    ///
    /// # Returns
    ///
    /// The algorithm always finds a page to replace, so it returns `Some(Page)`
    /// unless the page list is empty.
    pub fn replace(&mut self) -> Option<T> {
        loop {
            let mut page = self.pages.pop_front()?;

            // Page is invalid, which means it's may have been unmapped.
            if !page.is_valid() {
                continue;
            }

            if !page.is_accessed() && !page.is_dirty() {
                return Some(page);
            } else if page.is_accessed() {
                page.clear_accessed();
            } else if page.is_dirty() {
                page.clear_dirty();
            } else {
                unreachable!("Logically unreachable");
            }

            // The page is still in use, push it back to the queue.
            self.pages.push_back(page);
        }
    }
}

#[cfg(test)]
mod tests {
    extern crate std;
    use std::{cell::RefCell, collections::BTreeSet, println, rc::Rc, vec::Vec};

    use super::*;

    /// Test page implementation.
    #[derive(Clone, Debug)]
    struct TestPage {
        id: usize,
        valid: bool,
        accessed: bool,
        dirty: bool,
    }

    impl TestPage {
        fn new(id: usize, valid: bool) -> Self {
            Self {
                id,
                valid,
                accessed: false,
                dirty: false,
            }
        }
    }

    impl Drop for TestPage {
        fn drop(&mut self) {
            println!("Page {} dropped", self.id);
        }
    }

    impl Page for Rc<RefCell<TestPage>> {
        fn is_valid(&self) -> bool {
            self.borrow().valid
        }

        fn is_accessed(&self) -> bool {
            self.borrow().accessed
        }

        fn is_dirty(&self) -> bool {
            self.borrow().dirty
        }

        fn set_accessed(&mut self) {
            let mut page = self.borrow_mut();
            page.accessed = true;
            println!(
                "Page {} accessed, current AD bits: {} {}",
                page.id, page.accessed, page.dirty
            );
        }

        fn set_dirty(&mut self) {
            let mut page = self.borrow_mut();
            page.dirty = true;
            println!(
                "Page {} dirty, current AD bits: {} {}",
                page.id, page.accessed, page.dirty
            );
        }

        fn clear_accessed(&mut self) {
            let mut page = self.borrow_mut();
            page.accessed = false;
            println!(
                "Page {} accessed cleared, current AD bits: {} {}",
                page.id, page.accessed, page.dirty
            );
        }

        fn clear_dirty(&mut self) {
            let mut page = self.borrow_mut();
            page.dirty = false;
            println!(
                "Page {} dirty cleared, current AD bits: {} {}",
                page.id, page.accessed, page.dirty
            );
        }
    }

    /// Simulate a memory access.
    struct MemoryAccess {
        page_id: usize,
        write: bool,
    }

    impl From<(usize, bool)> for MemoryAccess {
        fn from((page_id, write): (usize, bool)) -> Self {
            Self { page_id, write }
        }
    }

    /// Test basic replacement.
    #[test]
    fn test_basic() {
        let mut replacer = ClockPageReplacer::new();

        for i in 0..10 {
            let page = TestPage {
                id: i,
                valid: i % 5 != 0,
                accessed: i % 2 == 0,
                dirty: i % 3 == 0,
            };
            println!("Registered page {page:?}");
            replacer.register(Rc::new(RefCell::new(page)));
        }

        for _ in 0..10 {
            if let Some(page) = replacer.replace() {
                let page = page.borrow();
                println!("Replaced page {page:?}");
                assert_eq!(page.accessed, false);
                assert_eq!(page.dirty, false);
            } else {
                println!("No page to replace");
            }
        }
    }

    /// Test using the example from [THU OS Lecture].
    ///
    /// [THU OS Lecture]: https://learningos.cn/os-lectures/lec6/p2-localpagereplace.html#66
    #[test]
    fn test_example() {
        const MEM_SIZE: usize = 4;
        let mem = (0..5)
            .map(|i| Rc::new(RefCell::new(TestPage::new(i, i != 4))))
            .collect::<Vec<_>>();
        let mem_accesses = [
            (2, false),
            (0, true),
            (3, false),
            (1, true),
            (4, false),
            (1, false),
            (0, true),
            (1, false),
            (2, false),
            (3, false),
        ]
        .into_iter()
        .map(Into::into)
        .collect::<Vec<MemoryAccess>>();

        let mut working_set: BTreeSet<_> = (0..4).collect();
        let mut replacer = ClockPageReplacer::new();

        for i in 0..4 {
            replacer.register(mem[i].clone());
        }

        // Simulate memory access
        for access in mem_accesses {
            println!("Accessing page {}, write: {}", access.page_id, access.write);

            if !working_set.contains(&access.page_id) {
                println!(
                    "Page {} is not in the working set, loading it",
                    access.page_id
                );
                if working_set.len() == MEM_SIZE {
                    println!("Working set is full, replacing a page");
                    let replaced_page = replacer.replace().unwrap();
                    replacer.register(mem[access.page_id].clone());

                    println!("Replacing page {:?}", replaced_page);
                    let replaced_id = replaced_page.borrow().id;
                    working_set.remove(&replaced_id);
                    replaced_page.borrow_mut().valid = false;

                    working_set.insert(access.page_id);
                    mem[access.page_id].borrow_mut().valid = true;
                }
            }
            assert!(working_set.contains(&access.page_id));

            let mut page = mem[access.page_id].clone();
            assert!(page.is_valid());

            if access.write {
                page.set_dirty();
            }
            page.set_accessed();
        }
    }
}