Why threads enable concurrent execution in Operating Systems - Performance Analysis

Time Complexity: Why threads enable concurrent execution

O(t)

Understanding Time Complexity

We want to understand how using threads affects the time it takes to run tasks.

Specifically, how does splitting work into threads change the total execution time as tasks grow?

Scenario Under Consideration

Analyze the time complexity of this simple threaded task execution.

for each task in tasks:
    create a thread to run task
wait for all threads to finish

This code runs multiple tasks by creating a thread for each, then waits for all to complete.

Identify Repeating Operations

Look at what repeats and takes time:

• Primary operation: Creating and running a thread for each task
• How many times: Once per task, so as many times as there are tasks

How Execution Grows With Input

When tasks increase, threads run many tasks at the same time.

Input Size (n)	Approx. Operations
10	About 10 threads running mostly together
100	About 100 threads running mostly together
1000	About 1000 threads running mostly together

Pattern observation: The total time depends on the longest task, not the number of tasks, because threads run tasks concurrently.

Final Time Complexity

Time Complexity: O(t)

This means the total time grows with the longest single task time, not the total number of tasks.

Common Mistake

[X] Wrong: "More tasks always mean more total time because each task adds time."

[OK] Correct: Threads let tasks run at the same time, so total time depends on the longest task, not the count.

Interview Connect

Understanding how threads let tasks run together helps you explain real-world programs that do many things at once efficiently.

Self-Check

"What if tasks have to share a resource and wait for each other? How would that affect the time complexity?"

Practice

1. Why do threads enable concurrent execution in an operating system?

easy

A. Because threads allow multiple tasks to run at the same time within a single program

B. Because threads use separate memory spaces for each task

C. Because threads prevent any task from running simultaneously

D. Because threads slow down the program to avoid errors

Solution

1. Step 1: Understand what concurrent execution means

   Concurrent execution means running multiple tasks at the same time or overlapping in time.

2. Step 2: Identify how threads work within a program

   Threads allow different parts of a program to run independently but share the same memory, enabling multiple tasks to happen simultaneously.

3. Final Answer:

   Because threads allow multiple tasks to run at the same time within a single program -> Option A

4. Quick Check:

   Threads = multiple tasks at once [OK]

Hint: Threads run tasks together inside one program [OK]

Common Mistakes:

• Thinking threads use separate memory spaces
• Believing threads prevent simultaneous tasks
• Assuming threads slow down programs

2. Which of the following is the correct way to create a new thread in many programming languages?

easy

A. start Thread(task)

B. Thread.run(task)

C. create thread task

D. new Thread(task).start()

Solution

1. Step 1: Recall common thread creation syntax

   Many languages use a Thread object with a start() method to begin execution.

2. Step 2: Compare options to correct syntax

   new Thread(task).start() matches the common pattern: creating a Thread with a task and calling start() to run it.

3. Final Answer:

   new Thread(task).start() -> Option D

4. Quick Check:

   Thread creation = new Thread(...).start() [OK]

Hint: Threads start with new Thread(...).start() [OK]

Common Mistakes:

• Using run() instead of start() to begin thread
• Writing incorrect keywords like 'create thread'
• Confusing thread creation with task execution

3. Consider this pseudocode using threads:

start thread A: print("Hello")
start thread B: print("World")

What is a possible output?

medium

A. HelloHello

B. World Hello

C. Either 'Hello World' or 'World Hello'

D. Hello World

Solution

1. Step 1: Understand thread execution order

   Threads run independently and may execute in any order or overlap.

2. Step 2: Analyze possible outputs

   Since thread A and B print different words, output order can vary: "Hello World" or "World Hello".

3. Final Answer:

   Either 'Hello World' or 'World Hello' -> Option C

4. Quick Check:

   Thread output order varies = Either 'Hello World' or 'World Hello' [OK]

Hint: Thread outputs can appear in any order [OK]

Common Mistakes:

• Assuming threads always run in start order
• Expecting combined outputs like 'HelloHello'
• Ignoring concurrency effects on output order

4. What is wrong with this thread code snippet?

Thread t = new Thread();
t.run();

medium

A. It should call t.start() to run the thread concurrently

B. Thread cannot be created without a task

C. run() method does not exist in Thread class

D. Threads must be named before running

Solution

1. Step 1: Identify how to start a thread properly

   Calling run() directly runs the code in the current thread, not a new thread.

2. Step 2: Correct method to start a thread

   Using start() launches the thread to run concurrently.

3. Final Answer:

   It should call t.start() to run the thread concurrently -> Option A

4. Quick Check:

   Use start() to run thread concurrently [OK]

Hint: Use start(), not run(), to launch threads [OK]

Common Mistakes:

• Calling run() instead of start()
• Not providing a task to the thread
• Thinking threads need names to run

5. A program uses multiple threads to download files and update a shared progress counter. What must the program do to avoid errors when threads update this shared counter?

hard

A. Avoid using threads for updating shared data

B. Use synchronization methods to control access to the counter

C. Create a separate counter for each thread without sharing

D. Allow all threads to update the counter at the same time

Solution

1. Step 1: Understand shared data risks in threads

   When multiple threads access shared data, race conditions can cause errors.

2. Step 2: Identify how to prevent race conditions

   Synchronization (like locks) ensures only one thread updates the counter at a time, preventing conflicts.

3. Final Answer:

   Use synchronization methods to control access to the counter -> Option B

4. Quick Check:

   Synchronize shared data access = Use synchronization methods to control access to the counter [OK]

Hint: Synchronize shared data updates to avoid errors [OK]

Common Mistakes:

• Letting threads update shared data simultaneously
• Ignoring synchronization needs
• Avoiding threads instead of managing access