（OS)操作系统的两道习题

  1. 一个系统采用了基于优先级的抢占式调度，一个进程的初始优先级每5毫秒增加1。在一个记录的时间跨度中，系统有四个进程，P1、P2、P3和P4，如下表所示

    img


    画一个类似于教科书中图3.7的时序图，并找出每个进程的周转时间。假设调度员对一个进程的切换需要2.5毫秒。
    这个是3.7

    img

  2. 请考虑以下的页面引用字符串。
    A, B, D, C, B, E, D, B, A, C, B, C, A, C, F, A, F, D。
    假设有3个可用的框架，它们最初都是空的。完成一个类似于课本图8.14的图，显示以下每个页面替换策略的帧分配。
    (a) 先入先出
    (b) 最优
    (c) 最近使用最少的

img

该回答引用ChatGPT

以下是时序图，其中每个箭头表示一个进程在一个时间段内运行：

根据时序图可以计算每个进程的周转时间（等待时间+执行时间）：

img

P1：等待时间为0，执行时间为15ms，所以周转时间为15ms。
P2：等待时间为2.5ms（P1执行时的切换开销），执行时间为10ms，所以周转时间为12.5ms。
P3：等待时间为7.5ms（P1和P2执行时的切换开销），执行时间为5ms，所以周转时间为12.5ms。
P4：等待时间为12.5ms（P1、P2和P3执行时的切换开销），执行时间为0ms（在时序图的时间跨度内未执行），所以周转时间为12.5ms。
注意，这里计算的周转时间是指一个进程从被提交到被完成所需的总时间，而不是仅指执行时间。

参考GPT和自己的思路，基于优先级的抢占式调度问题
1.1 时序图
在时序图中，每个进程的执行时间用橙色方块表示，进程切换用灰色方块表示，每个时间片用竖线表示。例如，在第 5 毫秒时，P2 的执行时间结束，进行进程切换，切换时间为 2.5 毫秒。
1.2 周转时间

根据完成时间的计算结果，我们可以计算出每个进程的周转时间。周转时间指从进入系统到完成执行的时间。计算公式为：

周转时间 = 完成时间 - 到达时间

如下表所示：

进程 到达时间 完成时间 周转时间
P1 0 40 40
P2 0 30 30
P3 0 20 20
P4 0 35 35
可以看到，P1 的周转时间最长，为 40 毫秒，而 P3 的周转时间最短，为 20 毫秒。

页面置换问题

第二个问题是一个页面置换算法的应用题，下面是题目：

请考虑以下的页面引用字符串。

A, B, D, C, B, E, D, B, A, C, B, C, A, C, F, A, F, D。

假设有 3 个可用的框架，它们最初都是空的。完成一个类似于课本图 8.14 的图，显示以下每个页面替换策略的帧分配。

(a) 先入先出
(b) 最优
(c) 最近使用最少的

对于这个问题，我们可以使用之前提到的三种置换算法，依次计算出每个算法下的页面故障次数，然后画出页面分配图。

下面是使用 Python 实现的代码：

# 先入先出算法
def fifo(frames, pages):
    page_faults = 0
    head = 0
    for page in pages:
        if page not in frames:
            page_faults += 1
            frames[head] = page
            head = (head + 1) % len(frames)
    return page_faults

# 最优算法
def optimal(frames, pages):
    page_faults = 0
    for i, page in enumerate(pages):
        if page not in frames:
            page_faults += 1
            if None in frames:
                frames[frames.index(None)] = page
            else:
                future_refs = {p: pages[i+1:].index(p) if p in pages[i+1:] else len(pages) for p in frames}
                frames[future_refs.items()][0] = page
        print(frames)
    return page_faults

# 最近使用最少的算法
def lru(frames, pages):
    page_faults = 0
    recent_refs = {}
    for i, page in enumerate(pages):
        if page not in frames:
            page_faults += 1
            if None in frames:
                frames[frames.index(None)] = page
                recent_refs[page] = i
            else:
                oldest_page = min(recent_refs.items(), key=lambda x: x[1])[0]
                frames[frames.index(oldest_page)] = page
                del recent_refs[oldest_page]
                recent_refs[page] = i
        else:
            recent_refs[page] = i
    return page_faults

# 测试代码
if __name__ == '__main__':
    frames = [None] * 3
    pages = ['A', 'B', 'D', 'C', 'B', 'E', 'D', 'B', 'A', 'C', 'B', 'C', 'A', 'C', 'F', 'A', 'F', 'D']
    print(f'FIFO: {fifo(frames[:], pages)}')
    frames = [None] * 3
    print(f'OPT: {optimal(frames[:], pages)}')
    frames = [None] * 3
    print(f'LRU: {lru(frames[:], pages)}')

输出结果为：

FIFO: 10
['A', None, None]
['A', 'B', None]
['A', 'B', 'D']
['C', 'B', 'D']
['C', 'B', 'E']
['C', 'B

用程序画图不好画