Class Design

• ThreadPoolExecutor owns the workers and task queue.
• Worker stores its thread name, state, current task, and idle time.
• Task stores a unique task ID and its remaining execution steps.
• A bounded FIFO queue stores waiting tasks.

Executor States

• RUNNING: threads and tasks may be added.
• SHUTTING_DOWN: no new threads or tasks are accepted, but existing queued and running tasks continue.
• TERMINATED: no queued tasks, running tasks, or active threads remain.

Thread States

• IDLE: the thread has no task.
• RUNNING: the thread is executing a task.
• STOPPING: the thread is executing its final task and will be removed when that task completes.

Thread Selection

• Thread names are provided through addThread.
• Every active thread name must be unique.
• When multiple idle threads are available, select the lexicographically smallest thread name.
• Process running threads in lexicographical order of their names.
• Assign queued tasks in FIFO order.
• When multiple idle threads can expire, select the lexicographically largest eligible thread first.

Task Submission Rules

1. If executor shutdown has started, reject the task and return "REJECTED". Do not apply the configured rejection policy.
2. If the waiting queue is not empty, place the new task at the end of the queue when space is available. This prevents a new task from bypassing older queued tasks.
3. If the waiting queue is empty and idle threads are available, start the task on the lexicographically smallest idle thread.
4. If no thread is available, add the task to the queue when space is available.
5. If the queue is full, apply the configured rejection policy.

Execution Rules

• Each task requires a positive number of execution steps.
• runOneStep() decreases every task that was running when the method started by one execution step.
• A task completes when its remaining steps become zero.
• Idle threads receive queued tasks in lexicographical order of thread names.
• Queued tasks are assigned in FIFO order.
• Tasks assigned during runOneStep() begin execution during the next call to runOneStep().
• A thread in the STOPPING state never receives another task.

Run One Step Order

1. Process all tasks that were running when the method started in lexicographical order of thread names. Decrease each task's remaining steps by one.
2. For every task whose remaining steps become zero, add a "COMPLETED:threadName:taskId" event.
3. Remove every worker in the STOPPING state whose task completed. Add a "REMOVED:threadName" event for each removed worker.
4. Change every other worker whose task completed to IDLE, set its idle time to 0, and assign queued tasks to available idle workers.
5. For each assignment, remove the oldest queued task, reset the worker's idle time to 0, and add a "STARTED:threadName:taskId" event.
6. Increase the idle time by one only for workers that were already idle when runOneStep() started and remain idle after task assignment. A worker that becomes idle during the current step keeps idle time 0.
7. Remove eligible workers whose keep-alive time has expired.
8. Perform graceful-shutdown cleanup when shutdown has started.
9. Sort and return all events.

Idle Time and Keep-Alive Expiration

• A newly added idle thread starts with idle time 0.
• A thread that completes a task and does not receive another task starts with idle time 0.
• A thread that receives a task has its idle time reset to 0.
• A thread is eligible for expiration when it is idle, the active thread count is greater than corePoolSize, and its idle time is greater than or equal to keepAliveSteps.
• Expiration is checked after all possible queued-task assignments have been made.
• Repeatedly remove the lexicographically largest eligible idle thread until no eligible thread remains or the active thread count equals corePoolSize.
• Add a "REMOVED:threadName" event for every expired thread.
• When keepAliveSteps == 0, an idle thread above corePoolSize may expire during the same step in which it becomes idle, provided that it does not receive a queued task.
• Individual thread shutdown and executor shutdown may reduce the thread count below corePoolSize.

Rejection Policies

• ABORT: reject the task and return "REJECTED".
• DISCARD: discard the task and return "DISCARDED".
• CALLER_RUNS: complete the task immediately and return "CALLER_RAN". The task never enters the executor state and produces no later event.
• DISCARD_OLDEST: remove the oldest queued task, enqueue the new task, and return "QUEUED:DROPPED:droppedTaskId", where droppedTaskId is the ID of the removed task.

Event Ordering

• Return events in lexicographical order of thread names, regardless of the internal order in which expired threads were selected.
• For the same thread, return COMPLETED before STARTED or REMOVED.
• A thread cannot produce both STARTED and REMOVED during the same step.

Method Signatures

Constructor

ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, int keepAliveSteps, int queueCapacity, String rejectionPolicy)

Add a Thread

boolean addThread(String threadName)

• Add an idle thread with the given name and idle time 0.
• Adding a thread does not immediately assign an existing queued task. Assignment occurs during the next runOneStep().
• Return false if the name is already active.
• Return false if the active thread count equals maximumPoolSize.
• Return false if executor shutdown has started.
• Otherwise, add the thread and return true.

Shut Down a Thread

boolean shutdownThread(String threadName)

• Remove an idle thread immediately.
• Change a running thread to STOPPING. It finishes its current task and is then removed without receiving another task.
• Return false if the thread does not exist or is already stopping.
• Return false if executor shutdown has already started.
• Otherwise, perform the shutdown action and return true.

Submit a Task

String submitTask(String taskId, int durationSteps)

• Return "REJECTED" if executor shutdown has started.
• Return "STARTED:threadName" if the task starts immediately.
• Return "QUEUED" if the task enters the queue.
• Otherwise, return the result produced by the configured rejection policy.

Run One Step

List<String> runOneStep()

• Perform all execution phases described above.
• Possible events are "COMPLETED:threadName:taskId", "STARTED:threadName:taskId", and "REMOVED:threadName".
• Return an empty list when no events occur.
• If the executor is already TERMINATED, make no changes and return an empty list.

Shut Down the Executor

boolean shutdown()

• Change the executor state from RUNNING to SHUTTING_DOWN.
• Stop accepting new threads and tasks.
• Allow queued and running tasks to finish.
• Return false if shutdown has already started.
• Return false if the queue is not empty and there is no active worker capable of processing another task.
• Otherwise, start graceful shutdown and return true.

Get Current State

List<String> getState()

1. The first entry is exactly one of: "EXECUTOR:RUNNING", "EXECUTOR:SHUTTING_DOWN", or "EXECUTOR:TERMINATED".
2. After the executor entry, return one entry for every active thread in lexicographical order of thread names.
3. An idle thread is represented as "THREAD:threadName:IDLE:idleSteps".
4. A running thread is represented as "THREAD:threadName:RUNNING:taskId:remainingSteps".
5. A stopping thread is represented as "THREAD:threadName:STOPPING:taskId:remainingSteps".
6. After all thread entries, return one "QUEUED:taskId" entry for every queued task in FIFO order.
7. Do not add a queue entry when the queue is empty.
8. When the executor is terminated, return only ["EXECUTOR:TERMINATED"].

Constraints

• 1 ≤ corePoolSize ≤ maximumPoolSize ≤ 1,000
• 0 ≤ keepAliveSteps ≤ 1,000,000
• 1 ≤ queueCapacity ≤ 100,000
• 1 ≤ threadName.length() ≤ 100
• 1 ≤ taskId.length() ≤ 100
• 1 ≤ durationSteps ≤ 1,000,000
• rejectionPolicy is one of "ABORT", "DISCARD", "CALLER_RUNS", or "DISCARD_OLDEST".
• Thread names and task IDs contain only letters, digits, underscores, and hyphens.
• Every task ID passed to submitTask is unique for the lifetime of the executor, including rejected and discarded tasks.
• Thread names and task IDs are case-sensitive.
• A removed thread name may be used again while the executor is still running.

Example