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


 

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

66419. Виховання патріотизму в учнів середніх шкіл США 169 KB
  Тому ставлення до виховання патріотизму в молодого покоління у сучасній українській школі повинно докорінно змінитися. Вдосконаленню і збагаченню вітчизняних традицій патріотичного виховання в школі може слугувати аналогічний зарубіжний досвід зокрема Сполучених Штатів Америки країни де цьому питанню завжди приділялася належна увага.
66420. РОЗВИТОК ПІДПРИЄМСТВ ОРГАНІЧНОГО СЕКТОРУ АГРОБІЗНЕСУ В КОНТЕКСТІ ВИКЛИКІВ ГЛОБАЛІЗАЦІЇ ТА ЄВРОІНТЕГРАЦІЇ 211.5 KB
  В контексті викликів глобалізації та євроінтеграції не повинна стати винятком і Україна тим більше що є всі передумови для ефективного функціонування підприємств органічного сектору. Теоретичні основи й узагальнення практичного досвіду розвитку...
66421. МЕХАНІЗМ РЕГУЛЮВАННЯ РИНКУ ФІНАНСОВИХ ПОСЛУГ УКРАЇНИ 979 KB
  На сучасному етапі розвитку економіки України ринок фінансових послуг знаходиться лише на стадії свого формування у зв’язку з чим виникає потреба в адекватному механізмі регулювання що є необхідною передумовою ефективного функціонування цього ринку.
66422. ТОВАРОЗНАВЧА ХАРАКТЕРИСТИКА РЕДИСКИ ЗАЛЕЖНО ВІД СОРТУ ТА УМОВ ЗБЕРІГАННЯ 231 KB
  В літку якісні коренеплоди ізза біологічних особливостей редиски виростити неможливо. Проблемами зберігання редиски в різні часи займалися такі науковці як П. Дженєєв 1968 але залишилось багато невирішених питань щодо збереженості...
66423. ПОДАТКИ НА СПОЖИВАННЯ В УКРАЇНІ: ОРГАНІЗАЦІЯ СПРАВЛЯННЯ ТА ФІСКАЛЬНІ НАСЛІДКИ ФУНКЦІОНУВАННЯ 306 KB
  Фіскальна історія свідчить що оподаткування споживання давно практикується державами. Поряд з цим саме представники групи податків на споживання універсальні акцизи відіграли роль рятівників бюджетів провідних держав світу в умовах гіперінфляції під час двох Світових воєн та низки економічних криз.
66424. Клініко-патогенетичні особливості перебігу ревматоїдного артриту за наявності ендотеліальної та субклінічної гіпотиреоїдної дисфункції 214 KB
  Не дивлячись на дуже часте співіснування цих нозологічних одиниць клінічна діагностика уражень ЩЗ у хворих на РА достатньо складна особливо у випадках м’якої клінічної маніфестації. У хворих із ревматичними захворюваннями ЕД відіграє не менш важливу роль у розвитку та прогресуванні...
66425. Виховання соціальної усталеності особистості старшокласника в навчально-виховному процесі 211 KB
  У Законі Про соціальне становлення та розвиток молоді в Україні Національній доктрині Державній національній програмі Діти України Національній концепції виховання актуалізується проблема виховання особистості здатної на активну роль...
66426. СТАНОВЛЕННЯ ТА РОЗВИТОК БДЖІЛЬНИЦТВА В УКРАЇНІ 372.5 KB
  Сучасна наука акцентує увагу до проблеми власного самопізнання, розглядаючи її як своєрідний ключ для розв’язання багатьох актуальних дослідницьких проблем. Реалізація потенціалу сільськогосподарської науки, її завдань та цілей, місця в загальній системі знань про закономірності...
66427. ЕФЕКТИВНІСТЬ ВИКОРИСТАННЯ ВИРОБНИЧОГО ПОТЕНЦІАЛУ ПІДПРИЄМСТВ ПЕРЕРОБНОЇ ПРОМИСЛОВОСТІ СИСТЕМИ АПК 269 KB
  Ефективність діяльності переробних підприємств в умовах ринкової конкуренції залежить в основному від якості формування та рівня використання виробничого потенціалу. Розвиток економіки регіону на довгострокову перспективу пов’язаний саме з цими...