algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Dijkstry - Implementacja w C/C++
Ocena użytkownikóww: *****  / 1
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 26 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

dijkstra.c:
//(c)2002 Tomasz Lubinski
//www.algorytm.org
//algorytm Dijkstry - problem wzajemnego wykluczania


#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <signal.h>

int n;

void usun_pamiec()
{
int shmid,key;
shmid=shmget(100, 4, IPC_CREAT);
shmctl(shmid, IPC_RMID, NULL);
for (key=1; key<=n; key++)
	{
	shmid=shmget(100+key, 4, IPC_CREAT);
	shmctl(shmid, IPC_RMID, NULL);
	}
exit(0);
}

int main()
{
int* flag[100];
int* turn;
int shmid,key;
struct shmid_ds buf;

printf("Podaj dla ilu procesow chcesz przetestowac algorytm (max. 99)\n");
scanf("%d", &n);

//zainicjowanie zmiennych wspoldzielonych
shmid=shmget(100, 4, IPC_CREAT);
shmctl(shmid, IPC_STAT, &buf);
buf.shm_perm.mode=0666;
shmctl(shmid, IPC_SET, &buf);
turn=shmat(shmid, NULL, SHM_RND);
*turn=1;

for (key=1; key<=n; key++)
	{
	shmid=shmget(100+key, 4, IPC_CREAT);
	shmctl(shmid, IPC_STAT, &buf);
	buf.shm_perm.mode=0666;
	shmctl(shmid, IPC_SET, &buf);
	flag[key]=shmat(shmid, NULL, SHM_RND);
	*flag[key]=0;
	}

//po zakonczeniu wykonywania progamu pamiec wspoldzielona nalezy usunac.
//po nacisnieciu klawiszy ctrl+c sygnal SIGINT jest przechwytywany i
//uruchamiana jest funkcja usun_pamiec
signal(SIGINT, usun_pamiec);

printf("Program nalezy przerwac wciskajac ctrl+c\n\n");

//uruchomienie n procesow potomnych, ktore beda dzialaly wspolbieznie
for (key=1; key<=n; key++)
	{
	if (fork()==0)
		{
		int test,k,other,temp,pid;
		pid=key;		//kazdy proces potomny otrzymuje wlasny numer pid
		//algorytm Dijsktry
		while(1)
			{
			printf("P%d jest poza sekcja krytyczna\n", pid);
			sleep(random()%15);
			printf("P%d chce wejsc do sekcji krytycznej\n", pid);
		L: 	*flag[pid]=1;
			other=*turn;
			while (other!=pid)
				{
				test=*flag[other];
				if (test==0) *turn=pid;
				other=*turn;
				}
			*flag[pid]=2;
			for (k=1; k<=n; k++)
				if (k!=pid)
					{
					test=*flag[k];
					if (test==2) goto L;
					}
			printf("\t\t\t\tP%d jest w sekcji krytycznej\n", pid);
			sleep(random()%10);
			*flag[pid]=0;	
			}
		}
	}
wait(NULL);
}
Dodaj komentarz