Витиснення сторінок. Розробка програми по витисненню сторінок

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ «ХПІ»

Кафедра “Обчислювальна техніка та програмування”

Лабораторна робота №9

з курсу “Системне програмне забезпечення”

 на тему: “Витиснення сторінок “.

Виконав:             

                         студент  групи АП-30б   

                                               Попов О.С.

Перевірив:

       Межерицький С. Г.

Харків 2002

Тема: “Витиснення сторінок.”

Мета: Розробити програму по витисненню сторінок.

Постановка задачі: Витиснення сторінок за алгоритмом MFU.

Текст програми.

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#define kk 9

#define ks 15

#define no 20

#define ko 27

struct mem

{ char page;

   int uses;

}m[kk];

void print(void)

{ int i;

   printf("\n\nЗагр. страницы(обращения) ");

   for (i=0;i<kk; i++)

      if (m[i].uses==0)

        printf("NO(%d%s",m[i].uses,") ");

        else printf("%d%s%d%s",m[i].page,"(",m[i].uses,") ");

   printf("\n");

}

int otkaz(char s)

{ int i=0,otk=1;

   while (i<kk && otk)

      if (m[i].page==s)

        otk=0;

        else i++;

   return otk;

}

int poisk(void)

{ int i,max,n=0;

   max=m[0].uses;

   for (i=0;i<kk;i++)

      if (m[i].uses==0)

        return i;

        else if (m[i].uses>max)

                    {max=m[i].uses;

                       n=i;}

   return n;

}

void zamena(int n,char s)

{ m[n].page=s;

   m[n].uses=0;}

void use(char s)

{  int i;

   for (i=0; m[i].page!=s; i++);

   m[i].uses++;

}

void main (void)

{ int i,del,o100,o=0;

   char str;

   clrscr();

   randomize();

   for (i=0; i<500; i++)

   { str=random(ks);

      if (no<i && i<ko)

        { print();

            printf("  Обращение к %d%s",str," странице... ");

        }

      if (otkaz(str))

        {    if (no<i && i<ko)

              printf("Старничный отказ, загрузка %d%s",str," страницы");

           o++;

           del=poisk();

           zamena(del,str);

        }

      use(str);

      if (i==100)

        o100=o;

   }

   printf("\nПри 100 обращениях к страницам кол-во отказов равно %d",o100);

   printf("\nПри 500 обращениях - %d",o);

}

MFU – сторінка, яка найбільше використовується. Це вибирається сторінка, у якої значення лічильника максимальне. Для кожної сторінки, яка знаходиться у пам’яті створюється лічильник звертань. Цей лічильник автоматично збільшується на 1 при кожному звертанні до сторінки.

Структура програми.

Програма складається з основної, 5 допоміжних функцій та однієї структури.

Опис структури:  

struct mem

{ char page; - сторінка;

   int uses; - скільки раз було проведено звертань до сторінки;

}m[kk]; - масив кадрів;

void print (void) – виводить на екран сторінки, до яких було звертання;

int otkaz (char s) – визначає кількість відмов при звертаннях;

int poisk (void) – шукає сторінку, до якої було найбільше звертань;

void zamena (int n, char s) – вивантажує сторінку з максимальною кількістю звертань, та завантажує нову сторінку;

void use (char s) – функція звертання до сторінки;

Константи:

kk 9 – кількість кадрів;

ks 15 – кількість сторінок;

no 20 – початок лічильника  завантажень ;

ko 27 – кінець лічильника завантажень;

Опис алгоритму програми.

  Спочатку завантажується потрібна кількість сторінок, за допомогою функції void print (void) виводиться список завантажених сторінок. Після цього проводиться звертання до сторінки – і якщо вона є, її лічильник збільшується на 1, але якщо цієї сторінки немає, лічильник відмов збільшується на одиницю. При наступному завантаженні вивантажується сторінка з найбільшим значенням лічильника звертань, а завантажується інша. Далі для порівняння кількості відмов завантажується 100 і 500 сторінок. 

Результати:

Загр. страницы(обращения) 7(2) 1(1) 4(2) 14(2) 9(3) 3(1) 5(2) 6(2) 8(2)

  Обращение к 5 странице...

Загр. страницы(обращения) 7(2) 1(1) 4(2) 14(2) 9(3) 3(1) 5(3) 6(2) 8(2)

  Обращение к 14 странице...

Загр. страницы(обращения) 7(2) 1(1) 4(2) 14(3) 9(3) 3(1) 5(3) 6(2) 8(2)

  Обращение к 9 странице...

Загр. страницы(обращения) 7(2) 1(1) 4(2) 14(3) 9(4) 3(1) 5(3) 6(2) 8(2)

  Обращение к 4 странице...

Загр. страницы(обращения) 7(2) 1(1) 4(3) 14(3) 9(4) 3(1) 5(3) 6(2) 8(2)

  Обращение к 4 странице...

Загр. страницы(обращения) 7(2) 1(1) 4(4) 14(3) 9(4) 3(1) 5(3) 6(2) 8(2)

  Обращение к 7 странице...

При 100 обращениях к страницам кол-во отказов равно 45

При 500 обращениях - 208

Висновки: В ході лабораторної роботи була розроблена програма по витисненню сторінок з пам’яті за алгоритмом MFU.