#----------------------------------------------------------------------------#
#                                                                            #
# Matthew Reeves                                                             #
# This program simulates a simple process scheduler                          #
#                                                                            #
#----------------------------------------------------------------------------#

import re

simulation = 0
next_num_cpu = 0
next_num_proc = 0
next_quantum_size = 0

line = raw_input()

# read first line of input containing system data for first simulation
matchObj = re.match( r'(\d+)\s(\d+)\s(\d+)$', line, re.M|re.I)

if matchObj:

    next_num_cpu = int(matchObj.group(1))
    next_num_proc = int(matchObj.group(2))
    next_quantum_size = int(matchObj.group(3))

# while eof has not been reached, read data from input
while line:

    # initialize variables for system data
    check = 1
    time = 0
    idle = 0
    num_cpu = next_num_cpu
    num_proc = next_num_proc
    quantum_size = next_quantum_size

    # initialize lists for process data
    pid = []
    priority = [0]
    submit_time = [0]
    total_cpu_time = [0]
    compute_time = [0]
    io_time = [0]

    complete_time = [0]

    # initialize process state queues
    not_yet_submitted = []
    ready = []
    running = [0]
    blocked = [0]
    completed = []

    track_running = [0]
    track_complete = [0]
    track_quantum = [0]

    # while data still being input, read data, and run simulation
    while check==1:

        # read a line of input
        line = raw_input()

        # check if input matches new process input
        matchObj = re.match( r'(\d+)\s(\d+)\s(\d+)\s(\d+)\s(\d+)\s(\d+)$',
                         line, re.M|re.I)

        # if match was found store process data
        if matchObj:

            pid.append(int(matchObj.group(1)))
            priority.append(int(matchObj.group(2)))
            submit_time.append(int(matchObj.group(3)))
            total_cpu_time.append(int(matchObj.group(4)))
            compute_time.append(int(matchObj.group(5)))
            io_time.append(int(matchObj.group(6)))

        # if match NOT found, check if input looks like new system data
        else:
            matchObj = re.match( r'(\d+)\s(\d+)\s(\d+)$', line, re.M|re.I)

            # if new system data found, store for next simulation run
            if matchObj:

                next_num_cpu = int(matchObj.group(1))
                next_num_proc = int(matchObj.group(2))
                next_quantum_size = int(matchObj.group(3))

            # otherwise, indicate eof reached    
            else:

                line = ""

            # if line input was NOT a process stop reading in processes
            check = 0

    # add input processes to not_yet_submitted_queue        
    for i in range(0, num_proc):
        temp = pid.pop(0)
        pid.append(temp)
        not_yet_submitted.append(temp)
        blocked.append(0)
        
        # initialize tracking lists
        complete_time.append(0)
        track_running.append(0)
        track_complete.append(0)
        track_quantum.append(0)

    # establishes size of running list based on num_cpu
    for i in range(0, num_cpu-1):
        running.append(0)

    # resets time and check variables for each simulation
    check = 1
    time = 0

    while check==1:

        # Submit each program to ready queue at designated time
        for i in range(0, num_proc):
            if len(not_yet_submitted) > 0:            
                temp = not_yet_submitted.pop(0)
                if time == int(submit_time[temp]):
                    ready.append(temp)                            
                else:
                    not_yet_submitted.append(temp)

        # tracks time blocked process have been blocked
        # moves back to ready, when I/O time complete
        for j in range(1, len(blocked)):
            if int(blocked[j]) > 0:
                blocked[j] = int(blocked[j])-1
                if int(blocked[j]) == 0:
                    print "Moved to ready at time", time
                    ready.append(j)

        # Move highest priority processes to front of ready queue
        for i in range(0, len(ready)):
            for j in range(0, len(ready)-1):
                if int(priority[ready[j]]) < int(priority[ready[j+1]]):
                    ready[j], ready[j+1] = ready[j+1], ready[j]

        # moves processes from ready to running; tracks idle time
        for i in range(0, len(running)):
            print "-------------------------------------------------------"
            if int(running[i]) == 0:
                if len(ready) > 0:
                    print "Moved to running at time", time
                    temp = ready.pop(0)
                    running[i] = temp
                    # if appropriate, update tracking of process status
                    track_quantum[int(running[i])] = quantum_size
                    if int(track_running[running[i]]) == 0:
                        track_running[int(running[i])] = compute_time[int(running[i])]
                    if int(track_complete[running[i]]) == 0:
                        track_complete[int(running[i])] = total_cpu_time[int(running[i])]
                else:
                    idle+=1

        # checks if preemption condition exists, and preempts if needed
        for i in range(0, len(running)):
            if int(running[i]) != 0 and len(ready) > 0:
                if int(priority[ready[0]]) > int(priority[running[i]]):
                    print "Preempted at time", time
                    temp = running[i]
                    running[i] = ready.pop(0)
                    # if appropriate, update tracking of process status
                    track_quantum[int(running[i])] = quantum_size
                    if int(track_running[running[i]]) == 0:
                        track_running[int(running[i])] = compute_time[int(running[i])]
                    if int(track_complete[running[i]]) == 0:
                        track_complete[int(running[i])] = total_cpu_time[int(running[i])]
                    # add preempted process to back of queue
                    ready.append(temp)

        # Move highest priority processes to front of ready queue
        for i in range(0, len(ready)):
            for j in range(0, len(ready)-1):
                if int(priority[ready[j]]) < int(priority[ready[j+1]]):
                    ready[j], ready[j+1] = ready[j+1], ready[j]



        # checks if running process has hit completion time limit, and if it has,
        # move currently running process to completed
        for i in range(0, len(running)):
            if int(running[i]) != 0:
                if int(track_complete[running[i]]) > 0:
                    # decrements time-til-complete tracker
                    track_complete[int(running[i])] = int(track_complete[running[i]])-1
                    # if completion time reached, move to complete
                    if int(track_complete[running[i]]) == 0:
                        print "completed at time", time
                        track_quantum[int(running[i])] = 0
                        track_running[int(running[i])] = 0
                        complete_time[int(running[i])] = time
                        temp = running[i]
                        running[i] = 0
                        completed.append(temp)
                        blocked[int(temp)] = io_time[int(temp)]       


        # checks if running process has hit compute time limit, and if it has,
        # move currently running process to blocked
        for i in range(0, len(running)):
            if int(running[i]) != 0:
                if int(track_running[running[i]]) > 0:
                    # decrements time-til-io tracker
                    track_running[int(running[i])] = int(track_running[running[i]])-1
                    # if compute time limit reached, move to blocked
                    if int(track_running[running[i]]) == 0:
                        print "Moved to blocked at time", time
                        track_quantum[int(running[i])] = 0
                        temp = running[i]
                        running[i] = 0
                        blocked[int(temp)] = io_time[int(temp)]        

        # checks if running process has hit quantum limit, and if it has,
        # move currently running process to ready
        for i in range(0, len(running)):
            if int(running[i]) != 0:
                if int(track_quantum[running[i]]) > 0:
                    # decrements time-til-quantum limit tracker
                    track_quantum[int(running[i])] = int(track_quantum[running[i]])-1
                    # if quantum limit reached move to ready
                    if int(track_quantum[running[i]]) == 0:
                        print "Moved to ready at time", time
                        temp = running[i]
                        running[i] = 0
                        ready.append(temp)
            
        time += 1
        
        print "time:",time
        print "ready:",ready
        print "running:",running
        print "blocked:",blocked
        print "completed:",completed
        print "track_running:",track_running
        print "track_quantum:",track_quantum
        print "track_complete:",track_complete

        # check if all processes are in completed state for simulation
        # Also prints formatted output upon simulation completion
        if len(completed)==num_proc:

            print complete_time
            print submit_time
            
            simulation+=1

            # initialize total turnaround for simulation
            TT_time=0
            print "\nSimulation # %d" % simulation
            print "----------------"
            print "Input:"
            
            # print system data
            print "\t%d CPU(s), %d process(es), quantum size = %d" % (num_cpu, num_proc, quantum_size)

            # loop to print process data
            for i in range(1, num_proc+1):
                print "\tPID %s, prio = %s, submit = %s, totCPU = %s, CPU = %s, I/O = %s" % (pid[i-1], priority[i], submit_time[i], total_cpu_time[i], compute_time[i], io_time[i])
                        
            print "Output:"

            # loop to calculate and print completion time and turnaround time
            # for each PID in the simulation
            for i in range(1, num_proc+1):
                print "complete_time[i]:", complete_time[i]
                print "submit_time[i]:", submit_time[i]
                turnaround = int(complete_time[i])-int(submit_time[i])
                print "turnaround:", turnaround
                TT_time+=turnaround
                print "TT_time", TT_time
                print "\tPID %s completed execution at %s, turnaround time = %d" % (pid[i-1], complete_time[i], turnaround)

            # calculate average total turnaround time, avg idle time, and
            # idle percent, then prints out results
            avg_TT_time = TT_time/num_proc
            avg_idle = idle/num_cpu
            percent_idle = avg_idle/float(complete_time[completed[num_proc-1]])*100

            print "\tAverage CPU idle time = %d (%d%%)" % (avg_idle, percent_idle)
            print "\tAverage process turnaround time = %d" % avg_TT_time
            
            check = 0