Benefits and challenges of multithreading in Operating Systems - Time & Space Complexity

Time Complexity: Benefits and challenges of multithreading

O(task_time / n + overhead)

Understanding Time Complexity

When using multithreading, we want to understand how the time to complete tasks changes as we add more threads.

We ask: Does adding threads always make things faster, and what costs come with it?

Scenario Under Consideration

Analyze the time complexity of this simple multithreaded task execution.

for each thread in threads:
    start thread to run task
wait for all threads to finish

This code runs the same task in multiple threads simultaneously and waits for all to complete.

Identify Repeating Operations

Look at what repeats and what costs time.

• Primary operation: Running the task in each thread.
• How many times: Once per thread, all running at the same time.

How Execution Grows With Input

As we add more threads, the total work is split, but overhead also grows.

Number of Threads (n)	Approx. Time
1	Full task time
10	About 1/10 task time + overhead
100	Much less task time but more overhead and possible delays

Pattern observation: More threads can reduce task time but overhead and resource limits slow gains.

Final Time Complexity

Time Complexity: O(task_time / n + overhead)

This means total time decreases roughly by the number of threads but extra costs limit perfect speedup.

Common Mistake

[X] Wrong: "Adding more threads always makes the program run faster."

[OK] Correct: More threads add overhead and can cause delays if resources like CPU or memory are limited.

Interview Connect

Understanding how multithreading affects time helps you explain real-world program behavior and shows you grasp practical system limits.

Self-Check

What if the tasks in each thread depend on each other? How would that affect the time complexity?

Practice

1. What is one main benefit of using multithreading in an operating system?

easy

A. It prevents any need for synchronization.

B. It allows multiple tasks to run at the same time, improving speed.

C. It guarantees no errors in program execution.

D. It makes the computer use less memory overall.

Solution

1. Step 1: Understand what multithreading does

   Multithreading lets a program run several tasks at once, which can make it faster and more responsive.

2. Step 2: Compare options to this benefit

   Only It allows multiple tasks to run at the same time, improving speed. correctly states this benefit. Other options mention memory, error prevention, or synchronization, which are not guaranteed benefits.

3. Final Answer:

   It allows multiple tasks to run at the same time, improving speed. -> Option B

4. Quick Check:

   Multithreading improves speed = D [OK]

Hint: Multithreading means doing many tasks simultaneously [OK]

Common Mistakes:

• Thinking multithreading reduces memory use
• Believing multithreading prevents all errors
• Ignoring the need for synchronization

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

easy

A. use the sleep() method to begin the thread

B. call run() method directly on the thread object

C. call start() method on the thread object

D. declare the thread with a variable but do not start it

Solution

1. Step 1: Recall thread starting method

   In many languages, calling the start() method on a thread object begins its execution in a new thread.

2. Step 2: Evaluate other options

   Calling run() directly runs code in the current thread, sleep() pauses a thread, and declaring without starting does not run the thread.

3. Final Answer:

   call start() method on the thread object -> Option C

4. Quick Check:

   start() begins thread execution = A [OK]

Hint: Use start() to run a thread, not run() directly [OK]

Common Mistakes:

• Calling run() instead of start()
• Using sleep() to start a thread
• Not starting the thread after declaring

3. Consider this scenario: Two threads try to update the same bank account balance at the same time without coordination. What is the likely result?

medium

A. The balance updates correctly every time.

B. The program will crash immediately.

C. One thread will wait until the other finishes automatically.

D. The balance may become incorrect due to race conditions.

Solution

1. Step 1: Understand race conditions in multithreading

   When two threads access and modify shared data without coordination, they can interfere and cause incorrect results.

2. Step 2: Analyze the options

   The balance may become incorrect due to race conditions. correctly describes this problem. The balance updates correctly every time. is wrong because updates can be wrong. One thread will wait until the other finishes automatically. is incorrect as waiting requires explicit synchronization. The program will not necessarily crash immediately.

3. Final Answer:

   The balance may become incorrect due to race conditions. -> Option D

4. Quick Check:

   Uncoordinated access causes errors = B [OK]

Hint: Shared data needs coordination to avoid errors [OK]

Common Mistakes:

• Assuming threads auto-wait for each other
• Thinking no errors happen without locks
• Believing program always crashes on conflict

4. A programmer wrote multithreaded code but notices inconsistent results when threads access shared data. What is the best fix?

medium

A. Add synchronization mechanisms like locks or mutexes.

B. Increase the number of threads to speed up processing.

C. Remove all thread creation to avoid errors.

D. Use sleep() calls to delay threads randomly.

Solution

1. Step 1: Identify cause of inconsistent results

   Inconsistent results usually come from threads accessing shared data without proper coordination.

2. Step 2: Choose the correct fix

   Adding synchronization like locks ensures only one thread accesses data at a time, preventing errors. Increasing threads or using sleep() won't fix data conflicts. Removing threads removes benefits.

3. Final Answer:

   Add synchronization mechanisms like locks or mutexes. -> Option A

4. Quick Check:

   Use locks to fix shared data errors = C [OK]

Hint: Use locks to control shared data access [OK]

Common Mistakes:

• Adding more threads without synchronization
• Using sleep() to fix timing issues
• Removing multithreading entirely

5. A video game uses multithreading to handle graphics rendering and user input simultaneously. What challenge must the developers carefully manage?

hard

A. Ensuring threads do not share data without proper synchronization to avoid glitches.

B. Making sure only one thread runs at a time to save CPU power.

C. Avoiding any use of threads to keep the game simple.

D. Using threads only for graphics and never for input.

Solution

1. Step 1: Understand multithreading in games

   Games use threads to do tasks like rendering and input at the same time for smooth play.

2. Step 2: Identify the main challenge

   Developers must prevent threads from causing errors by sharing data without synchronization, which can cause glitches or crashes.

3. Final Answer:

   Ensuring threads do not share data without proper synchronization to avoid glitches. -> Option A

4. Quick Check:

   Synchronization prevents glitches in multithreaded games = A [OK]

Hint: Synchronize shared data to avoid game glitches [OK]

Common Mistakes:

• Thinking only one thread should run at a time
• Avoiding threads to keep code simple
• Using threads only for graphics, ignoring input