2,413 views

1 Answer

Best answer
5 votes
5 votes

A precedence graph is a directed, acyclic graph where nodes represent sequential activities and where arrows, say from node $i$ to node $j$, requires that activity $i$ complete before activity $j$ can start.

Now, following is a precedence graph:

Here,

  1. Starting activity is $A$, it can execute without any restriction.
  2. After completion of $A$, activity $B$ and $C$ can execute in parallel.
  3. After completion of $B$ and $C$ only, activity $D$ can start and execute.
  4. After completion of $C$ and $D$ only, activity $E$ can start and execute.

We can implement these activities using fork() and wait() system calls. But simpler option will be to implement this by pthreads and synchronize all of them using semaphore.

But before going to the actual code here is the pseudo code using  par_begin par_end  construct to understand it.

sem p,q,r,s,t,u
// all semaphores are initialized to zero
par_begin
		
		begin A , par_begin V(p) , V(q) , par_end , end
		begin P(p) , B , V(r) , end
		begin P(q) , C , par_begin V(s) , V(u) , par_end , end
		begin P(r),P(s) , D , V(t) , end
		begin P(t),P(u) , E , end

par_end

Now this is one possible implementation using posix thread and posix semaphore

We will be using $6$ semaphores viz. p,q,r,s,t

#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <pthread.h>
#include <semaphore.h>
// sem_wait(sem_t *) == P() or down()
// sem_post(sem_t *) == V() or up()
sem_t p,q,r,s,t,u;

void *A(void *arg) {
	printf("A\n");
	sem_post(&p);
	sem_post(&q);
}
void *B(void *arg) {
	sem_wait(&p);
	printf("B\n");
	sem_post(&r);
}
void *C(void *arg) {
	sem_wait(&q);
	printf("C\n");
	sem_post(&s);
	sem_post(&u);	
}
void *D(void *arg) {
	sem_wait(&r);
	sem_wait(&s);
	printf("D\n");
	sem_post(&t);
}
void *E(void *arg) {
	sem_wait(&t);
	sem_wait(&u);
	printf("E\n");	
}	

int main(int argc, char const *argv[]) {

	pthread_t a_t,b_t,c_t,d_t,e_t;
	void *thread_result;
	
	sem_init(&p,0,0);
	sem_init(&q,0,0);
	sem_init(&r,0,0);
	sem_init(&s,0,0);
	sem_init(&t,0,0);
	sem_init(&u,0,0);

	pthread_create(&a_t,NULL,A,NULL);
	pthread_create(&b_t,NULL,B,NULL);
	pthread_create(&c_t,NULL,C,NULL);
	pthread_create(&d_t,NULL,D,NULL);
	pthread_create(&e_t,NULL,E,NULL);

	pthread_join(a_t,&thread_result);
	pthread_join(b_t,&thread_result);
	pthread_join(c_t,&thread_result);
	pthread_join(d_t,&thread_result);
	pthread_join(e_t,&thread_result);

	sem_destroy(&p);
	sem_destroy(&q);
	sem_destroy(&r);
	sem_destroy(&s);
	sem_destroy(&t);
	sem_destroy(&u);

	return 0;
}

Possible valid output:

// first
A
B
C
D
E

// second
A
C
B
D
E
selected by

Related questions

0 votes
0 votes
0 answers
1
Prince Sindhiya asked Dec 16, 2018
208 views
What is normalised turn around time for a process ? if we are using any scheduling algorithm
0 votes
0 votes
2 answers
3
Satbir asked Jul 22, 2018
346 views
If a process comes from block state to ready state then what can be said about preemption ?
0 votes
0 votes
0 answers
4
soumikplus asked Feb 27
65 views
Could you suggest any btech project which also help in my gate cs preparation and for building the concepts?