题目如下所示。
Introduction
In this assignment you will learn to use three programming constructs provided by the POSIX pthread library: threads, mutexes and condition variables.
Your goal is to construct a simulation of an automated control system for a single lane bridge. You will use threads to simulate trains approaching the bridge from two different
directions. Your software will ensure (among other things) that there is never more than one train on the bridge at any given time.
Step 1
Your program accepts two parameters on the command line. The first one is required, the second one is optional.
- The first parameter is an integer, greater than 0, which is the number of trains to simulate.
- The second parameter is optional: a filename to use as input data for the simulation. Theformat of the file is shown below.
You may assume :
1. the file always contains data for at least the number of trains specified in the first parameter.
2. during our testing the file specified on the command line will exist, and it will contain valid data.If the second parameter is not specified (no filename is given) your program will randomly generate trains for the simulation. (This code is already given to you.)
Complete the implementation of train.c so that it correctly reads the input files.
Step 2
Complete the implementation of ArriveBridge and LeaveBridge so that the following conditions hold for the bridge:
1. only one train is on the bridge at any given time.
trains do not overtake each other, trains cross the bridge in the order they arrive (subject to the requirement below)
2. trains headed East have priority over trains going West.
if there are trains waiting headed both East and West then two of the East bound trains should be allowed to cross for every West bound train allowed to cross.
Input file format
The input files have a simple format. Each line contains information about a single train. The files end with a blank line.
The first character on each line is one of the following four characters: ‘e’, ‘E’, ‘w’, or ‘W’. The first two letters specify a train that is going East, the second two letters specify a train headed West.
Immediately following the letter specifying the direction is an integer that indicates the length of the train. There is no space between the direction character and the length.
The following file specifies three trains, two headed East and one headed West.
E10
w6
E3
解决方案
整个程序包含三个程序，train.h，train.c，main.c。前两个文件主要是描述train的结构，main.c包含主要的实现代码。
train.h的内容如下所示。
/*
* train.h
*
* Some definitions for the Trains
*/
#ifndef __TRAIN__H
#define __TRAIN__H
/* Trains at maximum MAX_LENGTH long and minimum MIN_LENGTH long */
#define MIN_LENGTH 3
#define MAX_LENGTH 25
/* Trains can be headed in one of two directions: EAST or WEST */
#define DIRECTION_NONE 0
#define DIRECTION_WEST 1
#define DIRECTION_EAST 2
/* To simulate the length of the train, we will sleep for
* length*SLEEP_MULTIPLE when leaving the station and
* crossing the bridge.
*/
#define SLEEP_MULTIPLE 100000
/*
* The information about a train. You may need to add more fields to this
* structure.
*
* Make sure you update the trainCreate function to provide default values for
* your new fields.
*/
typedef struct
{
int trainId;
int direction;
int length;
int arrival;// you might not need this, I used it in my solution
} TrainInfo;
/*
* Initialize the train library. You must call this before any other
* function.
*
* The parameter is an optional file name which contains a
* description of trains to simulate. If the filename is
* NULL, trains are generated randomly.
*/
void initTrain ( char *filename );
/*
* Allocate a new train structure with a new trainId,
* trainIds are assigned consecutively, starting at
*
* Randomly choose a direction and a length.
*
* This function malloc's space for the TrainInfo structure.
* The caller is responsible for freeing it.'
*/
TrainInfo *createTrain ( void );
#endif
文件train.c的内容如下所示。
/*
* train.c
*/
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include "train.h"
/* A global to assign IDs to our trains */
int idNumber = ;
/* If this value is set to , trains lengths
* etc will be generated randomly.
*
* If it is set to , the lengths etc will be
* input from a file.
*/
int doRandom = ;
/* The file to input train data from */
FILE *inputFile;
/* You can assume that no more than characters
* will be on any line in the input file
*/
#define MAXLINE 80
void initTrain ( char *filename )
{
doRandom = ;
/* If no filename is specified, generate randomly */
if ( !filename )
{
doRandom = ;
srandom(getpid());
}
else
{
/* remove this line and add your code here */
inputFile=fopen(filename,"r");
// printf ("File input not implemented.\n");
}
}
/*
* Allocate a new train structure with a new trainId, trainIds are
* assigned consecutively, starting at
*
* Either randomly create the train structures or read them from a file
*
* This function malloc's space for the TrainInfo structure.
* The caller is responsible for freeing it.
*/
TrainInfo *createTrain ( void )
{
TrainInfo *info = (TrainInfo *)malloc(sizeof(TrainInfo));
/* I'm assigning the random values here in case
* there is a problem with the input file. Then
* at least we know all the fields are initialized.
*/
info->trainId = idNumber++;
info->arrival = ;
info->direction = (random() % + );
info->length = (random() % MAX_LENGTH) + MIN_LENGTH;
if (!doRandom)
{
/* Your code here to read a line of input
* from the input file
*/
char buf[MAXLINE];
fscanf(inputFile,"%s",buf);
info->direction=buf[]=='E'||buf[]=='e'?DIRECTION_EAST:DIRECTION_WEST;
info->length=atoi(&buf[]);
}
return info;
}
接着是主要的实现过程。显然每个线程都是一个线程，根据从文件读取的参数，休眠一段时间，然后准备过桥。规则在前面已经说过。
先上代码。
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include "train.h"
static int lastTrainDirection=DIRECTION_NONE; //direction of last train through bridge
static int lastSecondTrainDirection=DIRECTION_NONE;//direction of last second train throught bridge
static int isTrainCrossingBridge=; //true if a train is crossing bridge
static pthread_mutex_t crossMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t crossCond=PTHREAD_COND_INITIALIZER;
static int eastWaitNum=;// number of east bound trains in waiting queue
static pthread_mutex_t eastWaitMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t eastWaitCond=PTHREAD_COND_INITIALIZER;
static int westWaitNum=;// number of west bound trains in waiting queue
static pthread_mutex_t westWaitMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t westWaitCond=PTHREAD_COND_INITIALIZER;
//#define DEBUG 1
void ArriveBridge (TrainInfo *train);
void CrossBridge (TrainInfo *train);
void LeaveBridge (TrainInfo *train);
/*
* This function is started for each thread created by the
* main thread. Each thread is given a TrainInfo structure
* that specifies information about the train the individual
* thread is supposed to simulate.
*/
void * Train ( void *arguments )
{
TrainInfo *train = (TrainInfo *)arguments;
/* Sleep to simulate different arrival times */
usleep (train->length*SLEEP_MULTIPLE);
ArriveBridge (train);
CrossBridge (train);
LeaveBridge (train);
/* I decided that the paramter structure would be malloc'd
* in the main thread, but the individual threads are responsible
* for freeing the memory.
*
* This way I didn't have to keep an array of parameter pointers
* in the main thread.
*/
free (train);
return NULL;
}
/*
* add train to its waiting queue until previous trains are gone
*/
void enqueue(TrainInfo*train,int*pWaitNum,pthread_mutex_t*mutex,pthread_cond_t*cond){
int waitNum;
pthread_mutex_lock(mutex);
waitNum = (*pWaitNum)++;
#ifdef DEBUG
printf ("Train %2d wait: prev=%d\n", train->trainId, waitNum);
fflush(stdout);
#endif
while(waitNum--){
pthread_cond_wait(cond, mutex);
}
//minEastArrivalTime=train->arrival;
pthread_mutex_unlock(mutex);
}
/*
* wake up other trains in waiting queue with same direction
*/
void wakeUpWaitingTrains(int*pWaitNum,pthread_mutex_t*mutex,pthread_cond_t*cond){
pthread_mutex_lock(mutex);
--(*pWaitNum);
pthread_cond_broadcast(cond);
pthread_mutex_unlock(mutex);
}
/*
* You will need to add code to this function to ensure that
* the trains cross the bridge in the correct order.
*/
void ArriveBridge ( TrainInfo *train )
{
int*pWaitNum;
pthread_mutex_t*mutex;
pthread_cond_t*cond;
printf ("Train %2d arrives going %s\n", train->trainId,
(train->direction == DIRECTION_WEST ? "West" : "East"));
fflush(stdout);
/* Your code here... */
if(train->direction==DIRECTION_EAST){
pWaitNum=&eastWaitNum;
mutex=&eastWaitMutex;
cond=&eastWaitCond;
}else{
pWaitNum=&westWaitNum;
mutex=&westWaitMutex;
cond=&westWaitCond;
}
//enqueue waiting-queue
enqueue(train,pWaitNum, mutex, cond);
//begin to cross bridge
pthread_mutex_lock(&crossMutex);
while(isTrainCrossingBridge){
#ifdef DEBUG
printf ("Train %2d wait to cross\n", train->trainId);
fflush(stdout);
#endif
//wait for the train to go through bridge
pthread_cond_wait(&crossCond, &crossMutex);
if(train->direction==DIRECTION_EAST){
//check west-headed train
do{
int westWait;
pthread_mutex_lock(&westWaitMutex);
westWait=westWaitNum;
pthread_mutex_unlock(&westWaitMutex);
if(westWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST){
//wait for west-headed train to cross bridge
#ifdef DEBUG
printf("Train %2d wait for once\n", train->trainId);
fflush(stdout);
#endif
pthread_cond_wait(&crossCond, &crossMutex);
}else{
break;
}
}else{
//last direction won't make difference to next
lastTrainDirection=DIRECTION_NONE;
break;
}
}while();
}else{
//check east-headed train
int eastWait;
do{
pthread_mutex_lock(&eastWaitMutex);
eastWait=eastWaitNum;
pthread_mutex_unlock(&eastWaitMutex);
if(eastWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST)
break;
//wait for east train to cross first
pthread_cond_wait(&crossCond, &crossMutex);
}else
break;
}while();
}
}
#ifdef DEBUG
printf ("Train %2d begin to cross\n", train->trainId);
fflush(stdout);
#endif
isTrainCrossingBridge=;
lastSecondTrainDirection=lastTrainDirection;
lastTrainDirection = train->direction;
pthread_mutex_unlock(&crossMutex);
//
wakeUpWaitingTrains(pWaitNum, mutex, cond);
}
/*
* Simulate crossing the bridge. You shouldn't have to change this
* function.
*/
void CrossBridge ( TrainInfo *train )
{
printf ("Train %2d is ON the bridge (%s)\n", train->trainId,
(train->direction == DIRECTION_WEST ? "West" : "East"));
fflush(stdout);
/*
* This sleep statement simulates the time it takes to
* cross the bridge. Longer trains take more time.
*/
usleep (train->length*SLEEP_MULTIPLE);
printf ("Train %2d is OFF the bridge(%s)\n", train->trainId,
(train->direction == DIRECTION_WEST ? "West" : "East"));
fflush(stdout);
}
/*
* Add code here to make the bridge available to waiting
* trains...
*/
void LeaveBridge ( TrainInfo *train )
{
pthread_mutex_lock(&crossMutex);
isTrainCrossingBridge=;
pthread_cond_broadcast(&crossCond);
pthread_mutex_unlock(&crossMutex);
}
int main ( int argc, char *argv[] )
{
int trainCount = ;
char *filename = NULL;
pthread_t *tids;
int i;
/* Parse the arguments */
if ( argc < )
{
printf ("Usage: part1 n {filename}\n\t\tn is number of trains\n");
printf ("\t\tfilename is input file to use (optional)\n");
exit();
}
if ( argc >= )
{
trainCount = atoi(argv[]);
}
if ( argc == )
{
filename = argv[];
}
initTrain(filename);
/*
* Since the number of trains to simulate is specified on the command
* line, we need to malloc space to store the thread ids of each train
* thread.
*/
tids = (pthread_t *) malloc(sizeof(pthread_t)*trainCount);
/*
* Create all the train threads pass them the information about
* length and direction as a TrainInfo structure
*/
for (i=;i<trainCount;i++)
{
TrainInfo *info = createTrain();
printf ("Train %2d headed %s length is %d\n", info->trainId,
(info->direction == DIRECTION_WEST ? "West" : "East"),
info->length );
if ( pthread_create (&tids[i],, Train, (void *)info) != )
{
printf ("Failed creation of Train.\n");
exit();
}
}
/*
* This code waits for all train threads to terminate
*/
for (i=;i<trainCount;i++)
{
pthread_join (tids[i], NULL);
}
free(tids);
return ;
}
如代码所示，每个火车线程的流程都是上桥、过桥、下桥。过桥用睡眠表示，最重要的是上桥和下桥。这里上下桥的同步难点有3个。
1. 同一方向的火车须按照到来的次序依次离开，也就意味着，如果一辆车刚到桥头的时候，碰上有其它车在等待中，则它必须也随之等待，等前面所有车都在了才能走；
2. 当一个车经过千辛万苦终于等到上桥的机会的时候，需要判断桥上是否有车，如果有则还需要等待，否则进入下一步；
3. 当桥上没有车的时候，两个方向的排队的队首的车可以进行判断哪个开了。这里的难题在于，东向的车有一定的优先级。也就是说，对于西向的车而言，必须先让2个东向的车先过（包括刚过桥的东向车）。比如说，现在东向和西向的车都等着过桥。如果西向的车已经等了两次，也就是已经让两个东向车先走了，则西向车可以发了。如果西向车只等了一次，则需给东向车让路。如果还没等过一次，则本轮要让东向车走，下一轮也一样。
现在来看需要同步访问的变量。
桥
这是必须互斥访问的，同一时间最多允许一个车过桥。这里用一个标志记录是否有车通过。同时记录上一趟、上上一趟车的方向。
static int lastTrainDirection=DIRECTION_NONE; //direction of last train through bridge
static int lastSecondTrainDirection=DIRECTION_NONE;//direction of last second train throught bridge
static int isTrainCrossingBridge=; //true if a train is crossing bridge
static pthread_mutex_t crossMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t crossCond=PTHREAD_COND_INITIALIZER;
东向车等待队列
所有东向的车的排队队列。当然这里不需要真的放一个队列结构。这里采用的办法是等待车数计数。每个车到来的时候会记下排在前面的车有几个，然后就一直等待这个数到0，也就是前面的车都走了。
static int eastWaitNum=;// number of east bound trains in waiting queue
static pthread_mutex_t eastWaitMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t eastWaitCond=PTHREAD_COND_INITIALIZER;
西向车等待队列
西向车一样有等待队列，实现如东向车所示。同步变量如下所示。
static int westWaitNum=;// number of west bound trains in waiting queue
static pthread_mutex_t westWaitMutex=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t westWaitCond=PTHREAD_COND_INITIALIZER;
上桥
这个过程可以分为三个步骤。
1. 进入等待队列；
2. 等待上桥机会；
3. 上桥
上桥函数是
void ArriveBridge ( TrainInfo *train )
。主要过程如下所示。
//enqueue waiting-queue
enqueue(train,pWaitNum, mutex, cond);
//begin to cross bridge
pthread_mutex_lock(&crossMutex);
while(isTrainCrossingBridge){
#ifdef DEBUG
printf ("Train %2d wait to cross\n", train->trainId);
fflush(stdout);
#endif
//wait for the train to go through bridge
pthread_cond_wait(&crossCond, &crossMutex);
if(train->direction==DIRECTION_EAST){
//check west-headed train
do{
int westWait;
pthread_mutex_lock(&westWaitMutex);
westWait=westWaitNum;
pthread_mutex_unlock(&westWaitMutex);
if(westWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST){
//wait for west-headed train to cross bridge
#ifdef DEBUG
printf("Train %2d wait for once\n", train->trainId);
fflush(stdout);
#endif
pthread_cond_wait(&crossCond, &crossMutex);
}else{
break;
}
}else{
//last direction won't make difference to next
lastTrainDirection=DIRECTION_NONE;
break;
}
}while();
}else{
//check east-headed train
int eastWait;
do{
pthread_mutex_lock(&eastWaitMutex);
eastWait=eastWaitNum;
pthread_mutex_unlock(&eastWaitMutex);
if(eastWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST)
break;
//wait for east train to cross first
pthread_cond_wait(&crossCond, &crossMutex);
}else
break;
}while();
}
}
#ifdef DEBUG
printf ("Train %2d begin to cross\n", train->trainId);
fflush(stdout);
#endif
isTrainCrossingBridge=;
lastSecondTrainDirection=lastTrainDirection;
lastTrainDirection = train->direction;
pthread_mutex_unlock(&crossMutex);
//
wakeUpWaitingTrains(pWaitNum, mutex, cond);
进入等待队列直到离开的函数是enqueue()。该函数的实现过程如前所述，代码如下所示。
int waitNum;//前面等待的车数
pthread_mutex_lock(mutex);
waitNum = (*pWaitNum)++;//递增等待车数
#ifdef DEBUG
printf ("Train %2d wait: prev=%d\n", train->trainId, waitNum);
fflush(stdout);
#endif
while(waitNum--){//等待前面所有车离开
pthread_cond_wait(cond, mutex);
}
pthread_mutex_unlock(mutex);
火车排队到队首，终于有机会过桥了。这时候需要综合判断两方的车。东向和西向的车判断方式不同，所以这里分开叙述。
对于东向的车而言，等待过桥的思路是这样。首先判断是否有西向车，如果没有就直接过去了，这里有个小细节，就是要清除上一轮过桥的车向。如果有西向车，则要判断是否前两轮都是东向车，如果是则需要等待对方先过。否则允许通过。具体代码如下所示。
//check west-headed train
do{
int westWait;
pthread_mutex_lock(&westWaitMutex);
westWait=westWaitNum;
pthread_mutex_unlock(&westWaitMutex);
if(westWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST){
//wait for west-headed train to cross bridge
#ifdef DEBUG
printf("Train %2d wait for once\n", train->trainId);
fflush(stdout);
#endif
pthread_cond_wait(&crossCond, &crossMutex);
}else{
break;
}
}else{
//last direction won't make difference to next
lastTrainDirection=DIRECTION_NONE;
break;
}
}while();
接着是西向车。判断的条件是，如果没有东向车，则直接过桥。如果有东向车，则判断是否前两趟都是东向车，则西向车可以走了，否则需要让车~~总共两次。具体代码如下所示。
//check east-headed train
int eastWait;
do{
pthread_mutex_lock(&eastWaitMutex);
eastWait=eastWaitNum;
pthread_mutex_unlock(&eastWaitMutex);
if(eastWait){
if(lastTrainDirection ==DIRECTION_EAST
&& lastSecondTrainDirection ==DIRECTION_EAST)
break;
//wait for east train to cross first
pthread_cond_wait(&crossCond, &crossMutex);
}else
break;
}while();
经过千辛万苦，终于可以上桥了，这时候就是设置过桥标志，然后唤醒同向等待的车次，让它们醒来后递减一次等待次数。这样排在后一个的车终于会醒来，等待上桥。
下桥
下桥过程简单，只是简单将过桥标志清除，然后唤醒两方等待的队列。代码如下所示。
void LeaveBridge ( TrainInfo *train )
{
pthread_mutex_lock(&crossMutex);
isTrainCrossingBridge=0;
pthread_cond_broadcast(&crossCond);
pthread_mutex_unlock(&crossMutex);
}
整个方案经过验证，测试通过。
![图形处理单元(GPU)的演进[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)