令和７年度東京大学大学院情報理工学系研究科修士課程・博士後期課程入学試験
筆記試験における出題ミスについて
東京大学大学院情報理工学系研究科
このたび、令和７年度大学院情報理工学系研究科入学試験（一般選抜及び社会人特別選抜、夏入試）において、コンピュータ科学専攻筆記試験（専門科目）の試験問題の一部に出題ミスがあることが判明いたしました。出題ミスの内容及び本研究科の対応は次のとおりです。
今後、再びこのような事態が起こらぬよう必要な対策を講じ、再発防止に取り組んでまいります。
１

出題ミスの内容
専門科目の問題３（別紙参照）中の(c)のケースについて、小問(1)(3)(4)に意図せず２通りの正解があった。
なお、小問(2)については、小問(1)に連動して２通りの計算過程が存在するものの、最終的な正解は同一である。

２

出題ミスへの対応
問題３(c)のケースでは、２通りのいずれの解答も正解とし、それ以外の解答は不正解として採点を行った。この措置により、入学試験の合否判定において不利益を被る受験者がないよう対応した。

別紙問題3
オペレ ー ティングシステムにおける，プロセス �(i=1,2,3,4,5) のスケジュ ー リングを考える．

Pi,P2,P3 ,P4,P5 の到着時刻はそれぞれ 0, 5, 10, 15, 20, 処理時間は 40, 60, 30, 40, 10 である． 次の 4 つのスケジュ ー リングアルゴリズムを考える ． （a) first come, first serve (FCFS), (b) (non­preemptive) shortest job first (SJF), (c) shortest remaining time first (SRTF), (d) round robin(RR) (time quantum は 30)． ただし，一度に実行できるプロセスは一つだけで，言及のないコストは無視できるものとする．

また，バイナリセマフォ的(j=1,2) を取得解放するための操作をそれぞれ wait(Sj ), signal(Sj )とする． 操作 wait(Sj ) は，Sを取得できなかったら，実行したプロセスをふの待ちキュ ー の末尾に入れる． 操作 signal(Sj ) は，Sj を解放したあと，的の待ちキュ ー が空でなければ，その先頭のプロセスを実行可能キュ ー に移動する．
なお，プロセスの待ち時間は，実行可能キュ ー または Sj (j = 1, 2) の待ちキュ ー で待つ時間の合計とする． プロセスの平均待ち時間とは，各プロセス� (i=1,2,3,4,5) の待ち時間の平均のことである ．

(a)-(d) のそれぞれのスケジュ ー リングアルゴリズムについて，以下の問いに答えよ． ただし，以下の問い (1), (2) では，プロセスはセマフォ操作はおこなわないものとする ．

P140

P2

1100

P3

凡一ズ。

(1) �(i=l,2,3,4,5) がスケジュ ー ルされる時刻を，以下のようなガントチャ ー トの形で描け．
9130170 180(2) プロセスの平均待ち時間を求めよ．
(3) P1 ,P3 ,P計ま起動時に wait(Sリ，終了時に signal(S1 ) をそれぞれ実行し，P2 ，凡はセマフォ操作をおこなわないとする． このときのプロセスの平均待ち時間を求めよ．

(4) piが以下のようにセマフォ操作をおこなう場合を考える．

• P1 と杓は，起動時に wait （ふ），実行時間が 15 経過後に wait(S叫，終了時に signal(S砂及び signal(Sリ をこの順に実行する ．

• P3 と凡は，起動時に wait(S叫，実行時間が 15 経過後に wait(S1 )，終了時に signal(Sリ及び signal(S2) をこの順に実行する．
• P5 はセマフォ操作をおこなわない．

このとき，デッドロックが発生する場合はその発生時刻を求めよ． デッドロックが発生しない
場合はプロセスの平均待ち時間を求めよ．

Problem 3
Consider the scheduling of processes Pi (i = 1, 2, 3, 4, 5) in an operating sy stem.

The arrival

times of A, P2, P3, P4 and Ps are 0, 5, 10, 15 and 20, and processing times are 40, 60, 30, 40 and10, respectively. We consider the following four scheduling algorithms: (a) first come, first serve(FCFS), (b) (non-preemptive) shortest job first (SJF), (c) shortest remaining time first (SRTF),and (d) round robin (RR) (time quantum is 30). Here, we assume that only one process can run
at a time and unmentioned costs can be ignored.

Also, the operations to acquire and release binary semaphores Sj (j = 1, 2) are denoted aswait（ふ） and signal(Sj), respectively. If the operation wait(Sj) cannot acquire Sj, it puts theexecuting process at the end of the waiting queue for Si. The operation signal(Sj) releases Sj,
and if the waiting queue for Sj is non-empty, then the first process in the waiting queue is moved
to the ready queue.
Here, the waiting time of a process is the total amount of time the process spends waiting in theready queue or the waiting queue for Sj (j = 1, 2). The average waiting time of the processes isthe average of the waiting time of each process Pi (i = 1, 2, 3, 4, 5).

For each of the scheduling algorithms (a) to (d), answer the following questions. In questions(1) and (2), assume that the processes do not perform any semaphore operations.

゜(1) Draw the time Pi (i = 1, 2, 3, 4, 5) is scheduled in the form of a Gantt chart as shown below.
P1

40

P2

100

p3

P4

130170 180(2) Calculate the average waiting time of the processes.
(3) Suppose that A, P3, and A perform wait(S1) at startup and signal(S1) at termination,respectively, and P2 and P4 do not perform any semaphore operations. Calculate the average
waiting time of the processes in this case.

(4) Consider the case where Pi performs semaphore operations as follows.

• A and P2 perform wait(S1) at startup, wait(S2) after a runtime of 15 elapsed, andsignal(S2) and signal(S1) at termination in this order.
• P3 and P4 perform wait(S刃at startup, wait(S1) after a runtime of 15 elapsed, andsignal(S1) and signal(S砂at termination in this order.
• Ps does not perform any semaphore operations.
In this case, if a deadlock occurs, find the time when the deadlock occurs. If no deadlock
occurs, calculate the average waiting time of the processes.