页面置换+生产者消费者（ *** 作系统实习）

页面置换+生产者消费者（ *** 作系统实习） 消费者生产者 + 页面置换算法 南京林业大学（淮安校区）大二 *** 作系统实习

2022/1/1

新年第一天当然要写代码啦

已在github上更新

this is link to github

本文实现了OPT，FIFO，LRU，CLOCK 存储管理 1．设计目的

通过请求页面式存储管理中页面置换算法设计，了解存储技术的特点，掌握 请求页式存储管理的页面置换算法。

2．设计内容 2.1 具体任务

用程序实现生产者——消费者问题，将指令序列转换为用户虚存中的请求调 用页面流。

2.2 具体要求：

页面大小为 1K； l 用户内存容量为 4 页到 40 页； l 用户外存的容量为 40k；

在用户外存中，按每 K 存放 10 条指令，400 条指令在外存中的存放方式为：

Ø 0-9 条指令为第 0 页；

Ø 10-19 条指令为第 1 页；

Ø 。。。。。 Ø

390-399 条指令为第 39 页；

Ø 按以上方式，用户指令可组成 40 页； 通过随机数产生一个指令序列，共 400 个指令（0-399）。 模拟请求页式存储管理中页面置换算法。执行一条指令，首先在外存中查找 所对应的页面和页面号，然后将此页面调入内存中，模拟并计算下列各述算法在 不同内存容量下的命中率(页面有效次数/页面流的个数)。

（注意：至少完成下面 三个算法） (1). 最佳置换算法 (2). 先进先出置换算法(FIFO) (3). 最久未使用置换算法(LRU) (4). 最少使用置换算法（LFU） (5). 改进的 Clock 置换算法 2.3 编程提示： l 随机指令的产生：rand() 或 srand()。 l 用户内存中页面控制结构采用链表

//main.cc
#include "PageManager.h"
#include 
#include 
#include 
#include 
#include 
#include 
using std::vector;

static const int NUM = 400;
sem_t blank_num, pro_num; // signal varible
pthread_mutex_t mutex;    // muetx
int cur = -1;             // current point in order vector
int INT = 0;              // INT count
PageManager p;
vector order; // our_storage
int choose = 0;

// four page exchange function pointer
vector func;
bool (PageManager::*f1)(int num) = &PageManager::OPT;
bool (PageManager::*f2)(int num) = &PageManager::FIFO;
bool (PageManager::*f3)(int num) = &PageManager::LRU;
bool (PageManager::*f4)(int num) = &PageManager::CLOCK;

void showMessage() {
    std::cout << "[-1]: change_RAM_SIZE" << std::endl;
    std::cout << "[0]: OPT" << std::endl;
    std::cout << "[1]: FIFO" << std::endl;
    std::cout << "[2]: LRU" << std::endl;
    std::cout << "[3]: CLOCK" << std::endl;
    std::cout << "put in not-num to exit" << std::endl;
}

// producter
void *producer(void *arg) {
    while (cur < 400) {
        sem_wait(&blank_num);
        pthread_mutex_lock(&mutex);
        if (cur < 400)
            cur++;
        pthread_mutex_unlock(&mutex);
        sem_post(&pro_num);
        usleep(1000);
    }
    return 0;
}

// consumer
void *consumer(void *num) {
    int *n = static_cast(num);
    while (cur < 400) {
        sem_wait(&pro_num);
        pthread_mutex_lock(&mutex);
        if (cur < 400 && (p.*func[*n])(cur))
            // if(cur<400 && (p.*f2)(cur))
            INT++;
        std::cout << order[cur].pagenum << " ";
        if ((cur + 1) % 40 == 0) {
            std::cout << std::endl;
        }
        pthread_mutex_unlock(&mutex);
        sem_post(&blank_num);
    }
    return 0;
}

// main manager
class Master {
  private:
    pthread_t pid, cid;
    int choose;

  public:
    Master(int choose) {
        this->choose = choose;
        func.push_back(f1);
        func.push_back(f2);
        func.push_back(f3);
        func.push_back(f4);
    }
    ~Master() {
        cur = -1;
        INT = 0;
        p.clear();
        sem_destroy(&blank_num);
        sem_destroy(&pro_num);
        pthread_mutex_destroy(&mutex);
    }
    void init() {
        std::cout << "In order storage there are 400 orders need to get page, "
                     "they are :"
                  << std::endl
                  << std::endl;
        sem_init(&blank_num, 0, NUM);
        sem_init(&pro_num, 0, 0);
        pthread_mutex_init(&mutex, NULL);
        pthread_create(&pid, NULL, producer, NULL);
        pthread_create(&cid, NULL, consumer, &choose);

        pthread_join(pid, NULL);
        pthread_join(cid, NULL);
    }
    void getResult() {
        std::cout << std::endl << std::endl;
        switch (choose) {
        case 0:
            std::cout << "OPT" << std::endl;
            break;
        case 1:
            std::cout << "FIFO" << std::endl;
            break;
        case 2:
            std::cout << "LRU" << std::endl;
            break;
        case 3:
            std::cout << "CLOCK" << std::endl;
            break;
        }
        std::cout << "----------------INT = " << INT
                  << " INT rate = " << INT * 1.0 / order.size() << "----------------------" << std::endl
                  << std::endl;
    }
};

int main() {
    srand((unsigned)time(NULL));

    for (int i = 0; i < NUM; i++) {
        Page p(rand() % NUM / 10);
        order.push_back(p);
    }
    p = PageManager(order);
    std::cout << std::endl
              << std::endl
              << "RAM size = " << p.get_RAM_Size() << std::endl
              << "you have -1 - 3 to choose" << std::endl
              << std::endl;
    showMessage();

    Master *m;
    while (std::cin >> choose) {
        if (choose < -1 || choose > 3) {
            std::cerr << "error choose" << std::endl;
            exit(0);
        } else if (choose == -1) {
            int newSize;
            std::cout << "new Size" << std::endl;
            std::cin >> newSize;
            p.set_RAM_SIZE(newSize);
            std::cout << "RAM size = " << p.get_RAM_Size() << std::endl;
            std::cout << "put in next choose -1 - 3" << std::endl;
            continue;
        }
        m = new Master(choose);
        m->init();
        m->getResult();
        delete m;

        showMessage();
    }
}

//page.h
#ifndef PAGE_CPP
#define PAGE_CPP
#include 
struct Page {
    int pagenum;
    int count;
    int next;
    bool visited;
    Page() : count(0) ,visited(true){}
    Page(int num) : Page() { pagenum = num; }
    //show what in RAM
    bool operator==(Page p){
        return pagenum==p.pagenum;
    }
    friend std::ostream &operator<<(std::ostream &os, Page obj) {
        os << "{"< 
//RAM.h
#ifndef RAM_H
#define RAM_H
#include "Page.h"
#include 
#include 
#include 
#include 

using std::list;
using std::vector;

class RAM {
  private:
    int SIZE;
    list pages;

  public:
    RAM() { SIZE = 20; }
    RAM(int size);
    ~RAM();
    int getCurSize();
    void setSIZE(int size) { SIZE = size; }
    int getSIZE() { return SIZE; }
    vector getPage() const;
    list &asList();
    void setPage(int index, Page p);
    void clear();

    friend std::ostream &operator<<(std::ostream &os, const RAM &ram) {
        std::cout << "RAM : " << std::endl;
        for (Page i : ram.getPage()) {
            os << i << " ";
        }
        os << std::endl;
        return os;
    }
    RAM operator=(RAM obj) { pages = obj.pages;
        SIZE = obj.SIZE;
        return *this;
    }
};

RAM::RAM(int size) : SIZE(size) {}

RAM::~RAM() {}

int RAM::getCurSize() { return pages.size(); }

vector RAM::getPage() const {
    // std::cout << "!!!SIZE  = = " << pages.size() << std::endl;
    return vector(pages.begin(), pages.end());
}

list &RAM::asList() { return this->pages; }

void RAM::setPage(int index, Page page) {
    if(getCurSize() 
//PageManager.h
#ifndef PAGEMANAGER_h
#define PAGEMANAGER_h
#include "Page.h"
#include "RAM.h"
#include 
#include 
#include 
#include 

using std::pair;
using std::vector;

class PageManager {
  private:
    RAM ram;           //RAM
    vector order; // order_storage
    void next();

  public:
    PageManager();
    PageManager(vector order);
    PageManager(const PageManager &obj);
    ~PageManager();
    int get_RAM_Size() { return ram.getSIZE(); }
    void set_RAM_SIZE(int num) { ram.setSIZE(num); }
    bool OPT(int i);
    bool FIFO(int i);
    bool LRU(int i);
    bool CLOCK(int i);
    void clear();
};
PageManager::PageManager() { next(); }

PageManager::PageManager(vector order){
    this->order = order;
    next();
}

PageManager::PageManager(const PageManager &obj){
    ram = obj.ram;
    order = obj.order;
    next();
}

void PageManager::clear() { ram.clear(); }

PageManager::~PageManager() {}

void PageManager::next() {
    vector> pre; //保存已访问过的
    int order_size = order.size();
    for (int i = order_size - 1; i >= 0; i--) {
        Page &p = order.at(i);
        // std::cout << p << std::endl;
        vector>::iterator pos =
            std::find_if(pre.begin(), pre.end(),
                         [p](auto page) { return p.pagenum == page.first; });

        if (pos == pre.end()) {
            // not found
            pre.push_back(std::make_pair<>(p.pagenum, i));
            // std::cout << "first push back" << p.pagenum << ":" << std::endl;
            p.next = order_size;
        } else {
            p.next = (*pos).second;
            // std::cout << "change" << p.pagenum << ":" << i << std::endl;
            (*pos).second = i;
        }
    }
    // std::copy(std::begin(order), std::end(order),
    //           std::ostream_iterator(std::cout, " "));
    // std::cout << std::endl;
}

bool PageManager::OPT(int i) {
    // init next
    bool flag = false;
    int order_size = order.size();
    // std::cout << ram.getCurSize() << std::endl;
    auto arr = ram.getPage();
    auto page = order.at(i);
    auto p = std::find_if(arr.begin(), arr.end(), [page](const Page &a) {
        return a.pagenum == page.pagenum;
    });
    if (p != arr.end()) {
        // find in RAM
        int choose = p - arr.begin();
        ram.setPage(choose, order.at(i));
    } else {
        flag = true;
        if (ram.getCurSize() < ram.getSIZE()) {
            ram.asList().push_back(order.at(i));
        } else {
            auto arr = ram.getPage();
            auto choose =
                std::max_element(arr.begin(), arr.end(), [](auto a, auto b) {
                    return a.next < b.next;
                });
            int choose_num = choose - arr.begin();
            ram.setPage(choose_num, order.at(i));
        }
    }
    // std::cout << ram << std::endl;
    return flag;
}

bool PageManager::FIFO(int i) {
    // std::copy(std::begin(order), std::end(order),
    //           std::ostream_iterator(std::cout, " "));
    bool ret = false;
    // for (int i = 0; i < order.size(); i++) {
    vector pages = ram.getPage();
    auto p = std::find(pages.begin(), pages.end(), order.at(i));
    if (p != pages.end()) {
        // found
        ;
    } else {
        if (ram.getCurSize() < ram.getSIZE()) {
            ram.asList().push_back(order.at(i));
        } else {

            auto max = std::max_element(
                pages.begin(), pages.end(),
                [](auto a, auto b) { return a.count < b.count; });
            int choose = max - pages.begin();
            ram.setPage(choose, order.at(i));
        }
        ret = true;
    }
    auto &list = ram.asList();
    std::for_each(list.begin(), list.end(), [](auto &p) { p.count++; });
    // std::cout << ram << std::endl;
    // }
    // std::cout << "FIFO page exchange: INT = " << INT << "  INT rate = "
    //           << INT * 1.0 / (order.size()) << std::endl;
    return ret;
}

bool PageManager::LRU(int i) {
    // std::copy(std::begin(order), std::end(order),
    //           std::ostream_iterator(std::cout, " "));
    bool flag = false;
    auto arr = ram.getPage();
    Page &page = order.at(i);
    auto p = std::find_if(arr.begin(), arr.end(), [page](Page &obj) {
        return page.pagenum == obj.pagenum;
    });
    if (p == arr.end()) {
        // not found
        flag = true;
        if (ram.getCurSize() (std::cout, " "));
    bool flag = false;
    auto arr = ram.getPage();
    Page &page = order.at(i);
    auto p = std::find_if(arr.begin(), arr.end(), [page](Page &obj) {
        return page.pagenum == obj.pagenum;
    });
    if (p == arr.end()) {
        // not found
        flag = true;
        if (ram.getCurSize() < ram.getSIZE()) {
            ram.asList().push_back(order.at(i));
            // std::cout << "add " << order.at(i) << std::endl;
        } else {
            auto &list = ram.asList();
            auto q =
                std::find_if(list.begin(), list.end(), [](const Page page) {
                    return page.visited == false;
                });
            // TODO: why this is not working

            // std::for_each(list.begin(), list.end(), [&](Page &page) {
            //     if (page.visited == true)
            //         page.visited ==false;
            // });
            for (auto &i : list) {
                if (i.visited == true) {
                    i.visited = false;
                }
            }
            if (q != list.end()) {
                // found
                // std::cout << *q << "ChangeTo";
                *q = order.at(i);
                // std::cout << order.at(i) << std::endl;
            } else {
                // std::cout << *list.begin() << "ChangeTo" << order.at(i)
                //           << std::endl;
                ram.setPage(0, order.at(i));
            }
        }

    } else {
        // found
        // std::cout << "found" << *p << std::endl;
        int choose = p - arr.begin();
        auto z = ram.asList().begin();
        for (int i = 0; i < choose; i++) {
            z++;
        }
        z->visited = false;
        auto &list = ram.asList();
        for (auto &i : list) {
            if (i.visited == true) {
                i.visited = false;
            }
        }
        // std::cout << ram << std::endl;
    }
    return flag;
}
#endif


					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5695671.html