問題
要点
キュー（queue）あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。 データを先入れ先出しのリスト構造で保持するものである。 キューからデータを取り出すときには、先に入れられたデータから順に取り出される。 キューにデータを入れることをエンキュー、取り出すことをデキューという。
つまり、ところてん方式
ラウンドロビン1スケジューリングは、プロセスを格納（管理）するキューを用いてシミュレートすることができる。まず、初期状態のプロセスを順番にキューに入れる。次にキューが空になるまで、「先頭からプロセスを取り出し、最大でもクオンタム2だけ処理を行い、まだ必要な処理（時間）が残っている場合は再度キューに追加する」処理を繰り返す。
キューの操作
- enqueue(x)
- キューの末尾に要素xを追加する。
- dequeue()
- キューの先頭から要素を取り出す。
- isEmpty()
- キューが空かどうか調べる。
- isFull()
- キューが満杯かどうか調べる。
実装
- Q
- データを格納するための整数型1次元配列
- head
- 先頭ポインタである整数型変数
- tail
- 末尾ポインタである整数型変数
- enqueue(x)
- キューに要素を追加する関数
- dequeue()
- キューの先頭から要素を取り出す関数
コード
#include <stdio.h>
#include <string.h>
#define LEN 100000
typedef struct
{
char name[100];
int time;
} Process;
/* global variable */
static Process Q[LEN];
static int head, tail, n;
/* enqueue */
void enqueue(Process process_obj)
{
Q[tail] = process_obj;
tail = (tail + 1) % LEN;
}
/* dequeue */
Process dequeue()
{
Process process_obj;
process_obj = Q[head];
head = (head + 1) % LEN;
return process_obj;
}
int min(int a, int b) { return a < b ? a : b; }
int main(void)
{
int elapse_time = 0;
int time_ms;
int qms;
Process process_obj;
/* input */
scanf("%d %d", &n, &qms);
for (int i = 1; i <= n; i++)
{
scanf("%s", Q[i].name);
scanf("%d", &Q[i].time);
}
/* initialize */
head = 1;
tail = n + 1;
while (head != tail)
{
process_obj = dequeue();
time_ms = min(qms, process_obj.time);
process_obj.time -= time_ms;
elapse_time += time_ms;
if (process_obj.time > 0)
enqueue(process_obj);
else
printf("%s %d\n", process_obj.name, elapse_time);
}
return 0;
}
ポイント
- 使われなかったクオンタムが持ち越されることはない。
- 20 - 100 = 0となってループが進んでいく。
- モジュロ演算をすることでキューが円環状につながってループする。
所感
- 見ていた解説の変数名が簡略化されすぎていたので、補った。
- 丁寧にデバッグしながらでないと理解できなかった。
- 円環の形をイメージすると、headとtailの概念がわかりにくくなるので、ところてん式のイメージを持って、取り出し→処理→格納の感覚でみた方がよい。
所要時間 180分
【復習】
- 2020/04/05
- 自分で書いたら下記の書き方になった。こっちのほうが良さそう。
- キューを全体を操作するのではなく、headとtailを操作する。
- モジュロ演算でキューをクリアしながら使うという考え方は忘れていた
- 未実装
- 所要時間：80分
while (head != tail)
{
process_obj = dequeue();
if(process_obj.time > qms){
process_obj.time -= qms;
elapse_time += qms;
enqueue(process_obj);
} else {
elapse_time += process_obj.time;
printf("%s %d\n", process_obj.name, elapse_time);
}
}