# Simulate Round Robin Scheduling

Alternatively, guess who's doing a course on operating systems

Round Robin scheduling is a way to schedule ready processes in an operating system. Each process in the queue is run for a certain amount of time (quantum), interrupted after that time (if not yet finished), and then added back to the ready queue for another round.

Your task today is to print the order that tasks are executed in a round robin simulation.

## The Challenge

Given a list of [int, int] (both > 0), as well as a quantum, return a list of int representing the order that processes were executed. Assume that all the processes arrive at the same time.

The list of [int, int] represents a (simplified) list of processes. The two ints are the process id and service time (the time the process needs to fully run).

For example:

[[1, 5], [2, 10], [3, 3], [4, 12]]


Represents the following processes

Process ID Service Time
1 5
2 10
3 3
4 12

The quantum is an integer > 0 that represents the time slice dedicated to each process. A quantum of 4 means that each process is executed for 4 time units before being interrupted and then added to the ready queue.

If a quantum is larger than the time left on a process, then the next process is selected after the running process ends.

## Worked Example

Using the above process list ([[1, 5], [2, 10], [3, 3], [4, 12]]), and a quantum of 4, the process execution order will be:

t = 0
ready queue = [1, 2, 3, 4]
time left = [5, 10, 3, 12]
Select process 1 to run for 4 time units

t = 4
interrupt process 1
ready queue = [2, 3, 4, 1]
time left = [10, 3, 12, 1]
Select process 2 to run for 4 time units.

t = 8
interrupt process 2
ready queue = [3, 4, 1, 2]
time left = [3, 12, 1, 6]
Select process 3 to run for 3 time units

t = 11
process 3 finished
ready queue = [4, 1, 2]
time left = [12, 1, 6]
Select process 4 to run for 4 time units

t = 15
interrupt process 4
ready queue = [1, 2, 4]
time left = [1, 6, 8]
Select process 1 to run for 1 time unit

t = 16
process 1 finished
h    t
time left = [6, 8]
Select process 2 to run for 4 time units

t = 20
interrupt process 2
h     t
time left = [8, 2]
Select process 4 to run for 4 time units

t = 24
interrupt process 4
h     t
time left = [2, 4]
Select process 2 to run for 2 time units

t = 26
process 2 finished
h    t
time left = [4]
Select process 4 to run for 4 time units

t = 30
process 4 finished
no more proceses in the queue.


Therefore, the order of processes executed is:

[1, 2, 3, 4, 1, 2, 4, 2, 4]


## Rules

• Input can be taken as list[list[int, int]], int, list[int], list[int], int, or some other reasonable input method.
• The processes and quantum can be taken in any order.
• For example:
list[int: processIds]
list[int: serviceTimes]
int: quantum


or

list[int: serviceTimes]
int: quantum
list[int: processIds]


or any other combination.

• Output can be list[int], str (joined on newlines, or spaces, or any constant delimiter) or some other reasonable output method.
• There will always be at least one process.
• The process ids list will always be a permutation of the range [1, number of processes].
• The process ids can be 0-indexed if you want it to be for some reason. Using 0-indexing, the ids list will always be a permutation of the range [0, number of processes].
• The order of the process ids list is important - processes are executed in the order they arrive (in a first come first serve manner). That is how the ready queue in an actual RR simulation works after all (FCFS selection strategy, with pre-emption on time quantums).

## Test Cases

processes, times, quantum => order
[1, 2, 3, 4], [5, 10, 3, 12], 4 => [1, 2, 3, 4, 1, 2, 4, 2, 4]
[5, 4, 3, 2, 1], [20, 20, 20, 20, 20], 4 => [5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5], [3, 3, 3, 3, 8], 4 => [1, 2, 3, 4, 5, 5]
[1, 2, 3, 4, 5], [3, 3, 10, 3, 8], 2 => [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 5, 3, 5, 3]
[1], [20], 5 => [1, 1, 1, 1]
[1], [19], 4 => [1, 1, 1, 1, 1]


This is , so the shortest answer in each language wins.

• For N processes, are the process IDs guaranteed to be from 1 to N? If yes, are we allowed to take them 0-indexed instead? Sep 9, 2023 at 23:35
• You can use 0-indexed, yes. It'll be guaranteed that every number in the range [1, N] (or [0, N) if 0-indexed) will be present, but it may not be sorted. Sep 9, 2023 at 23:40
• Ah oops my bad. I've corrected it now Sep 9, 2023 at 23:47
• Wow, it's my research area! Sep 11, 2023 at 17:32

# Jelly, 7 bytes

÷Ċ⁵x"ZẎ


A full program that accepts Times Quantum ProcessIds and prints the schedule.

Try it online!

### How?

÷Ċ⁵x"ZẎ - Main Link: Times, Quantum
÷       - {Times} divided by {Quantum}
Ċ      - ceiling -> {SlotCounts}
⁵     - program's third argument -> ProcessIds
"   - {ProcessIds} zip {SlotCounts} with:
x    -   {ProcessId} times {SlotCount}
Z  - transpose
Ẏ - tighten
- implicit print


# APL(Dyalog Unicode), 17 bytes SBCS

{0~⍨,⍉↑⍺/⍨¨⌈⍵÷⍺⍺}


Try it on APLgolf!

An operator that takes the quantum as ⍺⍺, times as right argument ⍵ and 1-indexed process ids as left argument ⍺.

⌈⍵÷⍺⍺ times divided by quantum, rounded up.
⍺/⍨¨ For each result, make a vector with the corresponding process id repeated that many times.
↑ Join the vectors into a rectangular matrix, padding shorter vectors with 0s.
,⍉ Transpose matrix, then flatten into vector.
0~⍨ Remove 0s from vector.

# Excel, 45 bytes

=TOCOL(IF(A2#-A3*(ROW(1:99)-1)>0,A1#,NA()),2)


Quantum in cell A3, Process IDs and Service Times in spilled, horizontal ranges A1# and A2# respectively.

Returns a vertical array.

• Using Excel always feels like cheating, but this definitely works 😂 Sep 12, 2023 at 21:33

# K (ngn/k), 46 bytes

{2*:'/-1_(#:){(1_y),(0<*|x)#,x:(*y)-0,x}[x]\y}


Try it online!

• {(*+y)@*|+@/1<:\,/(!'-_-(*|+y)%x),\:'!#y} saves bytes but is not as nice somehow.
– doug
Sep 10, 2023 at 6:36

U{R])]O:]-[};{N)UO}:NE.UO[N):-E;UP^U][{N)UO}:](>):DOD]O;NE


Takes input as a list like quantum, id_1, servicetime_1, id_2, servicetime_2... with each argument on a separate line. I've gone ahead and made links for each individual test case because I know it's a bit cumbersome to translate.

### Explanation:

Pretty straightforward, just subtracts the quantum from each service time, checks if the service time has been used up, and decides whether to keep the values on the queue.

U{R])]O:]-[};{N)UO}:NE.  code block 0
U                        take quantum (q)
{R])]O:]-[};            negate q and store on queue:
{         }             loop
R])                      if q + r2 == 0
]O                      store r2 on queue
:    ;                break from loop
else
]-[                  decrement r2
end loop
{N)UO}:     store the remaining inputs on the queue:
{N)  }:     while there are still inputs
UO         store input on queue
NE   go to code block 1
.  end code block

UO[N):-E;UP^U][{N)UO}:](>):DOD]O;NE  code block 1
UO                                   keep q at top of queue
[                                  r2 = q
N):                               if there are no items left on the queue
-E                               go to block -1 (error, halt)
;                            endif
UP                          print the id on top of queue
^                         r1 = id
U][                      r2 = remaining service time + r2
{N)UO}:               retain remaining values on the queue
](>):          if r2 > 0
DO          put r1 on bottom of queue
D]O       put r2 on bottom of queue
;    endif
NE  go to code block 1

• why is it called Headass, if I may ask? Sep 11, 2023 at 3:20
• @Jonah I definitely had brainfuck in mind when designing it (for some reason), so I went for something similar: brain -> head (synonym), profanity -> profanity. Any other associations with the name to how the language functions are coincidental, for better or worse. If it were a better language I'd feel worse for giving it such a dumb name :-) Sep 11, 2023 at 14:57

# Vyxal, 44 bitsv2, 5.5 bytes

/⌈$ẋ∩f  Try it Online! ### How? Port of my Jelly answer. /⌈$ẋ∩f - [Quantum, Times, ProcessIds]
/      - divide -> [Times/Quantum, ProcessIds]
⌈     - ceil -> [SlotCounts, ProcessIds]
dups"; @"&#
1_ roll0.: Q n>o0$n , -1.: Q0>"pop"|#  Try it on scline! Initial solution. ## Explanation Prettified code: =$n.
dups ( ; @ ) &#
1_ roll 0.: Q n>o 0 $n , - 1.: Q 0> \pop |#  Takes processes input as a list of [int int]. • =$n quantum as n
• dups ( ; @ ) &# if stack is not empty, execute next line and loop...
• 1_ roll rotate bottom of stack to the top
• 0.: Q n>o output process number
• 0 $n , - decrement service time by n • 1.: Q 0> \pop |# if service time <= 0, then pop from the stack # Python, 61 bytes lambda q,i:[I for Q in range(max(i)[0])for C,I in i if C>q*Q]  Attempt This Online! Expects quantum,list of cost-id pairs. ## How? Instead of updating the remaining cost in each pair we run through the unchanged list repeatedly and after each cycle update the threshold (0,q,2q,3q,...) by which processes are filtered. # Charcoal, 23 bytes Ｆ⌈Ｅθ§ι¹ＩＥΦθ››§κ¹ι﹪ιη§κ⁰  Try it online! Link is to verbose version of code. Takes input as a list of pairs of (process id, service time) and the quantum. Explanation: Ｆ⌈Ｅθ§ι¹  Loop up to the maximum service time. ＩＥΦθ››§κ¹ι﹪ιη§κ⁰  Output any processes due to be serviced at this time (i.e. their service time is higher and this is actually a multiple of the quantum.) Would be 17 bytes if dictionary order was guaranteed: Ｆ⌈ＥθιＩＥΦθ››κι﹪ιηλ  Attempt This Online! Link is to verbose version of code. Takes input as a dictionary and a number. Explanation: Ｆ⌈Ｅθι  Loop up to the maximum service time. ＩＥΦθ››κι﹪ιηλ  Output any processes due to be serviced at this time (i.e. their service time is higher and this is actually a multiple of the quantum.) • > Input can be taken as list[list[int, int]], int...or some other reasonable input format Sep 10, 2023 at 7:53 • Your 23 byter is valid as taking int int pairs is perfectly fine. Sep 10, 2023 at 7:53 • @lyxal Thanks, I had overlooked that. – Neil Sep 10, 2023 at 8:49 # Scala 3, 72 bytes A port of @loopy walt's Python answer in Scala. Golfed version. Attempt This Online! (q,i)=>(for{Q<-0 to i.map(_._1).max-1;p<-i;if p._1>q*Q}yield p._2).toSeq  Ungolfed version. Attempt This Online! def f(q: Int, i: List[(Int, Int)]): List[Int] = { val maxC = i.maxBy(_._1)._1 (for { Q <- 0 until maxC pair <- i if pair._1 > q * Q } yield pair._2).toList }  # 05AB1E, 10 9 bytes /îδиÅ\ζ˜þ  -1 thanks to Kevin Cruijssen Try it online! • 9 bytes - /îδиÅ\ζ˜þ Sep 11, 2023 at 6:27 • @KevinCruijssen Nice! Didn't think of using Å\  there Sep 11, 2023 at 11:54 # Retina 0.8.2, 76 75 bytes \d+(?=,|$)
$*# (?=.*, (#)+)(?<-1>#)+ @ S, rM!&.+@ O$^.+: (@+)
$1_ : @+  Try it online! Link includes test cases. Takes input as a list of pairs and an integer. Explanation: \d+(?=,|$)
$*#  Convert the durations to unary. (?=.*, (#)+)(?<-1>#)+ @  Calculate the number of times each process gets scheduled. S,  Split each process to its own line. rM!&.+@  Match each process once for each tick. This has to be done in reverse for the overlapping matches to work properly, so the processes actually come out in the wrong order. O$^.+: (@+)
$1_  Sort them according to the tick count and fix up the ordering. : @+  Delete the tick counts. (Out of interest I did try a repeat/transpose/flatten approach but the best I could do in Retina 1 was 79 bytes.) # Uiua, 11 bytes ▽±.♭⍉⬚0≡↯⌈÷  Try it online! ▽±.♭⍉⬚0≡↯⌈÷ input: quantum, times, IDs ⌈÷ divide times by quantum and take ceiling -> occurrence count ⬚0≡↯ duplicate each ID that many times forming a row in a matrix, padding short rows with zeros for the first example, [[1,1,0], [2,2,2], [3,0,0], [4,4,4]] ♭⍉ transpose and flatten ▽±. keep nonzero elements  Some 12- and 13-byte solutions: ⊏⍏⊐/⊂⊃⊐∵⇡▽⌈÷ # 12 ⌈÷ same as the above ⊃ run two functions over two stack items(repetitions, ids): ⊐/⊂ ⊐∵⇡ ranges of repetitions concatenated; [0, 1, 0, 1, 2, 0, 0, 1, 2] ▽ duplicate each ID in a vector; [1, 1, 2, 2, 2, 3, 4, 4, 4] ⊏⍏ reorder the IDs by the ascending order of the ranges ⊏⍏-⊗⊃.⍏⊃⊚▽⌈÷ # 12 ⊏⍏ ⊃ ▽⌈÷ same as above ⊚ duplicate indices by values; [0, 0, 1, 1, 1, 2, 3, 3, 3] ⊗⊃.⍏ self-index and sorting order: [0, 0, 2, 2, 2, 5, 6, 6, 6], [0, 1, 2, 3, 4, 5, 6, 7, 8] - subtract first from second: [0, 1, 0, 1, 2, 0, 0, 1, 2] ⊏⍏⍜⊕□⊐≡⍏..▽⌈÷ # 13 ⊏⍏ .▽⌈÷ same as above, but using just duplicated ids ⍜⊕□⊐≡⍏. group by itself and replace each group with range of that length  # Python3, 83 bytes: def R(p,t,q): Q,s=[*zip(p,t)],[] for a,b in Q:s+=[a];Q+=[(a,b-q)]*(b>q) return s  Try it online! • (b-q>0) is (b>q) Sep 10, 2023 at 0:20 • @Arnauld Thank you, updated Sep 10, 2023 at 0:59 # AWK, 68 bytes a=$1{for(b=1;b<NF;){$++c=$++b;if(0<d=$++b-c){$++NF=$c;$++NF=d}}}NF=c


Try it online!

This program expects the first commandline argument to give the quantum. And the arguments after that are pairs of pid/service-time values. It works by iterating through the pid/time pairs, adding the pid to an output list. Then if the service time remaining is larger than the quantum, the pid and remaining time are appended to the argument. So it essentially extends the commandline arguments as needed. And the "output list" is stored at the beginning of the argument list. Each iteration consumes two values from the argument list but only adds one (the pid) to the front of the argument list. So once the all the arguments have been processed, all that's left to do is set the number of arguments to the size of the output list. The pid list if printed automatically since the "test" that sets the number of arguments has no associated code.

a=$1{ ... } -- set "a" to the quantum (first arg) .. for( ... ){ ... } -- loop to process pairs of args .. .. b=1;b<NF; -- stops when at the end of args .. .. ..$++c=$++b; -- copy the "pid" to the output list and increment .. .. .. if( ... ){ ... } -- "true" when service time > quantum .. .. .. .. 0<d=$++b-c    -- set "d" to remaining service time
.. .. .. .. .. $++NF=$c;  -- append pid to end of args
.. .. .. .. .. \$++NF=d    -- append remaining service time
NF=c                      -- set the number of pids to print


# C++ (gcc), 97 93 bytes

[](auto&l,int q,auto o){for(int m;m=0,q;q=m<q?m:q)for(auto&[p,t]:l)m=t>m?t:m,t>0?o=p:o,t-=q;}


Try it online!

4 bytes shaved off thanks to ceilingcat. Takes a list of pairs as input, and uses an insert iterator to return the results. Explanation:

[](auto& l, int q, auto o) {   // Process list, quantum, output iterator
for (int m; m = 0,         // Will track maximum time of all processes
q;                  // As long as quantum is still non-zero
q = m < q ? m : q)  // Limit quantum to the maximum process time
for (auto& [p, t]: l)   // Loop over all processes
m = t > m ? t : m,  // Update the maximum time
t > 0 ? o = p : o,  // Output process number if time left is positive
t -= q;             // Subtract the quantum from the time
}