The Cigarette Smokers Problem, first presented by Suhas Patil in 1971, is a classic concurrency problem that illustrates the use of semaphores to solve the problem of synchronization between threads. There are many variations to the problem, but the one presented here involves three cigarette smokers and an agent.
The smokers each have an unlimited supply of one of the ingredients needed to make a cigarette (tobacco, paper, or matches), while the agent has an unlimited supply of all three ingredients. The agent selects two ingredients at random and places them on a shared table. The smoker who has the third complementary ingredient can then take the two ingredients from the table and use them to make and smoke a cigarette. The problem requires synchronization between the threads to ensure that the smokers can only take ingredients from the table when they are available and that the agent can only place ingredients on the table when a smoker is ready to take them. The solution involves using semaphores to control access to the shared table and to coordinate the actions of the agent and the smokers.
The C code provided below is an implementation of the Cigarette Smokers’ Problem using semaphores and threads. The semaphores used are table, agent, and smoker[3]. The table semaphore controls access to the shared table where the ingredients are placed. The agent semaphore represents the agent, who can produce any two ingredients at a time. The smoker[3] semaphores represent the three smokers (smoker[0], smoker[1], and smoker[2]), each of whom can smoke if they have all the necessary ingredients. The smokeCount[3] array keeps track of the maximum number of smokes that each smoker can have before they die from cancer. This is a user determined value.
#define _DEFAULT_SOURCE
#include <semaphore.h> // sem_t, sem_wait(), sem_post(), sem_init()
#include <pthread.h> // pthread_t, pthread_create(), pthread_join()
#include <stdbool.h> // bool, true, false
#include <stdlib.h> // atoi(), rand(), srand(), exit()
#include <string.h> // strcmp()
#include <unistd.h> // usleep()
#include <stdio.h> // printf()
#include <time.h> // time()
// Global Variables
sem_t table; //< place where agent produces its ingredients
sem_t agent; //< entity with unlimited ingredients
sem_t smoker[3]; //< cigarette smokers 1, 2 and 3
int smokeCount[3]; //< max number of smokes that cause cancer
// Function definations
/// ---------------------------------------------------------------------------
/// Checks if a smoker is alive or dead.
///
/// @param id The smoker identifier.
///
/// @returns 'true' if smoker[id] is alive; else 'false'.
/// ---------------------------------------------------------------------------
bool is_alive(int id)
{
return (smokeCount[id] == 0) ? false : true;
}
/// ---------------------------------------------------------------------------
/// Generates a random number based on scenarios determined by the
/// number of living & dead smokers.
///
/// @returns ret_val The random number generated
/// ---------------------------------------------------------------------------
int rand_num()
{
int ret_val; //< function return value
// all smokers are alive
if(is_alive(0) && is_alive(1) && is_alive(2)) {
ret_val = rand() % 3;
}
// smoker[0] is dead; others are alive
else if(!is_alive(0) && is_alive(1) && is_alive(2)) {
ret_val = (rand() % 2) + 1;
}
// smoker[1] is dead; others are alive
else if(!is_alive(1) && is_alive(0) && is_alive(2)) {
ret_val = (((rand() % 2) + 1) == 1) ? 0 : 2;
}
// smoker[2] is dead; others are alive
else if(!is_alive(2) && is_alive(0) && is_alive(1)) {
ret_val = rand() % 2;
}
// if all smokers are dead
else if(!is_alive(0) && !is_alive(1) && !is_alive(2)) {
ret_val = -1;
}
// if only one smoker is alive
else {
for(int i = 0; i < 3; i++) {
if(is_alive(i)) {
ret_val = i;
}
}
}
return ret_val;
}
/// ---------------------------------------------------------------------------
/// Generates a pair of ingredients needed by living smokers. Resources are
/// represented as:
/// 0 => tobacco & paper
/// 1 => matches & paper
/// 2 => matches & tobacco
///
/// @param *arg A pointer argument to any type.
/// ---------------------------------------------------------------------------
void *agentThdFunc(void *arg)
{
int randNum; //< pair-of-ingredients identifier
while(true) {
sem_wait(&table); // close access to table
// choose two ingredients to produce
randNum = rand_num();
// if all smokers are dead, quit production
if( randNum == -1) {
break;
}
// put chosen ingredients on the table
switch(randNum) {
case 0:
printf("Agent produced tobacco and paper\n");
break;
case 1:
printf("Agent produced matches and paper\n");
break;
case 2:
printf("Agent produced matches and tobacco\n");
break;
}
sem_post(&table); // allow table access
sem_post(&smoker[randNum]); // signal smoker[randNum]
sem_wait(&agent); // wait for table to be cleared
}
pthread_exit(NULL); // terminate thread
}
/// ---------------------------------------------------------------------------
/// Simulates smoker behavior using resources provided by the agent.
/// smoker[0] - has matches; needs tobacco and paper
/// smoker[1] - has tobacco; needs matches and paper
/// smoker[2] - has paper; needs matches and tobacco
///
/// @param *arg A pointer argument to any type.
/// ---------------------------------------------------------------------------
void *smokerThdFunc(void *arg)
{
int smkr_id = *(int*)arg;
printf("Smoker %d starts...\n", smkr_id); // starting message
while(is_alive(smkr_id))
{
sem_wait(&smoker[smkr_id]); // wait for ingredient
sem_wait(&table); // block table access
usleep(rand() % 1500000); // smoke for a while; clear table
switch(smkr_id) {
case 0: // red
printf("\033[0;31mSmoker %d completed smoking\033[0m\n", smkr_id);
break;
case 1: // green
printf("\033[0;32mSmoker %d completed smoking\033[0m\n", smkr_id);
break;
case 2: // blue
printf("\033[0;34mSmoker %d completed smoking\033[0m\n", smkr_id);
break;
}
smokeCount[smkr_id]--; // update current smoker's smoke count
sem_post(&table); // allow table access
sem_post(&agent); // notify agent that table is cleared
}
printf("Smoker %d dies of cancer.\n", smkr_id);
free(arg); // deallocate dynamic memory
pthread_exit(NULL); // terminate thread
}
/// -----------------------------------------------------------------------
/// Main entry point for this program.
///
/// @return Exit-code for the process - 0 for success, else an error code.
/// -----------------------------------------------------------------------
int main(int argc, char **argv)
{
srand(time(0)); //< use current time as seed for rand()
char str[3] = "-s"; //< required cmd line option
pthread_t smokerThd[3]; //< threads for smoker operations
pthread_t agentThd; //< thread for agent operation
// validate command line arguments
if (argc != 3) {
printf("Error, unexpected number of arguments\n");
exit(1);
}
if(strcmp(argv[1], str) != 0) {
printf("Error, invalid argument/s\n");
exit(1);
}
if((atoi(argv[2]) < 3) || (atoi(argv[2]) > 10)) {
printf("Error, invalid smoke count\n");
exit(1);
}
// Initialize global variables
sem_init(&table, 0, 1);
sem_init(&agent, 0, 0);
for(int i=0; i<3; i++) {
sem_init(&smoker[i], 0, 0);
smokeCount[i] = atoi(argv[2]);
}
// Spawn threads
pthread_create(&agentThd, NULL, &agentThdFunc, NULL);
for(int i=0; i<3; i++) {
int *smkr_id_ptr = malloc(sizeof(int));
*smkr_id_ptr = i;
pthread_create(&smokerThd[i], NULL, &smokerThdFunc, smkr_id_ptr);
}
// Join threads
pthread_join(agentThd, NULL);
for(int i=0; i<3; i++) {
pthread_join(smokerThd[i], NULL);
}
// Destroy all semaphores
sem_destroy(&table);
sem_destroy(&agent);
for(int i=0; i<3; i++) {
sem_destroy(&smoker[i]);
}
exit(0); // Exit program
}
/* EOF */
The is_alive() function checks if a smoker is alive or dead based on their smokeCount. The rand_num() function generates a random number based on the scenarios determined by the number of living and dead smokers. The agentThdFunc() function represents the agent thread, which produces a pair of ingredients (determined by the rand_num()) and places them on the table. The smokerThdFunc() function simulates smoker behavior which includes picking up the ingredients from the table and smoking the resulting cigarette if all the necessary ingredients are obtained.
Finally, the main function creates and initializes the semaphores, creates the threads, and waits for them to finish. The program terminates when all the smokers have died from cancer or when the user presses CTRL + C. A sample run of the above program with a smoke count of 3 will result in an output similar to the one shown below:
Ultimately, the cigarette smokers’ problem is a metaphor for real-world situations where multiple entities (threads) need to access shared resources in a coordinated manner. For example, it could represent a situation in which multiple users need to access a shared database or a situation in which multiple processes need to access shared memory. In these cases, semaphores or other synchronization mechanisms would be used to ensure that the resources are accessed in a controlled and coordinated manner.
Latest comments (1)
I'm glad I was able to quit smoking cigarettes and tobacco. I didn't really quit for health or anything, I just don't like the fact that I, my hands, my clothes smelled bad. Besides, I couldn't smoke cigarettes at home either. Now I've found a lot of different products from Vampire Vape, and it's a really cool vape brand that's sold on Red Vape. I suggest it if you want to vape too.