python - Python CPU 调度程序模拟器

Question

所以我有一个 FCFS 和 SJF CPU 模拟器调度算法，但是我正在努力实现最短剩余时间优先算法。

这就是我到目前为止所拥有的。

def srtf(submit_times, burst_times):
    """First Come First Serve Algorithm returns the time metrics"""
    cpu_clock = 0
    job = 0
    response_times = []
    turn_around_times = []
    wait_times = []
    total_jobs = []
    remaining_burst_times = []

    for stuff in range(len(submit_times)):
        total_jobs.append(tuple((submit_times[stuff], burst_times[stuff])))
        remaining_burst_times.append(burst_times[stuff])

    while job < len(submit_times):

        if cpu_clock < int(submit_times[job]):
            cpu_clock = int(submit_times[job])

        ready_queue = []
        for the_job in total_jobs:
            job_time = int(the_job[0])
            if job_time <= cpu_clock:
                ready_queue.append(the_job)

        short_job = ready_queue_bubble(ready_queue)

        submit, burst = short_job[0], short_job[1]

        next_event = cpu_clock + int(burst)

        response_time = cpu_clock - int(submit)
        response_times.append(response_time)

        remaining_burst_times[job] = next_event - cpu_clock

        # cpu_clock = next_event
        if remaining_burst_times[job] == 0:
            turn_around_time = next_event - int(submit)
            wait_time = turn_around_time - int(burst)
            turn_around_times.append(turn_around_time)
            wait_times.append(wait_time)
        else:
            pass

        job += 1
        total_jobs.remove(short_job)
        remaining_burst_times.remove(short_job[1])

    return response_times, turn_around_times, wait_times

基本上，该函数接受提交时间和突发时间的列表，并返回响应、转身和等待时间的列表。我一直在尝试先用准备好的队列编辑我的短期工作的剩余部分，但无济于事。

谁能指出我正确的方向？

标签： pythonalgorithmcpuschedulingsimulator

Answer 1

由于抢占，这不是一个非常简单的模拟。设计模拟就是代表 1) 世界的状态和 2) 作用于世界的事件。

这里的世界状况是：

• 流程。这些都有自己的内部状态。

  • 提交时间（不可变）
  • 突发时间（不可变）
  • 剩余时间（可变）
  • 完成时间（可变）

• 挂钟时间。

• 下一个流程要提交。

• 运行过程。

• 运行开始时间（当前运行的进程）。

• 等待可运行的进程（即过去提交剩余> 0）。

只有两种事件。

• 一个进程的提交时间发生。
• 运行过程完成。

当没有更多进程等待提交，并且没有进程在运行时，模拟结束。您可以从流程中获取所需的统计信息。

该算法初始化状态，然后执行标准事件循环：

processes = list of Process built from parameters, sorted by submit time
wall_clock = 0
next_submit = 0 # index in list of processes
running = None # index of running process
run_start = None # start of current run
waiting = []
while True:
   event = GetNextEvent()
   if event is None:
     break
   wall_clock = event.time
   if event.kind == 'submit':
     # Update state for new process submission.
   else: # event.kind is 'completion'
     # Update state for running process completion.

一个重要的细节是，如果完成和提交事件同时发生，则首先处理完成。反过来，更新逻辑变得复杂；剩余时间为零的正在运行的进程是一种特殊情况。

“更新状态”方法根据 srtf 算法调整状态的所有元素。大概是这样...

def UpdateStateForProcessCompletion():
  # End the run of the running process
  processes[running].remaining = 0
  processes[running].completion_time = wall_clock

  # Schedule a new one, if any are waiting.
  running = PopShortestTimeRemainingProcess(waiting)
  run_start_time = clock_time if running else None

新的提交更复杂。

def UpdateStateForProcessCompletion():
  new_process = next_submit
  next_submit += 1
  new_time_remaining = processes[new_process].remaining

  # Maybe preempt the running process.
  if running:
    # Get updated remaining time to run.
    running_time_remaining = processes[running].remaining - (wall_clock - run_start)
    # We only need to look at new and running processes. 
    # Waiting ones can't win because they already lost to the running one.
    if new_time_remaining < running_time_remaining:
      # Preempt.
      processes[running].remaining = running_time_remaining
      waiting.append(running)
      running = new_process
      run_start_time = wall_clock
    else:
      # New process waits. Nothing else changes
      waiting.append(new_process)
  else:
    # Nothing's running. Run the newly submitted process.
    running = new_process
    run_start_time = wall_clock

唯一剩下的就是获得下一个事件。您只需要检查processes[next_submit].submit和wall_clock + processes[running].remaining. 选择最小的。该事件具有该时间和相应的类型。当然，您需要处理next_submitand/or runningare的情况None。

我可能在这里没有完美的一切，但它非常接近。

添加

希望你在这个时候完成你的作业。编写代码很有趣。我在这个例子上运行了它，并且跟踪匹配得很好。干杯

import heapq as pq

class Process(object):
  """A description of a process in the system."""
  def __init__(self, id, submit, burst):
    self.id = id
    self.submit = submit
    self.burst = burst
    self.remaining = burst
    self.completion = None
    self.first_run = None

  @property
  def response(self):
    return None if self.first_run is None else self.first_run - self.submit

  @property
  def turnaround(self):
    return None if self.completion is None else self.completion - self.submit

  @property
  def wait(self):
    return None if self.turnaround is None else self.turnaround - self.burst
 
  def __repr__(self):
    return f'P{self.id} @ {self.submit} for {self.burst} ({-self.remaining or self.completion})'


def srtf(submits, bursts):
  # Make a list of processes in submit time order.
  processes = [Process(i + 1, submits[i], bursts[i]) for i in range(len(submits))]
  processes_by_submit_asc = sorted(processes, key=lambda x: x.submit)
  process_iter = iter(processes_by_submit_asc)
  
  # The state of the simulation:
  wall_clock = 0  # Wall clock time.
  next_submit = next(process_iter, None)  # Next process to be submitted.
  running = None  # Running process.
  run_start = None  # Time the running process started running.
  waiting = []  # Heap of waiting processes. Pop gets min remaining.
 
  def run(process):
    """Switch the running process to the given one, which may be None."""
    nonlocal running, run_start
    running = process
    if running is None:
      run_start = None
      return
    running.first_run = running.first_run or wall_clock
    run_start = wall_clock

  while next_submit or running:
    print(f'Wall clock: {wall_clock}')
    print(f'Running: {running} since {run_start}')
    print(f'Waiting: {waiting}')

    # Handle completion first, if there is one.
    if running and (next_submit is None or run_start + running.remaining <= next_submit.submit):
      print('Complete')
      wall_clock = run_start + running.remaining
      running.remaining = 0
      running.completion = wall_clock
      run(pq.heappop(waiting)[1] if waiting else None)
      continue

    # Handle a new submit, if there is one.
    if next_submit and (running is None or next_submit.submit < run_start + running.remaining):
      print(f'Submit: {next_submit}')
      new_process = next_submit
      next_submit = next(process_iter, None)
      wall_clock = new_process.submit
      new_time_remaining = new_process.remaining
      if running:
        # Maybe preempt the running process. Otherwise new process waits.
        running_time_remaining = running.remaining - (wall_clock - run_start)
        if new_time_remaining < running_time_remaining:
          print('Preempt!')
          running.remaining = running_time_remaining
          pq.heappush(waiting, (running_time_remaining, running))
          run(new_process)
        else:
          pq.heappush(waiting, (new_time_remaining, new_process))
      else:
        run(new_process)

  for p in processes:
    print(f'{p} {p.response} {p.turnaround} {p.wait}')

  return ([p.response for p in processes],
          [p.turnaround for p in processes],
          [p.wait for p in processes])


submits = [6,3,4,1,2,5]
bursts = [1,3,6,5,2,1]
print(srtf(submits, bursts))