Katkat
Back

Schedule Dependent Tasks on a Bounded Thread Pool

BalyasnySoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a task scheduling system that manages complex dependency graphs while operating under strict concurrency constraints.

Problem Statement

Design a task scheduling system that executes jobs with inter-dependencies using a fixed-size thread pool. The system must ensure that a task only executes once all its prerequisites have successfully completed. If a prerequisite fails, the downstream tasks must be marked as 'blocked' or 'cancelled' appropriately.

Functional Requirements

  1. Dependency Resolution: Support a Directed Acyclic Graph (DAG) structure for task dependencies.
  2. Bounded Execution: Utilize a thread pool of size N. The system must not exceed this concurrency limit.
  3. Failure Propagation: If a task fails, all tasks transitively dependent on it must be prevented from running.
  4. Dynamic Submission: Support adding new tasks to the graph while the scheduler is running.

Non-Functional Requirements

  • Thread Safety: Multiple producers may submit tasks concurrently.
  • Efficiency: Minimize idle CPU time; maximize thread utilization without violating dependencies.
  • Scalability: The system should handle thousands of tasks without excessive memory overhead.

Your Deliverables

  • API Design: Define the interface for submitting tasks and defining dependencies (e.g., submit(task_id, callable, dependencies)).
  • Data Model: How will you represent the dependency graph and track the state of each task (e.g., PENDING, RUNNING, COMPLETED, FAILED)?
  • Architecture: Explain the synchronization mechanism (e.g., how workers wait for dependencies) and how you detect when a task becomes eligible for execution.
  • Failure Handling: Describe the mechanism for propagating failure states through the DAG.

Hints

Hint 1

Represent the dependency graph using an adjacency list and keep an atomic counter for each task representing the number of incomplete prerequisites.

Hint 2

Use a thread-safe task queue to hold tasks whose prerequisite counters have reached zero, allowing worker threads to pull from this queue.

Hint 3

When a task completes, decrement the counters of its dependent tasks and add those that reach zero to the task queue.

Follow-up questions

  • How would you implement task priorities if some tasks are more time-sensitive than others?
  • What changes would be necessary to support periodic tasks or tasks that need to retry upon transient failure?
  • How would you handle a scenario where the dependency graph contains a cycle, and how could you detect this at submission time?