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,
- Starting activity is $A$, it can execute without any restriction.
- After completion of $A$, activity $B$ and $C$ can execute in parallel.
- After completion of $B$ and $C$ only, activity $D$ can start and execute.
- 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