---

import copy

class Process:
    def __init__(self, pid, arrival_time, burst_time):
        self.pid = pid
        self.arrival_time = arrival_time
        self.burst_time = burst_time
        self.remaining_time = burst_time  # для RR
        self.start_time = None
        self.completion_time = None
        self.waiting_time = None
        self.turnaround_time = None

def fcfs_scheduling(processes):
    """Алгоритм FCFS (First Come, First Served)"""
    procs = sorted(processes, key=lambda p: p.arrival_time)
    current_time = 0
    
    for p in procs:
        if current_time < p.arrival_time:
            current_time = p.arrival_time
        p.start_time = current_time
        p.completion_time = current_time + p.burst_time
        p.turnaround_time = p.completion_time - p.arrival_time
        p.waiting_time = p.turnaround_time - p.burst_time
        current_time = p.completion_time
    
    return procs

def round_robin_scheduling(processes, time_quantum):
    """Алгоритм Round Robin"""
    procs = copy.deepcopy(processes)
    for p in procs:
        p.remaining_time = p.burst_time
        p.start_time = None
        p.completion_time = None
    
    queue = []
    current_time = 0
    idx = 0
    n = len(procs)
    completed = 0
    
    # сортируем по времени прибытия для начального заполнения
    procs_sorted = sorted(procs, key=lambda p: p.arrival_time)
    
    while completed < n:
        # добавляем все процессы, которые прибыли к текущему времени
        while idx < n and procs_sorted[idx].arrival_time <= current_time:
            queue.append(procs_sorted[idx])
            idx += 1
        
        if not queue:
            # нет процессов — перематываем время до следующего прибытия
            current_time = procs_sorted[idx].arrival_time
            continue
        
        p = queue.pop(0)  # берём первый из очереди
        
        if p.start_time is None:
            p.start_time = current_time
        
        # выполняем процесс
        exec_time = min(time_quantum, p.remaining_time)
        p.remaining_time -= exec_time
        current_time += exec_time
        
        # добавляем новые процессы, прибывшие во время выполнения
        while idx < n and procs_sorted[idx].arrival_time <= current_time:
            queue.append(procs_sorted[idx])
            idx += 1
        
        if p.remaining_time == 0:
            # процесс завершён
            p.completion_time = current_time
            p.turnaround_time = p.completion_time - p.arrival_time
            p.waiting_time = p.turnaround_time - p.burst_time
            completed += 1
        else:
            # процесс ещё не завершён — в конец очереди
            queue.append(p)
    
    return procs

def print_results(procs, algo_name):
    """Вывод результатов"""
    print(f"\n{'='*50}")
    print(f"Результаты: {algo_name}")
    print(f"{'='*50}")
    print(f"{'PID':<5} {'Arrival':<8} {'Burst':<8} {'Start':<8} {'Completion':<10} {'Waiting':<8} {'Turnaround':<8}")
    print("-" * 65)
    
    total_waiting = 0
    total_turnaround = 0
    for p in procs:
        print(f"{p.pid:<5} {p.arrival_time:<8} {p.burst_time:<8} {p.start_time:<8} {p.completion_time:<10} {p.waiting_time:<8} {p.turnaround_time:<8}")
        total_waiting += p.waiting_time
        total_turnaround += p.turnaround_time
    
    n = len(procs)
    avg_waiting = total_waiting / n
    avg_turnaround = total_turnaround / n
    
    print("-" * 65)
    print(f"Среднее время ожидания: {avg_waiting:.2f}")
    print(f"Среднее время выполнения (turnaround): {avg_turnaround:.2f}")

# Пример использования
if __name__ == "__main__":
    # Создаём процессы: PID, время прибытия, время CPU burst
    processes = [
        Process(1, 0, 5),
        Process(2, 1, 3),
        Process(3, 2, 2),
        Process(4, 3, 4)
    ]
    
    # FCFS
    fcfs_result = fcfs_scheduling(copy.deepcopy(processes))
    print_results(fcfs_result, "FCFS")
    
    # Round Robin с квантом = 2
    rr_result = round_robin_scheduling(copy.deepcopy(processes), time_quantum=2)
    print_results(rr_result, f"Round Robin (квант = 2)")