#进程调度算法

def fcfs_schedule(processes):
    """
    processes: [(arrival_time, burst_time), ...]
    按到达时间排序
    """
    # 按到达时间排序
    sorted_procs = sorted(processes, key=lambda x: x[0])
    
    current_time = 0
    waiting_time = 0
    
    for arrival, burst in sorted_procs:
        if current_time < arrival:
            current_time = arrival
        
        waiting_time += current_time - arrival
        current_time += burst
    
    return waiting_time / len(processes)

# 示例：进程P1-P4
# P1: 到达0，执行4
# P2: 到达1，执行3
# P3: 到达2，执行2
# P4: 到达3，执行1

# 执行顺序：P1 → P2 → P3 → P4
# Gantt图：
# | P1 | P2 | P3 | P4 |
# 0    4    7    9   10

# 等待时间：
# P1: 0 - 0 = 0
# P2: 4 - 1 = 3
# P3: 7 - 2 = 5
# P4: 9 - 3 = 6
# 平均等待时间 = (0 + 3 + 5 + 6) / 4 = 3.5

def sjf_schedule(processes):
    """
    非抢占式SJF
    """
    processes = sorted(processes, key=lambda x: x[1])  # 按执行时间排序
    # 注意：这里简化了，实际还需要考虑到达时间
    
    current_time = 0
    total_waiting = 0
    
    # 使用优先级队列
    import heapq
    ready_queue = []
    idx = 0
    
    while idx < len(processes) or ready_queue:
        # 添加所有已到达的进程
        while idx < len(processes) and processes[idx][0] <= current_time:
            arrival, burst = processes[idx]
            # 按burst时间排序
            heapq.heappush(ready_queue, (burst, arrival))
            idx += 1
        
        if ready_queue:
            burst, arrival = heapq.heappop(ready_queue)
            current_time += burst
            total_waiting += current_time - arrival - burst
        else:
            # 没有可运行的进程，跳到下一个到达时间
            current_time = processes[idx][0]
    
    return total_waiting / len(processes)

def srtf_schedule(processes):
    """
    最短剩余时间优先（抢占式SJF）
    """
    import heapq
    
    current_time = 0
    ready_queue = []
    completed = []
    idx = 0
    n = len(processes)
    
    while len(completed) < n:
        # 添加新到达的进程
        while idx < n and processes[idx][0] <= current_time:
            arrival, burst = processes[idx]
            # (remaining_time, arrival_time, original_burst)
            heapq.heappush(ready_queue, (burst, arrival, burst))
            idx += 1
        
        if ready_queue:
            remaining, arrival, original = heapq.heappop(ready_queue)
            current_time += 1
            remaining -= 1
            
            # 检查是否有新进程到达
            while idx < n and processes[idx][0] <= current_time:
                new_arrival, new_burst = processes[idx]
                heapq.heappush(ready_queue, (new_burst, new_arrival, new_burst))
                idx += 1
            
            if remaining > 0:
                heapq.heappush(ready_queue, (remaining, arrival, original))
            else:
                completed.append((current_time - arrival - original, arrival, original))
        else:
            current_time = processes[idx][0]
    
    return sum(p[0] for p in completed) / len(completed)

def round_robin_schedule(processes, time_slice=2):
    """
    时间片轮转调度
    """
    from collections import deque
    
    current_time = 0
    ready_queue = deque()
    remaining = {}  # pid -> remaining_time
    idx = 0
    
    # 初始化
    while idx < len(processes) and processes[idx][0] <= current_time:
        arrival, burst = processes[idx]
        ready_queue.append(arrival)
        remaining[arrival] = burst
        idx += 1
    
    total_waiting = 0
    
    while ready_queue:
        arrival = ready_queue.popleft()
        burst = remaining[arrival]
        
        if burst <= time_slice:
            # 进程完成
            current_time += burst
            waiting = current_time - arrival - burst
            total_waiting += waiting
            
            # 添加新到达的进程
            while idx < len(processes) and processes[idx][0] <= current_time:
                new_arrival, new_burst = processes[idx]
                ready_queue.append(new_arrival)
                remaining[new_arrival] = new_burst
                idx += 1
        else:
            # 时间片用完，放回队列
            current_time += time_slice
            remaining[arrival] = burst - time_slice
            ready_queue.append(arrival)
            
            # 添加新到达的进程
            while idx < len(processes) and processes[idx][0] <= current_time:
                new_arrival, new_burst = processes[idx]
                ready_queue.append(new_arrival)
                remaining[new_arrival] = new_burst
                idx += 1
    
    return total_waiting / len(processes)

def priority_schedule(processes):
    """
    优先级调度（数值越小优先级越高）
    """
    import heapq
    
    current_time = 0
    ready_queue = []
    idx = 0
    
    while idx < len(processes) or ready_queue:
        # 添加所有已到达的进程
        while idx < len(processes) and processes[idx][0] <= current_time:
            arrival, burst, priority = processes[idx]
            heapq.heappush(ready_queue, (priority, arrival, burst))
            idx += 1
        
        if ready_queue:
            priority, arrival, burst = heapq.heappop(ready_queue)
            current_time += burst
        else:
            current_time = processes[idx][0]