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


 

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

54323. МЕТОД ПРОЕКТІВ ЯК ТЕХНОЛОГІЯ НАВЧАННЯ 257.5 KB
  Метод проектів це метод в основі якого лежить розвиток пізнавальних творчих навичок студентів умінь самостійно конструювати свої знання орієнтуватися в інформаційному просторі критично мислити. Мета застосування методу полягає у формуванні навичок ефективного використання різних джерел інформації при навчанні студентів за допомогою інноваційних педагогічних технологій якими передбачається самостійна індивідуальна чи групова дослідницькопошукова та творча діяльність студентів підвищення рівня комунікабельності. Завдання методу...
54324. З’єднання болтом і шпилькою 496 KB
  Оформлення завдання Завдання виконується на креслярському папері в олівці у відповідність з правилами ЕСКД. Креслення повинне мати основний напис. Діаметри крізних отворів
54325. МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ДО СТВОРЕННЯ НАВЧАЛЬНОГО ПРОЕКТУ 146.5 KB
  АНАТОМІЯ НАВЧАЛЬНОГО ПРОЕКТУ. Планування реалізації проекту. Методика управління для неосяжної кількості найрізноманітніших проектів має єдину структуру у якій можна виділити такі групи процесів: ініціації прийняття рішення щодо запуску проекту зазвичай завершується складанням і затвердженням уставу проекту із визначенням його мети терміну виконання критеріїв успіху призначенням та чітким окресленням повноважень керівника проекту; планування безперервне визначення кращих...
54326. Особливості використання кейс-методу при викладанні інженерної графік 704.5 KB
  Наявність головної умови використання кейс-методу при викладанні будь–якої дисципліни – наявність протиріч, на основі яких формуються і формулюються проблемні ситуації, задачі, практичні завдання для обговорення та знаходження оптимального розвязання учнями або студентами.
54327. Методичні рекомендації щодо формування комунікативно-мовленнєвих умінь в учнів початкових класів на уроках української мови в російськомовних класах 367.5 KB
  Діти що приходять у 1 клас особливо російськомовні мають обмежений словниковий запас для спілкування українською мовою. Наприклад: ТВАРИНИ Ведмідь медведь Лисиця лисица Вовк волк Заєць заяц Білка белка Їжак ежик Мавпа обезьяна Пташка птичка Жаба лягушка Ящірка ящерица Бобер бобёр Кажан летучая мышь Паралельно з цією карткою діти працюють з карткою з малюнками на якій намальовані ті предмети які були записані в картці словами. Скажіть діти кого із названих членів сім'ї ви вдома називаєте не так Пропоную з...
54328. Метод проектів як основа творчого розвитку особистості 170.5 KB
  Практична теоретична пізнавальна значимість передбачуваних результатів наприклад доповідь у відповідні служби про демографічний стан даного регіону фактори що впливають на цей стан тенденції що просліджуються в розвитку даної проблеми; спільний з партнером по проекту випуск газети альманаху з репортажами з місця подій; охорона лісу в різних місцевостях план заходів і т. Структурування змістовної частини проекту із указівкою поетапних результатів. Але незалежно від типу проекту всі вони в означеній мірі неповторні та унікальні;...
54329. Групування, формули, адресація, імена комірок, авто заповнення в Microsoft Excel (MICROSOFT OFFICE 2010) 429 KB
  Мета: Навчитися обєднувати дані за природними групами, користуватися документом, в якому є групування, створювати в комірках формули для обчислення нових даних, копіювати дані та формули, призначати імена коміркам, користуватися автозаповненням.
54330. ПРОЕКТНА ДІЯЛЬНІСТЬ НА УРОКАХ ІНФОРМАТИКИ 239.5 KB
  Це з одного боку сукупність прийомів операцій оволодіння певною областю практичного або теоретичного знання тієї чи іншої діяльності. Цей результат можна побачити осмислити застосувати в реальній практичній діяльності. Саме тому на уроках інформатики корисно вводити елементи проектної діяльності. Провідні принципи такої діяльності: Основні вимоги до проекту Необхідно наявність соціально значущої задачі проблеми дослідної інформаційної практичної.
54331. Застосування методу проектів на уроках світової літератури 797.5 KB
  У сучасній школі можна виділити чотири основні напрями при яких ефективно застосовувати методи проектів: 1 проект як метод навчання на уроці; 2 проектні технології дистанційного навчання; 3 для формування дослідницьких навичок школярів у позаурочній роботі;4 як метод організації дослідницької діяльності вчителів. Метод проектів знаходить все більше поширення у системі освіти різних країн світу. Із історії виникнення методу проектів Метод проектів не є принципово новим у світовій педагогіці. Метод проектів ефективна технологія навчання...