50149

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

Контрольная

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

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

Русский

2014-03-25

68.5 KB

13 чел.

Оглавление:

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


 

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

85690. Анализ финансового состояния «ООО Дракон» 1.19 MB
  Бухгалтерский баланс является важнейшим источником информации о финансовом положении предприятия на отчетную дату. Он позволяет определить состав и структуру имущества предприятия ликвидность и оборачиваемость оборотных активов. Наличие собственного капитала и текущих обязательств, состояние и динамику...
85691. ПРОЕКТИРОВАНИЕ РАЙОННОЙ ЭЛЕКТРИЧЕСКОЙ СЕТИ 220/110 КВ 2.67 MB
  В нормальных режимах работы ЭП первой категории должны обеспечиваться электрической энергией от двух независимых взаимно резервирующих источников питания. Перерыв в электроснабжении ЭП первой категории может быть допущен лишь на время автоматического восстановления питания.
85692. Психологічні аспекти депресивного стану 217.5 KB
  Депресія – це стан зниженого, пригніченого настрою зі спаданням психічної активності, песимізмом, апатією, своєрідними уявленнями, загальмуванням дій. Така проблема, як депресія в наш час стає дедалі актуальнішою. Ця хвороба є поширеною особливо серед підлітків, враховуючи ще сам по собі тяжкий...
85693. Що означає бути людиною? В. Сухомлинський «Який слід повинна залишити людина на землі?» 55 KB
  Мета: Познайомити з твором В.Сухомлинського; вчити давати характеристику головним дійовим особам; порівнювати вчинки і поведінку персонажів; робити висновки щодо прочитаного; розвивати зв’язне мовлення, вміння цінувати думки товаришів; виховувати доброту.
85694. «Осінь така мила…» за методикою В.Сухомлинського «Уроки під небом голубим» 84.5 KB
  Повторити й узагальнити знання учнів про осінь та її відображення в художніх творах; удосконалювати вміння виразного читання напамять віршів; розвивати кмітливість творчі здібності учнів емоційно-образне сприйняття природи; виховувати взаємоповагу в стосунках із ровесниками та дорослими любов до рідної...
85695. УРОК РАДОСТІ. УРОК ПОЗАКЛАСНОГО ЧИТАННЯ 79 KB
  Формування ключових компетентностей, які сприяють досягненню успіхів у житті, а саме: демонструвати творче мислення; застосувати різни види спілкування в різних ситуаціях; довести здатність пристосування до різних ситуацій; розвивати здібності дослідження та набувати власний досвід...
85696. Коляда. Урок українського читання 52 KB
  Мета: Ознайомити дітей з історичними довідками про святкування свята Різдво-Коляда. Навчити виразному читанню колядок і щедрівок. Розвивати мовленнєві навички. Виховувати культуру мовлення, повагу до історичних традицій українського народу.
85697. Урок внеклассного чтения по методике критического мышления В. А. Сухомлинский «Стыдно перед соловушкой» 93 KB
  Задачи: учить детей строить текст по опорным словам и словосочетаниям, продолжить работу над нарушенной последовательностью, развивать речь, мышление, умение ставить вопросы к тексту, пересказывать прочитанное, характеризовать героев, воспитывать бережное отношение к природе.
85698. В. Сухомлинський «Який слід повинна залишити людина на Землі» 66.5 KB
  Сприяти усвідомленню учнями того факту що життя людини є найвищою цінністю для будьякої країни; розширювати і актуалізувати знання дітей про чинники які мають великий вплив на життя кожної людини піклування держави про життя згідно з Конституцією України; вчити учнів піклуватися про своє життя...