CNDP  22.08.0
examples/phil/phil.c
/* SPDX-License-Identifier: BSD-3-Clause
* Copyright (c) 2019-2022 Intel Corporation
*/
/* phil.c - Dining Philosophers problem */
/* Includes */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>
#include <sys/queue.h>
#include <netinet/in.h>
#include <setjmp.h>
#include <stdarg.h>
#include <ctype.h>
#include <errno.h>
#include <getopt.h>
#include <termios.h>
#include <stdbool.h>
#include <cne_log.h>
#include <cne_tailq.h>
#include <cne_common.h>
#include <cne_cycles.h>
#include <cne_prefetch.h>
#include <cne_system.h>
#include <cne_per_thread.h>
#include <cne_timer.h>
#include <cne_spinlock.h>
#include <cne.h>
#include <ctx.h>
#include <cthread.h>
#include <cthread_api.h>
#include <cthread_barrier.h>
#include <cthread_once.h>
#include "main.h"
#include "phil.h"
// clang-format off
const char *doing_str[] = {
" thinking..........", // 0
" wants to eat......", // 1
" wait for forks....", // 2
" eating............", // 3
" ask right fork....", // 4
" wait right fork...", // 5
" ask left fork.....", // 6
" wait left fork....", // 7
" give all forks....", // 8
" ------------------", // 9
NULL
};
// clang-format on
static struct cthread_barrier **barriers;
static volatile int phil_quit = 0;
void
phil_create_barriers(void)
{
int max_threads = cne_max_threads();
barriers = calloc(max_threads, sizeof(struct cthread_barrier *));
if (!barriers)
CNE_RET("Unable to allocate cthread_barrier structures\n");
}
/*******************************************************************************
*
* forks_get - Get the right-hand and left-hand pair of forks
*
* This routine attempts to acquire the forks a philosopher needs to be able to
* eat. Forks are always acquired in pair, i.e. if only one of the forks is
* available then no fork is acquired.
*
* RETURNS: TRUE if both forks are acquired, FALSE otherwise.
* ERRNO: N/A
*
* \NOMANUAL
*/
static BOOL
forks_get(phil_info_t *phil, int my_num, /* Philosopher's order number */
int solution, /* Solution to execute */
fork_attr_t *forks_attr) /* Forks attributes */
{
BOOL forks_acquired = false;
BOOL pass_turn = false;
int right_fork = my_num;
int left_fork = (my_num + 1) % forks_attr->num_forks;
/* Acquire the mutex protecting the critical section */
phil->saved_count = 3;
cthread_mutex_lock(forks_attr->fork_mutex);
if (solution == TICKET_BASED) {
/* Check whether it is this philosopher's turn to get the forks */
if (((forks_attr->forks[right_fork].philosopher == my_num) ||
(forks_attr->forks[right_fork].philosopher == NOBODY)) &&
((forks_attr->forks[left_fork].philosopher == my_num) ||
(forks_attr->forks[left_fork].philosopher == NOBODY)))
forks_acquired = true;
} else { /* Claim-based solution */
/*
* A fork can be acquired only if it is not in use and if no one else
* has claimed it. If the fork is in use already then the philosopher
* simply claims it and waits for it to be available. If the fork is
* available but has already been claimed then the philosopher must
* wait for his/her turn.
*
* Note: if we were to randomize the think time of the philosophers it
* might be more efficient for a philosopher to claim the fork
* when the fork is available but has been claimed by the other
* philosopher (i.e. implement a two-slot queue for the fork).
*/
if (forks_attr->forks[right_fork].status == FORK_IN_USE) {
forks_attr->forks[right_fork].philosopher = my_num;
pass_turn = true;
phil->saved_doing = PHIL_ASK_RIGHT_FORK;
} else if ((forks_attr->forks[right_fork].philosopher != my_num) &&
(forks_attr->forks[right_fork].philosopher != NOBODY)) {
pass_turn = true;
phil->saved_doing = PHIL_WAIT_RIGHT_FORK;
}
if (forks_attr->forks[left_fork].status == FORK_IN_USE) {
forks_attr->forks[left_fork].philosopher = my_num;
pass_turn = true;
phil->saved_doing = PHIL_ASK_LEFT_FORK;
} else if ((forks_attr->forks[left_fork].philosopher != my_num) &
(forks_attr->forks[left_fork].philosopher != NOBODY)) {
pass_turn = true;
phil->saved_doing = PHIL_WAIT_LEFT_FORK;
}
/*
* if both forks are available and claimed by no one else then the
* philosopher may acquire them.
*/
if (!pass_turn) {
forks_attr->forks[right_fork].status = FORK_IN_USE;
forks_attr->forks[left_fork].status = FORK_IN_USE;
forks_attr->forks[right_fork].philosopher = NOBODY;
forks_attr->forks[left_fork].philosopher = NOBODY;
forks_acquired = true;
}
}
/* Release the mutex protecting the critical section */
phil->saved_count = PHIL_ASK_RIGHT_FORK;
cthread_mutex_unlock(forks_attr->fork_mutex);
return forks_acquired;
}
/*******************************************************************************
*
* forks_put - Put down the right-hand and left-hand pair of forks
*
* This routine simply releases the forks a philosopher was using to eat.
*
* RETURNS: N/A
* ERRNO: N/A
*
* \NOMANUAL
*/
static void
forks_put(phil_info_t *phil, int my_num, /* Philosopher's order number */
int solution, /* Solution to execute */
fork_attr_t *forks_attr) /* Forks attributes*/
{
int right_fork = my_num;
int left_fork = (my_num + 1) % forks_attr->num_forks;
/* Acquire the mutex protecting the critical section */
phil->saved_count = PHIL_WAIT_RIGHT_FORK;
cthread_mutex_lock(forks_attr->fork_mutex);
if (solution == TICKET_BASED) {
/*
* The forks are handed over to the philosophers on the immediate right
* and immediate left of the philosopher that is done eating.
*/
forks_attr->forks[right_fork].philosopher =
(right_fork ? right_fork - 1 : (forks_attr->num_forks - 1));
forks_attr->forks[left_fork].philosopher = left_fork;
phil->saved_doing = PHIL_GIVE_FORK;
} else { /* Claim-based solution */
/* The forks are simply flagged as available */
forks_attr->forks[right_fork].status = FORK_AVAILABLE;
forks_attr->forks[left_fork].status = FORK_AVAILABLE;
}
/* Release the mutex protecting the critical section */
phil->saved_count = PHIL_ASK_LEFT_FORK;
cthread_mutex_unlock(forks_attr->fork_mutex);
}
/*******************************************************************************
*
* philosopher_run - A philosopher task's run routine
*
* This routine is the starting point for each of the philosopher task.
*
* RETURNS: N/A
* ERRNO: N/A
*
* \NOMANUAL
*/
static void
philosopher_run(void *arg)
{
phil_info_t *phil = arg;
int my_num = phil->idx; /* This philosopher's order number */
int solution = phil->solution; /* Solution to execute */
phil_attr_t *phils_attr = phil->philos_attr; /* Philosophers attributes */
fork_attr_t *forks_attr = phil->forks_attr; /* Forks attributes*/
stats_t *pStats = phil->stats; /* statistics data */
struct cthread_barrier **b = &barriers[cne_id()];
phils_attr->i_am_ready[my_num] = true;
if (cthread_set_thread_private(NULL, phil) < 0) {
cne_printf("Failed to set private data for thread\n");
return;
}
do {
phil->doing = PHIL_THINKING;
phil->saved_count = 0;
cthread_sleep_msec(rand() & 0x3FF);
phil->doing = PHIL_WANTS_TO_EAT;
/*
* If the forks cannot be acquired this implementation simply does
* an active wait and checks again for the fork's availability after a
* random milli-seconds of delay.
*/
while (forks_get(phil, my_num, solution, forks_attr) == false) {
if (solution == TICKET_BASED)
phil->doing = PHIL_WAIT_FORK;
if (phil->quit)
break;
pStats->go_hungry[my_num]++;
phil->saved_count = 1;
cthread_sleep_msec(rand() & 0x3FF);
}
phil->doing = PHIL_ASK_RIGHT_FORK;
pStats->food_in_take[my_num]++;
phil->saved_count = 2;
cthread_sleep_msec(rand() & 0x3FF);
forks_put(phil, my_num, solution, forks_attr);
} while (phil->quit == 0);
}
/*******************************************************************************
*
* phil_demo_start - Dining philosopher demo
*
* This is the main entry of the dining philosopher's demo.
*
* If the demo is left to run forever (the default) then it will stop and
* print statistics when the main task is resumed from the shell.
*
* RETURNS: N/A
* ERRNO: N/A
*/
void
phil_demo_start(void *arg)
{
struct app_info *a = arg;
phil_info_t *phil;
unsigned int solution; /* Either one of the impl. solutions */
phil_attr_t philos_attr; /* Philosopher attributes */
fork_attr_t forks_attr; /* Fork attributes */
stats_t stats; /* Statistic data */
char name[32];
/* By default let's run the claim-based solution */
solution = TICKET_BASED;
/* Default number of philosophers */
philos_attr.num_phil = (a->num_threads > cne_max_threads()) ? cne_max_threads()
: a->num_threads;
/* There is as many forks as there are philosophers */
forks_attr.num_forks = philos_attr.num_phil;
/* Create the various arrays used in this implementation */
philos_attr.i_am_ready = calloc((size_t)philos_attr.num_phil, sizeof(BOOL));
stats.food_in_take = calloc((size_t)philos_attr.num_phil, sizeof(unsigned int));
forks_attr.forks = calloc((size_t)philos_attr.num_phil, sizeof(fork_t));
stats.go_hungry = calloc((size_t)philos_attr.num_phil, sizeof(unsigned int));
if (forks_attr.forks) {
/* Initialize the owner of the forks */
for (int i = 0; i < philos_attr.num_phil; i++)
forks_attr.forks[i].philosopher = -1;
} else
goto err;
/* Create mutex semaphore protecting the critical sections */
cthread_mutex_init("phil mutex", &forks_attr.fork_mutex, NULL);
int id = cne_id();
struct cthread_barrier **b = &barriers[id];
snprintf(name, sizeof(name), "Barrier-%d", id);
cthread_barrier_init(name, b, philos_attr.num_phil + 1);
/* Create philosopher tasks */
for (int i = 0; i < philos_attr.num_phil; i++) {
phil = calloc(1, sizeof(phil_info_t));
if (!phil)
CNE_ERR_GOTO(error, "Unable to allocate philosopher structure %d\n", i);
phil->doing = PHIL_THINKING;
phil->idx = i;
phil->solution = solution;
phil->philos_attr = &philos_attr;
phil->forks_attr = &forks_attr;
phil->stats = &stats;
snprintf(name, sizeof(name), "Philosopher-%d", i);
phil->cthd = cthread_create(name, philosopher_run, phil);
if (!phil->cthd)
CNE_RET("Unable to start philosopher cthread %d\n", i);
}
do {
} while (phil_quit == 0);
error:
/* Free resources */
cthread_mutex_destroy(forks_attr.fork_mutex);
err:
free(philos_attr.i_am_ready);
free(stats.food_in_take);
free(stats.go_hungry);
free(forks_attr.forks);
}
void
phil_demo_quit(void)
{
phil_quit = 1;
}
CNDP_API int cne_id(void)
CNDP_API int cne_max_threads(void)
#define CNE_RET(...)
Definition: cne_log.h:238
#define CNE_ERR_GOTO(lbl,...)
Definition: cne_log.h:273
CNDP_API int cne_printf(const char *fmt,...)
CNDP_API int cthread_barrier_wait(struct cthread_barrier *b)
CNDP_API int cthread_barrier_destroy(struct cthread_barrier *b)
CNDP_API int cthread_mutex_destroy(struct cthread_mutex *mutex)
CNDP_API int cthread_mutex_lock(struct cthread_mutex *mutex)
CNDP_API int cthread_barrier_init(const char *name, struct cthread_barrier **barr, unsigned count)
CNDP_API int cthread_mutex_unlock(struct cthread_mutex *mutex)
CNDP_API struct cthread * cthread_create(const char *name, cthread_func_t func, void *arg)
CNDP_API int cthread_set_thread_private(struct cthread *c, void *arg)
CNDP_API int cthread_mutex_init(const char *name, struct cthread_mutex **mutex, const struct cthread_mutexattr *attr)
CNDP_API void cthread_sleep_msec(uint64_t ms)