problem
實(shí)驗(yàn)內(nèi)容：
編寫(xiě)一個(gè)單處理機(jī)下的進(jìn)程調(diào)度程序抹恳，模擬操作系統(tǒng)對(duì)進(jìn)程的調(diào)度有额。
要求：
能夠創(chuàng)建指定數(shù)量的進(jìn)程，每個(gè)進(jìn)程由一個(gè)進(jìn)程控制塊表示慕蔚。
實(shí)現(xiàn)先來(lái)先服務(wù)調(diào)度算法：進(jìn)程到達(dá)時(shí)間可由進(jìn)程創(chuàng)建時(shí)間表示丐黄。
實(shí)現(xiàn)短作業(yè)優(yōu)先調(diào)度算法：可指定進(jìn)程要求的運(yùn)行時(shí)間。（說(shuō)明：對(duì)不可剝奪的短作業(yè)優(yōu)先算法孔飒，當(dāng)作業(yè)運(yùn)行時(shí)間相等時(shí)灌闺，優(yōu)先調(diào)度進(jìn)程號(hào)小的進(jìn)程執(zhí)行；對(duì)可剝奪式的短作業(yè)優(yōu)先算法坏瞄，即選最短剩余時(shí)間的進(jìn)程進(jìn)行運(yùn)行桂对，在剩余時(shí)間相同的情況下，選擇到達(dá)時(shí)間早的進(jìn)程進(jìn)行運(yùn)行）
實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法：可指定生成時(shí)間片大小鸠匀。（說(shuō)明：新進(jìn)程到來(lái)時(shí)插入到就緒隊(duì)列的隊(duì)尾蕉斜，當(dāng)進(jìn)程P運(yùn)行完一個(gè)時(shí)間片時(shí)，若同時(shí)有進(jìn)程Q到達(dá)，則先在就緒隊(duì)列隊(duì)尾插入新到達(dá)的進(jìn)程Q宅此，之后再插入進(jìn)程P)
實(shí)現(xiàn)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法：可指定進(jìn)程的初始優(yōu)先級(jí)（優(yōu)先級(jí)與優(yōu)先數(shù)成反比机错，優(yōu)先級(jí)最高為0），優(yōu)先級(jí)改變遵循下列原則：進(jìn)程在就緒隊(duì)列中每停留一個(gè)時(shí)間片父腕，優(yōu)先級(jí)加1弱匪，進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先級(jí)減3璧亮。（說(shuō)明：本算法在優(yōu)先級(jí)相同的情況下萧诫，選擇到達(dá)時(shí)間早的進(jìn)程進(jìn)行運(yùn)行）
測(cè)試用例格式如下：
輸入：調(diào)度算法
進(jìn)程號(hào)/到達(dá)時(shí)間/運(yùn)行時(shí)間/優(yōu)先級(jí)/時(shí)間片
輸出：調(diào)度順序/進(jìn)程號(hào)/開(kāi)始運(yùn)行時(shí)間/結(jié)束運(yùn)行時(shí)間/優(yōu)先級(jí)
其中調(diào)度算法選項(xiàng)為：1----先來(lái)先服務(wù)，2----短作業(yè)優(yōu)先枝嘶，3----最短剩余時(shí)間優(yōu)先帘饶，4----時(shí)間片輪轉(zhuǎn)，5----動(dòng)態(tài)優(yōu)先級(jí)
測(cè)試用例
| 測(cè)試輸入 | 期待的輸出 |
|---|---|
| 1 1/0/24/1/1 2/0/3/1/1 3/0/3/1/1 |
1/1/0/24/1 2/2/24/27/1 3/3/27/30/1 |
| 2 1/0/7/1/1 2/2/4/1/1 3/4/1/1/1 4/5/4/1/1 |
1/1/0/7/1 2/3/7/8/1 3/2/8/12/1 4/4/12/16/1 |
| 3 1/0/7/1/1 2/2/4/1/1 3/4/1/1/1 4/5/4/1/1 |
1/1/0/2/1 2/2/2/4/1 3/3/4/5/1 4/2/5/7/1 5/4/7/11/1 6/1/11/16/1 |
| 4 1/0/53/1/20 2/0/17/1/20 3/0/68/1/20 4/0/24/1/20 |
1/1/0/20/1 2/2/20/37/1 3/3/37/57/1 4/4/57/77/1 5/1/77/97/1 6/3/97/117/1 7/4/117/121/1 8/1/121/134/1 9/3/134/154/1 10/3/154/162/1 |
| 5 1/0/3/1/2 2/0/4/1/2 3/0/2/3/2 4/2/1/1/2 5/2/4/4/2 |
1/1/0/2/4 2/2/2/4/3 3/4/4/5/3 4/3/5/7/3 5/1/7/8/4 6/2/8/10/3 7/5/10/12/3 8/5/12/14/6 |
ac code
# -*- coding: utf-8 -*-：
import Queue
class Thread:
id,arrive, cost, priority, time, done = 0, 0, 0, 0, 0, False
def __init__(self, param):
self.id = param[0]
self.arrive = param[1]
self.cost = param[2]
self.priority = param[3]
self.time = param[4]
def inputThread():
threads,num = [], 0
while True:
try:
threads.append(Thread(raw_input().split("/")))
num += 1
except:
break
return threads, num
def output(logidx, tid, tstart, tend, tpriority):
print str(logidx) + '/' + str(tid) + '/' + str(tstart) + '/' + str(tend) + '/' + str(tpriority)
def cmp_arrive_id(x, y):
if int(x.arrive) == int(y.arrive):
return int(x.id) - int(y.id)
return int(x.arrive) - int(y.arrive)
def cmp_cost_id(x, y):
if int(x.cost) == int(y.cost):
return int(x.id) - int(y.id)
return int(x.cost) - int(y.cost)
def cmp_arrive_cost_id(x, y):
if int(x.arrive) == int(y.arrive):
if int(x.cost) == int(y.cost):
return int(x.id) - int(y.id)
return int(x.cost) - int(y.cost)
return int(x.arrive) - int(y.arrive)
def fcfs():
threads, num = inputThread()
threads.sort(cmp_arrive_id)
time,idx = 0, 1
for ech in threads:
if time < int(ech.arrive):
time = int(ech.arrive)
endtime = time + int(ech.cost)
output(idx, ech.id, time, endtime, ech.priority)
time, idx = endtime, idx + 1
def sjf():
threads, num = inputThread()
threads.sort(cmp_arrive_cost_id)
time, m, idx = int(threads[0].arrive), 0, 1
while m < num:
thds = [fl for fl in threads if int(fl.arrive) <= time and not bool(fl.done)]
if len(thds) == 0:
tmp = [fl for fl in threads if not bool(fl.done)]
tmp.sort(cmp_arrive_id)
time = int(tmp[0].arrive)
continue
thds.sort(cmp_cost_id)
cur = thds[0]
output(idx, cur.id, time, time + int(cur.cost), cur.priority)
time,thds[0].done, m, idx = time + int(cur.cost), True, m + 1, idx + 1
def rr():
threads, num = inputThread()
threads.sort(cmp_arrive_id)
tq = Queue.Queue()
time, idx, m, i = int(threads[0].arrive), 1, 0, 0
while m < num:
if tq.empty():
time = int(threads[i].arrive)
while i < num and int(threads[i].arrive) <= time:
tq.put(threads[i])
i += 1
ech = tq.get()
if int(ech.time) < int(ech.cost):
output(idx, ech.id, time, time + int(ech.time), ech.priority)
idx, time = idx + 1, time + int(ech.time)
ech.cost = int(ech.cost) - int(ech.time)
while i < num and int(threads[i].arrive) <= time:
tq.put(threads[i])
i += 1
tq.put(ech)
continue
output(idx, ech.id, time, time + int(ech.cost), ech.priority)
idx += 1
ech.done = True
time = time + int(ech.cost)
while i < num and int(threads[i].arrive) <= time:
tq.put(threads[i])
i += 1
m += 1
# 最短剩余時(shí)間優(yōu)先
def srt():
threads, num = inputThread()
threads.sort(cmp_arrive_cost_id)
threads.append(Thread([0, 0, 0, 0, 0]))
time = int(threads[0].arrive)
execi = -1
start = time
m = 0
idx = 1
i = 0
while m < num:
while int(threads[i].arrive) <= time and i < num:
i += 1
min = 99999999999999999999999999999999999999999999
mini = -1
j = 0
for j in range(i):
if int(threads[j].cost) < min and not bool(threads[j].done):
min = int(threads[j].cost)
mini = j
if mini == -1:
time = int(threads[i].arrive)
continue
if execi == -1:
execi = mini
start = int(threads[execi].arrive)
if int(threads[execi].arrive) < time:
start = time
if int(threads[mini].cost) < int(threads[execi].cost):
output(idx, threads[execi].id, start, time, threads[execi].priority)
idx += 1
execi = mini
start = time
runnable = int(threads[i].arrive) - time
if runnable >= int(threads[execi].cost) or runnable <= 0:
time += int(threads[execi].cost)
output(idx, threads[execi].id, start, time, threads[execi].priority)
idx += 1
threads[execi].cost = 0
threads[execi].done = True
m += 1
execi = -1
start = time
else:
time += runnable
threads[execi].cost = int(threads[execi].cost) - runnable
def dp():
threads, num = inputThread()
threads.sort(cmp_arrive_id)
time,last, m, idx = int(threads[0].arrive), int(threads[0].arrive), 0, 1
while m < num:
i = 0
while i < num and int(threads[i].arrive) <= time:
if last < int(threads[i].arrive) < time:
if int(threads[i].priority) > 1:
threads[i].priority = int(threads[i].priority) - 1
else:
threads[i].priority = 0
i += 1
min, mini = 99999999999999999999, -1
for j in range(i):
if int(threads[j].priority) < min and not bool(threads[j].done):
min, mini = int(threads[j].priority), j
if mini == -1:
time = int(threads[i].arrive)
continue
last = time
if int(threads[mini].cost) <= int(threads[mini].time):
output(idx, threads[mini].id, time, time + int(threads[mini].cost), int(threads[mini].priority) + 3)
idx, m, time, threads[mini].done = idx + 1, m + 1, time + int(threads[mini].cost), True
else:
output(idx, threads[mini].id, time, time + int(threads[mini].time), int(threads[mini].priority) + 3)
idx, time, threads[mini].cost = idx + 1, time + int(threads[mini].time), int(threads[mini].cost) - int(threads[mini].time)
for j in range(i):
if not bool(threads[j].done):
if j == mini:
threads[j].priority = int(threads[j].priority) + 3
else:
if int(threads[j].priority) > 1:
threads[j].priority = int(threads[j].priority) - 1
else:
threads[j].priority = 0
if __name__ == '__main__':
method = input()
if method == 1:
fcfs()
elif method == 2:
sjf()
elif method == 3:
srt()
elif method == 4:
rr()
elif method == 5:
dp()
