Модель распределения памяти разделами переменного размера

Федеральное государственное образовательное
учреждения высшего профессионального образования
Национальный исследовательский технологический университет
«МИСиС»


Институт ИТАСУ

Кафедра Инженерной кибернетики




КУРСОВАЯ РАБОТА
по дисциплине «Операционные системы и среды»

Вариант 9
Модель распределения памяти разделами переменного размера с общей очередью со стратегией «наиболее подходящий».


Выполнил













Москва 2014 г.


Содержание:
1.Теоретическое введение 2
1.1.Свойства многозадачной среды 2
1.2.Вытесняющая и невытесняющая многозадачность. 3
Системы пакетной обработки 4
Системы с разделением времени. 5
Системы реального времени 5
1.4.Основные свойства вычислительных задач 6
2.Описание программы 9
2.1.Формулировка задания 9
2.2.Алгоритм и перечень задаваемых исходных данных 9
2.3.Код программы 11
2.4.Описание результатов работы программы 15
3.Литература 17



Теоретическое введение
Многозадачность (англ. multitasking) — свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределённых вычислительных системах.
Существует 2 типа многозадачности:
• Процессная многозадачность (основанная на процессах — одновременно выполняющихся программах). Здесь программа — наименьший элемент кода, которым может управлять планировщик операционной системы. Более известна большинству пользователей (работа в текстовом редакторе и прослушивание музыки).
• Поточная многозадачность (основанная на потоках). Наименьший элемент управляемого кода — поток (одна программа может выполнять 2 и более задачи одновременно).
Свойства многозадачной среды
Примитивные многозадачные среды обеспечивают чистое «разделение ресурсов», когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени.
Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. Такая многозадачная среда обладает следующими особенностями:
• Каждая задача имеет свой приоритет, в соответствии с которым получает процессорное время и память
• Система организует очереди задач так, чтобы все задачи получили ресурсы, в зависимости от приоритетов и стратегии системы
• Система организует обработку прерываний, по которым задачи могут активироваться, деактивироваться и удаляться
• По окончании положенного кванта времени ядро временно переводит задачу из состояния выполнения в состояние готовности, отдавая ресурсы другим задачам. При нехватке памяти страницы невыполняющихся задач могут быть вытеснены на диск (своппинг), а потом через определённое системой время, восстанавливаться в памяти
• Система обеспечивает защиту адресного пространства задачи от несанкционированного вмешательства других задач
• Система обеспечивает защиту адресного пространства своего ядра от несанкционированного вмешательства задач
• Система распознаёт сбои и зависания отдельных задач и прекращает их
• Система решает конфликты доступа к ресурсам и устройствам, не допуская тупиковых ситуаций общего зависания от ожидания заблокированных ресурсов
• Система гарантирует каждой задаче, что рано или поздно она будет активирована
• Система обрабатывает запросы реального времени
• Система обеспечивает коммуникацию между процессами
Вытесняющая и невытесняющая многозадачность.
Важнейшим разделяемым ресурсом является процессорное время. Способ распределения процессорного времени между несколькими одновременно существующими в системе вычислительными процессами во многом определяет особенность ОС. Среди множества существующих способов реализации многозадачности можно выделить две группы алгоритмов:
• невытесняющая многозадачность (NetWare, Windows 3.x);
• вытесняющая многозадачность (Windows NT, OS/2, Unix).

Основным различием между вытесняющим и невытесняющим алгоритмом многозадачности является степень централизации планирования вычислительных процессов. В первом случае планирование вычислительных процессов целиком возлагается на операционную систему, а во втором – распределено между операционной системой и прикладными программами.
При невытесняющей многозадачности активный вычислительный процесс выполняется до тех пор, пока сама прикладная программа по собственной инициативе не отдаст указание операционной системе выбрать из очереди другой готовый к выполнению процесс. При вытесняющей многозадачности решение о переключении процессора с одного активного вычислительного процесса на другой принимается самой ОС, а не прикладной программой.
В зависимости от областей использования многозадачные ОС подразделяются на три типа:
• системы пакетной обработки (например, ОС ЕС);
• системы с разделением времени (Unix, VMS, Windows, Linux);
• системы реального времени (QNX, RT/11).

Системы пакетной обработки
Предназначены для решения задач такого характера, которые не требуют быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, т. е. решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используется следующий порядок обработки данных: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется множество одновременно выполняемых задач. Для одновременного выполнения выбираются те задачи, которые предъявляют различные требования к ресурсам. Это делается с целью обеспечения сбалансированной загрузки всех устройств вычислительной машины. Например, является желательным одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом.
Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, т.е. выбирается наиболее оптимальное, «выгодное» задание. Следовательно, в таких ОС невозможно гарантировать выполнение того или иного задания в течение определенного периода времени. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит только в случае, если активная задача сама отказывается от процессора, например, из-за необходимости выполнить операцию ввода-вывода. Очевидно, что такой алгоритм вычислительного процесса снижает эффективность работы пользователя в интерактивном режиме, но остается актуальным для обеспечения высокой производительности при обработке больших объемов информации и до настоящего времени, особенно в прикладных информационных системах.
Системы с разделением времени.
В системах с разделением времени каждой задаче выделяется небольшой квант процессорного времени, ни одна задача не занимает процессор надолго и время ответа оказывается приемлемым. Если квант выбран достаточно небольшим, то это предполагает параллельное выполнение нескольких программ, существующих в рамках одной вычислительной системы. Ясно, что подобные системы обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая «выгодна» системе. Критерием эффективности систем с разделением времени является не максимальная пропускная способность процессора, а эффективность работы пользователя в интерактивном режиме.
Системы реального времени
Применяются для управления различными техническими объектами (такими, как станок, спутник, научная экспериментальная установка) или технологическими процессами (гальваническая линия, доменный процесс и т.п.). Применяют ОС РВ и в банковском деле. Критерием эффективности для систем реального времени является их способность выдерживать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия). Это время называется временем реакции системы, а соответствующее свойство системы – реактивностью. Среди наиболее известных ОС РВ для IBM PC – RTMX, AMX, OS-9000, FLEX OS, QNX и др. Среди перечисленных ОС наиболее полным набором инструментальных средств обладает ОС РВ QNX, которая выполняет 32-разрядные приложения и может работать совместно с ОС семейства Unix.
Некоторые операционные системы могут совмещать в себе свойства систем разных типов, например, часть задач может выполняться в режиме пакетной обработки, а часть – в режиме реального времени или в режиме разделения времени. В таких случаях режим пакетной обработки часто называют фоновым режимом.
Основные свойства вычислительных задач
Как правило, вся важная, с точки зре¬ния операционной системы, информа¬ция о задаче хранится в унифициро¬ванной структуре данных — управляющем блоке (Task Control Block, TCB). В блоке хранятся такие параметры, как имя и номер задачи, верхняя и нижняя границы стека, ссылка на очередь сооб¬щений, статус задачи, приоритет и т. п .
Приоритет — это некое целое число, присваиваемое задаче и характеризую-щее ее важность по сравнению с други¬ми задачами, выполняемыми в системе. Приоритет используется в основном планировщиком задач для определе¬ния того, какая из готовых к работе за¬дач должна получить управление. Раз¬личают системы с динамической и ста¬тической приоритетностью. В первом случае приоритет задач может менять¬ся в процессе исполнения, в то время как во втором приоритет задач жестко задается на этапе разработки или во время начального конфигурирования системы.
Контекст задачи — это набор дан¬ных, содержащий всю необходимую информацию для возобновления вы¬полнения задачи с того места, где она была ранее прервана. Часто контекст хранится в TCB и включает в себя такие данные, как счетчик команд, указатель стека, регистры CPU и FPU и т. п.[3] Плани¬ровщик задач в случае необходимости сохраняет контекст текущей активной задачи и восстанавливает контекст за¬дачи, назначенной к исполнению. Та¬кое переключение контекстов и явля¬ется, по сути, основным механизмом ОС РВ при переходе от выполнения од¬ной задачи к выполнению другой.
Состояние (статус) задачи. С точ¬ки зрения операционной системы, за¬дача может находиться в нескольких состояниях. Число и название этих со¬стояний различаются от одной ОС к другой. По-видимому, наибольшее чис¬ло состояний задачи определено в язы¬ке Ada. Тем не менее, практически в лю¬бой ОС РВ загруженная на выполнение задача может находиться, по крайней мере, в трех состояниях.
1. Активная задача — это задача, выпол¬няемая системой в текущий момент времени.
2. Готовая задача — это задача, готовая к выполнению и ожидающая у плани-ровщика своей «очереди».
3. Блокированная задача — это задача, выполнение которой приостановле¬но до наступления определенных со¬бытий. Такими событиями могут быть освобождение необходимого задаче ресурса, поступление ожидае¬мого сообщения, завершение интер¬вала ожидания и т. п.
Пустая задача (Idle Task) — это зада¬ча, запускаемая самой операционной системой в момент инициализации и выполняемая только тогда, когда в сис¬теме нег других готовых для выполнения задач. Пустая задача запускается с самым низким приоритетом и, как пра¬вило, представляет собой бесконечный цикл «ничего не делать». Наличие пус¬той задачи предоставляет операцион¬ной системе удобный механизм отра¬ботки ситуаций, когда нет ни одной го¬товой к выполнению задачи.[5]
Многократный запуск задач. Как правило, многозадачные ОС позволя¬ют запускать несколько копий одной и той же задачи. При этом для каждой та¬кой копии создается свой TCB и выде¬ляется своя область памяти. В целях экономии памяти может быть предус¬мотрено совместное использование одного и того же исполняемого кода для всех запущенных копий. В этом случае программа должна обеспечивать повторную входимость (реентера¬бельность). Кроме того, программа не должна использовать временные фай¬лы с фиксированными именами и должна корректно осуществлять до¬ступ к глобальным ресурсам.
Реентерабельность (повторная входимость) означает возможность без негативных последствий временно пре¬рвать выполнение какой-либо функции или подпрограммы, а затем вызвать эту функцию или подпрограмму снова. Частным проявлением реентерабельности является рекурсия, когда тело подпрограммы содержит вызов самой себя. Классическим примером нереентерабельной системы является DOS, a типичной причиной нереентерабель¬ности служит использование глобаль¬ных переменных. Предположим, что у нас есть функция, реализующая низкоу¬ровневую запись на диск, и пусть она использует глобальную переменную write_sector, которая устанавливается в соответствии с параметром, передавае¬мым этой функции при вызове. Пред¬положим теперь, что Задача А вызывает эту функцию с параметром 3, то есть хо¬чет записать данные в сектор номер 3. Допустим, что когда переменная write_sector уже равна 3, но сама запись еще не произведена, выполнение Зада¬чи А прерывается и начинает выпол-няться Задача В, которая взывает ту же функцию, но с аргументом 10. После то¬го как запись в сектор номер 10 будет произведена, управление рано или поздно вернется к Задаче А, которая продолжит работу с того же места. Од¬нако, так как переменнаяwrite_sector имеет теперь значение 10, данные Зада¬чи А, предназначавшиеся для сектора номер 3, будут вместо этого записаны в сектор номер 10. Из приведенного при¬мера видно, что ошибки, связанные с нереентерабельностью, трудно обнару¬жить, а последствия они могут вызвать самые катастрофические.

Описание программы
Формулировка задания
Создать модель распределения памяти разделами переменного размера с общей очередью со стратегией «наиболее подходящий».
Такая модель распределения памяти предполагает, что до начала загрузки программ вся память разделяется на непрерывные участки переменного размера (блоки). Для каждой поступающей программы выделяется один из свободных участков памяти. Таким образом, размер поступающей программы не должен превышать размера блока максимального объема. Если все блоки заняты, то программа ожидает первого освободившегося. Если имеется несколько свободных блоков, то программа загружается в первый подходящий по размеру.
Исходные данные:
- общий объем памяти 64мб;
- размер блока 4мб, 8мб, 18мб, 32мб. Всего 4 блока памяти;
- поток заявок на размещения в памяти (номер заявки, объем требуемой памяти, время поступления, продолжительность обработки заявки).
Результаты работы модели на дисплее показывают, сколько процессов загружено и сколько свободных блоков памяти на данный момент времени.
Алгоритм и перечень задаваемых исходных данных
Программа написана в приложение WindowsForm. В начале программы задаем очередь для каждого элемента процесса. В каждом процессе 4 элемента. В очереди запросов есть поля, в которых описывается, из каких входных данных состоит каждый запрос. Запрос включает в себя: «Номер заявки», «Объем требуемой памяти», «Время поступления» и «Продолжительность обработки заявки». Все эти поля инициализируем.
В программе присутствует виртуальный таймер (счетчик), по которому определяется, когда конкретно поступает тот или иной запрос. В программе пишем цикл по нашей ранее составленной очереди. В цикле работаем с «объемом требуемой памяти» . После этого необходимо проверить, что время поступления равно общему времени и после этого можно добавить запрос в блок памяти, который для него наиболее подходящий. Наиболее подходящим считается тот блок памяти, в котором после поступления запроса останется наименьшее количество свободного места. Для того чтобы наш запрос попал именно в подходящий блок памяти мы ставим 4 условия, которые проверяются на каждой итерации цикла. Если разность между конкретным блоком памяти и памяти программы меньше, чем разность всех остальных блоков памяти, то программа поступает в данный блок. Когда все блоки памяти заполнились, то следующий запрос поступает в очередь. Как только освободился тот или иной блок в него поступает следующий запрос.
Структура программы:
1. Программа принимает на вход любые имеющиеся данные из любого файла, интерфейса WindowsForm и т.д. Проверяет соответствующие ограничения по объему занимаемой памяти.
2. Запросы каждой программы поступают в очередь и хранятся там.
3. Симуляция обработки запроса в цикле и в нем же удаление выполненных запросов.
4. Данные из цикла поступают в регистратор и там создается полная картина происходящего.
5. По окончанию работы программы, отображается в каком состоянии находится каждый блок памяти.

Код программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Forms;
using System.Windows.Forms.Integration;
using System.IO;

namespace WindowsFormsApplication22
{
public partial class Form1 : Form
{
Queue<Process> Queue1 = new Queue<Process>();
List<Process> _pr = new List<Process>();
int _count = 0;
int _barVal1 = 0; int _barVal2 = 0; int _barVal3 = 0; int _barVal4 = 0; int _barCap1; int _barCap2; int _barCap3; int _barCap4;
List<string> _bar1 = new List<string>(); List<string> _bar2 = new List<string>(); List<string> _bar3 = new List<string>(); List<string> _bar4 = new List<string>();
bool flag = false; bool flagc = false;
public Form1()
{
InitializeComponent();
}

public int getMem(string name)
{
Process pr;
int mem = -1;
for (int i = 0; i < _pr.Count; i++)
{
pr = _pr[i];
if (pr.name.Equals(name))
{
mem = pr.memory;
}
}
return mem;
}
public bool ifProc(string name, List<string> ls)
{
bool fl = false;
for (int i = 0; i < ls.Count; i++)
{
if (ls[i].Equals(name))
{
fl = true;
}
}
return fl;
}


private void button4_Click(object sender, EventArgs e)
{
_barCap1 = int.Parse(textBox3.Text); _barCap2 = int.Parse(textBox4.Text); _barCap3 = int.Parse(textBox5.Text); _barCap4 = int.Parse(textBox6.Text);
progressBar1.Maximum = _barCap1; progressBar2.Maximum = _barCap2; progressBar3.Maximum = _barCap3; progressBar4.Maximum = _barCap4;
openFileDialog1.Filter = "TXT Files|*.txt";
if (openFileDialog1.ShowDialog() == System.Windows.Forms.DialogResult.OK)
{
StreamReader sr = new
StreamReader(openFileDialog1.FileName);
string line; string[] _str;
while ((line = sr.ReadLine()) != null)
{
_str = line.Split( );
Process doProc = new Process(_str[0], int.Parse(_str[1]), int.Parse(_str[2]), int.Parse(_str[3]));
_pr.Add(doProc);
tb3.Rows.Add(_str[0], _str[1], _str[2], _str[3]);
}
sr.Close();
}
}
private void button2_Click(object sender, EventArgs e)
{
_barCap1 = int.Parse(textBox3.Text); _barCap2 = int.Parse(textBox4.Text); _barCap3 = int.Parse(textBox5.Text); _barCap4 = int.Parse(textBox6.Text);
progressBar1.Maximum = _barCap1; progressBar2.Maximum = _barCap2; progressBar3.Maximum = _barCap3; progressBar4.Maximum = _barCap4;
string[] _str = textBox1.Text.Split( );
try
{
Process doProc = new Process(_str[0], int.Parse(_str[1]), int.Parse(_str[2]), int.Parse(_str[3]));
_pr.Add(doProc);
tb3.Rows.Add(_str[0], _str[1], _str[2], _str[3]);
}
catch { MessageBox.Show("Введите процесс [имя_размер_начало_продолжительность]"); }
textBox1.Text = "";
}
private void button1_Click(object sender, EventArgs e)
{
textBox2.Text = _count.ToString();
for (int k = 0; k < _pr.Count; k++)
{
Process doP = _pr[k];
a1: if (Queue1.Count != 0 & !flagc)
{
int _mem = Queue1.Peek().memory;
if (((_barCap1 - _barVal1) >= _mem) || ((_barCap2 - _barVal2) >= _mem) || ((_barCap3 - _barVal3) >= _mem) || ((_barCap4 - _barVal4) >= _mem))
{
doP = Queue1.Peek();
int Time = _count;
tb1.Rows.Add(doP.name, doP.memory, Time, doP.executeTime);

Queue1.Dequeue(); tb2.Rows.RemoveAt(0);
int CountRows = tb1.RowCount; int _cell = doP.memory;

if (_barVal1 + _cell <= _barCap1)
{
_barVal1 += _cell; _bar1.Add(doP.name);
flagc = false;
}
else if (_barVal2 + _cell <= _barCap2)
{
_barVal2 += _cell; _bar2.Add(doP.name);
flagc = false;
}
else if (_barVal3 + _cell <= _barCap3)
{
_barVal3 += _cell; _bar3.Add(doP.name);
flagc = false;
}
else if (_barVal4 + _cell <= _barCap4)
{
_barVal4 += _cell; _bar4.Add(doP.name);
flagc = false;
}
else
{
tb1.Rows.RemoveAt(CountRows - 1);
flagc = true; goto a1;
}
}
}
else
doP = _pr[k];
a0: if (doP.startTime == _count)
{
if (flag == false)
{
tb1.Rows.Add(doP.name, doP.memory, doP.startTime, doP.executeTime);
int CountRows = tb1.RowCount; int _cell = doP.memory;

if (_barVal1 + _cell <= _barCap1)
{
_barVal1 += _cell; _bar1.Add(doP.name);
flag = false;
}
else if (_barVal2 + _cell <= _barCap2)
{
_barVal2 += _cell; _bar2.Add(doP.name);
flag = false;
}
else if (_barVal3 + _cell <= _barCap3)
{
_barVal3 += _cell; _bar3.Add(doP.name);
flag = false;
}
else if (_barVal4 + _cell <= _barCap4)
{
_barVal4 += _cell; _bar4.Add(doP.name);
flag = false;
}
else
{
tb1.Rows.RemoveAt(CountRows - 1);
flag = true; goto a0;
}
}
else
{
tb2.Rows.Add(doP.name, doP.memory, doP.startTime, doP.executeTime); flag = false;
Queue1.Enqueue(doP);
}
}

}
try
{
for (int i = 0; i < tb1.Rows.Count; i++)
{
a2: int _val = int.Parse(tb1.Rows[i].Cells[3].Value.ToString());
int _st = int.Parse(tb1.Rows[i].Cells[2].Value.ToString());
int _ext = _val - (_count - _st);
if (_ext < 0)
{
string _strName = tb1.Rows[i].Cells[0].Value.ToString();
tb1.Rows.RemoveAt(i);

int _strMem = getMem(_strName);
if (ifProc(_strName, _bar1))
{
_barVal1 -= _strMem;
}
else if (ifProc(_strName, _bar2))
{
_barVal2 -= _strMem;
}
else if (ifProc(_strName, _bar3))
{
_barVal3 -= _strMem;
}
else if (ifProc(_strName, _bar4))
{
_barVal4 -= _strMem;
}
goto a2;
}
if (tb1.Rows.Count != 0)
tb1.Rows[i].Cells[4].Value = tb1.Rows[i].Cells[0].Value + " – " + _ext;
}
}
catch(ArgumentOutOfRangeException){}

if (tb1.Rows.Count <= 0)
label6.Text = "ПРОСТОЙ СИСТЕМЫ!";
else
label6.Text = "";
progressBar1.Value = _barVal1; progressBar2.Value = _barVal2; progressBar3.Value = _barVal3; progressBar4.Value = _barVal4;
label2.Text = progressBar1.Value.ToString() + " / " + _barCap1;
label3.Text = progressBar2.Value.ToString() + " / " + _barCap2;
label4.Text = progressBar3.Value.ToString() + " / " + _barCap3;
label5.Text = progressBar4.Value.ToString() + " / " + _barCap4;
_count++;
}
}
class Process
{
public string name;//имя процесса
public int memory;//память процесса
public int startTime;//время запуска процесса
public int executeTime;//длительность работы процесса

public Process(string name, int memory, int startTime, int executeTime)//конструктор
{

this.startTime = startTime;
this.executeTime = executeTime;
this.name = name;
this.memory = memory;

}
}
}




Литература
1. Таненбаум Э. Современные операционные системы. Изд-е 4. СПб.: Питер, 2010.
2. Широков А.И., Калашникова О.Н., Крапухина Н.В., Мурадханов С.Э., Подлазова А.В. Многопользовательские операционные системы. (№592). Лаб. практикум. 2-е изд. Изд. дом МИСиС,, 2010
3. 5. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2007. – 544 с.: ил.
4. Карпов В.Е, Коньков К.А., Иванникова В.П. Основы операционных систем. Интернет-Университет информационных технологий www.intuit.ru Москва, 2005.
5. Назаров С.В., Широков А.И., Многопользовательские операционные системы.