Динамічні структури даних

МИНИСТЕРСТВО ТРАНСПОРТА РОСИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

ГОСУДАРСТВЕННОЕОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГООБРАЗОВАНИЯ

СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

Кафедра «Информационные технологии транспорта»

КУРСОВОЙ ПРОЕКТ

По дисциплине «Операционные системы»

Тема: «Динамическое выделение в оперативной памяти»

Содержание

Введение

. Динамическое выделение в оперативной памяти

. Имитатор динамического выделения оперативной памяти

. Логическая структура программы

. Тестирование

Заключение

Введение

Программа-имитатор динамического распределения оперативной памяти выполнена на ОС Windows 7 в интегрированной среде разработки приложений с графическим интерфейсом Delphi XE3. В работе применены знания, полученные при изучении курса «Операционные системы, среды и оболочки». Данная программа наглядно показывает процесс динамического распределения процессов в оперативной памяти, фрагментацию оперативной памяти, работу программного объекта «сжатие» и пошаговое представление распределения процессов с заданными параметрами.

1. Динамическое выделение в оперативной памяти

В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутствует, то задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобождается, и на это место может быть загружена другая задача. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рисунке 1 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 задачами, причем задача П4, завершаясь, покидает память. На освободившееся после задачи П4 место загружается задача П6, поступившая в момент t3.

Рис. 1. Распределение памяти динамическими разделами

Задачами операционной системы при реализации данного метода управления памятью является:

·ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти,

·при поступлении новой задачи - анализ запроса, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения поступившей задачи,

·загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей,

·после завершения задачи корректировка таблиц свободных и занятых областей.

Программный код не перемещается во время выполнения, то есть может быть проведена единовременная настройка адресов посредством использования перемещающего загрузчика.

Выбор раздела для вновь поступившей задачи может осуществляться по разным правилам, таким, например, как "первый попавшийся раздел достаточного размера", или "раздел, имеющий наименьший достаточный размер", или "раздел, имеющий наибольший достаточный размер". Все эти правила имеют свои преимущества и недостатки.

По сравнению с методом распределения памяти фиксированными разделами данный метод обладает гораздо большей гибкостью, но ему присущ очень серьезный недостаток - фрагментация памяти. Фрагментация - это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Настолько маленького, что ни одна из вновь поступающих программ не может поместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти.

Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших либо в сторону младших адресов, так, чтобы вся свободная память образовывала единую свободную область (рисунок 2). В дополнение к функциям, которые выполняет ОС при распределении памяти переменными разделами, в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется "сжатием". Сжатие может выполняться либо при каждом завершении задачи, либо только тогда, когда для вновь поступившей задачи нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц, а во втором - реже выполняется процедура сжатия. Так как программы перемещаются по оперативной памяти в ходе своего выполнения, то преобразование адресов из виртуальной формы в физическую должно выполняться динамическим способом.

Рис. 2. Распределение памяти перемещаемыми разделами

Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.

2. Имитатор динамического выделения оперативной памяти

. Назначение программы.

Данная программа позволяет имитировать процесс динамического выделения оперативной памяти и визуально показывает процесс заполнения оперативной памяти, сжатия и освобождения.

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

Используется динамический массив. При нажатии кнопки старт создается запись. В записи присутствуют переменные Imya - имя процесса, PID -номер процесса, Razmer - размер процесса, prohoj - переменная, показывающая количество перемещений процесса при дефрагментации, cr, sin, zel - случайные переменные для задания цвета процесса. Затем в визуальном представлении рисуется прямоугольник с цветом процесса, и подписью, размерность которого рассчитывается относительно всего свободного пространства, размерность которого взята за 100%. Далее идет процесс дефрагментации. Если новый процесс, добавляемый после предыдущего, не помещается в остаток оперативной памяти, то происходит дефрагментация, при которой все процессы заново ставятся в начало один за другим. Далее идет запись нового процесса в таблицу процессов. Далее идет цикл, который содержит перезапись таблицы процессов, удаление процессов и таймер процессов.

Процесс перезаписи таблицы существует для того чтобы при завершении процесса и удалении его из таблицы, его место занималось еще не выполненным процессом. Осуществляется это путем проверки таблицы на наличие пустых ячеек и, при их наличии, записи в них процессов, располагающихся ниже. После, идет удаление процессов. При переменной stat принадлежащей «процессу», равной end процесс считается завершенным и удаляется из таблицы процессов, путем заполнения ячеек «». Если же переменная stat не равна end и процесс выполняется ИЛИ возможность выполнения процесса меньше, чем случайное число, генерируемое перед циклом, то переменная vremya убавляется на 1(с) и соответствующая строка в таблице переписывается. Дальше идет удаление процесса из визуальной области. Удаление происходит при тех же условиях, что и удаление из таблицы. Прямоугольник удаленного процесса закрашивается таким же прямоугольником белого цвета. Далее идет расчет параметров для statusbar который показывает количество свободной и занятой оперативной памяти.

В ручном режиме используются те же процедуры, что и в автоматическом, с той лишь разницей, что они не зациклены.

. Логическая структура программы

Автоматическая загрузка и исполнение процессов

:=strtoint(edit1.Text);:=0;.cells[1,0]:='Название процесса';.cells[2,0]:='Pазмер процесса(Байт)';.cells[3,0]:='Bремя выполнения';.cells[4,0]:='Адрес в ОП';(1000);_2:=random(2);rand_2=0 then begin(process,i+1);:=inttostr(i);[i].prohoj:=proh;[i].Imya:='Process #'+str;[i].PID:=i;:=random(26)+4 ;[i].Razmer:=inttostr(j);[i].PID:=i;_2:=inttostr(random(9)+2);[i].Vremya:=str_2;[i].ran:=random(99)+1;:=poz + prcent;:=(j/(razmerpam/100))*5;[i].Adress:=inttostr(round(poz));:=opraz+strtoint(process[i].Razmer);:=Round(prcent) ;:=round(poz);[i].cr:=random(255)+1;[i].sin:=random(255)+1;[i].zel:=random(255)+1;ListBox1.Canvas do.Color:=RGB(0,0,0);.Color:=RGB(process[i].cr, process[i].sin, process[i].zel);( Bounds(0, poz1, 400,prcent1 ));(10, poz1+1, process[i].Imya);;opraz>razmerpam then begin:=proh+1;ListBox1.Canvas do.Color:=clwhite;.Color:=clwhite;( Bounds(0, 0, 400,500));;:=0;:=0;:=0;h := 1 to i do beginprocess[h].stat <> 'end' then begin[h].prohoj:=proh;:=opraz+strtoint(process[h].Razmer);opraz<razmerpam then begin:=poz + prcent;:=(strtoint(process[h].Razmer)/(razmerpam/100))*5;[h].Adress:=inttostr(round(poz));:= ((strtoint(process[h].Razmer))/(razmerpam/100))*5 ;:=round(razm);ListBox1.Canvas do.Color:=clblack;.Color:=RGB( process[h].cr, process[h].sin, process[h].zel);( Bounds(0, strtoint(process[h].adress), 400,razm1));(10, strtoint(process[h].adress)+1, process[h].Imya);;.cells[4,process[h].pid]:=process[h].adress ;else begin MessageDlg('Память переполнена.', mtWarning, [mbOk],0);.Click;;.RowCount:= stringgrid1.rowcount+1;.cells[1,i]:=process[i].imya;.cells[2,i]:=process[i].razmer;.cells[3,i]:=process[i].vremya;.cells[4,i]:=process[i].adress;i:=i-1;:=random(79)+1;h:= 1 to i doj1 := 1 to i do begin(StringGrid1.cells[1,process[h].pid-1]='') and (process[h].stat<>'end') then beginprocess[h].pid>1 then begin.cells[1,process[h].pid-1]:= process[h].Imya ;.cells[2,process[h].pid-1]:=process[h].Razmer ;.cells[3,process[h].pid-1]:=process[h].vremya ;.cells[4,process[h].pid-1]:=process[h].adress ;.cells[1,process[h].pid]:='';.cells[2,process[h].pid]:='';.cells[3,process[h].pid]:='';.cells[4,process[h].pid]:='';[h].pid:= process[h].pid-1;;

(process[h].stat<>'end') and (strtoint(process[h].vremya)=0) then begin[h].stat:='end';.cells[1,process[h].pid]:='';.cells[2,process[h].pid]:='';.cells[3,process[h].pid]:='';.cells[4,process[h].pid]:='';;

(process[h].stat<>'end') and (strtoint(process[h].vremya)>0) then begin(process[h].ran > rand) or (process[h].ran_1=1) {or (kran>0)} then begin[h].Vremya:=inttostr(strtoint(process[h].vremya)-1);[h].ran_1:=1;.cells[3,process[h].pid]:=process[h].vremya;

(process[h].stat = 'end') and (process[h].prohoj = proh) then:= (strtoint(process[h].Razmer)/(razmerpam/100))*5 ;:=round(razm);ListBox1.Canvas do.Color:=clwhite;.Color:=clwhite;( Bounds(0, strtoint(process[h].adress), 400,razm1));;:=0;j3 := 1 to i do beginprocess[j3].stat <> 'end' then:=strtoint(process[j3].Razmer)+sump;.Panels.items[0].text:='Свободно памяти: '+inttostr(strtoint(edit1.Text)-sump)+' Mb';.Panels.items[1].text:='Занято памяти: '+inttostr(sump)+' Mb';:=i+1;butt=1 ;;

программа оперативный память интерфейс

Ручное добавление процессов

.cells[1,0]:='Название процесса';.cells[2,0]:='Pазмер процесса (Байт)';.cells[3,0]:='Bремя выполнения';.cells[4,0]:='Адрес в ОП';;:=strtoint(edit1.Text);(process,i+1);:=inttostr(i);[i].prohoj:=proh;[i].Imya:='Process #'+str;[i].PID:=i;:=random(19)+4 ;edit3.text ''then process[i].Razmer:=edit3.text else process[i].Razmer:=inttostr(j);[i].PID:=i;_2:=inttostr(random(9)+2);edit2.text then process[i].Vremya:=edit2.text else process[i].Vremya:=str_2;edit4.text then process[i].ran:=strtoint(edit4.text) else process[i].ran:=random(99)+1;:=poz + prcent;:=(strtoint(process[i].Razmer)/(razmerpam/100))*5;[i].Adress:=inttostr(round(poz));:=opraz+strtoint(process[i].Razmer);:=Round(prcent) ;:=round(poz);[i].cr:=random(255)+1;[i].sin:=random(255)+1;[i].zel:=random(255)+1;ListBox1.Canvas do.Color:=RGB(0,0,0);.Color:=RGB(process[i].cr, process[i].sin, process[i].zel);( Bounds(0, poz1, 400,prcent1 ));(10, poz1+1, process[i].Imya);;

opraz>razmerpam then begin:=proh+1;ListBox1.Canvas do.Color:=clwhite;.Color:=clwhite;( Bounds(0, 0, 400,500));;:=0;:=0;:=0;h := 1 to i do beginprocess[h].stat <> 'end' then begin[h].prohoj:=proh;:=opraz+strtoint(process[h].Razmer);opraz<razmerpam then begin:=poz + prcent;:=(strtoint(process[h].Razmer)/(razmerpam/100))*5;[h].Adress:=inttostr(round(poz));:= ((strtoint(process[h].Razmer))/(razmerpam/100))*5 ;:=round(razm);ListBox1.Canvas do.Color:=clblack;.Color:=RGB( process[h].cr, process[h].sin, process[h].zel);( Bounds(0, strtoint(process[h].adress), 400,razm1));;else begin MessageDlg('Память переполнена.', mtWarning, [mbOk],0);.Click;;

.RowCount:= stringgrid1.rowcount+1;.cells[1,i]:=process[i].imya;.cells[2,i]:=process[i].razmer;.cells[3,i]:=process[i].vremya;.cells[4,i]:=process[i].adress;:=0;j3 := 1 to i do beginprocess[j3].stat <> 'end' then:=strtoint(process[j3].Razmer)+sump;.Panels.items[0].text:='Свободно памяти: '+inttostr(strtoint(edit1.Text)-sump)+' Mb';.Panels.items[1].text:='Занято памяти: '+inttostr(sump)+' Mb'; i:=i+1;

Ручное выполнение процесса.cells[1,0]:='Название процесса';.cells[2,0]:='Pазмер процесса(Байт)';.cells[3,0]:='Bремя выполнения';.cells[4,0]:='Адрес в ОП';:=100;I1 :=1 to i doprocess[i1].PID =StringGrid1.Row then h:=i1;i1:=1 to strtoint(process[h].Vremya)+1 do begin(process[h].stat<>'end') and (strtoint(process[h].vremya)=0) then begin[h].stat:='end';.cells[1,process[h].pid]:='';.cells[2,process[h].pid]:='';.cells[3,process[h].pid]:='';.cells[4,process[h].pid]:='';;j2:=1 to i doprocess[j2].ran_1 <> 0 then kran:= kran+1;(process[h].stat<>'end') and (strtoint(process[h].vremya)>0) then begin(process[h].ran < rand) or (process[h].ran_1=1) then begin[h].Vremya:=inttostr(strtoint(process[h].vremya)-1);[h].ran_1:=1;.cells[3,process[h].pid]:=process[h].vremya;

(process[h].stat = 'end') and (process[h].prohoj = proh) then:= (strtoint(process[h].Razmer)/(razmerpam/100))*5 ;:=round(razm);ListBox1.Canvas do.Color:=clwhite;.Color:=clwhite;( Bounds(0, strtoint(process[h].adress), 400,razm1));;(100);;:=0;j3 := 1 to i-1 do beginprocess[j3].stat <> 'end' then:=strtoint(process[j3].Razmer)+sump;.Panels.items[0].text:='Свободнопамяти: '+inttostr(strtoint(edit1.Text)-sump)+' Mb';.Panels.items[1].text:='Занято памяти: '+inttostr(sump)+' Mb';

Очистка

ListBox1.Canvas do.Color:=clwhite;.Color:=clwhite;( Bounds(0, 0, 400,500));;:=0;:=1;:=0;:=0;:=0;:=1;; with StringGrid1 do beginvv:=0 to ColCount-1 do[vv].Clear;;(process,0);

4. Тестирование

. Штатный режим работы программы.

Рисунок 3

) Внештатный режим работы программы. Возникает при переполнении оперативной памяти и отсутствии места для поступающих процессов.

Рисунок 4

Заключение

Динамическое распределение оперативной памяти хотя и являлось прогрессивной находкой для своего времени, но полностью не удовлетворяло пользователей ПК, как из-за фрагментации памяти, вызывающей потерю пространства оперативной памяти, так и из-за невозможности использования дискового пространства. Пусть данная система и не применяется в настоящее время, она достойно заняла свое место в истории развития вычислительной техники и дала множество идей разработчикам следующих систем работы с памятью.

Больше работ по теме: