problem

实验内容：

编写一个单处理机下的进程调度程序，模拟操作系统对进程的调度。

要求：

能够创建指定数量的进程，每个进程由一个进程控制块表示。
实现先来先服务调度算法：进程到达时间可由进程创建时间表示。
实现短作业优先调度算法：可指定进程要求的运行时间。（说明：对不可剥夺的短作业优先算法，当作业运行时间相等时，优先调度进程号小的进程执行；对可剥夺式的短作业优先算法，即选最短剩余时间的进程进行运行，在剩余时间相同的情况下，选择到达时间早的进程进行运行）

实现时间片轮转调度算法：可指定生成时间片大小。（说明：新进程到来时插入到就绪队列的队尾，当进程P运行完一个时间片时，若同时有进程Q到达，则先在就绪队列队尾插入新到达的进程Q，之后再插入进程P)

实现动态优先级调度算法：可指定进程的初始优先级（优先级与优先数成反比，优先级最高为0），优先级改变遵循下列原则：进程在就绪队列中每停留一个时间片，优先级加1，进程每运行一个时间片，优先级减3。（说明：本算法在优先级相同的情况下，选择到达时间早的进程进行运行）

测试用例格式如下：

输入：调度算法

进程号/到达时间/运行时间/优先级/时间片

输出：调度顺序/进程号/开始运行时间/结束运行时间/优先级

其中调度算法选项为：1----先来先服务，2----短作业优先，3----最短剩余时间优先，4----时间片轮转，5----动态优先级

测试用例

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

        # 最短剩余时间优先


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()