TypeScript: A pool of async workers

Run many tasks with at most K at a time, the way a server limits how many requests it sends at once.

What to build

A program that simulates a pool of K workers running timed tasks.

Requirements

  • Declare interface Job { name: string; ms: number } and run the jobs with K async workers that share one queue, taking jobs in input order.
  • When a worker starts a job print start NAME at T; when it finishes print done NAME at T, where T is the simulated time in milliseconds (the run starts at 0). A worker that finishes a job prints its done line and then starts its next job at the same time.
  • At the end print total T, the time the last job finished.

Input

Line 1: K and n. Then n lines NAME MS.

Output

2n lines, then the total.

Constraints

1 ≤ K ≤ 5; 1 ≤ n ≤ 20; 1 ≤ MS ≤ 10000; no two jobs finish at the same time.

Example

Input:

2 4
a 300
b 100
c 250
d 60

Output:

start a at 0
start b at 0
done b at 100
start c at 100
done a at 300
start d at 300
done c at 350
done d at 360
total 360

Why it works

Each worker awaits one job at a time, so at most K timers are pending, and because a worker takes the next job as soon as it is free, the pool finishes far sooner than one worker would while never running more than K at once.

Examples

Example 1 · Input
2 4
a 300
b 100
c 250
d 60
Expected output
start a at 0
start b at 0
done b at 100
start c at 100
done a at 300
start d at 300
done c at 350
done d at 360
total 360
Example 2 · Input
1 2
x 10
y 20
Expected output
start x at 0
done x at 10
start y at 10
done y at 30
total 30

Hints

Hint 1

Start K async workers; each takes the next task from a shared queue until it is empty.

Hint 2

Time is simulated: a task that starts at time S with duration D finishes at S + D, so keep the clock in a variable you update when a task finishes.

Solution

Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";

interface Job {
  name: string;
  ms: number;
}

function wait(ms: number): Promise<void> {
  return new Promise((resolve) => setTimeout(resolve, ms));
}

const [k, n] = read().split(" ").map(Number);
const queue: Job[] = [];
for (let i = 0; i < n; i++) {
  const [name, ms] = read().split(" ");
  queue.push({ name, ms: Number(ms) });
}

let clock = 0;

async function worker(): Promise<void> {
  for (let job = queue.shift(); job; job = queue.shift()) {
    const start = clock;
    console.log("start " + job.name + " at " + start);
    await wait(job.ms);
    clock = start + job.ms;
    console.log("done " + job.name + " at " + clock);
  }
}

async function main(): Promise<void> {
  const workers: Promise<void>[] = [];
  for (let i = 0; i < k; i++) workers.push(worker());
  await Promise.all(workers);
  console.log("total " + clock);
}

main();

Lesson: Async code with types →