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

 

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

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

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

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

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

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

на тему:

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

ПГУ 3.220400.005 ПЗ

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

Группа 99ВП1

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

Пенза 2002

РЕФЕРАТ

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

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

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

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

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

СОДЕРЖАНИЕ

Введение

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

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

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

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

Приложение А. Текст программы

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

Заключение

ВВЕДЕНИЕ

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

До недавнего времени вопрос о выборе операционной системы для персональных компьютеров вообще не ставился. Все пользователи находились в равных условиях - в среде MS-DOS. Но с развитием аппаратных средств и хроническим отставанием как DOS, так и Windows от уровня "железа", на сцену начали выходить Windows NT и OS/2. Но кроме этих, коммерческих систем, совершенно неожиданно начал получать популярность и один из клонов UNIX - 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_permmsg_firstУказатель на самое старое сообщение в очередиmsg_lastУказатель на самое последнее сообщение в очередиmsg_cbyteОбщее число байтов во всех сообщениях, находящихся в очереди на данный моментmsg_qnumОбщее число сообщений, находящихся в очереди на данный моментmsg_qbyteМаксимальное число байтов во всех сообщениях, которые могут находиться в очередиmsg_lspidPid процесса, который последним передал в очередь сообщениеmsg_lrpidPid процесса, который последним прочитал из очереди сообщениеmsg_stimeВремя, когда в очередь было передано самое последнее сообщениеmsg_rtimeВремя, когда из очереди было прочитано самое последнее сообщениеmsg_ctimeВремя последнего изменения управляющих параметров очереди сообщений

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

Таблица 3

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

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

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

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

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

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

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

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

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

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

typedef struct{m_type;Ttm;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

struct {m_type;Ttm;Qtm;

}Msg;

mes, mes2;M;Za;

message(int Key)

{Id;= msgget(Key, IPC_CREAT|P);(Id == -1) printf("msgget\n");Id ;

}

open_mq(Id)

{(Id >= 0) return 1;return 0;

}

remove_mq(int Id)

{rc;= msgctl(Id, IPC_RMID,0);(rc ==-1) perror("msgctl");rc;

}

send_mes(int size, int type, int Id)

{.m_type = type;( msgsnd( Id, &mes, size, 0) )

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

}

recive_mes(int size, int type, int Id)

{len;= msgrcv(Id, &mes, size, type, MSG_NOERROR);(len == -1) {perror("msgrcv"); return -1;}len;}.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"

main()

{Length, Id, Id4, ex, Len;time = 35000;delta = 2000;tim;

msqid_ds mbuf;

= 0;= message(KEY1);= message(KEY4);

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

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

{

tim = 2*delta + 1;.Qtm = time - delta + rand()%tim;+=1;=0;

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

(Id, IPC_STAT, &mbuf);

("Za %d\n",Za);("Generating time = %d\n",mes.Ttm);("Processor time = %d\n",mes.Qtm,"\n");

.Qtm = mbuf.msg_qnum;_mes(sizeof(mes), TYPE4, Id4);

}//while

0;

}.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"

main()

{Id1, Id2, Id3, i;msqid_ds mbuf;

= message(KEY1);= message(KEY2);= message(KEY3);

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

{(Id1, IPC_STAT, &mbuf);

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

( mbuf.msg_qnum < MAX_LEN )

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

(Id1, IPC_STAT, &mbuf);

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

( mbuf.msg_qnum < MAX_LEN )

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

}while(1);0;

}.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"

main()

{Id;j=0;time = 8000;delta = 2000;tim;

= message(KEY2);

{

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

= 2*delta + 1;.Ttm = time - delta + rand()%tim;

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

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

}while(1);0;

}.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"

main()

{Id;j=0;time = 16000;delta = 2000;tim;

= message(KEY3);

{

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

= 2*delta + 1;.Ttm = time - delta + rand()%tim;

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

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

}while(1);0;

}.c

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include "Cr.h"

main()

{Id, Id1, Id2, Id3, i;msqid_ds mbuf;Nac = 0;Kol = 0;Sr;

= message(KEY1);= message(KEY2);= message(KEY3);= message(KEY4);

(Id3, IPC_STAT, &mbuf);= mbuf.msg_qnum;( i > 0)

{_mes(sizeof(mes), TYPE4, Id3);+= mes.Qtm;+=1;=1;

}= Nac/Kol;("\nQueue sr. length = %d\n",Sr);_mq(Id);_mq(Id1);_mq(Id2);_mq(Id3);

return 0;

}

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

Za 1time = 8424time = 354242time = 16424time = 362073time = 9207time = 334594time = 17207time = 333635

.........................589time = 8638time = 34482590time = 16638time = 34140591time = 6066time = 34815592time = 14066time = 36229 sr. length = 17

Заключение

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

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

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

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

1.А. Богатырев. Си в UNIX. М. [email protected] Copyright © CIT <#"justify">3.Б. Керниган, Д. Ритчи, А. Фьюер. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 1985.

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

Министерство общего и профессионального образования Российской Федерации Пензенский государственный университет Кафедра МО и ПЭВМ Специальность 22.0400

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