def cipandiaodu():
    # 磁盘调度
    n = int(input("请输入进程数："))

    zhizhen = int(input("请输入指针初始位置："))
    yemian = []
    yemian1 = []
    yemian2 = []
    yemian41 = []

    def cunfang():  # 数据的存放
        for i in range(n):
            jincheng = int(input("请输入第%d进程所在位置" % (i + 1)))
            yemian.append([jincheng, 0])
            yemian41.append([0, 0])
        print("您输入的界面信息为:")
        print(yemian)

    def first():
        global zhizhen
        zhizhen1 = zhizhen
        yidong = 0
        yemian1 = yemian[:]
        for i in range(n):
            yemian1[i][1] = abs(float(zhizhen1) - float(yemian1[i][0]))
            yidong = yidong + yemian[i][1]
            zhizhen1 = yemian1[i][0]
        print("所得fcfs磁盘调度结果：")
        print(yemian1)
        yidong = float(yidong / n)
        print("平均寻道长度为：%0.1f" % (yidong))

    def zhen():  # 排序等简单处理
        global zhizhen
        global zhi
        zhi = 0
        yidong = 0
        zhizhen1 = zhizhen
        yemian2 = yemian3[:]
        global qian
        qian = []
        global hou
        hou = []
        global right
        right = 0
        for i in range(n):
            if (zhizhen1 <= yemian2[i][0]):  # 问题：如果指针初始位置恰好在某一进程位置，会怎样？
                yidong = yemian2[i][0]
                zhi = i
                break
        if (yidong == zhizhen1):
            if (abs(yidong - yemian2[zhi - 1][0]) < abs(yidong - yemian2[zhi + 1][0])):
                zhi = zhi
                right = 1
            else:
                zhi = zhi - 1
        else:

            if (abs(zhizhen1 - yemian2[zhi - 1][0]) < abs(zhizhen1 - yemian2[zhi][0])):
                right = 1
            else:
                right = 0
            zhi = zhi - 1
        qian = yemian2[0:zhi + 1]
        hou = yemian2[zhi + 1:]

    def sstf():
        global yemian41
        yemian4 = yemian41[:]
        global zhizhen
        zhizhen1 = zhizhen
        global right
        global zhi
        global qian
        qian1 = qian[:]
        global hou
        ppp = 0
        global n
        hou1 = hou[:]
        qqq = 0
        zhi1 = zhi

        if (right == 1):
            while (zhi1 >= 0):
                yemian4[ppp][0] = qian1[zhi1][0]
                yemian4[ppp][1] = zhizhen1 - qian1[zhi1][0]
                zhizhen1 = yemian4[ppp][0]
                zhi1 = zhi1 - 1
                ppp = ppp + 1
            ppp = 0
            zhi1 = zhi + 1
            while (zhi1 < n):
                yemian4[zhi1][0] = hou1[ppp][0]
                yemian4[zhi1][1] = hou1[ppp][0] - zhizhen1
                zhizhen1 = hou1[ppp][0]
                zhi1 = zhi1 + 1
                ppp = ppp + 1

        else:
            zhi1 = zhi
            ppp = 0
            zhizhen1 = zhizhen
            while (ppp < n - zhi1 - 1):
                yemian4[ppp][0] = hou1[ppp][0]
                yemian4[ppp][1] = hou1[ppp][0] - zhizhen1
                zhizhen1 = hou1[ppp][0]
                ppp = ppp + 1

            while (zhi1 >= 0):
                yemian4[ppp][1] = zhizhen1 - qian1[zhi1][0]
                yemian4[ppp][0] = qian[zhi1][0]
                zhi1 = zhi1 - 1
                zhizhen1 = qian[zhi1][0]
                ppp = ppp + 1
        print("所得sstf磁盘调度结果：")
        print(yemian4)
        for i in range(n):
            qqq = qqq + yemian4[i][1]
        qqq = float(qqq / n)
        print("平均寻道长度为：%0.1f" % (qqq))

    def scan():
        global zhizhen
        zhizhen1 = zhizhen
        global yemian3
        yemian2 = yemian3[:]
        zhi3 = 0
        ppp = 0
        for i in range(n):
            if (zhizhen1 <= yemian2[i][0]):  # 问题：如果指针初始位置恰好在某一进程位置，会怎样？

                zhi3 = i
                break
        zhi4 = zhi3
        global yemian41
        while (zhi4 < n):
            yemian41[ppp][0] = yemian2[zhi4][0]
            yemian41[ppp][1] = yemian2[zhi4][0] - zhizhen1
            zhizhen1 = yemian2[zhi4][0]
            ppp = ppp + 1
            zhi4 = zhi4 + 1
        zhi4 = zhi3 - 1
        while (zhi4 >= 0):
            yemian41[ppp][0] = yemian2[zhi4][0]
            yemian41[ppp][1] = zhizhen1 - yemian2[zhi4][0]
            zhizhen1 = yemian2[zhi4][0]
            ppp = ppp + 1
            zhi4 = zhi4 - 1
        qqq = 0
        print("所得scan磁盘调度结果：")
        print(yemian41)
        for i in range(n):
            qqq = qqq + yemian41[i][1]
        qqq = float(qqq / n)
        print("平均寻道长度为：%0.1f" % (qqq))

    def cscan():
        global zhizhen
        zhizhen1 = zhizhen
        global yemian3
        yemian2 = yemian3[:]
        zhi3 = 0
        ppp = 0
        qqq = 0
        for i in range(n):
            if (zhizhen1 <= yemian2[i][0]):  # 问题：如果指针初始位置恰好在某一进程位置，会怎样？

                zhi3 = i
                break
        zhi4 = zhi3
        global yemian41
        while (zhi4 < n):
            yemian41[ppp][0] = yemian2[zhi4][0]
            yemian41[ppp][1] = yemian2[zhi4][0] - zhizhen1
            zhizhen1 = yemian2[zhi4][0]
            ppp = ppp + 1
            zhi4 = zhi4 + 1
        zhi4 = zhi3
        while (qqq < zhi4):
            yemian41[ppp][0] = yemian2[qqq][0]
            yemian41[ppp][1] = abs(zhizhen1 - yemian2[qqq][0])
            zhizhen1 = yemian2[qqq][0]
            ppp = ppp + 1
            qqq = qqq + 1
        print("所得cscan磁盘调度结果：")
        print(yemian41)
        qqq = 0
        for i in range(n):
            qqq = qqq + yemian41[i][1]
        qqq = float(qqq / n)
        print("平均寻道长度为：%0.1f" % (qqq))

    if __name__ == '__main__':
        cunfang()
        yemian3 = yemian[:]
        yemian3.sort(key=lambda x: x[0], )
        print("进行简易排序：")
        print(yemian3)
        sss = 0
        zhen()
        while (sss == 0):
            print("请输入1，2，3，4选择FCFS。SSTF.SCAN.CSCAN等算法，其余终止程序(输入):")
            rrr = int(input())
            if (rrr == 1):
                first()
            elif (rrr == 2):
                sstf()
            elif (rrr == 3):
                scan()
            elif (rrr == 4):
                cscan()
            else:
                print("运行结束！")
                sss = 1


def zuoyediaodu():
    pcb = []  # 生成列表，存放信息
    n = int(input("请输入进程数:"))  # 进程数输入

    def inpcb():  # 相关数据输入与存放
        i = 0
        while (i < n):
            NAME = input("请输入第%d个进程名:" % (i + 1))
            ARRIVE = float(input("请输入到达时间:"))
            SERVICE = float(input("请输入服务时长:"))
            pcb.append([NAME, ARRIVE, SERVICE, 0, 0, 0, 0])
            # 名字，到达时间，服务时长，开始，结束，平均周转，平均带权周转
            i = i + 1

    def FCFS():
        pcb.sort(key=lambda x: x[1], reverse=False)
        for i in range(n):  # 计算开始结束时刻
            if (i == 0):
                pcb[i][3] = pcb[i][1]
                pcb[i][4] = pcb[i][1] + pcb[i][2]
            elif (i > 0 and pcb[i - 1][4] < pcb[i][1]):
                pcb[i][3] = pcb[i][1]
                pcb[i][4] = pcb[i][1] + pcb[i][2]
            else:
                pcb[i][3] = pcb[i - 1][4]
                pcb[i][4] = pcb[i - 1][4] + pcb[i][2]
            i = i + 1
        ZZ = 0
        DZZ = 0
        for i in range(n):  # 计算周转，带权周转时间
            ZZ = float(ZZ + (pcb[i][4] - pcb[i][1]))
            DZZ = float(DZZ + (pcb[i][4] - pcb[i][1]) / (pcb[i][2]))
        print("运行结果:")
        for i in range(n):
            print("时刻:%0.2f 程序名:%s 到达:%0.2f 服务:%0.2f 开始:%0.2f 结束:%0.2f " \
                  % (pcb[i][3], pcb[i][0], pcb[i][1], pcb[i][2], pcb[i][3], pcb[i][4]))
        print("平均周转时间:%0.2f" % (ZZ / n))
        print("平均带权周转时间:%0.2f" % (DZZ / n))

    if __name__ == '__main__':
        inpcb()
        FCFS()


def yemianzhihuan():
    # 页面置换的三种算法——Optimal,FIFO,LRU
    # 列表中每一行的后两位“0“有特殊作用
    # werite by he
    yemian = []
    kuai = []
    n = int(input("请输入页面总数量:"))
    m = int(input("请输入可用块数:"))

    def inyemian():  # 页面编号的输入
        for i in range(n):
            name1 = int(input("请依次顺序输入第%d个页面的页面号(非负整数):" % (i + 1)))
            yemian.append(name1)
        print("页面号引用串:")
        print(yemian)
        print("$$$$$$$$$$$$$$$$$$$$")

    def diaoru1():  # 开始进行页面的分配(调入)，所有算法都要按照相同的调入算法
        global diaoru
        diaoru = 0
        global xuhao
        xuhao = 0
        aaa = 1

        for i in range(n):

            if (aaa <= m):
                print("当前为第%d页面(从1开始编号),页面号为%d" % ((i + 1), yemian[i]))
                if (i == 0):
                    print("发生调入:")
                    diaoru = diaoru + 1
                    kuai.append([yemian[0], 0, 0])
                    aaa = aaa + 1
                    print(kuai)
                    xuhao = xuhao + 1

                else:
                    bbb = 0
                    for e in range(aaa - 1):  # 此处aaa-1不可用i
                        if (kuai[e][0] == yemian[i]):  # question
                            bbb = bbb + 1
                            break
                    if (bbb == 0):
                        print("发生缺页，调入结果:")
                        diaoru = diaoru + 1
                        kuai.append([yemian[i], 0, 0])  # 此处两个零在不同的页面置换算法中将有不同的作用
                        print(kuai)
                        aaa = aaa + 1
                        xuhao = xuhao + 1

                    elif (bbb != 0):
                        print("此时命中，无需调入")
                        print(kuai)
                        xuhao = xuhao + 1
            else:
                break
        print("$$$$$$$$$$$$$$")

    def Optimal1():  # 按照最佳置换算法进行置换
        global zhihuan  # 通过global相当于桥，使局部变量能在多个函数中使用
        zhihuan = 0
        global xuhao
        xuhao1 = xuhao

        while (xuhao1 < n):
            print("当前为第%d页面(从1开始编号),页面号为%d" % ((xuhao1 + 1), yemian[xuhao1]))
            ccc = 0
            for t in range(m):
                if (kuai[t][0] == yemian[xuhao1]):
                    ccc = ccc + 1
                    break
            if (ccc != 0):
                print("此时命中，无需置换")
            else:
                print("发生缺页，置换为:")
                zhihuan = zhihuan + 1
                xuhao2 = xuhao1
                ddd = 1
                while (xuhao2 < n):

                    for o in range(m):
                        if ((kuai[o][0] == yemian[xuhao2]) and (kuai[o][2] == 0)):
                            kuai[o][2] = 1
                            kuai[o][1] = ddd
                            ddd = ddd + 1
                    xuhao2 = xuhao2 + 1
                for p in range(m):
                    if ((kuai[p][1] == 0) or (kuai[p][1] == m)):
                        kuai[p][0] = yemian[xuhao1]
                        break

                for f in range(m):
                    kuai[f][1] = 0
                    kuai[f][2] = 0
                print(kuai)
            xuhao1 = xuhao1 + 1
        print("$$$$$$$$$$$$$$$")

    def FIFO():  # 先进先出页面置换算法
        global xuhao

        global zhihuan
        zhihuan = 0
        xuhao2 = xuhao
        canshu = 0
        while (xuhao2 < n):
            linshi = 0
            print("当前为第%d页面(从1开始编号),页面号为%d" % ((xuhao2 + 1), yemian[xuhao2]))
            for i in range(m):
                if (kuai[i][0] == yemian[xuhao2]):
                    linshi = linshi + 1
                    break
            if (linshi != 0):
                print("此时命中，无需置换")
            else:
                print("发生缺页，请求置换")
                zhihuan = zhihuan + 1
                kuai[canshu % m][0] = yemian[xuhao2]
                canshu = canshu + 1
                print(kuai)
            xuhao2 = xuhao2 + 1

    def LRU():  # 最近最久未使用置换算法
        global xuhao
        xuhao3 = xuhao
        global zhihuan
        zhihuan = 0
        ttt = m
        for q in range(m):
            kuai[q][1] = ttt  # 数值越大，优先被置换
            ttt = ttt - 1

        while (xuhao3 < n):

            jishu = 0
            print("当前为第%d页面(从1开始编号),页面号为%d" % ((xuhao3 + 1), yemian[xuhao3]))
            for i in range(m):
                if (kuai[i][0] == yemian[xuhao3]):
                    jishu = jishu + 1
                    break
            if (jishu != 0):
                print("此时命中,无需置换")
                for y in range(m):
                    kuai[y][1] = kuai[y][1] + 1

                for t in range(m):
                    if (kuai[t][0] == yemian[xuhao3]):
                        kuai[t][1] = 0

                        break

            else:
                print("发生缺页，请求置换")
                zhihuan = zhihuan + 1
                pcb = kuai[:]
                pcb.sort(key=lambda x: x[1], reverse=True)
                for y in range(m):
                    kuai[y][1] = kuai[y][1] + 1
                for w in range(m):
                    if (kuai[w][0] == pcb[0][0]):
                        kuai[w][0] = yemian[xuhao3]
                        kuai[w][1] = 0
                        break
                print(kuai)
            xuhao3 = xuhao3 + 1

    def jisuan():  # 调入次数，置换次数的统计，缺页率的计算
        print("缺页率的相关计算:")
        global diaoru
        global zhihuan
        print("调入次数为:%d" % (diaoru))
        print("置换次数为:%d" % (zhihuan))
        print("缺页率为:%0.2f" % (float((diaoru + zhihuan) / n)))

    if __name__ == "__main__":
        inyemian()
        diaoru1()
        qqqq = 0
        while (qqqq == 0):
            print("请输入数字1或2或3进行选择(Optimal或FIFO或LRU)，输入其他正整数则终止")
            shuru = int(input("请输入正整数:"))
            if (shuru == 1):

                Optimal1()
                jisuan()
            elif (shuru == 2):
                FIFO()
                jisuan()
            elif (shuru == 3):
                LRU()
                jisuan()

            else:
                qqqq = 1
                print("运行结束！")


def yinhangjia():
    # 状态码0表示进程未执行;数字越小优先级越高
    n = int(input("请输入进程数:"))
    m = int(input("请输入资源种类数:"))
    pcb = []
    ziyuan = []
    shengyu = []
    guodu = []
    qingqiu = []
    shengyu111 = []
    guodu = []
    qingqiu111 = []
    safenumber = 0
    youxianji = m * 3 + 2
    jianduan = m * 2 + 1

    def biaoge():  # 数据的输入与初步计算，已得到课本表格
        for i in range(m):
            number = int(input("请输入第%d类资源系统总数目:" % (i + 1)))
            ziyuan.append(number)
        print("系统资源数为:")
        print(ziyuan)
        i = 0
        while (i < n):
            name = input("请输入第%d个进程的id:" % (i + 1))
            pcb.append([name, 0, 0])  # 后面数字分别作为状态码和优先级的标记
            i = i + 1
        # print(pcb)
        for i in range(n):  # 各个进程对各种资源的最大需求量
            k = m
            for q in range(m):
                shu = int(input("请输入第%d个进程对第%d类资源的最大需求量:" % (i + 1, k)))
                pcb[i].insert(1, shu)
                k = k - 1
                q = q + 1
            i = i + 1
        print(pcb)
        for i in range(n):  # 各进程对资源的占有量
            z = m
            for q in range(m):
                shuzi = int(input("请输入第%d个进程对第%d类资源的占有量:" % (i + 1, z)))
                pcb[i].insert(m + 1, shuzi)
                z = z - 1
                q = q + 1
            i = i + 1
        for i in range(n):  # 计算进程对各资源需求量
            u = m
            w = m * 2
            for q in range(m):
                shuju = int(pcb[i][u] - pcb[i][w])
                pcb[i].insert(m * 2 + 1, shuju)
                u = u - 1
                w = w - 1
                q = q + 1
            i = i + 1
        for i in range(m):
            sum1 = 0
            yu = 0
            k = m
            for q in range(n):
                sum1 = sum1 + pcb[q][k + 1 + i]
                q = q + 1
            yu = ziyuan[i] - sum1
            shengyu.append(yu)
            i = i + 1
        print("此时表格为:")
        print(pcb)
        print("此时系统各资源剩余量:")
        print(shengyu)

    def safe12():  # 判断并输出此时的安全序列

        shengyu111 = shengyu[:]
        r = 0
        zhongjian = 0
        jishuqi = 0

        while (r < n):
            i = 0
            while (i < n):
                qqq = jianduan
                bbb = 0
                ttt = 0
                if (jishuqi < n):
                    while (bbb < m):
                        if ((pcb[i][qqq] <= shengyu111[bbb]) and (pcb[i][m * 3 + 1] == 0)):
                            ttt = ttt + 1
                        qqq = qqq + 1
                        bbb = bbb + 1

                    if (ttt == m):
                        pcb[i][m * 3 + 1] = 1
                        pcb[i][youxianji] = jishuqi
                        shengyu111[0] = shengyu111[0] + pcb[i][m + 1]
                        shengyu111[1] = shengyu111[1] + pcb[i][m + 2]
                        shengyu111[2] = shengyu111[2] + pcb[i][m + 3]
                        jishuqi = jishuqi + 1
                i = i + 1
            r = r + 1

        for i in range(n):
            pcb[i][m * 3 + 1] = 0
            i = i + 1
        guodu = pcb[:]
        guodu.sort(key=lambda x: x[youxianji], reverse=False)
        print("各程序获得优先级后：")
        print(pcb)
        global safenumber
        if (jishuqi == n):
            print("此时存在安全序列:")
            safenumber = 0
            for i in range(n):
                print(guodu[i][0])
                i = i + 1
        else:
            safenumber = 1
            print("此时不存在安全序列")

    def qingqiu12():
        sss = 0
        www = 0
        qingqiu111 = qingqiu[:]
        v = int(input("进程发出请求，该进程位于第（ ）位(从1开始编号)："))
        for i in range(m):
            b = int(input("对第%d类资源请求量为:" % (i + 1)))
            qingqiu111.append(b)
        print("此时该进程请求资源为:")
        print(qingqiu111)
        # if ((qingqiu111[0] <= pcb[v - 1][m*2+1]) and (qingqiu111[1] <= pcb[v - 1][m*2+2]) and (
        # qingqiu111[2] <= pcb[v - 1][m*2+3])):
        # if((qingqiu111[0] <= shengyu[0]) and (qingqiu111[1] <= shengyu[1]) and (qingqiu111[2] <= shengyu[2])):
        pppp = 0
        while (pppp < m):
            if (qingqiu111[pppp] <= pcb[v - 1][jianduan + pppp]):
                sss = sss + 1

            if (qingqiu111[pppp] <= shengyu[pppp]):
                www = www + 1

            pppp = pppp + 1
        if (sss + www == m * 2):
            print("检查此时是否存在安全序列:")
            pcb[v - 1][m * 2 + 1] = pcb[v - 1][m * 2 + 1] - qingqiu111[0]
            pcb[v - 1][m * 2 + 2] = pcb[v - 1][m * 2 + 2] - qingqiu111[1]
            pcb[v - 1][m * 2 + 3] = pcb[v - 1][m * 2 + 3] - qingqiu111[2]
            pcb[v - 1][m + 1] = pcb[v - 1][m + 1] + qingqiu111[0]
            pcb[v - 1][m + 2] = pcb[v - 1][m + 2] + qingqiu111[1]
            pcb[v - 1][m + 3] = pcb[v - 1][m + 3] + qingqiu111[2]
            shengyu[0] = shengyu[0] - qingqiu111[0]
            shengyu[1] = shengyu[1] - qingqiu111[1]
            shengyu[2] = shengyu[2] - qingqiu111[2]
            print("假定分配资源")

            safe12()
            if (safenumber == 0):
                print("资源可以分配")
            else:
                print("收回分配的资源，数据刷新:")

                shengyu[0] = shengyu[0] + qingqiu111[0]
                shengyu[1] = shengyu[1] + qingqiu111[1]
                shengyu[2] = shengyu[2] + qingqiu111[2]
                print("系统剩余资源为:")
                print(shengyu)
                print("表格数据为:")
                pcb[v - 1][m * 2 + 1] = pcb[v - 1][m * 2 + 1] + qingqiu111[0]
                pcb[v - 1][m * 2 + 2] = pcb[v - 1][m * 2 + 2] + qingqiu111[1]
                pcb[v - 1][m * 2 + 3] = pcb[v - 1][m * 2 + 3] + qingqiu111[2]
                pcb[v - 1][m + 1] = pcb[v - 1][m + 1] - qingqiu111[0]
                pcb[v - 1][m + 2] = pcb[v - 1][m + 2] - qingqiu111[1]
                pcb[v - 1][m + 3] = pcb[v - 1][m + 3] - qingqiu111[2]
                print(pcb)

        else:
            if (www != m):
                print("资源请求数量shengyu异常，进程%d等待" % (v))
            if (sss != m):
                print("资源请求数量need异常，进程%d等待" % (v))


    if __name__ == '__main__':
        biaoge()
        safe12()
        dd = 1
        while (dd == 1):
            ff = int(input("请输入是否继续请求(其他继续，1退出):"))
            if (ff != 1):
                qingqiu12()
            else:
                print("运行结束！")
                dd = 2


if __name__ == '__main__':
    eee = 0

    print("输入1.2.3.4选择银行家，作业调度，页面置换，磁盘调度，其余终止程序,(输入):")
    ttt = int(input())
    while (eee == 0):
        if (ttt == 1):
            print("银行家算法启动")
            yinhangjia()
        elif (ttt == 2):
            print("作业调度启动")
            zuoyediaodu()
        elif (ttt == 3):
            print("页面置换启动")
            yemianzhihuan()
        elif (ttt == 4):
            print("磁盘调度启动")
            cipandiaodu()
        else:
            print("程序终止！")
            eee = 1