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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство общего и профессионального образования Российской Федерации

Пензенский государственный университет

Кафедра МО и ПЭВМ

Специальность 22.0400

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ

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

на тему:

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

ПГУ 3.220400.005 ПЗ

Автор работы Захарова Л.М.

Группа 99ВП1

Руководитель работы Шашков Б.Д.

Пенза 2002



РЕФЕРАТ

Пояснительная записка содержит 17 листов,1 рисунок, 3 таблицы, 2 приложения, библиографический список из 4 источников.

Программирование, программа, СИ, UNIX, межпроцессное взаимодействие, механизм сообщений, очередь сообщений

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

Данная программа, разработанная студенткой четвертого курса ПГУ группы 99ВП1 Захаровой Л.М., реализована для ОС Linux на языке С.

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



СОДЕРЖАНИЕ

• Введение
• 1. Анализ требований и постановка задачи
• 2. Проектирование
• 3. Кодирование
• 4. Тестирование
• Приложение А. Текст программы
• Приложение Б. Результаты тестирования
• Заключение


ВВЕДЕНИЕ

Поистине неисповедимы пути, которыми следует отечественная мода на операционные системы. Еще несколько лет назад в России активно развивались многозадачные и многопользовательские операционные системы, но вот, словно по мановению волшебной палочки их место, где оправдано, а где и не слишком, заняли MS-DOS и Windows. И хотя сегодня все возвращается на свои места, выясняется, что за эти годы мы потеряли слишком много - мы потеряли культуру многозадачных операционных систем, и поэтому найти сегодня специалиста по UNIX, пусть даже пользователя, несоизмеримо труднее, чем пользователя MS-DOS и Windows.

До недавнего времени вопрос о выборе операционной системы для персональных компьютеров вообще не ставился. Все пользователи находились в равных условиях - в среде MS-DOS. Но с развитием аппаратных средств и хроническим отставанием как DOS, так и Windows от уровня "железа", на сцену начали выходить Windows NT и OS/2. Но кроме этих, коммерческих систем, совершенно неожиданно начал получать популярность и один из клонов UNIX - Linux, разрабатываемый широкими (без преувеличения) кругами энтузиастов

Linux-это версия UNIX для процессоров 80386 и 80486. Linux в полной мере реализует все возможности процессоров, предоставляя программисту полностью 32-разрядную многозадачную и многопользовательскую систему, функционирующую в защищенном режиме. Система соответствует стандарту POSIX, что позволяет говорить о переносе программного обеспечения, разработанного для Linux, на другие версии UNIX и обратно как о более или менее рутинной задаче.

Подводя итоги, следует отметить, что Linux оказывается неожиданно мощной системой, которая разработана неорганизованной группой программистов-любителей. Идеи, положенные в его основу проверены временем. И если, наконец, будет завершен проект Wine, позволяющий запускать Windows-приложения в среде X/Window, Linux получит дополнительный козырь в борьбе с коммерческими операционными системами. Возможности этой системы открывают все новые и новые пользователи. И с эволюционным развитием всех трех систем наблюдается устойчивый рост количества пользователей Linux.



1. Анализ требований и постановка задачи

Межпроцессное взаимодействие (Interprocess communication, IPC)-это механизм, с помощью которого два и более процессов взаимодействуют между собой.

Эти процессы могут работать по схеме клиент/сервер (когда один или несколько процессов-клиентов посылают данные в центральный процесс-сервер) или по одноранговой схеме (когда любой процесс может обмениваться данными с другими процессами).

IPC поддерживают все UNIX-подобные системы, но в каждой из них этот механизм реализован по-своему.

IPC на основе сообщений позволяет нескольким процессам, выполняемым на одной UNIX-машине, взаимодействовать между собой путем передачи и приема сообщений. Метод, основанный на использовании сообщений, был предложен для того, чтобы устранить некоторые недостатки каналов (именованных и неименованных). Один из этих недостатков заключается в том, что к обеим точкам канала с целью чтения и записи данных может подключаться множество процессов, но механизма, который обеспечивал бы избирательную связь между читающим и записывающим процессами, нет. Другая проблема состоит в том, что для успешной передачи данных к обоим концам канала должны быть подсоединены процессы, иначе данные теряются. Таким образом, каналы и находящиеся в них данные являются нерезидентными объектами, и если процессы выполняются не одновременно, надежный обмен данными не обеспечивается.

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

Если в UNIX-системе существует несколько очередей, каждая из них может использоваться для организации межпроцессного взаимодействия сразу нескольких приложений.

На процедуру манипулирования сообщениями система устанавливает ряд ограничений, которые определяются в заголовочном файле <sys/msg.h>

Таблица 1

Системные ограничения

Системное ограничение	Значение
MSGMNI	Максимальное число очередей сообщений, которые могут существовать в системе в конкретный момент времени.
MSGMAX	Максимальное число байт данных в сообщении
MSGMNB	Максимальное число байт данных во всех сообщениях
MSGTQL	Максимальное число сообщений во всех очередях

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

Запись таблицы сообщений имеет тип данных struct msqid_ds.

Таблица 2

Поля структуры msqid_ds

Поле	Данные
msg_perm	Данные в записи типа struct ipc_perm
msg_first	Указатель на самое старое сообщение в очереди
msg_last	Указатель на самое последнее сообщение в очереди
msg_cbyte	Общее число байтов во всех сообщениях, находящихся в очереди на данный момент
msg_qnum	Общее число сообщений, находящихся в очереди на данный момент
msg_qbyte	Максимальное число байтов во всех сообщениях, которые могут находиться в очереди
msg_lspid	Pid процесса, который последним передал в очередь сообщение
msg_lrpid	Pid процесса, который последним прочитал из очереди сообщение
msg_stime	Время, когда в очередь было передано самое последнее сообщение
msg_rtime	Время, когда из очереди было прочитано самое последнее сообщение
msg_ctime	Время последнего изменения управляющих параметров очереди сообщений

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Структура struct msg определена в <sys/msg.h> следующим образом.

Таблица 3

Поля структуры msg

Поле	Данные
msg_type	Тип сообщения
msg_ts	Количество байтов в тексте сообщения
msg_spot	Указатель текст сообщения
msg_next	Указатель на следующее сообщение

2. Проектирование

Рассмотрим схему взаимодействия процессов:



Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1. Схема взаимодействия процессов

Генерация запросов осуществляется случайным образом. Длина очереди Q₃ ограничена и равна 30. В случае переполнения заявки теряются, P - поток потерянных заявок. Длины очередей Q₁ и Q₂ ограничены только системно. Обслуживание ведется в порядке поступления запросов. Время обслуживания случайно. Программа должна определять среднюю длину очереди. Взаимодействие между отдельными процессами реализовать с использованием механизма сообщений.

R - распределитель. R определяет длину очереди Q₃ и, если в ней меньше 30 заявок, то отправляет пришедшую заявку на процессор PR.

3. Кодирование

Кодирование осуществлено на языке С. Результат кодирования приведен в приложении А.

Был использован следующий тип данных:

typedef struct{

long m_type;

long Ttm;

long Qtm;

}Msg;

Где m_type - тип сообщения, Ttm - время генерации заявки, Qtm - время обработки заявки в PR.

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

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

При тестировании вначале осуществлялся запуск процессов - генераторов заявок, затем - процесса распределителя, и последним - процесс - обработчик заявок. Процессы - генераторы и процесс - распределитель запускались в фоновом режиме, а выходные данные процесс - обработчика перенаправлялись в файл Out. При нажатии сочетания клавиш <Ctrl + C> процесс - обработчик заканчивает работу, а остальные процессы продолжали работу в фоновом режиме. Для их завершения осуществлялся запуск скрипта *Zap2, который посылал им сигнал SIGTERM(при программной настройке процессов - генераторов и процесса распределителя как процессов - демонов их завершение происходило по сигналу SIGKILL).

При ином порядке запуска процессов ошибок не наблюдалось, программа работала также устойчиво. Это связано с тем, что сообщения удаляются из очереди только тогда, когда процессы обращаются к ним явно («выбирают» их) и не удаляются из очереди, даже если к ней не обращается ни один процесс.

межпроцессный программа сообщение очередь

Приложение А

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

Cr.h

#define P 0666

#define Max 80

#define MAX_LEN 30

#define KEY1 1

#define KEY2 2

#define KEY3 3

#define KEY4 4

#define TYPE1 123

#define TYPE2 124

#define TYPE3 125

#define TYPE4 126

typedef struct {

long m_type;

long Ttm;

long Qtm;

}Msg;

Msg mes, mes2;

int M;

int Za;

int message(int Key)

{

int Id;

Id = msgget(Key, IPC_CREAT|P);

if (Id == -1) printf("msgget\n");

return Id ;

}

int open_mq(Id)

{

if (Id >= 0) return 1;

else return 0;

}

int remove_mq(int Id)

{

int rc;

rc = msgctl(Id, IPC_RMID,0);

if (rc ==-1) perror("msgctl");

return rc;

}

int send_mes(int size, int type, int Id)

{

mes.m_type = type;

if ( msgsnd( Id, &mes, size, 0) )

{perror("msgsnd"); return -1;}

return 0;

}

int recive_mes(int size, int type, int Id)

{

int len;

len = msgrcv(Id, &mes, size, type, MSG_NOERROR);

if (len == -1) {perror("msgrcv"); return -1;}

return len;}

c1.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include "Cr.h"

int main()

{

int Length, Id, Id4, ex, Len;

int time = 35000;

int delta = 2000;

int tim;

struct msqid_ds mbuf;

Za = 0;

Id = message(KEY1);

Id4 = message(KEY4);

if ( !open_mq(Id) ) {printf("open_mq\n"); exit(1);};

while (Length = recive_mes(sizeof(mes), TYPE1, Id) > 0 )

{



tim = 2*delta + 1;

mes.Qtm = time - delta + rand()%tim;

Za+=1;

ex=0;

do {ex+=1;} while ( ex < mes.Qtm);

msgctl(Id, IPC_STAT, &mbuf);

printf("Za %d\n",Za);

printf("Generating time = %d\n",mes.Ttm);

printf("Processor time = %d\n",mes.Qtm,"\n");

mes.Qtm = mbuf.msg_qnum;

send_mes(sizeof(mes), TYPE4, Id4);

}//while

return 0;

}

c2.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include "Cr.h"

int main()

{

int Id1, Id2, Id3, i;

struct msqid_ds mbuf;

Id1 = message(KEY1);

Id2 = message(KEY2);

Id3 = message(KEY3);

if ( !open_mq(Id2)) {printf("open_mq2"); exit(1);}

if ( !open_mq(Id3) ) {printf("open_mq1"); exit(1);}

do{

msgctl(Id1, IPC_STAT, &mbuf);

recive_mes(sizeof(mes), TYPE2, Id2);

if ( mbuf.msg_qnum < MAX_LEN )

{ send_mes(sizeof(mes), TYPE1, Id1);}

msgctl(Id1, IPC_STAT, &mbuf);

recive_mes(sizeof(mes2), TYPE3, Id3);

if ( mbuf.msg_qnum < MAX_LEN )

{ send_mes(sizeof(mes2), TYPE1, Id1);}

}while(1);

return 0;

}

c3.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include "Cr.h"

int main()

{

int Id;

int j=0;

int time = 8000;

int delta = 2000;

int tim;

Id = message(KEY2);

do{

if ( !open_mq(Id) ) {printf("open_mq_c3"); exit(1);}

tim = 2*delta + 1;

mes.Ttm = time - delta + rand()%tim;

do{j+=1;}while(j <= mes.Ttm);

send_mes(sizeof(mes), TYPE2, Id);

}while(1);

return 0;

}

c4.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include "Cr.h"

int main()

{

int Id;

int j=0;

int time = 16000;

int delta = 2000;

int tim;

Id = message(KEY3);

do{

if ( !open_mq(Id) ) {printf("open_mq"); exit(1);}

tim = 2*delta + 1;

mes.Ttm = time - delta + rand()%tim;

do{j+=1;}while(j<=mes.Ttm);

send_mes(sizeof(mes),TYPE3,Id);

}while(1);

return 0;

}

c5.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include "Cr.h"

int main()

{

int Id, Id1, Id2, Id3, i;

struct msqid_ds mbuf;

long Nac = 0;

int Kol = 0;

long Sr;

Id = message(KEY1);

Id1 = message(KEY2);

Id2 = message(KEY3);

Id3 = message(KEY4);

msgctl(Id3, IPC_STAT, &mbuf);

i = mbuf.msg_qnum;

while ( i > 0)

{

recive_mes(sizeof(mes), TYPE4, Id3);

Nac += mes.Qtm;

Kol+=1;

i-=1;

}

Sr = Nac/Kol;

printf("\nQueue sr. length = %d\n",Sr);

remove_mq(Id);

remove_mq(Id1);

remove_mq(Id2);

remove_mq(Id3);

return 0;

}

Приложение Б. Результаты тестирования.

Za 1

Generating time = 8424

Processor time = 35424

Za 2

Generating time = 16424

Processor time = 36207

Za 3

Generating time = 9207

Processor time = 33459

Za 4

Generating time = 17207

Processor time = 33363

Za 5

.........................

Za 589

Generating time = 8638

Processor time = 34482

Za 590

Generating time = 16638

Processor time = 34140

Za 591

Generating time = 6066

Processor time = 34815

Za 592

Generating time = 14066

Processor time = 36229

Queue sr. length = 17

Заключение

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

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

В ходе решения задачи были разработаны схема взаимодействия процессов, структура сообщений, параметры и ограничения очередей. Было произведено кодирование на языке программирования С и функциональное тестирование, в ходе которого было выявлено, что программа решает задачу корректно и устойчиво работает на тестовом наборе данных.



Использованные источники

1. А. Богатырев. Си в UNIX. М. info@citmgu.ru Copyright © CIT.

2. В. Водолазкий. Путь к LINUX. Москва 1996

3. Б. Керниган, Д. Ритчи, А. Фьюер. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985.

4. Т. Чан. С++ для UNIX. Спб.: bhv, 1996

Размещено на Allbest.ru