maneger.cpp
#include "Prototypes.h"

struct controlblock
{
int start;
int size;
int handle;
int busy;
};

struct controlblock bla [30];
char mas[10000];
int handle=1;

void initmemory(void)
{
bla [0].start=0;
bla [0].size=10000;
bla [0].handle=1;
bla [0].busy=0;
}

int allocmemory(int size)
{
for(int i=0;i<30;i++){
if(bla[i].busy==0 && bla[i].size>=size){
if(bla[i].size==size){
bla[i].busy=1;
bla[i].handle=handle++; //присвоение индивидуального номера блоку указанного размера
return bla[i].handle;
}
else{
for(int j=0;j<30;j++){
if(bla[j].size==0){
bla[j].start=bla[i].start;
bla[j].size=size;
bla[j].busy=1;
bla[j].handle=handle++;
bla[i].start=bla[j].start+size;
bla[i].size=bla[i].size-bla[j].size;
return bla[i].handle;
}
}
}
}
}
return -1;
}

void dumpmemory(void){//функция вывода на экран
printf("\n");
for(int i=0;i<30;i++){
if(bla[i].size != 0) {
printf( "Handle=%d Start=%d Size=%d Busy=%d \n" ,bla[i].handle,bla[i].start,bla[i].size, bla[i].busy );
}
}
}

void freememory(int handle)
{
int Sm,i;
Sm=bla[i].size+bla[i].start;
for(int i=0;i<30;i++){
if (bla[i].handle==handle){
bla[i].busy=0;
for(int k=0;k<30;k++){
if(bla[k].busy==0 && bla[k].start==bla[i].start + bla[i].size){
bla[i].size=bla[i].size + bla[k].size;
bla[k].size=0;
return;
}
}
int szi=bla[i].size;
for(int k=0;k<30;k++){
if(bla[k].start>bla[i].start)
bla[k].start=bla[k].start-szi;
if(bla[k].busy==0){
bla[k].size=bla[i].size+bla[k].size;
bla[i].size=0;
}
}
int a[i];
for(int i=Sm;i<10000;i++){
a[i]=a[i]-bla[i].size;
return;
}
}
}
}

Test.cpp
#include "Prototypes.h"
#include <conio.h>
#include <stdio.h>
void main()
{
initmemory();
allocmemory(100);
allocmemory(300);
allocmemory(200);
allocmemory(10000);
dumpmemory();
freememory(2);
dumpmemory();
getch();
}

Продумайте систему страничного хранения информации. Исходные данные:
1. Программа на Cи (Си++), под Windows, Консольное приложение.
2. Вся доступная память представлена массивом 10 КБайт. Все операции с выделением, доступом и освобождением памяти проводятся только с памятью внутри этого массива. Размер виртуальной памяти в 2 раза больше, т.е. 20 Кбайт. Размер страницы – 1Кбайт.
Инициализация менеджера памяти (если необходима) должна вся находиться в функции:
void InitMemory(void);
3. Необходима функция для выделения памяти с прототипом:
int AllocMemory(int Size);
Size – запрашиваемый размер в байтах.
Функция возвращает описатель выделенного блока или 0, если нет доступной памяти.
Память при выделении заполняется нулями.
4. Необходима функция для освобождения памяти с прототипом:
void FreeMemory(int MemoryHandle);
MemoryHandle – описатель ранее выделенной памяти.
5. Необходима функция для записи информации в ранее выделенную память с прототипом:
int WriteMemory(int MemoryHandle, int Offset, int Size, void *Data);
MemoryHandle – описатель ранее выделенной памяти.
Offset – смещение внутри выделенного блока от его начала до места с которого необходимо записать данные.
Size – размер блока данных для записи в байтах.
Data – указатель на буфер, содержащий данные для копирования.
Функция возвращает 0, если запись в память осуществлена корректно или 1, если произошла какая-либо ошибка.
6. Необходима функция для чтения информации из ранее выделенной памяти с прототипом:
int ReadMemory(int MemoryHandle, int Offset, int Size, void *Data);
MemoryHandle – описатель ранее выделенной памяти.
Offset – смещение внутри выделенного блока от его начала до места с которого необходимо прочитать данные.
Size – размер блока данных для чтения в байтах.
Data – указатель на буфер, куда должны быть скопированы данные. Функция возвращает 0, если чтение из памяти осуществлено корректно или 1, если произошла какая-либо ошибка.
7. Система должна поддерживать образ виртуальной памяти на диске. В случае, если при чтении или записи (где необходимо) страница не присутствует в памяти, то она должна быть подгружена. При этом одна из представленных в памяти страниц должна быть выгружена при необходимости.
8. Необходима функция для вывода дампа всех блоков на экран:
void DumpMemory(void);
Функция выводит на экран для каждого блока внутри массива следующую информацию (одна строка на один блок):
- описатель блока;
- номера физических страниц для блока (* после номера означает не присутствующие в памяти страницы и номер страницы на диске);
- размер блока;
- первые 10 байт блока.
Пример:
H:35 P:5,2,1*,4* S:3500 2,3,3,2,1,1,2,3,4,5
Здесь: H–описатель, P-список страниц блока, S-размер блока.
9. Необходима функция для тестирования работоспособности менеджера памяти. Использоваться должны все вышеперечисленные функции для работы с памятью. Также необходимо сымитировать ситуацию, когда не хватает физических страниц памяти.

Программа представляет собой систему страничного хранения информации, работает с физической памятью объемом 10 Кбайт и виртуальной памятью объемом 20 Кбайт, образ виртуальной памяти хранится в файле на жестком диске, размер одной страницы – 1 Кбайт. Программа может выделять память, высвобождать ранее выделенную память, производить запись/считывание информации в выделенной памяти, а также просматривать состояние выделенных блоков памяти (делать дамп памяти).

2. Описание функций

void InitMemory(); инициализация памяти.
void ReleaseMemory(); освождаются ресурсы, выделенные в void InitMemory()
nt AllocMemory(int size); функция для выделения памяти
void FreeMemory(int MemoryHandle); функция для освобождения памяти
int WriteMemory(int MemoryHandle, int Offset, int Size, void *Data); функция для записи информации в ранее выделенную память
int ReadMemory(int MemoryHandle, int Offset, int Size, void *Data); функция для чтения информации из ранее выделенной памяти
void DumpMemory(); функция для вывода дампа всех блоков на экран

3. Принцип работы программы

Программа может выделить любой объем памяти в пределах доступной, однако, т.к. модель памяти является страничной, то минимальный размер реально выделяемой памяти равен размеру одной страницы. Пользователю, тем не менее, будет доступен только тот объем памяти, который он запросил.
Память состоит из "оперативной" и "файла подкачки", 10 и 20 кб соответственно, и поделена на страницы по 1 кб. Работать со страницами можно только в оперативной памяти.
Сброс страниц в виртуальную память осуществляется в соответствии с тем, какие страницы используются наиболее редко. То есть в первую очередь будут выгружены те страницы, доступ к которым производился реже всего.
При выделении памяти выделяем блок заданного размера, делим его на страницы и помечаем порядковым номером и общим handle'ом.
При чтении и и записи проверяем, хватит ли страниц для данного размера данных.
Потом ищем по страничке из этого блока (по порядку), находим страничку, если она в файле подкачки, достаем ее оттуда и пишем. Сначала мы "отступаем" на оффсет и дописываем кусочек данных в оставшееся место. Остаток данных мы делим на куски по 1024 и пишем в следующие страницы, следя, чтобы данные закончились

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

3.1. pagememman.h

#define MEM_SIZE (1024*10)

void InitMemory(void);
int AllocMemory(int size);
void FreeMemory(int mem_handle);
int WriteMemory(int mem_handle, int offset, int size, void *data);
int ReadMemory(int mem_handle, int offset, int size, void *data);
void DumpMemory();

3.2 pagememman.cpp

#include "pagememman.h"
#include <stdio.h>
#include <cassert>
#include <io.h>
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>

namespace
{

int const PAGE_SIZE = 1024;

inline int DivRoundUp(int n, int m)
{
return (n+m-1)/m;
}

struct Page
{
int Handle;
int LogPage;
int Counter;
};

char const *pagefilename = "pagefile.bin";
char RamArr[MEM_SIZE];
struct Page PArr[30];

int SearchNextPageInBlock(int mem_handle, int curr)
{
for(int i=0; i<30; i++)
if(PArr[i].Handle == mem_handle && PArr[i].LogPage == curr + 1)
return i;
return -1;
}

int currHandle;
int currCounter;

void PrintBlock(int handle)
{
printf("H: %d, P: ", handle);

int num = SearchNextPageInBlock(handle, 0);

while(num != -1)
{
if(num < 9)
printf("%d ", num);
else
printf("%d* ", num);

num = SearchNextPageInBlock(handle, PArr[num].LogPage);
}

//âûâîäèì ïåðâûå 10 áàéò
num = SearchNextPageInBlock(handle, 0);

if(num < 10)
{
for(int i = num*PAGE_SIZE; i < num*PAGE_SIZE + 10; i++)
printf("%c ", RamArr[i]);
}
else
{
FILE *fh = fopen(pagefilename, "rb");
assert(fh);

char c;

for(int i=0; i< 10; i++)
{
fseek(fh, (num-10)*PAGE_SIZE + i , SEEK_SET);
fread(&c, sizeof©, 1, fh);
printf("%c, ", c);
}

fclose(fh);

}
printf("\n");
}

int GetOlderPage()
{
int min = currCounter, num = 0;

for(int i=0; i<10; i++)
if(PArr[i].Handle != 0)
if(PArr[i].Counter <= min)
{
min = PArr[i].Counter;
num = i;
}

return num;
}

for(int i=10; i<30; i++)
if(PArr[i].Handle == 0)
return i;

printf("Not enough free pages\n");
return -1;
}

void CheckCounter()
{
if(currCounter < 65535)
return;
for(int i=0; i<10; i++)
if(PArr[i].Handle != 0)
PArr[i].Counter -= 65535;
}

void MoveData(int from, int to)
{
//çàïèñûâàåì äàííûå èç ñòðàíèöû íà äèñê
FILE *fh = fopen(pagefilename, "wb");
assert(fh);
fseek(fh, (to-10)*PAGE_SIZE , SEEK_SET);
fwrite(&RamArr[from*PAGE_SIZE], sizeof(PAGE_SIZE), 1, fh);
fclose(fh);

//çàïèñûâàåì ïàðàìåòðû ñòðàíèöû
PArr[to].Handle = PArr[from].Handle;
PArr[to].LogPage = PArr[from].LogPage;
PArr[to].Counter = PArr[from].Counter;
CheckCounter();
PArr[from].Handle = currCounter;

}

int UnloadPage()
{
int old_f_page = GetOlderPage(), f_page = GetFreeDiskPage();

if(old_f_page == -1 || f_page == -1)
return -1;

MoveData(old_f_page,f_page);
return old_f_page;

}

int Swap(int virt_page, int ram_page)
{
//ïåðåíîñèì äàííûå èç virt_page íà ñâîáîäíîå ìåñòî â ïàìÿòè

//ïåðåíîñèì äàííûå â íóæíîå ìåñòî â ramarr
FILE *fh = fopen(pagefilename, "rb");
assert(fh);
fseek(fh, (virt_page-10)*PAGE_SIZE , SEEK_SET);
fread(&RamArr[ram_page*PAGE_SIZE], sizeof(PAGE_SIZE), 1, fh);
fclose(fh);

PArr[ram_page].Handle = PArr[virt_page].Handle;
PArr[ram_page].LogPage = PArr[virt_page].LogPage;
PArr[ram_page].Counter = currCounter;
PArr[virt_page].Handle = 0;

return ram_page;

}

int CheckPageNum(int num)
{
if(num > 9)
{
//ñíà÷àëà ïðîâåðèòü, åñòü ëè ñâîáîäíàÿ â ram è âåðíóòü åå
for(int i=0; i<10; i++)
if(PArr[i].Handle == 0)
return Swap(num, i);
return Swap(num, UnloadPage());
}

return num;
}

int GetFreePageCount()
{
int n = 0;
for(int i=0; i<30; i++)
if(PArr[i].Handle == 0)
n++;
return n;
}

}

void FreeMemory(int mem_handle)
{
for(int i=0; i<30; i++)
if(PArr[i].Handle == mem_handle)
PArr[i].Handle = 0;
}

void InitMemory()
{
int i;
for(i=0; i<30; i++)
PArr[i].Handle = 0;
FILE *fh = fopen(pagefilename, "wb");
assert(fh);
char c = '\0';
for(i=0; i<MEM_SIZE*2; i++)
fwrite(&c, sizeof©, 1, fh);
fclose(fh);
}

void DumpMemory()
{
if(currHandle == 0)
return;

for(int i=1; i<=currHandle; i++)
PrintBlock(i);
}

int AllocMemory(int size)
{
//îïðåäåëÿåì êîëè÷åñòâî ñòðàíèö äëÿ äàííîãî ðàçìåðà
int n = DivRoundUp(size, PAGE_SIZE);

//ïðîâåðèòü, ÷òîáû âñåãäà áûëà ñâîáîäíà îäíà ñòðàíèöà íà äèñêå
if(n >= GetFreePageCount())
{
printf("Not enough free pages\n");
return -1;
}
currHandle++;

//çàíèìàåì è ïðîíóìåðîâûâàåì ñòðàíèöû
//íà÷èíàåì ñ äèñêà
int num = 0;
for(int i=29; i>=0; i--)
{
if(PArr[i].Handle == 0)
{
PArr[i].Handle = currHandle;
PArr[i].LogPage = ++num;
if(num == n)
break;
}
}
return currHandle;
}

int WriteMemory(int mem_handle, int offset, int size, void *data)
{
char *p_data = (char*)data;

//õâàòèò ëè ñòðàíèö äëÿ äàííîãî size
int n = 0, i=0;
for(i=0; i<30; i++)
if(PArr[i].Handle == mem_handle)
n++;

if (n < DivRoundUp(offset + size,PAGE_SIZE))
{
printf("No enough pages\n");
return -1;
}

//ïåðâàÿ ñòðàíèöà áëîêà
int currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, 0) ),

//ðàçìåð íåçàïèñàííîãî "îñòàòêà"
remSize = size;

//îòñòóïèòü íà offset è çàïèñàòü êóñî÷åê â îñòàâøååñÿ ìåñòî

if(offset <= PAGE_SIZE)
{
memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], p_data, PAGE_SIZE - offset);
remSize -= PAGE_SIZE - offset;
}
else
{
for(i=0; i < offset/PAGE_SIZE; i++)
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );

PArr[currPageNum].Counter = ++currCounter;

if(remSize <=0)
return true;

//äîçàïèñûâàåì äàëüøå ïî îäíîé ñòðàíèöå
while ( (remSize >= PAGE_SIZE) && (currPageNum != -1) )
{
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );
memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], &p_data[size - remSize], PAGE_SIZE);
remSize -= PAGE_SIZE;
PArr[currPageNum].Counter = ++currCounter;
}

if(remSize <=0)
return true;

//îñòàòîê
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );
memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], &p_data[size - remSize], remSize);
PArr[currPageNum].Counter = ++currCounter;

return true;
}

int ReadMemory(int mem_handle, int offset, int size, void *data)
{
char *p_data = (char*)data;

//õâàòèò ëè ñòðàíèö äëÿ äàííîãî size
int n = 0, i=0;
for(i=0; i<30; i++)
if(PArr[i].Handle == mem_handle)
n++;

if (n < DivRoundUp(offset + size, PAGE_SIZE))
{
printf("No enough pages\n");
return -1;
}

//ïåðâàÿ ñòðàíèöà áëîêà
int currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, 0) ),

//ðàçìåð íåçàïèñàííîãî "îñòàòêà"
remSize = size;

//îòñòóïèòü íà offset è ïðî÷èòàòü êóñî÷åê èç îñòàâøåãîñÿ ìåñòà

if(offset <= PAGE_SIZE)
{
//memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], p_data, PAGE_SIZE - offset);
if(size >= PAGE_SIZE)
{
memcpy(p_data, &RamArr[currPageNum * PAGE_SIZE + offset], PAGE_SIZE - offset);
}
else
{
memcpy(p_data, &RamArr[currPageNum * PAGE_SIZE + offset], size );
}
remSize -= PAGE_SIZE - offset;
}
else
{
for(i=0; i < offset/PAGE_SIZE; i++)
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );

//memcpy(&RamArr[currPageNum * PAGE_SIZE + offset - offset%PAGE_SIZE], p_data, offset%PAGE_SIZE);

memcpy(&p_data, &RamArr[currPageNum * PAGE_SIZE + offset - offset%PAGE_SIZE], offset%PAGE_SIZE);
remSize -= offset%PAGE_SIZE;
}

PArr[currPageNum].Counter = ++currCounter;

if(remSize <=0)
return true;

//äîñ÷èòûâàåì äàëüøå ïî îäíîé ñòðàíèöå
while ( (remSize >= PAGE_SIZE) && (currPageNum != -1) )
{
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );
//memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], &p_data[size - remSize], PAGE_SIZE);
memcpy(&p_data[size - remSize], &RamArr[currPageNum * PAGE_SIZE + offset], PAGE_SIZE);
remSize -= PAGE_SIZE;
PArr[currPageNum].Counter = ++currCounter;
}

if(remSize <=0)
return true;

//îñòàòîê
currPageNum = CheckPageNum( SearchNextPageInBlock(mem_handle, currPageNum) );
//memcpy(&RamArr[currPageNum * PAGE_SIZE + offset], &p_data[size - remSize], remSize);
memcpy(&p_data[size - remSize], &RamArr[currPageNum * PAGE_SIZE + offset], remSize);
PArr[currPageNum].Counter = ++currCounter;

data = p_data;

return true;
}

3.3 main.cpp

#include <stdio.h>
#include <conio.h>
#include "pagememman.h"

void main()
{
InitMemory();
int h1 = AllocMemory(5000);
int h2 = AllocMemory(18000);

DumpMemory();

char c[] = "asdfg";

WriteMemory(h1, 0, sizeof©, c);
WriteMemory(h2, 0, sizeof©, c);

DumpMemory();

char data[100];
ReadMemory(h1, 0, sizeof©, data);
data[5] = '\0';
printf(data);

_getch();
}