Моделирование обслуживания вычислительных процессов в системе

Национальный Исследовательский Технологический

Университет МИСиС

Контрольная работа

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

Студент: Рубаев Э.Ю.

Преподаватель: Широков А.И.

Москва 2012

1.Теоретическая часть

Процесс. Управление процессами

Одно из важнейшей части ОС, влияющей на работу компьютера (вычислительной машины), является подсистема управления процессами [1].

В Википедии определение процесса дается следующим образом: Процесс (или по-другому, задача) - выполнение инструкций компьютерной программы на процессоре ЭВМ.

Для ОС процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами [1].

Многозадачность

Определение из Википедии:

Многозадачность (англ. multitasking) - свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределённых вычислительных системах.

Существует 2 типа многозадачности [4]:

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

·Поточная многозадачность (основанная на потоках). Наименьший элемент управляемого кода - поток (одна программа может выполнять 2 и более задачи одновременно).

Состояние процессов

В многопроцессной системе процесс может находиться в одном из трех основных состояний [1]:

ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

ОЖИДАНИЕ - пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

Контекст и дескриптор процесса

На протяжении существования процесса его выполнение может быть многократно прервано и продолжено. Для того, чтобы возобновить выполнение процесса, необходимо восстановить состояние его операционной среды. Состояние операционной среды отображается состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых данным процессом системных вызовов и т.д. Эта информация называется контекстом процесса [1].

Кроме этого, операционной системе для реализации планирования процессов требуется дополнительная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. В некоторых ОС (например, в ОС UNIX) информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса [1].

Дескриптор процесса по сравнению с контекстом содержит более оперативную информацию, которая должна быть легко доступна подсистеме планирования процессов. Контекст процесса содержит менее актуальную информацию и используется операционной системой только после того, как принято решение о возобновлении прерванного процесса [1].

Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки. Таким образом, каждый дескриптор, кроме всего прочего, содержит по крайней мере один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое [1].

Программный код только тогда начнет выполняться, когда для него операционной системой будет создан процесс. Создать процесс - это значит [1]:

1.создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;

2.включить дескриптор нового процесса в очередь готовых процессов;

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

Стек - структура данных с методом доступа к элементам LIFO (Last In, First Out).

В качестве примера использования нескольких потоков в одном процессе можно привести ситуацию, когда приложению нужно записать большой файл на диск. При использовании одного потока доступ к другим функциям программы будет недоступен до окончания операции [2].

Преимущества использования нескольких потоков перед несколькими процессами:

·возможность совместного использования параллельными объектами адресного пространства и всех содержащихся в нем данных;

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

·- увеличивается производительность.

Поток может находиться в одном из нескольких состояний. Переходы между состояниями такие же, как у процессов [2].

2.Описание программы

2.1Формулировка задания

Разработать программу, моделирующую обслуживание множества вычислительных процессов в системе с 4 очередями, определяемыми значениями приоритетов.

2.2Описание алгоритма

вычислительный процесс операционная система

В первую очередь попадают процессы со значениями приоритетов от 1 до 5, во вторую - от 6 до 10, в третью - от 11 до 15 и последнюю (четвертую) - от 16 до 20. В системе не могут появиться процессы с приоритетами большими 20 и меньшими 1. Все процессы без прерывания обслуживаются одним устройством. Определено следующее правило выбора очередного процесса. Сначала поочередно (в порядке поступления) обрабатываются все процессы из четвертой очереди. Заметим, что они имеют наивысший приоритет. Если в этой очереди нет процессов, то обрабатываются процессы из третей очереди. Их приоритет больше, чем у процессов первой и второй очереди, но меньше чем у четвертой. Они обрабатываются, так же как и остальные процессы из одной очереди, в порядке поступления. Если третья и четвертая очереди пусты, то выполняются процессы второй очереди. И, наконец, когда в системе не обработаны процессы только из перовой очереди, то выполняются они.

Исходные данные: поток заявок на выполнение процессов (имя заявки, время поступления, приоритет, время исполнения).

Пример набора исходных данных и результата работы программы.

имя заявки, время поступления, приоритет, время исполнения (a,0,9,3); (b,1,3,3); (c,8,18,5); (d,9,6,3); (e,10,12,3) (f,11,11,3).

Имеется класс Process, который имеет четыре поля: с именем, приоритетом, временем запуска процесса и длительностью работы. Так же в классе описаны два открытых метода: конструктор с параметрами (для инициализации данных), конструктор по умолчанию, метод ToString(для вывода инициализированных значений наших полей). В классе Program имеются четыре очереди(экземпляры библиотечного класса Queue). После, в цикле, повторения которого зависят от количества процессов, происходит инициализация данных из файла test.txt и с помощью четырех условий процессы распределяются по очередям, в зависимости от приоритетов. В Console выводится таблица с результатами заполненных данных. Далее создается еще один цикл, в котором проверяются четыре условия(сравнивание поля startTime у всех процессов), для того, чтобы распределить поочередность работы процессов и если выполняется одно из условий, то к строке(в которой, показывается работа программы) прибавляется имя данного процесса(поле name) столько раз, сколько секунд он должен длиться и в итоге строка, принимает следующее значение: aaabbbccceeeddd (пример). После чего происходит вывод этой строки в Console.

2.3Исходный код программы(C#)

Проект типа ConsoleApplication:

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; namespace ConsoleApplication3 { class Process { public string name;//имя процесса Gname public int priority;//приоритет Gpriority public int startTime;//время запуска процесса GStart public int executeTime;//длительность работты процесса GexecTime public Process(string name, int startTime, int priority, int executeTime)//конструктор { this.startTime = startTime; this.executeTime = executeTime; this.name = name; this.priority = priority; } public Process() { } public override string ToString()//метод вывода { return String.Format("{0} {1} {2} {3}", name, priority, startTime, executeTime); } } class Program { static void Main(string[] args) { //создаём 4 очереди Queue<Process> Queue1 = new Queue<Process>(); Queue<Process> Queue2 = new Queue<Process>(); Queue<Process> Queue3 = new Queue<Process>(); Queue<Process> Queue4 = new Queue<Process>(); Console.WriteLine("\t\t\tИсходные данные:"); Console.WriteLine(); //заполняем из файла StreamReader koren = new StreamReader("test.txt", Encoding.GetEncoding(1251)); int number = int.Parse(koren.ReadLine()); int length = 0; int start = 0; for (int i = 0; i < number; i++) { string newLine = koren.ReadLine(); string[] proc = newLine.Split(' '); Process DoProc = new Process(proc[0], int.Parse(proc[1]), int.Parse(proc[2]), int.Parse(proc[3])); length += DoProc.executeTime; start = DoProc.startTime; //расставляем по приоритетам процессы if (DoProc.priority >= 15) { Queue4.Enqueue(DoProc); } if (DoProc.priority >= 10 && DoProc.priority < 15) { Queue3.Enqueue(DoProc); } if (DoProc.priority >= 5 && DoProc.priority < 10) { Queue2.Enqueue(DoProc); } if (DoProc.priority >= 0 && DoProc.priority < 5) { Queue1.Enqueue(DoProc); } } int[] graph = new int[(length + start) * 10]; string[] name = new string[(length + start) * 10]; for (int i = 0; i < graph.Length; i++) { graph[i] = -1; } Console.WriteLine("______________________________________________________________________"); for (int currentStep = 0; Queue1.Count!= 0 || Queue2.Count!= 0 || Queue3.Count!= 0 || Queue4.Count!= 0; currentStep++) { graph[currentStep] = 0; Process process4 = new Process(); Process process3 = new Process(); Process process2 = new Process(); Process process1 = new Process(); if (Queue4.Count!= 0) process4 = Queue4.Peek(); if (Queue3.Count!= 0) process3 = Queue3.Peek(); if (Queue2.Count!= 0) process2 = Queue2.Peek(); if (Queue1.Count!= 0) process1 = Queue1.Peek(); if (process4.startTime < currentStep && Queue4.Count > 0) { int busyTime = process4.executeTime; Console.WriteLine("имя процесса: {0} \t старт: {1}\t время работы: {2}\t приоритет: {3} ", process4.name, process4.startTime, process4.executeTime, process4.priority); Console.WriteLine("__________________________________________________________"); for (int i = currentStep; i < currentStep + busyTime; i++) { graph[i] = 4; name[i] = process4.name; } Queue4.Dequeue(); currentStep += busyTime; continue; } if (process3.startTime < currentStep && Queue3.Count > 0) { int busyTime = process3.executeTime; Console.WriteLine("имя процесса: {0} \t старт: {1}\t время работы: {2}\t приоритет: {3} ", process3.name, process3.startTime, process3.executeTime, process3.priority); Console.WriteLine("____________________________________________________"); for (int i = currentStep; i < currentStep + busyTime; i++) { graph[i] = 3; name[i] = process3.name; } Queue3.Dequeue(); currentStep += busyTime; continue; } if (process2.startTime < currentStep && Queue2.Count > 0) { int busyTime = process2.executeTime; Console.WriteLine("имя процесса: {0} \t старт: {1}\t время работы: {2}\t приоритет: {3} ", process2.name, process2.startTime, process2.executeTime, process2.priority); Console.WriteLine("_____________________________________________________________"); for (int i = currentStep; i < currentStep + busyTime; i++) { graph[i] = 2; name[i] = process2.name; } Queue2.Dequeue(); currentStep += busyTime; continue; } if (process1.startTime < currentStep && Queue1.Count > 0) { int busyTime = process1.executeTime; Console.WriteLine("имя процесса: {0} \t старт: {1}\t время работы: {2}\t приоритет: {3} ", process1.name, process1.startTime, process1.executeTime, process1.priority); Console.WriteLine("___________________________________________________________"); for (int i = currentStep; i < currentStep + busyTime; i++) { graph[i] = 1; name[i] = process1.name; } Queue1.Dequeue(); currentStep += busyTime; continue; } } Console.WriteLine(); string graphik = ""; //переменная в которою собираем процессы, для результата for (int current = 0; current < graph.Length; current++) { if (graph[current] == 1) { graphik += name[current]; } if (graph[current] == 2) { graphik += name[current]; } if (graph[current] == 3) { graphik += name[current]; } if (graph[current] == 4) { graphik += name[current]; } } Console.WriteLine("\n"); Console.WriteLine("\t\t\tРезультат работы процессов: "); Console.WriteLine(); Console.WriteLine(" \t\t\t{" + graphik + "}"); Console.ReadKey(); } } }

2.4Результаты работы программы

Пример №1:

Пример №2. Одинаковые приоритеты:

Пример №3:

Список используемой литературы

1.#"justify">2.Камерон Хьюз. «Параллельное и распределенное программирование»

3.Рудольф Марек. Ассемблер

4.Таненбаум Э. Современные операционные системы. Изд-е 4. СПб.: Питер, 2010

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