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


 

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

16609. Создание библиотеки элементов пакета Orcad 13.93 KB
  Лабораторная работа 2. Создание библиотеки элементов. Цель работы: научиться создавать библиотеку собственных схемных элементов с помощью программы LIBEDIT на примере создания резистора конденсатора диода транзистора. Порядок выполнения работы: 1. Запустить на
16610. Редактирование стандартных библиотечных элементов пакета Orcad 12.39 KB
  Лабораторная работа 3. Редактирование стандартных библиотечных элементов. Цель работы: получение навыков редактирования готовых элементов библиотек импортирование элемента из библиотеки изменение элементов библиотеки экспортирование элементов в собственн
16611. Работа с макрокомандами пакета Orcad 12.96 KB
  Лабораторная работа 4. Работа с макрокомандами. Цель работы: получение навыков работы с макросами макрокомандами. Использование встроенных макросов создание вызов сохранение собственных макрокоманд. Порядок выполнения работы: 1. Запустить на выполнение прогр
16612. Изучение команды LIBRARY программы PCB пакета Orcad 14.36 KB
  Лабораторная работа 5. Изучение команды LIBRARY программы PCB. Цель работы: изучить назначение возможности и основные команды пункта меню Library программы PCB пакета ORCAD. Порядок выполнения работы: 1. Запустить на выполнение программу pcb.exe находящуюся в подкаталоге EXE катал...
16613. Разработка корпусов схемных элементов пакета Orcad 12.88 KB
  Лабораторная работа 6. Разработка корпусов схемных элементов. Цель работы: получение навыков создания корпусов элементов принципиальных схем средствами программы PCB разработанных ранее с помощью программы LIBEDIT. Порядок выполнения работы: 1. Запустить на выполнени
16614. Модификация корпусов схемных элементов пакета Orcad 11.79 KB
  Лабораторная работа 7. Модификация корпусов схемных элементов. Цель работы: получение навыков редактирования готовых корпусов элементов схем при помощи программы PCB. Порядок выполнения задания: 1. Запустить на выполнение программу PCB. 2. Выбрать в основном меню пу
16615. АНАЛИЗ И ОПТИМИЗАЦИЯ СТОИМОСТИ ПРОЕКТА В MICROSOFT PROJECT 369.5 KB
  АНАЛИЗ И ОПТИМИЗАЦИЯ СТОИМОСТИ ПРОЕКТА В MICROSOFT PROJECT Методические указания к лабораторной работе по дисциплинам Проектирование информационных систем Территориальные информационные системы Цель работы: получение навыков анализа стоимости про
16616. ПЛАНИРОВАНИЕ ПРОЕКТОВ В MICROSOFT PROJECT 426.5 KB
  ПЛАНИРОВАНИЕ ПРОЕКТОВ Методические указания к лабораторной работе по дисциплинам Проектирование информационных систем Территориальные информационные системы Цель работы: подготовка к составлению проектов в MS Project изучение терминологии управления прое
16617. ПЛАНИРОВАНИЕ РЕСУРСОВ И СОЗДАНИЕ НАЗНАЧЕНИЙ В MICROSOFT PROJECT 646.5 KB
  ПЛАНИРОВАНИЕ РЕСУРСОВ И СОЗДАНИЕ НАЗНАЧЕНИЙ Методические указания к лабораторной работе по дисциплинам Проектирование информационных систем Территориальные информационные системы Цель работы: изучение принципов работы с ресурсами и особенностей план