待ち行列モデルについて

[kranke]

はじめまして、krankeと申します。
学校の課題にて、どうしてもうまくいかない問題が出ましたので、是非ともお力をお借りしたく思います。
次のプログラムはM/M/Sの待ち行列モデルのプログラムです

コード:

#include <stdio.h>
#include <stdlib.h>

struct st_cell {
	int data;                 /* 転送要求の到着時刻 */
	struct st_cell *next;     /* 次のセルへのポインタ */
};
typedef struct st_cell CELL;

/* 転送処理の終了を判定する関数 */
int departure(double);
/* 転送要求の到着を判定する関数 */
int arrival(double);
/* 待ち行列に残っているすべてのセルを削除する関数 */
void clear(CELL *);
/* 待ち行列の末尾にセルを追加する関数 */
void enqueue(CELL **, CELL **, int);
/* サーバのメモリにあるセルを削除する関数 */
int dequeue(CELL **);
/* 待ち行列の先頭のセルをサーバに転送する関数 */
void transmission(CELL **head, CELL **tail, CELL **memory);

int main(int argc, char *argv[])
{
	double lambda;  /* 単位時間あたりの到着確率 */
	double mu;      /* 単位時間あたりのサービス終了確率 */
	
	double rho;  /* システム利用率 */
	int S;       /* サーバ数 */
	int T;       /* シミュレーション時間*/
	int B;       /* 初期バイアス期間 */
	int N;       /* 繰り返し回数 */
	
	int t;  /* 現在の時刻 */
	int n;  /* 現在のシミュレーション回数 */
	int i;  /* カウンタ用変数 */
		
	double avgLength;      /* 平均系内客数 */
	double avgWait;        /* 平均滞在時間 */
	double avgThroughput;  /* スループット */
	
	double sumLength;      /* 合計系内客数*/
	double sumDeparture;   /* 合計退去数*/
	double sumWait;        /* 合計滞在時間*/
	int length;         /* 系内客数*/
	int wait;           /* 滞在時間 */
	CELL *head;         /* 待ち行列の先頭へのポインタ */
	CELL *tail;         /* 待ち行列の末尾へのポインタ */
	CELL **server;      /* サーバでメモリを表す配列へのポインタ */

	
	/* 引数の個数が5個ではないとき */
	if (argc != 5) {
		fprintf(stderr, "usage: %s <rho> <servers> <time> <repeat>\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	rho = (double)atof(argv[1]);
	
	/* 利用率の値が不正なとき */
	if (rho < 0 || rho > 1.0) {
		fprintf(stderr, "rho must be set in range [0,1.0].\n");
		exit(EXIT_FAILURE);
	}
	
	S = atoi(argv[2]);
	
	/* サーバ数の値が不正なとき */
	if (S <= 0) {
		fprintf(stderr, "servers must be set to a positive integer. \n");
		exit(EXIT_FAILURE);
	}
	
	T = atoi(argv[3]);
	
	/* シミュレーション時間の値が不正なとき  */
	if (T <= 0) {
		fprintf(stderr, "time must be set to a positive integer.\n");
		exit(EXIT_FAILURE);
	}

	N = atoi(argv[4]);
	
	/* 繰り返し回数の値が不正なとき  */
	if (N <= 0) {
		fprintf(stderr, "repeat must be set to a positive integer.\n");
		exit(EXIT_FAILURE);
	}
	
	B = T / 10;  /* 初期バイアス期間はシミュレーション時間の1割 */
	
	
	mu = 6.25 / 1000.0;  /* 単位時間あたりのサービス終了確率を設定 */

	lambda = rho * S * mu;  /* 単位時間あたりの到着確率を設定 */
	
	server =(CELL **)malloc(sizeof(CELL *) * S);
	
	if (server == NULL) {
		fprintf(stderr, "cannot allocate memories for server.\n");
		exit(EXIT_FAILURE);
	}
	
	avgLength = 0.0;      /* 平均系内客数の初期化 */
	avgWait = 0.0;        /* 平均滞在時間の初期化 */
	avgThroughput = 0.0;  /* 平均スループットの初期化 */
	
	srand(time(NULL));  /* 乱数の初期化 */
	
	/* N回だけシミュレーションを繰り返し*/
	for (n = 0; n <= N - 1; n++) {
		sumLength = 0;     /* 合計系内客数の初期化 */
		sumDeparture = 0;  /* 合計退去数の初期化 */
		sumWait = 0;       /* 合計滞在時間の初期化 */
		length = 0;        /* 系内客数の初期化 */
		head = NULL;       /* 待ち行列の先頭の初期化 */
		tail = NULL;       /* 待ち行列の末尾の初期化 */

		for (i = 0; i <= S - 1; i++) {
			server[i] = NULL;
		}
		
		for (t = 0; t <= T - 1; t++) {
			for (i = 0; i <= S - 1; i++) {
				if (server[i] != NULL && departure(mu)) {
					wait = t - dequeue(&server[i]);
					if (t >= B) {
						sumWait += wait;
						sumDeparture++;
					}
				
					length--;
				}
			}

			if (arrival(lambda)) {
				enqueue(&head, &tail, t);  
				length++;                  
			}
			
			for (i = 0; i <= S - 1; i++) {
				if (head != NULL && server[i] == NULL) {
					transmission(&head, &tail, &server[i]);
				}
			}
			
			if (t >= B) {
				sumLength += length;
			}
		}
		
		avgLength += (double)sumLength / (double)(T-B);
	
		if (sumDeparture >= 1) {
			avgWait += (double)sumWait / (double)sumDeparture;
		}
	
		avgThroughput += (double)sumDeparture / (double)(T-B);
		
		clear(head);
		
		for (i = 0; i <= S - 1; i++) {
			free(server[i]);
		}
	}
	
	avgLength /= (double)N;
	avgWait = avgWait / (double)N / 1000.0;
	avgThroughput = avgThroughput / (double)N * 1000.0;
	
	free(server);
	
	printf("%e,%d,%e,%e,%e\n", rho, S, avgLength, avgWait, avgThroughput);
	
	return EXIT_SUCCESS;	
}

int arrival(double lambda){
	double r; 
	r = (double)rand() / ((double)RAND_MAX+1.0);
	
	if (r < lambda) return 1;

	else return 0;
}

int departure(double mu){
	r = (double)rand() / ((double)RAND_MAX+1.0);
	
	if (r < mu) return 1;
	else return 0;

void clear(CELL *head)
{
	CELL *tmp;
	
	while (head != NULL) {
		tmp = head;
		head = head->next;
		free(tmp);
	}
}
}

と、ここまでプログラムとして完成しているという前提で、enqueue関数、dequeue関数、transmission関数を作れという問題なのですが、以下の通りにプログラムを作って動かしても、セグメントエラーや二重開放エラーが発生して、途中でプログラムが止まってしまいます。
どこがまずいのか、どこが間違っているのか、是非御教授いただけたらと思います。
enqueue関数は、待ち行列に新たなセルを挿入する関数。
dequeue関数は、待ち行列の先頭のセルを削除する関数。
tansmission関数は、待機している転送要求があり、かついずれかのサーバが空いている時、そのサーバにセルを送り出す関数です。

コード:

void enqueue(CELL **head, CELL **tail, int data)
{
  CELL *tmp;
  if((*head)==NULL){
    tmp = (CELL *) malloc(sizeof(CELL));
    tmp->data=data;
    tmp->next=NULL;
    *head = tmp;
    *tail = tmp;
    
  }
  else{
    tmp = (CELL *) malloc(sizeof(CELL));
    tmp->data=data;
    (*tail)->next = tmp;
    *tail = (*tail)->next;
  }
}

int dequeue(CELL **memory){
  
  int tmp;

  tmp=(*memory)->data;
  free(memory);
  memory == NULL;
  
  return tmp;
}


void transmission(CELL **head, CELL **tail, CELL **memory)
{
  *memory = *head;
  *head = (*head)->next;
  
  if((*head)==NULL) (*tail)==NULL;
}

[みけCAT]

dequeue関数でheadを更新していないのと、無意味な比較演算文が書かれているのが気になりますね。

[box]

無意味な比較演算文が書かれているのが気になりますね。

これは、transmission関数の最後の文も該当しそうですね。

[kranke]

今更ですが、このプログラムはM/M/S待ち行列の直列モデルです
dequeue関数は削除というよりもサーバのサービス完了処理だと思ってください

(1) enqueue関数で待ち行列にセルを追加
(2) 待ち行列にセルが存在し、かつメモリがNULLのサーバがあるかを探査
(3) (2)が満たされた時、transmission関数でそのサーバへ待ち行列のheadを送り、headをひとつ後ろへずらす
(4) サーバにセルが存在し、ランダムな条件を満たした時、そのサーバが参照しているセルのデータを返し、メモリを解放する
(5) (4)のちに再びサーバにNULLを代入し、transmission関数から新たなheadが送られてくるのを待機

稚拙な説明ですが、このような動きをするつもりです
もっと簡単に言えば、

複数あるレジ（サーバ）から空いているレジ(サーバ)を見つけ、そこへ行列の先頭にいる客(セル)を送る(transmission関数)
客(セル)が会計を終えて、金(データ)を返した後、レジ(サーバ)が空く(dequeue関数)
行列に客(セル)を追加する(enqueue関数)

……みたいな感じです

dequeue内のhead更新についてはよくわかりませんが、調べてみようと思います
transmissionについても同様に調べてみます

[box]

とりあえず、

コード:

  memory 『==』 NULL;
  if((*head)==NULL) (*tail)『==』NULL;

『』でくくった2箇所について、等号が本当に2個必要なのかどうか、チェックしてみてください。

[kranke]

コード:

 memory 『==』 NULL;
if((*head)==NULL) (*tail)『==』NULL;

『』でくくった2箇所について、等号が本当に2個必要なのかどうか、チェックしてみてください。

具体的な回答ありがとうございます。しかし修正しましても、未だうまく動きません
以下、修正しましたプログラムです。

コード:

/*
  サーバのメモリにある転送要求を削除する関数
  memory : サーバのメモリへのポインタ
  tail : 待ち行列の末尾への二重ポインタ
  戻り値 : 先頭のセルに格納されていたデータ

*/
int dequeue(CELL **memory)
{   
    int tmp; //data退避用

    tmp=(*memory)->data; //tmpに削除するセルのデータ値を挿入
    free(*memory); //メモリを解放
    (*memory) = NULL; 
  
  return tmp; //退避させたデータを返す
}


/*
  サーバに転送要求を転送する関数
  head : 待ち行列の先頭への二重ポインタ
  tail : 待ち行列の末尾への二重ポインタ
  memory : サーバが持つメモリへのポインタ
*/
void transmission(CELL **head, CELL **tail, CELL **memory){

  *memory = *head; //先頭のセルを参照させる
  *head = (*head)->next; //先頭を一つずらす
  
  if((*head)==NULL) (*tail)=NULL; //待ち行列が空になったら末尾にもNULLを入れる

}

[みけCAT]

dequeue関数でセルを削除したら、headまたはその周り(前)のセルのnextが指す先を更新しなければいけないのではないですか？

[kranke]

dequeue関数でセルを削除したら、headまたはその周り(前)のセルのnextが指す先を更新しなければいけないのではないですか？

dequeue関数ではheadを削除しませんので、更新は必要ないかなと思います
dequeue関数で削除するのはあくまでサーバのメモリに入っているセルのみで、待ち行列のhead自体は何も参照しません
nextを参照するのも、headを更新するのも、transmission関数にてheadをサーバに挿入した時のみかと思います

[みけCAT]

dequeue関数でセルを削除したら、headまたはその周り(前)のセルのnextが指す先を更新しなければいけないのではないですか？

dequeue関数ではheadを削除しませんので、更新は必要ないかなと思います
dequeue関数で削除するのはあくまでサーバのメモリに入っているセルのみで、待ち行列のhead自体は何も参照しません
nextを参照するのも、headを更新するのも、transmission関数にてheadをサーバに挿入した時のみかと思います

なるほど、transmission関数でセルをキューから外してサーバのメモリに入れているわけですね。
でしたら、そこは大丈夫そうに思えます。
関数名が紛らわしく感じますが、指定されているなら仕方ないでしょう。

[みけCAT]

enqueue関数で(*head)がNULLでないとき、tmp->nextにNULLを代入していないのがまずいかもしれません。

[kranke]

enqueue関数で(*head)がNULLでないとき、tmp->nextにNULLを代入していないのがまずいかもしれません。

おおおおおおおおお！
ありがとうございます。無事動きました。初歩的なミスで非常に恥ずかしい限りです。
お二方とも、こんな質問に長々とお付き合いいただきましてありがとうございました。大変助かりました。