经典信号量例题“抽烟者问题”的 C 语言实现

问题描述:The Cigarette-Smokers Problem. Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats.

问题分析:通过问题描述,可以构建出一个 4 进程的系统,其中 3 个进程为 smoker 程序的实例,另一个是 agent 程序的实例。首先,Agent 执行提供材料的操作(原则上来说,抽烟者先就座等待也是可行的,代码上也易于实现,但是我编写了一段代码发现很累赘,这作为一个需要改进的部分,暂时在代码中做 TODO 标记),然后执行对 Smoker_i 的 V 操作唤醒 Smoker_i,其信号量增 1,i 的值由 Agent 随机确定。接着,Agent 开始等待,进程切换到 Smoker_i,Smoker_i 执行 P 操作,信号量减为 0,开始获取材料,卷烟,抽烟操作。抽完烟后 Smoker_i 执行 V 操作,通知 Agent,然后 Smoker_i 循环至开头,开始等待,进程切换回 Agent。Agent 也开始循环,如此周期往复。采用同步机制的 PV 操作伪码如下:

Initial semaphores:
Agent: 0
Smoker_i: 0 (i = 0, 1, 2)

Agent{
loop:
Offer ingredients;
V(Smoker_i);
P(Agent);
GOTO loop;
} Smoker_i{
loop:
P(Smoker_i);
Get ingredients, roll and smoke;
V(Agent);
GOTO loop;
}//i = 0, 1, 2

技术细节:

1. Linux 系统调用函数 semget(),semctl(),semop()

1.1. semget()函数原型:int semget(key_t key,int nsems,int semflg);

这个函数用于创建一个信号量集,创建成功后在操作系统中的 Semaphore Array 中新建一条记录。第一个参数为 Semaphore Array 记录中的 key 值,用于不同进程间识别同一个信号量;第二个参数为信号量集中的信号量个数,如果为 0 则为打开现有的信号量集;第三个参数为信号量创建的操作类型和访问权限。

1.2. semctl()函数原型:int semctl(int semid,int semnum,int cmd,union semun arg);

这个函数用于控制信号量集中的每个信号量,具体操作由第三个参数 cmd 决定。

1.3. semop()函数原型:int semop(int semid,struct sembuf*sops,unsign ednsops);

这个函数用于操作信号量,通过对第二个参数结构体中的内容进行修改,可以封装成 PV 操作。

2. ipcs, ipcrm 命令

由于信号量是在操作系统中的共享区域中,所以可以使用系统命令查看和删除这些信号量集。ipcrm -S KEY 命令可以删除键值为 KEY 的信号量,ipcs 命令可以查看信号量列表(当然其中还有其他 IPC 列表)。

代码：

/*
 * File: PV.h
 * Author: Caspar Zhang
 */
#ifndef _PV_H
#define _PV_H

#define SEM_KEY 0x12345678

#define ERR_AND_EXIT(arg) do {
perror(arg);
exit(1);
} while(0)

int P(int semid, int sem_index);
int V(int semid, int sem_index);

#endif /* _PV_H */

/*
 * File: PV.c
 * Author: Caspar Zhang
 */
#include "PV.h"
#include 
#include 
#include

int P(int semid, int sem_index)
{ struct sembuf buf;

buf.sem_num = sem_index;
buf.sem_op = -1;
buf.sem_flg = SEM_UNDO;

if (semop(semid, &buf, 1) == -1)
return -1;

return 0;
}

int V(int semid, int sem_index)
{ struct sembuf buf;

buf.sem_num = sem_index;
buf.sem_op = 1;
buf.sem_flg = SEM_UNDO;

if (semop(semid, &buf, 1) == -1)
return -1;

return 0;
}

/*
 * File: Agent.c
 * Author: Caspar Zhang
 */
#include 
#include 
#include 
#include 
#include 
#include "PV.h"

int main(int argc, char *argv[])
{ /*
* 0 - Paper and matches
* 1 - Matches and tobacco
* 2 - Tobacco and paper
*/
char *ingredient[3] = {
"Paper and matches",
"Matches and tobacco",
"Tobacco and paper"};
int ingred_type;
int semid, i;

srand((unsigned)time(NULL));
/* Puts out the Agent's information */
fprintf(stdout, "I'm the Agent.n" );

/*
* Create a new semaphore set which has 4 semaphores in it.
* The first 3 semaphores are the Smokers' state,
* the last one is the Agent's state
*/
if ((semid = semget(SEM_KEY, 4, IPC_CREAT|0660)) < 0)
ERR_AND_EXIT("semget");
for (i = 0; i < 4; ++i)
if (semctl(semid, i, SETVAL, 0) < 0)
ERR_AND_EXIT("semctl");

/*
* The procedures are shown in below:
* 1. Offer Ingredients
* 2. V(Smoker_i)
* 3. P(Agent)
* 4. Go to 1 and repeat
*/
while (1)
{
/* Offer the ingredients randomly*/
ingred_type = rand() % 3;
fprintf(stdout, "Agent%d: I offered %s, waiting for the smoker.n",
ingred_type, ingredient[ingred_type]);
sleep(5);

/* Wake up the specified smoker */
if (V(semid, ingred_type) < 0) ERR_AND_EXIT("V failed");

/* Wait for smoker to roll and smoke */
if (P(semid, 3) < 0) ERR_AND_EXIT("P failed");
}

return 0;
}

/*
 * File: Smoker.c
 * Author: Caspar Zhang
 */

#include #include #include #include "PV.h"

int main(int argc, char *argv[])
{ /*
* 0 - Tobacco Smoker
* 1 - Paper Smoker
* 2 - Matches Smoker
*/
char *ingredient[3] = {"Tobacco", "Paper", "Matches"};
int smoker = argv[1][0] - '0';
int semid;

/* Puts out the Smoker's information */
fprintf(stdout, "I'm a smoker. I have %sn", ingredient[smoker]);

/* Get the existed semaphore set */
/* TODO How to create semaphores if smoker process executed first? */
if ((semid = semget(SEM_KEY, 0, 0)) < 0)
ERR_AND_EXIT("semget");
if (semctl(semid, smoker, GETVAL, 0) < 0)
ERR_AND_EXIT("semctl");
/*
* The procedures are shown in below:
* 1. P(Smoker_i)
* 2. Get Ingredients, Roll and Smoke
* 3. V(Agent)
* 4. Go to 1 and repeat
*/
while (1)
{
/* Wait for the Agent*/
fprintf(stdout, "%s: I'm waiting for the agent.n", ingredient[smoker]);
sleep(5);

if (P(semid, smoker) < 0) ERR_AND_EXIT("P failed");

/* Roll and smoke */
fprintf(stdout, "%s: I get the ingredients, I'm rolling and smoking now.n",
ingredient[smoker]);
sleep(5);

/* Wake up Agent */
if (V(semid, 3) < 0) ERR_AND_EXIT("V failed");
}

return 0;
}

顺便附一段用 Java 多线程实现的抽烟者问题解决代码，用 Semaphore 这个类实现的。

import java.util.Random;
import java.util.concurrent.Semaphore;

/**
* @author caspar
*
*/
public class AgentSmokerProblem
{ /* Create 4 semaphores, the first is for agent and the rest are for smokers */
public static Semaphore sem_agent;
public static Semaphore[] sem_smoker = new Semaphore[3];
public static void main(String[] args)
{
/* Initialize the semaphores to 0 */
sem_agent = new Semaphore(0);
sem_smoker[0] = new Semaphore(0);
sem_smoker[1] = new Semaphore(0);
sem_smoker[2] = new Semaphore(0);

/* Create agent and smokers */
Agent agent = new Agent();
Smoker[] smoker = new Smoker[3];
smoker[0] = new Smoker(0);
smoker[1] = new Smoker(1);
smoker[2] = new Smoker(2);

/* Start the threads */
agent.start();
smoker[0].start();
smoker[1].start();
smoker[2].start();
}

}

class Agent extends Thread
{ public Agent()
{
super("Agent");
}
public void run()
{
String[] smoker_type = {"tobacco", "paper", "matches"};
String[] ingre_type = {"paper and matches", "matches and tobacco", "tobacco and paper"};

System.out.println("Agent is ready...");

while (true)
{
/* Agent running, offering ingredients */
int smoker_num = new Random().nextInt(3);
System.out.println("Agent: I offer " + ingre_type[smoker_num] +
", now waiting for the smoker who has " + smoker_type[smoker_num]);
try {
sleep(2000);
} catch (InterruptedException e1) {
e1.printStackTrace();
}

/* Call the corresponding smoker */
AgentSmokerProblem.sem_smoker[smoker_num].release();

/* Wait for the smoker */
try {
AgentSmokerProblem.sem_agent.acquire();
} catch (Exception e) {
e.printStackTrace();
}
}
}
}

class Smoker extends Thread
{ private int smoker_num;
public Smoker(int smoker_num)
{
super("Smoker " + smoker_num);
this.smoker_num = smoker_num;
}
public void run()
{
String[] smoker_type = {"tobacco", "paper", "matches"};
String[] ingre_type = {"paper and matches", "matches and tobacco", "tobacco and paper"};

System.out.println("The smoker has " + smoker_type[smoker_num] + " is ready...");

while (true)
{
/* Smoker is waiting for the Agent*/
try {
AgentSmokerProblem.sem_smoker[smoker_num].acquire();
} catch (InterruptedException e1) {
e1.printStackTrace();
}

/* Smoker get ingredients, roll and smoke*/
System.out.println("The smoker has " + smoker_type[this.smoker_num] + ": I get the " +
ingre_type[this.smoker_num] + ", Let me roll a cigarette and smoke.");
try {
sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}

/* Call agent */
AgentSmokerProblem.sem_agent.release();

/* Smoker is waiting*/
System.out.println("The smoker has " + smoker_type[this.smoker_num] +
": I finish smoking, now waiting for the agent.");
try {
sleep(2000);
} catch (InterruptedException e1) {
e1.printStackTrace();
}
}
}
}

Ant-Veil

Caspar Blog

经典信号量例题“抽烟者问题”的 C 语言实现

Comments