50149

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

Контрольная

Информатика, кибернетика и программирование

Разработать для операционной системы Linux многопоточную программную имитацию работы маршрутного такси между конечными и одной промежуточной остановками. Фиксированое число N потенциальных пассажиров случайный интервал времени пребывают где-то вне маршрута, затем появляются случайным образом на одной из остановок.

Русский

2014-03-25

68.5 KB

12 чел.

Оглавление:

1.   Задание

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

2.1   Описание используемых функций и структур

  1.    Основные принципы работы приложения

3.   Заключение

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


1.   Задание

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

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

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


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

#include <pthread.h>

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

//_________________________________________________________________

int n;

int st1_p,st2_p,st3_p;

const int STATE_QUAL=3;

int COME_TO_STAT_TIME;

pthread_t tid;

pthread_mutex_t sema;

int razvez;

int global_time;

//------------------------------------------------------------------------

typedef struct _pass//пассажар

{

int id;

int be_stat; //begin station

int fin_stat;//finish station

int time;

} pass;

//0-------0-------------------------------------------------------------

_Bool taxi_work;

//-------------------------------------------------------------------------

typedef struct _queue//динамическая структура - очередь (на остановке)

{

pass man;

struct _queue* next;

} queue;

//------------------------------------------------------------------------

queue* home;

queue* st_home;

queue* any_man_from_home;

queue* queue1; //очередь №1 и указатель на конец очереди

queue* queue2; //очередь №2

queue* queue3; //очередь №3

queue* queue1_f;//указатель на первый элемент, первой очереди

queue* queue2_f;// -#-                         второй

queue* queue3_f;// -#-                         третьей

//-----------------------------------------------------------------------

int randomize(int n,int i) //процедура возвращяет псевдо-случайное число

{

double j;

int ret;

srand(i*n);

j=(double)rand()/(double)RAND_MAX;

j*=n;

ret=(int)j+1;

return ret;

}

//-------------------------------------------------------------------------

queue* add_to_end(queue* kucha,pass man)

//процедура добавляет в очередь элемент и возвращяет указатель на конец очереди

{

queue* p;

kucha->man=man;

p=malloc(sizeof(queue));

kucha->next=p;

kucha=kucha->next;

kucha->next=NULL;

kucha->man.id=0;

return kucha;

}

//--------------------------------------------------------------------------

pass get_first(queue* st)//получить значение первого элемента очереди

{

pass man;

man=st->man;

return man;

}

//--------------------------------------------------------------------------

queue* delet_first(queue* st)//удалить первый элемент очереди

{

queue* st_next;

st_next=st->next;

free(st);

return st_next;

}

//--------------------------------------------------------------------------

_Bool not_null(pass cab[5])//1-not null; 0-null

{

int i=0,k=0;

for(i=0;i<5;i++)

{

if(cab[i].id==0)

k++;

}

if(k==5)

return 0;

return 1;

}

//--------------------------------------------------------------------------

_Bool logik()

{_Bool logik_in=0;

logik_in=(queue1_f->man.id==0)&&(queue2_f->man.id==0)&&(queue3_f->man.id==0);

return logik_in;

}

//------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------

void forward(int i)//такси едет вперед

{

printf("\033[1;19H                                                                         ");

int j;

int posX=20;

if (i!=1)

{

posX=20*i;

 j=posX-20;

for(j;j<=posX;j=j+5)

 {

printf("\033[1;19H                                                                         ");

usleep(200000);

printf("\033[1;%dH[Taxi]\n",j);

 }

}

else

printf("\033[1;%dH[Taxi]\n",posX);

}

void back(int i)//такси едет назад

{

printf("\033[1;19H                                                                         ");

int j;

int posX=(i==2)?40:20;

if(i!=3)

{

 j=posX+20;

for(j;j>=posX;j=j-5)

 {

printf("\033[1;19H                                                                         ");

usleep(200000);

printf("\033[1;%dH[Taxi]\n",j);

 }

}

}

int taxi_inside(int space,_Bool id)

{

space+=2;

if(id!=0)

{

printf("\033[1;%dHI",space);

}

else

{

printf("\033[1;%dH-",space);

}

usleep(350000);

return 0;

}

//--------------------------------------------------------------------------

void pass_come_to_stat(int stat,int kol)

{int i;

stat=stat*20;

for(i=1;i<10;i++)

{

printf("\033[%d;%dH ",i+2,stat);

}

for (i=1;i<=kol;i++)

 {

printf("\033[%d;%dHI",i+2,stat);

}

usleep(350000);

}

//----------------------------ТАКСИ----------------------------------------------

void taxi_proc(void* arg)

{

pass cab[5]={0,0,0,0,0};

int stat_num=1;

int space;

int wait_time;

taxi_work=1;

forward(1);

do

{

pthread_mutex_lock(&sema);

for (stat_num=1;stat_num<=3;stat_num++)//едем "вперед"

{forward(stat_num);

 //printf("такси прибыло на %d остановку\n",stat_num);

 sleep(1);

 wait_time=0;

// высаживаем пассажиров

 for(space=0;space<5;space++)

 {

 if ((cab[space].fin_stat==stat_num)&&(cab[space].id!=0))

  {

  //printf("высадили пасажира № %d на остановке %d\n",cab[space].id,stat_num);

  cab[space].id=0;

  taxi_inside(space,0);

  }

 }

//посадка пассажиров, если никого нет  то ждем опр. время

if(stat_num==1)

{

 while(wait_time<2)

 {

  sleep(1);

  wait_time++;

  if(queue1_f->man.id!=0)

    {

  for(space=0;space<5;space++)

  {

   if((cab[space].id==0)&&(queue1_f->man.id!=0))

   {

   cab[space]=get_first(queue1_f);

   queue1_f=delet_first(queue1_f);

 st1_p=st1_p-1;

  // printf("пасажир № %d сел в такси на %d остановке\n",cab[space].id,stat_num);

pass_come_to_stat(1,st1_p);

  taxi_inside(space,1);

   }    }        }   }  }

if(stat_num==2)

{

 while(wait_time<2)

 {

  sleep(1);

  wait_time++;

  if(queue2_f->man.id!=0)

    {

  for(space=0;space<5;space++)

  {

   if((cab[space].id==0)&&(queue2_f->man.id!=0))

   {

   cab[space]=get_first(queue2_f);

   queue2_f=delet_first(queue2_f);

 st2_p=st2_p-1;

  // printf("пасажир № %d сел в такси на %d остановке\n",cab[space].id,stat_num);

pass_come_to_stat(2,st2_p);

  taxi_inside(space,1);

   }    }        }   }  }

if(stat_num==3)

{

 while(wait_time<2)

 {

  sleep(1);

  wait_time++;

  if(queue3_f->man.id!=0)

    {

  for(space=0;space<5;space++)

  {

   if((cab[space].id==0)&&(queue3_f->man.id!=0))

   {

   cab[space]=get_first(queue3_f);

   queue3_f=delet_first(queue3_f);

 st3_p=st3_p-1;

  // printf("пасажир № %d сел в такси на %d остановке\n",cab[space].id,stat_num);

pass_come_to_stat(3,st3_p);

  taxi_inside(space,1);

   }    }        }   }  }

}//for (stat_num;stat_num<=3;stat_num++)

usleep(200000);

if((logik())&&(!not_null(cab))&&(global_time==COME_TO_STAT_TIME))

{

printf("\033[8;1HTaxi over\n");

break;

}

// высаживаем пассажиров

back(2);

 for(space=0;space<5;space++)

 {

 if ((cab[space].fin_stat==2)&&(cab[space].id!=0))

  {

  cab[space].id=0;

  taxi_inside(space,0);

  }   }

 sleep(1);

 wait_time=0;

while(wait_time<2)

 {

  sleep(1);

  wait_time++;

  if(queue2_f->man.id!=0)

    {

  for(space=0;space<5;space++)

  {

   if((cab[space].id==0)&&(queue2_f->man.id!=0))

   {

   cab[space]=get_first(queue2_f);

   queue2_f=delet_first(queue2_f);

 st2_p=st2_p-1;

   pass_come_to_stat(2,st2_p);

  taxi_inside(space,1);

   }    }        }   }

back(1);

pthread_mutex_unlock(&sema);

usleep(200000);

}

while(((!logik())||(not_null(cab) )||((st1_p!=0)&&(st2_p!=0)&&(st3_p!=0)))&&(global_time<=COME_TO_STAT_TIME));

taxi_work=0;

printf("\033[10;1HTaxi time work is over\n");

printf("\033[10;1H%d",global_time);

assert(0);

sleep(2);

}

//-------------------------------ГЛАВНАЯ----------------------------------------

int main ()

{

int i,j,id,k;

st1_p=st2_p=st3_p=0;

int passag=0;

queue* p;

home=malloc(sizeof(queue));

queue1=malloc(sizeof(queue));

queue2=malloc(sizeof(queue));

queue3=malloc(sizeof(queue));

st_home=home;

global_time=0;

system("clear");

printf("Введите число пасажиров N (<40)");

scanf("%i",&n);

system("clear");

printf("\033[1;1H[-----]");

if(n<=10)

{COME_TO_STAT_TIME=n+5;}

else

if(n<20)

{COME_TO_STAT_TIME=n+10;}

else

if(n<40)

{COME_TO_STAT_TIME=n;}

if (n>40)

{return 0;}

for (i=0;i<n;i++)//появление пассажиров вне остановок

{

home->man.id=i+1;

k=0;

do

{

home->man.be_stat=randomize(STATE_QUAL,i+k);

home->man.fin_stat=randomize(STATE_QUAL,i*home->man.be_stat);

k++;

}

while (home->man.be_stat==home->man.fin_stat);

home->man.time=randomize(COME_TO_STAT_TIME,i*home->man.fin_stat);

home=add_to_end(home,home->man);

}  

queue1_f=queue1;

queue2_f=queue2;

queue3_f=queue3;

id=pthread_create(&tid,NULL,(void*)taxi_proc,(void*)0);

pthread_mutex_init(&sema,NULL);

for (i=1;i<=COME_TO_STAT_TIME;i++)

//люди появляются на остановках по прошествию определеного времени

{

sleep(1);

pthread_mutex_lock(&sema);

any_man_from_home=st_home;

  while(any_man_from_home!=0)

//ЛЮДИ ВЫСТРАИВАЮТСЯ В ОЧЕРЕДЬ НА ОСТАНОВКАХ

{

if (any_man_from_home->man.time==i)

  {

if (any_man_from_home->man.be_stat==1)

 {

 queue1=add_to_end(queue1,any_man_from_home->man);

 st1_p=st1_p+1;

passag+=1;

pass_come_to_stat(1,st1_p);

printf("\033[19;1Hна 1 остановку пришел пассажир № %d  \n",any_man_from_home->man.id);

 }

else

if (any_man_from_home->man.be_stat==2)

 {

 queue2=add_to_end(queue2,any_man_from_home->man);

 st2_p=st2_p+1;

passag+=1;

pass_come_to_stat(2,st2_p);

printf("\033[19;1Hна 2 остановку пришел пассажир № %d  \n",any_man_from_home->man.id);

 }

else

if (any_man_from_home->man.be_stat==3)

 {

 queue3=add_to_end(queue3,any_man_from_home->man);

 st3_p=st3_p+1;

passag+=1;

pass_come_to_stat(3,st3_p);

printf("\033[19;1Hна 3 остановку пришел пассажир № %d  \n",any_man_from_home->man.id);

 }

  }

any_man_from_home=any_man_from_home->next;

}

pthread_mutex_unlock(&sema);

usleep(50000);

global_time=i;

if (passag==n)

break;

}

while(taxi_work)

{

pthread_mutex_lock(&sema);

printf("\033[6;1HTaxi Work");

sleep(2);

pthread_mutex_unlock(&sema);

}

printf("\033[6;1HTaxi NOT  Work\n\033[20;1H");

return 0;

}


  1.  Описание используемых функций и структур

struct _pass структура задает свойства объекта «пассажир» который обладает уникальным номером, отправной и конечной точкой а также временем появления на остановке.

struct _queue описание динамической очереди.

int randomize(int n,int i) функция возвращает число от 0 до n, i-некий случайный параметр позволяющий генерировать случайное число(необходимо его динамическое изменение для получение нового значения отличного от предыдущего, т.к.  процедура построена на стандартных функциях языка C: rand() и srand() )

queue* add_to_end(queue* kucha,pass man) функция возвращает указатель на конец очереди, в качестве параметров kucha- указатель в котором хранится текущее значение конца очереди, man- данные добавляемые в очередь.

pass get_first(queue* st) возвращяется значение первого в очереди пасажира.

queue* delet_first(queue* st) удаление первого пассажира в очереди с последующим освобождением памяти.

_Bool not_null(pass cab[5]) анализирует состояние такси (наличие или отсутствие в нем пассажиров)  в случае наличия выдает 1 , отсутствия 0.

void forward(int i) отрисовка движения такси «вперед» (void back(int i)-назад)

int taxi_inside(int space,_Bool id) отображение внутреннего состояния такси

void pass_come_to_stat(int stat,int kol)  прибытие пассажира на остановку

void taxi_proc(void* arg) процедура иммитирующая работу такси

а также были применены стандартные процедуры и функции Linux для организации многопоточности:

pthread_create(pthread_t *tid,const pthread_attr_t* att,void* (*fun),void* argp)

где tid- идентификатор созданой нити

att- атрибут позволяет указать возвращять или нет идентификатор нити

*fun- адрес создаваемой нити

argp- параметры передаваемые в только что созданую нить

pthread_mutex_init(&sema,NULL)

создание нового семафора

pthread_mutex_lock(&sema)/pthread_mutex_unlock(&sema) блокировка/разблокировка семафора, т.е. Если нить заблокировала семафор (объявила право на его использование) то иная нить использующая этот же семафор не сможет ничего сделать пока не произойдет разблокировка.


  1.  Основные принципы работы приложения

При проектировании  маршрутного такси были приняты во внимание следующие процессы и состояния в его работе:

-  движение маршрутное такси начинает строго с первой конечной остановки.

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

в начале у пользователя запрашивается число пассажиров N, относительно этого числа вычисляется время в течении которого пассажиры появляются на остановках (оно хранится в переменной COME_TO_STAT_TIME).

Главная нить программы (процедура int main()) создает пассажиров, каждый из которых «знает» когда и где появится и место высадки. Изначально все пассажиры пребывают вне остановок в «Доме» (очередь home). Запускается паралельно основной нити нить отвечающая за работу такси(taxi_proc).После этого начинается процесс появления пассажиров на остановках. За еденицу времени была взята секунда и каждую секунду, до тех пор пока не выйдет время, пассажиры будут появлятся на остановках. При условии, что появление пассажира связано с его внутренним понятием о том когда нада выйти из Дома.  В процессе появления пассажиров было допущено следующее упрощение: такси ожидает еденицу времени после чего продолжает свою работу. Это связано с тем, что такси как и main() работают с одними и теми же динамическими структурами и во избежание одновременного обращения двух различных операций к одной области памяти был введен семафор.

В начале своей работы taxi_proc создает массив cab на пять элементов для хранения в нем данных о пассажирах направляющихся по своим делам.  Такси движется от остановки до остановки до тех пор пока не будет выполнено следующее условие:

(((!logik())||(not_null(cab) )||((st1_p!=0)&&(st2_p!=0)

&&(st3_p!=0)))&&(global_time<=COME_TO_STAT_TIME))

оно имеет следующий смысл:

пока очереди на остановках не будет пассажиров(!logik()) или  пока такси не развезет всех пассажиров успевших сесть в него(ot_null(cab)) и до тех пор пока не не пройдет установленое время работы такси((global_time<=COME_TO_STAT_TIME) оно по сути своей равно времени в течении которого пассажиры появляются на остановках), такси будет продолжать свое движение .(st1_p!=0)&&(st2_p!=0)&&(st3_p!=0) данные три условия необходимы для отслеживания посадки и высадки пассажиров (т.е. Когда пассажир сел в такси счетчик уменьшается, когда появился на остановке счетчик увеличивается, ри правлиной работе все три значения в конечном итоге должны быть равны 0). При движении такси по маршруту производятся следующие действия:

высадка пассажиров, т.е. Такси прибыло на остановку кому необходимо те вышли,

посадка пассажиров в такси, в течении некоторого промежутка времени такси ожидает, в это время если есть на остановке клиенты и место в такси свободно происходит запись в массив cab и извлечении, с последующим освобождение памяти, из очереди на остановке ( queue2_f, queue1_f, queue3_f). в момент посадки\высадки клиентов запускается процедура отрисовки состояния такси (наличие свободных и занятых мест). После того как такси отбыло от остановки происходит запуск процедуры отрисовки движения и т.к. Остановки расположены на некотором растоянии друг от друга происходи задержка в его работе.


3.   Заключение

В результате  данной работы мною были изучены основы работы с многопоточными приложениями, в часности по их созданию и синхронизации работы нескольких нитей. А также стандартные процедуры Linux по форматированию текста выводимого на экран, использованию семафоров. Также были повышены навыки в программировании на языке C. Не маловажным является освоение операционной системы Linux занимающей не последнее место среди сегоднишних ОС.


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

Флоренсов, А.Н. Операционные системы для программиста : учеб. Пособие / А.Н. Флоренсов. - ОмГТУ, 2005. -240 с. -УДК 004.4(075)

Шилдт, Герберт. Справочник программиста по C/C++ : справочник / Г. Шилдт. - 3-е изд. - М. : «И. Д. Вильямс»,2006.- 432с. - ББК 32.973.26-018.2.75


 

А также другие работы, которые могут Вас заинтересовать

12535. ОБНАРУЖЕНИЕ ИМПУЛЬСНЫХ СИГНАЛОВ В ШУМЕ 70.61 KB
  Лабораторная работа №16 ОБНАРУЖЕНИЕ ИМПУЛЬСНЫХ СИГНАЛОВ В ШУМЕ Цель работы Изучение принципа порогового обнаружения двоичных сигналов механизма возникновения ошибок обнаружения метода анализа и оптимизации процесса обнаружения. Экспериментальное
12536. Процессы протекающие в оптимальном фильтре детерминированных сигналов. Оптимальная линейная фильтрация детерминированных сигналов 1023 KB
  Оптимальная линейная фильтрация детерминированных сигналов Цель работы: эксперементальное исследование процессов протекающих в оптимальном фильтре детерминированных сигналов; закрепление теоретически
12537. Создание логотипа в CorelDRAW 3.19 MB
  Лабораторная работа №1 по CorelDRAW Создание логотипа Цель лабораторной работы В процессе выполнения этой лабораторной работы вы получите практические навыки по созданию и редактированию векторных изображений. При этом вы научитесь: Рисовать...
12538. СОЗДАНИЕ РИСОВАННОЙ ИЛЛЮСТРАЦИИ РУСАЛОЧКА 1.57 MB
  ЛАБОРАТОРНАЯ РАБОТА № СОЗДАНИЕ РИСОВАННОЙ ИЛЛЮСТРАЦИИ РУСАЛОЧКА Перейдя непосредственно к созданию картинки прежде всего прорисуем лицо русалки. Для этого используем панель инструментов Corel Draw позволяющую рисовать стандартные фигуры круг прямоугольник много
12539. Кодирование данных в телекоммуникационных сетях 24.26 KB
  Домашнее задание №1 Кодирование данных в телекоммуникационных сетях 1. ВВЕДЕНИЕ1 2. ЭТАПЫ РАБОТЫ1 2.1. Формирование сообщения1 2.2. Физическое кодирование исходного сообщения2 2.3. Логическое избыточное кодирование исходного сообщения2 2.4. Скремблирование и...
12540. Методы цифрового кодирования в телекоммуникационных сетях 149.78 KB
  Сети ЭВМ и средства телекоммуникаций Методы цифрового кодирования в телекоммуникационных сетях 1. Аналоговая модуляция1 2. Спектр модулированного сигнала1 3. Цифровое кодирование2 3.1. Требования к методам цифрового кодирования2 3.2. Потенциальный код без в
12541. Работа с программными средствами Internet. Утилиты ping и traceroute 22.64 KB
  ЛАБОРАТОРНАЯ РАБОТА Работа с программными средствами Internet. Утилиты ping и traceroute 1. ЦЕЛЬ РАБОТЫ Исследование вероятностновременных характеристик сети с использованием утилиты ping исследование топологии фрагментов Internet с использованием утилиты traceroute. 2. ЗАДАНИЕ Н
12542. Работа с операционной системой Linux. Утилита netstat 23.83 KB
  ЛАБОРАТОРНАЯ РАБОТА Работа с операционной системой Linux. Утилита netstat 1. ЦЕЛЬ РАБОТЫ С помощью утилиты netstat исследовать состояние локальной IPсети. 2. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ 2.1. С помощью утилиты netstat получить список соединений открытых на сервере pds.sut.ru.
12543. РАБОТА С СЕТЕВЫМИ УТИЛИТАМИ И ПРОТОКОЛАМИ ПРИКЛАДНОГО УРОВНЯ 276.5 KB
  Работа с сетевыми утилитами и протоколами прикладного уровня Цель работы: освоить приемы работы с сервисными сетевыми утилитами прикладного уровня изучить команды основных утилит получить представление о методах работы с ними под управлением различных операционных ...