регулирование движения поездов на станции, VC++ 2008 EE Опции

[18192123]

Здраствуйте!
У меня вот такая тема для разработки -
"Регулирование движения поездов на станции (Система массового обслуживания, потоки)"...
Т.е. можно сказать, что процессорное время (ресурс) - наша станция, тогда потоки - поезда.. и нужно распланировать использование этого ресурса...Но это всё общие фразы..
Объясните пожалуйста, как это должно выглядеть более конкретно..я пока не очень понимаю..

[18192123]

Может быть у кого-нибудь есть идеи, как это эту тему оформить в виде приложения...С чего вообще начать? Подскажите пожалуйста! Плохо себе представляю, как это должно выгдядеть в моём приложении, в этом и проблема...

[volvo]

Смотри... Я когда-то делал на форуме эмуляцию работы банка: есть клиенты пользователи, есть кассиры, очередь клиентов, и когда подходит очередь, клиент направляется к освободившемуся кассиру...

Можно сделать нечто подобное и здесь: есть "поезд", есть "путь", на который этот поезд можно поставить, и держать его там какое-то определенное время, и отправлять дальше; если свободных путей нет - то все поезда проходят мимо. Все действия (время прибытия поезда, время отправления) фиксируются в логе, возможно - сделать еще и визуализацию (скажем, какой-нибудь ListBox, в котором будет храниться информация о путях: "свободен"/"занят, кем занят, и когда освободится")...

При таком подходе можно потоками представлять пути, а "поезда" - сделать просто структуру, хранящую ID, число вагонов (это если тебе захочется помучиться, и сделать более приближенную к реальности программу: на путь можно поставить поезд только, если длина поезда не превышает длины пути), время стоянки. Можно и поезда реализовать потоками, хотя я бы этого не делал, смысла не вижу в этом, основное "действующее лицо" в твоей программе - это все-таки Станция, и соответственно, Путь. Поезд - это так, проходящее

Через рандомные промежутки времени генерируешь "поезд", пробегаешься по "путям" в поисках свободного и способного принять этот поезд, и направляешь поезд на подходящий путь...

Только непонятно, что делать, если подходящих путей нет? Что, просто пропускать поезд на следующую станцию, пусть с ним там разбираются?

Или тебе нужно нечто совсем другое?

[18192123]

Мне убедительно посоветовали выбрать несколько иной подход:
есть станция, для неё предусмотрено n-е количество мест для стоянки проходящих поездов (для определённости - 3 места, например, для реализации этой идеи использовать семафор с максимальным количеством ресурсов=3).
Если все места заняты - поезд (это будет поток) должен ожидать освобождения места для стоянки (т.е. поезд на время ожидания засыпает). Главная цель - не пропустить поезд на станцию, если там нет свободных мест.
Для поезда, который занял своё место на станции - его время простоя должно определяться по закону (экспоненциальному наверное - с тем смыслом, что чем дольше поезд простоял, тем выше вероятность, что скоро он отправится дальше и освободит место стоянки)
Потоки-поезда должны генерироваться по з-ну Пуассона.
Выходные данные: думаю представить статистику по простоям и по ожиданию освобождения места..

Пока не представляю себе, как должна выглядеть генерация потока-поезда по Пуассону..
тоже самое с временем простоя на станции...не знаю, как поезда-поток "заставить" остаться там на некоторое время (тоже определяемое по закону)..

Пока решила начать с того, что по рандому создавать поезда-потоки, в функции потока в зависимости от состояния семафора записывать на listbox идентификатор поезд и его состояние..Вот только выводятся поезда как попало...Даже не знаю, в чём причина может быть..
А вообще хочу представить движение-остановку поездов-потоков в виде передвижения-застывания label с каким-нибудь текстом..

DWORD TrainThread(int *p)
{
	wsprintf(buf,L"Train #%d...",*p);
	SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);

    // Проверяем состояние семафора
    DWORD dwResult = WaitForSingleObject(hSemaphore, 10000);
	DWORD time_stopping;
    switch(dwResult) {
        case WAIT_OBJECT_0:
            // Место есть, остановка
			wsprintf(buf,L"Train #%d is stoping...",*p);
			SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);
            time_stopping = (rand() % 3000) + 1000; // Время стоянки
            Sleep(time_stopping);
            ReleaseSemaphore(hSemaphore, 1, NULL); // Освободим семафор
            break;
            
        case WAIT_TIMEOUT:
            // Семафор занят, ожидаем ...
			wsprintf(buf,L"Train #%d: no empty places...waiting",*p);
			SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);            
			break;
    }
    return 0;
}

void OnClickButRun(HWND hwnd)
{
    // генератор случ. чисел
    srand(time(NULL));
    if(hSemaphore = CreateSemaphore(NULL, maxPlaces, maxPlaces, NULL)) {
        for(int i = 0; i < maxTrains; i++) {
            trainID[i] = i+1;
            trainHandles[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)TrainThread,
                &trainID[i], 0, NULL);
        }
        
        CloseHandle(hSemaphore);
    }
    else SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)TEXT("Error by creation semaphore"));
}

[volvo]

Вот только выводятся поезда как попало

Не то ты делаешь Тебе не надо ждать 10 секунд... Понимаешь, там, откуда ты взяла эту реализацию, задача другая стояла: там было "нет места - проезжай", у тебя "нет места - жди", поэтому ты должна после неудачной попытки не завершать поток, а повторить попытку проверки семафора:

DWORD TrainThread(int *p)
{
	wsprintf(buf,L"Train #%d...",*p);
	SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);

	int finished = 0;
	do {
		// Проверяем состояние семафора
		DWORD dwResult = WaitForSingleObject(hSemaphore, 1000); // !!! ждем 1 секунду
		DWORD time_stopping;
		switch(dwResult) {
	        case WAIT_OBJECT_0:
			// Место есть, остановка
			wsprintf(buf,L"Train #%d is stoping...",*p);
			SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);
			time_stopping = (rand() % 3000) + 1000; // Время стоянки
			Sleep(time_stopping);
			ReleaseSemaphore(hSemaphore, 1, NULL); // Освободим семафор
			finished = 1;
			break;
            
		case WAIT_TIMEOUT:
			// Семафор занят, сообщаем об этом, и повторяем попытку ...
			wsprintf(buf, L"Train #%d: no empty places...waiting",*p);
			SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);            
			break;
		}
	} while(!finished);
	return 0;
}

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

	WaitForMultipleObjects(maxTrains, trainHandles, TRUE, INFINITE); // дождаться всех
	CloseHandle(hSemaphore); // и только теперь удалить семафор

Вот что выдало мне:

Train #3...
Train #5...
Train #7...
Train #4...
Train #2...
Train #1...
Train #6...
Train #3 is stoping...
Train #8...
Train #9...
Train #5 is stoping...
Train #10...
Train #7 is stoping...
Train #4: no empty places...waiting
Train #2: no empty places...waiting
Train #1: no empty places...waiting
Train #6: no empty places...waiting
Train #8: no empty places...waiting
Train #10: no empty places...waiting
Train #9: no empty places...waiting
Train #4 is stoping...
Train #2 is stoping...
Train #1 is stoping...
Train #8: no empty places...waiting
Train #6: no empty places...waiting
Train #10: no empty places...waiting
Train #9: no empty places...waiting
Train #8 is stoping...
Train #6 is stoping...
Train #10 is stoping...
Train #9: no empty places...waiting
Train #9 is stoping...

[18192123]

Эх...а у меня не работает..приложение зависает..
изменила функцию потока..добавила ожидание завершения потоков..

void OnClickButRun(HWND hwnd)
{
    // генератор случ. чисел
    srand(time(NULL));
    if(hSemaphore = CreateSemaphore(NULL, maxPlaces, maxPlaces, NULL)) {
        for(int i = 0; i < maxTrains; i++) {
            trainID[i] = i+1;
            trainHandles[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)TrainThread,
                &trainID[i], 0, NULL);

        }
        WaitForMultipleObjects(maxTrains, trainHandles, TRUE, INFINITE); // дождаться всех
        CloseHandle(hSemaphore);
    }
    else SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)TEXT("Error by creation semaphore"));
}

и теперь мы просто висим...В чём же может быть дело?(

[volvo]

В чём же может быть дело?(

В том, что я проверяю в консольном приложении, там нет необходимости в синхронизации, а ты - в оконном, а в оконном надо обрабатывать сообщения.

В качестве "костыля" могу предложить использовать:

		int b = 1;
		do {
			// DWORD r = ; // дождаться всех
			switch(WaitForMultipleObjects(maxTrains, trainHandles, TRUE, 100)) {
				case WAIT_TIMEOUT:
					// Здесь добавить аналог Application->ProcessMessages() чтоб обновить окно;
					break;
				default:
					b = 0;
			}
		} while(b);

		CloseHandle(hSemaphore);

вместо

	WaitForMultipleObjects(maxTrains, trainHandles, TRUE, INFINITE); // дождаться всех
	CloseHandle(hSemaphore);

Кстати, случайными значения, генерируемые по rand() у тебя тоже не будут. Будет постоянно генерироваться одно и то же число. Чтобы это были действительно случайные числа, надо вызывать srand() не в основном потоке, а в каждом дочернем:

DWORD TrainThread(int *p)
{
    __int64 gTime;
    QueryPerformanceCounter((LARGE_INTEGER *)&gTime);
    srand(gTime);
    // дальше функция потока

[18192123]

...
				case WAIT_TIMEOUT:
					// Здесь добавить аналог Application->ProcessMessages() чтоб обновить окно;
					break;
.....

а что за Application->ProcessMessages()? и что за аналог?..Объясните пожалуйста..!

[volvo]

Тебе нужно заставить форму обработать полученные сообщения и элементарно перерисоваться, иначе ты ж ничего не увидишь... В Билдеровском VCL для этого используется метод Application->ProcessMessages(). Для чистого WinAPI, скорее всего, подойдет вот это:

				case WAIT_TIMEOUT:
					// Application->ProcessMessages();
					MSG lpMsg;
					while (PeekMessage(&lpMsg, NULL, 0, 0, PM_REMOVE)) {
						TranslateMessage(&lpMsg);
						DispatchMessage(&lpMsg);
					}
					break;

[18192123]

Спасибо большое!!
Теперь насчёт генерации потоков-поездов по Пуассоновскому з-ну..
Объясните пожалуйста, как это должно выглядеть..?? Я даже не представляю..Может потоки будут генерироваться по таймеру через промежутки времени, которые определяются в соответствии с з. Пуассона? или я не в том направлении думаю?

[volvo]

Может потоки будут генерироваться по таймеру через промежутки времени, которые определяются в соответствии с з. Пуассона?

Скорее всего так оно и должно быть... Как моделировать распределение Пуассона, знаешь?

[18192123]

Скорее всего так оно и должно быть... Как моделировать распределение Пуассона, знаешь?

Нет...Даже не представляю..

[volvo]

Вот тут лежит

вариант программной функции, осуществляющей моделирование распределения Пуассона с параметром λ

... Последовательные вызовы этой функции с одним и тем же параметром будут выдавать последовательность целых чисел, распределенных по Пуассону. Хотя программа на Паскале, я думаю перенести 10 строк кода не будет проблемой?

[18192123]

Вот тут лежит ... Последовательные вызовы этой функции с одним и тем же параметром будут выдавать последовательность целых чисел, распределенных по Пуассону. Хотя программа на Паскале, я думаю перенести 10 строк кода не будет проблемой?

спасибо, с этим разберусь.
ну вот сгенерировала я первый поток-поезд...потом с помощью этой функции получаю число, которое и буду рассматривать, как промежуток времени, через который нужно сгенерировать следующий поезд-поток? скажите, я правильно понимаю?

[volvo]

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

[18192123]

Что-то я явно не так делаю...у меня функция Puass() всегда возвращает единицу...:

int Puass(float Lamda)
{
	float ver,p0,P;
	int k;
	k=0;
	p0=exp(-Lamda);
	P=p0;
	__int64 gTime;
       QueryPerformanceCounter((LARGE_INTEGER *)&gTime);
       srand(gTime);
	ver=rand();
	do
	{
		ver=ver-P;
		if (ver >= 0) 
		{
			P=P*Lamda/(k+1);
			k++;
		}
	}
	while (ver<0);
	return k;
}

И ещё добавила SetTimer..Правда очень сомневаюсь в правильности его применения..
Думаю не всё так просто с применением таймера в моём случае..Объясните пожалуйста, как будет верно..:

if(hSemaphore = CreateSemaphore(NULL, maxPlaces, maxPlaces, NULL)) {
        for(int i = 0; i < maxTrains; i++) {
            trainID[i] = i+1;
	    SetTimer(hwnd,MY_TIMER,Puass(20000),NULL);
            trainHandles[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)TrainThread,
                &trainID[i], 0, NULL);

        }

Сообщение отредактировано: 18192123 - 15.12.2008 18:08

[volvo]

Что-то я явно не так делаю

Угу... Во-первых, зачем тебе понадобилось инициализировать ГСЧ внутри Puass? После этого даже если саму функцию Puass написать правильно - будут глюки, ГСЧ не должен инициализироваться в одном потоке больше одного раза.

Кроме всего прочего, функция Puass переведена неправильно, ты забыла, что в Repeat/Until условие - обратное, не такое, как в While. Цикл Repeat/Until выполняется, пока условие ложно. Как только оно станет истинным - цикл немедленно завершается. А ты заменила паскалевский Repeat/Intil Сишным while-ом с тем же условием, вот тебе и результат: после первой же итерации цикл завершается, при этом K = 1, что ты и наблюдала

Таймер тебе вообще не нужен. Все проще:

int Puass(double Lamda)
{
	int k = 0;
	double p0 = exp(-Lamda);
	double P = p0;
	
	// Генерируем вещественное число в интервале 0 .. 1
	double ver = (double)rand() / RAND_MAX;
	do {
		ver -= P;
		if(ver >= 0) {
			P = P*Lamda / (k+1);
			k += 1;
		}
	} while(ver >= 0);
	return k;
}

// А вот так будет выглядеть цикл генерации потоков:
	// генератор случ. чисел, основной поток приложения
	srand(time(NULL));
	if(hSemaphore = CreateSemaphore(NULL, maxPlaces, maxPlaces, NULL)) {
		for(int i = 0; i < maxTrains; i++) {
			DWORD timeWait = Puass(9.5) * 10; // <--- Ну, коэффициенты сама подберешь

			wsprintf(buf, "Ждем %ld ms перед генерацией следующего потока-поезда", timeWait);
			SendMessage(hListBox, LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);

			// Ожидание, но все запущенные ранее потоки уже работают,
			// на них Sleep не распространяется
			Sleep(timeWait); 

			trainID[i] = i+1;
			trainHandles[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)TrainThread,
				&trainID[i], 0, NULL);

		}

Сообщение отредактировано: volvo - 15.12.2008 18:52

[18192123]

здравствуйте!
скажите пожалуйста, а как сгенерировать время простоя поезда на станции по экспоненциальному з-ну?
т.е. вот здесь:

DWORD TrainThread(int *p)
{
	__int64 gTime;
    QueryPerformanceCounter((LARGE_INTEGER *)&gTime);
    srand(gTime);

	wsprintf(buf,L"Train #%d...",*p);
	SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);

	int finished = 0;
	do {
		// Проверяем состояние семафора
		DWORD dwResult = WaitForSingleObject(hSemaphore, 1000); // !!! ждем 1 секунду
		DWORD time_stopping;
		switch(dwResult) {
	        case WAIT_OBJECT_0:
			// Место есть, остановка
			wsprintf(buf,L"Train #%d is stoping...",*p);
			SendMessage(hListBox,LB_ADDSTRING, 0, (LPARAM)(LPCSTR)buf);
			time_stopping = (rand() % 3000) + 1000; // !!!Время стоянки  - нужно определить по эксп. з-ну
			Sleep(time_stopping);
			ReleaseSemaphore(hSemaphore, 1, NULL); // Освободим семафор
			finished = 1;
			break;
....

[volvo]

а как сгенерировать время простоя поезда на станции по экспоненциальному з-ну?

Внимательно читать, что написано в предыдущем посте, я же уже ответил на этот вопрос:

			DWORD timeWait = Puass(9.5) * 10; // <--- Ну, коэффициенты сама подберешь

[18192123]

оу..прошу прощения..как-то упустила, что з-н Пуассона вполне экспоненциальный

Добавлено через 19 мин.
Хотелось бы теперь движение-остановку поездов-потоков представить графически...
Примерно так: поезд-поток (например в виде Label) подъехал к станции, есть места - переходит на свободное место стоянки (постоял некоторое время - уехал со станции), нет мест - ждёт перед станцией.
Подскажите пожалуйста, как соотнести задумку с уже имеющимся?