操作系统作业调度python

### 使用Python实现操作系统作业调度算法

#### 先来先服务（FCFS）

此方法按请求顺序执行进程。下面是一个简单的例子：

def fcfs_scheduling(processes):
    current_time = 0
    result = []
    
    for process in processes:
        arrival_time, burst_time = process['arrival'], process['burst']
        
        start_time = max(current_time, arrival_time)
        end_time = start_time + burst_time
        
        result.append({
            'name': process['name'],
            'start': start_time,
            'end': end_time
        })
        
        current_time = end_time
    
    return result

这段代码实现了基本的先来先服务调度逻辑[^1]。

#### 最短作业优先(SJF)

最短作业优先策略会优先处理预计完成时间较短的任务。以下是其实现方式之一：

def sjf_scheduling(processes):
    sorted_processes = sorted(
        (p for p in processes),
        key=lambda x: (x['arrival'], x['burst'])
    )
    
    schedule = fcfs_scheduling(sorted_processes)
    
    return schedule

上述函数首先依据到达时间和估计的服务周期对所有任务进行了排序，之后再调用了`fcfs_scheduling()` 来安排这些已排序后的任务[^2]。

#### 时间片轮转(RR)

对于时间片轮转法而言，每个任务都会获得固定长度的时间片段去运行。一旦超出了这个限定，则会被暂停并将控制权交给下一个等待中的任务。下面是具体做法：

def rr_scheduling(processes, time_slice=3):
    queue = deque()
    current_time = 0
    results = []

    # 初始化队列
    for proc in processes:
        if proc["arrival"] <= current_time:
            queue.append(proc.copy())

    while queue or any(p["arrival"] <= current_time for p in processes if "executed" not in p):

        # 将新到的任务加入队列
        for i, proc in enumerate([p for p in processes if "executed" not in p]):
            if proc["arrival"] <= current_time and proc not in queue:
                queue.append(proc.copy())
                
        if not queue:
            current_time += 1
            continue
            
        running_process = queue.popleft()

        remaining_burst = running_process.get('remaining', running_process['burst'])

        execution_duration = min(time_slice, remaining_burst)
        new_remaining = remaining_burst - execution_duration

        results.append({
            'process': running_process['name'],
            'started_at': current_time,
            'ended_at': current_time + execution_duration
        })

        current_time += execution_duration

        if new_remaining > 0:
            running_process['remaining'] = new_remaining
            queue.append(running_process)
        else:
            running_process['executed'] = True

    return results

在此版本中，采用了双端队列(deque)作为内部数据结构以便于高效地管理待处理项，并且支持可变的时间切片大小参数。

#### 动态优先级(HRRN)

高响应比最高者优先是一种基于比例的调度机制，其中考虑到了等待时间和预期的服务需求量。这使得长时间处于准备状态下的低效用程序也能得到及时的关注。下面是如何构建这样一个系统的实例：

def hrrn_scheduling(processes):
    def calculate_priority(waiting_time, service_time):
        return 1 + waiting_time / float(service_time)

    scheduled_times = {}
    total_time = sum(p['burst'] for p in processes)

    for t in range(total_time):
        available_procs = [
            p for p in processes 
            if p['arrival'] <= t and ('completed' not in p or not p['completed'])]

        best_proc = None
        highest_ratio = -float('inf')

        for candidate in available_procs:
            ratio = calculate_priority(t-candidate['arrival'], candidate['burst'])
            
            if ratio >= highest_ratio:
                highest_ratio = ratio
                best_proc = candidate
                
        if best_proc is None:
            continue

        if best_proc['name'] not in scheduled_times:
            scheduled_times[best_proc['name']] = {'starts': [], 'ends': []}

        scheduled_times[best_proc['name']]['starts'].append(t)
        scheduled_times[best_proc['name']]['ends'].append(t+1)

        best_proc.setdefault('remaining', best_proc['burst']) -= 1

        if best_proc['remaining'] == 0:
            best_proc['completed'] = True

    formatted_result = [{'name': k, **v} for k,v in scheduled_times.items()]
    
    return formatted_result

在这个方案里定义了一个辅助性的 `calculate_priority()` 函数用于评估候选者的相对价值；随后遍历整个可能的时间范围寻找最优解直至所有的任务都被妥善安置为止.