کد برنامه مسابقه خرگوش و لاک پشت
فارسی english

یکی از داستان‌هایی که همگی در بچگی شنیدیم داستان مسابقه خرگوش و لاک پشته. خرگوش، لاک پشت رو به مبارزه دعوا می‌کنه، اول ازش جلو می‌زنه، بعد که خیالش از نرسیدن لاک پشت راحت می‌شه می‌گیره می‌خوابه. لاک پشت ازش جلو می‌زنه و برنده مسابقه می‌شه.

از اونجایی که ما همیشه داستان این مسابقه رو شنیدیم ولی اون رو ندیدیم wink، می‌خواهیم یک برنامه بنویسیم که این مسابقه رو برامون شبیه سازی کنه ...

One of the Stories all of us has heard in our childhood is the race between Tortoise and the Hare. The Hare challenges the Tortoise, first Hare outgoes Tortoise, then thinking that tortoise never will reach him, hare sleeps, then tortoise wins the game.

As we always have just heard about this race's story and never seen itwink, we want to write a program that virtualises this race for us ...
به ادامه مطلب مراجعه کنید continue to this link

 

حالا می‌خواهیم کد این برنامه رو تو C پیاده کنیم اما برای هر شرکت کننده، باید ماهیتی جدا داشته باشیم. به عبارت دیگه به جای اینکه برنامه ما به عنوان ناظر و بیننده مسابقه عمل کنه می‌خواهیم هر کدوم از شرکت کننده‌ها رو به صورت بازیگران پردازشی کد نویسی کنیم. در این صورت، باید یک روش ارتباطی بین این دو شیء پردازشی نیز داشته باشیم تا از موقعیت یکدیگر خبر داشته باشند.

برای این کار دو روش وجود داره:

  • پیاده سازی با process
  • پیاده سازی با thread

هر مدوم مزایا و سختی‌های خاص خودش رو داره. ما اینجا روی process کار می‌کنیم چون thread یک مقدار پیچیدگی بیشتری داره چون به سمافور نیاز داره تا همزمانی بین نخ‌ها رو رعایت کنه.

اول بهتره یه نگاهی به متغیر‌های عمومی داشته باشیم:

Now we want to start coding this program in C but the goal is that each player have a separate identity. In other word, instead of making the program as an observer for the race we want to have both players as processing enabled objects. This way there should be a communication way between two objects to know each-other's position (at least Hare needs to know about Tortoise).

To do this, there are two ways:

  • Implementation using "Process"
  • Implementation using "Threads"

Each one has its own advantages and difficulties. Here we'll work on processes as the threads has a little bit more complexity needing semaphores for synchronization.

First, lets have a look at general variables:

 
int length=30; //the length of the race
int Hare_speed=4; //clear I think; isn't it laugh
int tortoise_speed=1; // clear
long time_interval=200000; //the speed of the screen's refresh to see what's going on

گفتم متغیر و نه ثابت، چون می‌خواهیم کاری کنیم که کاربر همه این موارد رو بتونه بعدا تغییر بده.

اینجوری:

I called them variables and not constants because we want to make the user able to change them all later.

Something like this:

 
if(argc>1)
	length=atoi(argv[1]);
if(argc>2)
	time_interval=atoi(argv[2])*100000;
if(argc>4)
{
	Hare_speed=atoi(argv[3]);
	tortoise_speed=atoi(argv[4]);
}

خوب به نکته چالشی این الگوریتم می‌رسیم، اینکه چقدر خرگوش باید بخوابه؟ قرار بر این شد که خرگوش خودش فکر کنه، بنابر این اگر ثابت در نظر بگیریم بی‌معنی می‌شه در ضمن شروع خواب رو هم خود خرگوش انتخاب می‌کنه یعنی وقتی خیالش از لاک پشت راحت شد.

من نتونستم یک فرمول دقیق پیدا کنم که هم منطقی باشه و هم همیشه لاک پشت رو برنده کنه.

اصلا اینجوری هیجانش هم بیشتره که کدوم می‌بره cheeky

Now we reach to a challenging point. How much should Hare sleep? We decided to let it think for himself, so if we take a constant amount for it, it'll be meaningless also the start of sleep depends on the Hare itself, when he is sure that Tortoise is far enough.

I couldn't find a precise algorithm that is both logical and always make the Tortoise win.

This way it's a little bit more exciting to see which'll win cheeky

 
const int Hare_sleep=(Hare_speed+tortoise_speed)*2;

تو این نوع پیاده سازی فقط خرگوش دوست داره بدونه لاک پشت کجاست و برای لاک پشت مهم نیست حریفش کجاست.

برای اینکه خرگوش لاک پشت رو ببینه که کجاست یعنی بین پردازش‌های لاک پشت و خرگوش ارتباط برقرار کنیم از "لوله" استفاده می‌کنیم که یک راهکار ارتباط میان پردازشی است به صورت FIFO عمل می‌کنه.

هرچند مزیت لوله در اینه که تا زمانی که وقتی می‌خواد یک پردازش در وضعیت خواندن داده از لوله است، تا زمانی که لوله داده‌ای برای خوندن نداشته باشه، پردازش در همون وضعیت باقی می‌مونه، عیبش هم تو همینه یعنی اگر برنامه نویس درست از لوله‌ها استفاده نکنه ممکنه منجر به بن بست در پردازش‌ها برسه.

In this implementation just the Hare needs to know where is the Tortoise and it's not important for the Tortoise where the Hare is.

To avail Hare to see where the Tortoise is or to make a connection between two processes here we use "Pipe" which is a inter-process communication solution that works in a FIFO manner.

Also the advantage of Pipe is that when a process is in reading state until the pipe is empty of data, the process will wait, but the disadvantage of this method is this fact, too. It means that if the programmer doesn't use this method correctly it will end in "Deadlock".

 
int fd[2];
pipe(fd);

حالا پردازش‌ها رو می‌سازیم

امیدواریم با دستور fork و اینکه چه می‌کنه کاملا آشنا باشید.

Now we create the processes

I hope you know what exactly "fork" does

 
int Hare=getpid();
	
pid_t child=fork();

int pid=(int)getpid();
حالا پردازش خرگوش:

Now Hare's Process:

 
if(pid==Hare)
{
	while(1)
	{
		//read opponent's position from pipe
		close(fd[1]);
		read(fd[0],&oponent_pos,sizeof(oponent_pos));
		
		//if opponent has reached the end line stop useless progress and show ressults
		if(oponent_pos>=length||curr_pos>=length)
		{
			show_players(curr_pos,oponent_pos);
			getch();
			endwin();
			break;
		}
		
		//if not in sleep mode
		if(sleep_remaining<=0)
		{
			//if tortoise is too far, lets sleep for a while
			if(curr_pos-oponent_pos>Hare_speed-tortoise_speed)
				sleep_remaining=Hare_sleep;
			else
				progress(&curr_pos,Hare_speed);
		}
		else
			sleep_remaining--;
		
		//show the results up to now
		show_players(curr_pos,oponent_pos);
	}
}
حالا پردازش لاک پشت:

Now Tortoise's Process:

 
else{
	while(1)
	{
		progress(&curr_pos,tortoise_speed);
		
		//tell the Hare your position if it's this much important for him
		close(fd[0]);
		write(fd[1],&curr_pos,sizeof(curr_pos));
	}
}
و حالا کد پیشروی بازیگران:

And now players' progress:

 
void progress(int *curr_pos,int speed)
{
    if(*curr_pos+speed<length)
        *curr_pos+=speed;
    else
        *curr_pos=length;
}

برای نمایش نتایج از کتابخانه ncurses استفاده کرده‌ام، ابتدا مسیر مسابقه را رسم می‌کنیم:

To show the results I've used "Ncurses" library. First, let's draw the race's path:

 
void draw_race_path()
{
	int i=0;
	
	clear();

	printw("path length=%dkm (contest length=%dkm),Hare's speed=0.%dkm/h and Tortoise's speed=0.%dkm/h",length/2,length,Hare_speed,tortoise_speed);

	for(i=0;i<20+length/2;i++)mvprintw(2,i,"=");

	mvprintw(3,0,"    Hare||");

	for(i=0;i<20+length/2;i++)mvprintw(4,i,"=");

	mvprintw(5,0,"Tortoise||");

	for(i=0;i<20+length/2;i++)mvprintw(6,i,"=");printw("\n");

	refresh();
}

دور زدن درخت را که یادتان هست؟ آن را هم در نظر گرفته‌ام تا نصف مسیر را بروند و بعد برگردند به نقطه شروع. پس کد نمایش مسابقه دهندگان در مسیر مسابقه چنین خواهد بود:

You remember that players should go to a tree then turn and get back to the start position. Don't you? So I've put it into practice too. So the "show_players" function should be like this:

 
void show_players(int Hare, int tortoise)
{
	static int lastpose_hare=0;
	static int lastpose_tortoise=0;
	
	//players' position regard the tree
	int Hare_pos=(Hare>(length/2))?length-Hare:Hare;
	int tortoise_pos=(tortoise>(length/2))?length-tortoise:tortoise;
	
	//there should be a stop period between two steps, our eyes aren't that much fast
	usleep(time_interval);
	
	mvaddch(3,lastpose_hare+10,' ');
	mvprintw(3,Hare_pos+10,"+");
	mvprintw(3,length/2+11,"||  %d.%dkm",Hare/10,Hare%10);
	
	mvaddch(5,lastpose_tortoise+10,' ');
	mvprintw(5,tortoise_pos+10,"+");
	mvprintw(5,length/2+11,"||  %d.%dkm",tortoise/10,tortoise%10);
	
	lastpose_hare=Hare_pos;
	lastpose_tortoise=tortoise_pos;
	
	if(Hare>=length&&tortoise>=length)
	    mvprintw(8,0,"Withdaraw!!! Intresting. Isn't it?");
	else if(Hare>=length)
	    mvprintw(8,0,"Well! Not a fair game, you know! Of course Hare is much faster than tortoise!\n");
	else if(tortoise>=length)
	    mvprintw(8,0,"WOW!!! Can't Believe it! tortoise WON!\n");
	
	refresh();
}

خروجی یه چیزی شبیه اینه:

the output would be something like this:

 
path length=15km (contest length=30km),Hare's speed=0.4km/h and Tortoise's speed=0.1km/h
===================================
    Hare||    +           ||  0.4km
===================================
Tortoise|| +              ||  0.1km
===================================

و برای کامپایل از دستور زیر استفاده میشه:

and to compile, use this code:

 
//change current directory in terminal to the one that contains your code
gcc code.c -o tvh.o -lcurses
//code.c is your file's name

و برای اجرا از دستور زیر استفاده میشه:

and to run, use this code:

 
./tvh.o

یا:

Or:

 
./tvh.o 40 2 5 2
//40 stands for length of the path, 2 for 0.2 seconds between each output, 5 for Hare and 2 for Tortoise speed

توجه:

استفاده از کد این برنامه برای کارهای علمی و دانشگاهی بلامانع است اما باز نشر آن (حتی پس از تغییرات اندک) برای استفاده دیگران بدون قید منبع و لینک به این بلاگ شرعا حرام و غیر قانونی است.

Caution:

This code is usable for scientific and academic uses but reuse of this code in other websites or blogs without mentioning its initial source (even if it's changed to some extend) and withought linking to this blog, is amoral and illegal and so prohibited.

 
// Hare vs tortoise

#include <stdio.h>
#include <unistd.h>
#include <ncurses.h>

int length=30;
int Hare_speed=4;
int tortoise_speed=1;
long time_interval=200000;

void progress(int *curr_pos,int speed)
{
	if(*curr_pos+speed<length)
		*curr_pos+=speed;
	else
		*curr_pos=length;
}

void draw_race_path()
{
	int i=0;
	
	clear();

	printw("path length=%dkm (contest length=%dkm),Hare's speed=0.%dkm/h and Tortoise's speed=0.%dkm/h",length/2,length,Hare_speed,tortoise_speed);

	for(i=0;i<20+length/2;i++)mvprintw(2,i,"=");

	mvprintw(3,0,"    Hare||");

	for(i=0;i<20+length/2;i++)mvprintw(4,i,"=");

	mvprintw(5,0,"Tortoise||");

	for(i=0;i<20+length/2;i++)mvprintw(6,i,"=");printw("\n");

	refresh();
}

void show_players(int Hare, int tortoise)
{
	static int lastpose_hare=0;
	static int lastpose_tortoise=0;
	
	//players' position regard the tree
	int Hare_pos=(Hare>(length/2))?length-Hare:Hare;
	int tortoise_pos=(tortoise>(length/2))?length-tortoise:tortoise;
	
	//there should be a stop period between two steps, our eyes aren't that much fast
	usleep(time_interval);
	
	mvaddch(3,lastpose_hare+10,' ');
	mvprintw(3,Hare_pos+10,"+");
	mvprintw(3,length/2+11,"||  %d.%dkm",Hare/10,Hare%10);
	
	mvaddch(5,lastpose_tortoise+10,' ');
	mvprintw(5,tortoise_pos+10,"+");
	mvprintw(5,length/2+11,"||  %d.%dkm",tortoise/10,tortoise%10);
	
	lastpose_hare=Hare_pos;
	lastpose_tortoise=tortoise_pos;
	
	if(Hare>=length&&tortoise>=length)
	    mvprintw(8,0,"Withdaraw!!! Intresting. Isn't it?");
	else if(Hare>=length)
	    mvprintw(8,0,"Well! Not a fair game, you know! Of course Hare is much faster than tortoise!\n");
	else if(tortoise>=length)
	    mvprintw(8,0,"WOW!!! Can't Believe it! tortoise WON!\n");
	
	refresh();
}

int main(int argc, char *argv[])
{ 
	if(argc>1)
		length=atoi(argv[1]);
	if(argc>2)
		time_interval=atoi(argv[2])*100000;
	if(argc>4)
	{
		Hare_speed=atoi(argv[3]);
		tortoise_speed=atoi(argv[4]);
	}
	
	initscr();
		
	draw_race_path();
	
	int curr_pos=0;
	
	const int Hare_sleep=(Hare_speed+tortoise_speed)*2;
	
	int fd[2];
	pipe(fd);

	int Hare=getpid();
		
	pid_t child=fork();
	
	int pid=(int)getpid();
	
	int sleep_remaining=0;
	int oponent_pos;
	if(pid==Hare)
	{
		while(1)
		{
			//read opponent's position from pipe
			close(fd[1]);
			read(fd[0],&oponent_pos,sizeof(oponent_pos));
			
			//if opponent has reached the end line stop useless progress and show ressults
			if(oponent_pos>=length||curr_pos>=length)
			{
				show_players(curr_pos,oponent_pos);
				getch();
				endwin();
				break;
			}
			
			//if not in sleep mode
			if(sleep_remaining<=0)
			{
				//if tortoise is too far, lets sleep for a while
				if(curr_pos-oponent_pos>Hare_speed-tortoise_speed)
					sleep_remaining=Hare_sleep;
				else
					progress(&curr_pos,Hare_speed);
			}
			else
				sleep_remaining--;
			
			//show the results up to now
			show_players(curr_pos,oponent_pos);
		}
	}
	else{
		while(1)
		{
			progress(&curr_pos,tortoise_speed);
			
			//tell the Hare your position if it's this much important for him
			close(fd[0]);
			write(fd[1],&curr_pos,sizeof(curr_pos));
		}
	}
	endwin();
	system("clear");
}
تشکر:

باید از دوست خوبم، جناب آقای رضا خدائی، به خاطر کمک و راهنمایی‌هایشان در طول ترم تحصیلی که در درس "آزمایشگاه سیستم عامل" در خدمتشان بودم و مخصوصا در مورد این برنامه  به خصوص تذکراتی به بنده دادند، تشکر کنم.

acknowledgement:

Here I should thank my friend Mr. Reza Khodaee, the TA for "OS Lab" course, and specially for his useful hints on this specific program.