作業系統作業

main.py

import copy


class Work:
    def __init__(self, name: int, todo: int, weight: int = 1, arrive_time: int = 0):
        self.name = name
        self.todo = todo
        self.weight = weight
        self.arrive = arrive_time

    def run(self) -> int:
        if self.todo == 1:
            self.todo = self.todo - 1
            return 0
        else:
            self.todo = self.todo - 1
            return self.todo

    def split(self) -> list:
        return [Split(self, x) for x in range(self.todo)]


class Split(Work):
    def __init__(self, father: Work, serial: int):
        super().__init__(father.name, father.todo, father.weight, father.arrive)
        self.serial = serial

    @property
    def is_last(self) -> bool:  # 這是最後一個工作了嗎？
        if self.serial == self.todo - 1:
            return True
        return False

    @property
    def remain(self) -> int:  # 包含自己的話還要做幾次
        return self.todo - self.serial


class MaxTime:
    time = 0

    def set(self, time_: int):
        if time_ > self.time:
            self.time = time_


max_time = MaxTime()
process = []
pro_c = int(input("請輸入欲排序的程序數：\n"))
while True:
    use_weight = input("要啟用優先權嗎？(Y/N)：\n")
    if use_weight == "Y" or use_weight == "N":
        if use_weight == "Y":
            use_weight = True
        else:
            use_weight = False
        break
    else:
        print("不正確的輸入")
for i in range(pro_c):
    time = int(input(f"輸入程序P{i}到達時間：\n"))
    todo = int(input(f"輸入程序P{i}需費時間：\n"))
    if use_weight:
        weight = int(input(f"輸入程序P{i}權重(0~)：\n"))
    else:
        weight = 0
    max_time.set(time)
    process.append(Work(i, todo, weight, time))

input_sort_by_arrive_time = []  # 依照到達時間排序
for i in range(max_time.time + 1):
    for j in process:
        if j.arrive == i:
            input_sort_by_arrive_time.append(j)


# 很直觀的循序執行，但是若沒有到達的話不會做
def chose1(proces_, log, clock=0):
    if len(proces_) == 0:
        # print("沒有工作了")
        return log
    if proces_[0].arrive > clock:
        clock = clock + 1
        log.append("X")
    else:
        # print(f"程式{proces_[0].name}等待執行時間為{clock}")
        clock = clock + proces_[0].todo
        for t in range(proces_[0].todo):
            log.append(proces_[0].name)
        proces_.pop(0)
    chose1(proces_, log, clock)


print("=====First-Come,First-Served======")
c1_log = []  # 執行甘特圖
c1_input = []
for i in copy.deepcopy(process):  # 去除到達時間
    i.arrive = 0
    c1_input.append(i)
chose1(c1_input, c1_log)
print(c1_log)
wait_time = 0
for i in range(1, len(c1_log)):
    if c1_log[i-1] != c1_log[i]:
        wait_time = wait_time + i
wait_time = wait_time / pro_c
print(f"平均等待時間：{wait_time}")


print("=====Shortest-Job-First=====")
c2_input = []
for i in copy.deepcopy(process):
    i.arrive = 0
    c2_input.append(i)
c2_input.sort(key=lambda x: x.todo)  # 依照短的先做

c2_log = []
chose1(c2_input, c2_log)
print(c2_log)
wait_time = 0
for i in range(1, len(c2_log)):
    if c2_log[i-1] != c2_log[i]:
        wait_time = wait_time + i
        print(i)
wait_time = wait_time / pro_c
print(f"平均等待時間：{wait_time}")


print("=====Shortest-remaining-time-first=====")
work_split = []
for i in copy.deepcopy(process):
    work_split = work_split + i.split()
c3_clock = 0
c3_log = []
while len(work_split) != 0:  # 做完前繼續
    arrived_work_split = []  # 已到達的工作
    for i in work_split:
        if i.arrive <= c3_clock:
            arrived_work_split.append(i)

    #  如果目前沒有任何東西到達
    if len(arrived_work_split) == 0:
        c3_clock = c3_clock + 1
        c3_log.append("X")
        continue

    # 找出程序中所剩下分片中最大的，從最大開始做下去
    c3_split_max = {}
    for i in arrived_work_split:
        # 注意要先取出工作的分片最大值
        if i.name in c3_split_max:
            if i.remain > c3_split_max[i.name].remain:
                c3_split_max[i.name] = i
        else:
            c3_split_max[i.name] = i

    max_remain_by_work = list(c3_split_max.values())  # 這個List會包含所有程序的最大分片
    do_object = None
    min_remain = 999999999
    for i in max_remain_by_work:
        if i.remain < min_remain:
            min_remain = i.remain

    for i in max_remain_by_work:
        if i.remain == min_remain:
            c3_log.append(i.name)
            work_split.remove(i)
            break
    c3_clock = c3_clock + 1

print(c3_log)
wait_time = 0
for i in range(1, len(c3_log)):
    if c3_log[i-1] != c3_log[i]:
        wait_time = wait_time + i
wait_time = wait_time / pro_c
print(f"平均等待時間：{wait_time}")

print('=====Priority Scheduling=====')
c4_process = copy.deepcopy(process)
c4_process.sort(key=lambda x: x.weight)
c4_log = []  # 執行甘特圖
c4_input = []
for i in c4_process:
    i.arrive = 0
    c4_input.append(i)
chose1(c4_input, c4_log)
print(c4_log)
wait_time = 0
for i in range(1, len(c4_log)):
    if c4_log[i-1] != c4_log[i]:
        wait_time = wait_time + i
        print(i)
wait_time = wait_time / pro_c
print(f"平均等待時間：{wait_time}")


print('=====Round Robin=====')
round_len = int(input("輸入一個時間片段的長度\n"))
c5_queue = copy.deepcopy(process)
c5_log = []
while len(c5_queue) != 0:
    work = c5_queue.pop(0)
    for _ in range(round_len):
        if work.run() != 0:
            c5_log.append(work.name)
        else:
            c5_log.append(work.name)
            break
    if work.todo > 0:
        c5_queue.append(work)
print(c5_log)