Thread creation and management in Operating Systems - Time & Space Complexity

Time Complexity: Thread creation and management

O(n)

Understanding Time Complexity

When we create and manage threads in an operating system, it is important to understand how the time taken grows as we increase the number of threads.

We want to know how the cost of starting and handling threads changes when we add more threads.

Scenario Under Consideration

Analyze the time complexity of the following thread creation and management code snippet.

for (int i = 0; i < n; i++) {
    pthread_create(&thread[i], NULL, thread_function, NULL);
}

for (int i = 0; i < n; i++) {
    pthread_join(thread[i], NULL);
}
    

This code creates n threads and then waits for each to finish.

Identify Repeating Operations

• Primary operation: Creating and joining each thread in a loop.
• How many times: Each loop runs exactly n times, once per thread.

How Execution Grows With Input

As the number of threads n increases, the total time to create and join all threads grows proportionally.

Input Size (n)	Approx. Operations
10	About 20 operations (10 creates + 10 joins)
100	About 200 operations
1000	About 2000 operations

Pattern observation: The total operations increase linearly as the number of threads increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to create and manage threads grows directly in proportion to the number of threads.

Common Mistake

[X] Wrong: "Creating multiple threads happens instantly and does not add up with more threads."

[OK] Correct: Each thread creation and join takes some time, so more threads mean more total time spent.

Interview Connect

Understanding how thread creation time grows helps you design programs that use threads efficiently and avoid unexpected delays.

Self-Check

"What if threads were created recursively instead of in a loop? How would the time complexity change?"

Practice

1. What is the main purpose of creating threads in an operating system?

easy

A. To increase the size of the program's memory

B. To allow a program to perform multiple tasks at the same time

C. To make the program run slower

D. To reduce the number of files a program can open

Solution

1. Step 1: Understand what threads do

   Threads let a program split work into parts that run at the same time.

2. Step 2: Identify the main benefit

   This helps the program do many tasks faster and be more responsive.

3. Final Answer:

   To allow a program to perform multiple tasks at the same time -> Option B

4. Quick Check:

   Threads = multitasking [OK]

Hint: Threads let programs multitask simultaneously [OK]

Common Mistakes:

• Thinking threads increase memory size
• Believing threads slow down programs
• Confusing threads with file handling

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

easy

A. Define the thread function and call start() on the thread object

B. Write the thread code and call run() directly

C. Create a thread and call stop() immediately

D. Use delete() to begin the thread

Solution

1. Step 1: Understand thread starting methods

   Threads usually start by calling a special method like start() which runs the thread's code in parallel.

2. Step 2: Identify correct usage

   Calling run() directly runs code in the current thread, not a new one. stop() and delete() are not used to start threads.

3. Final Answer:

   Define the thread function and call start() on the thread object -> Option A

4. Quick Check:

   Use start() to launch threads [OK]

Hint: Always use start() to launch a thread, not run() [OK]

Common Mistakes:

• Calling run() instead of start()
• Trying to stop a thread to start it
• Using delete() to manage threads

3. Consider this pseudocode for thread creation:

thread = createThread(taskFunction)
thread.start()
thread.join()

What does thread.join() do?

medium

A. Waits for the thread to finish before continuing

B. Starts the thread execution

C. Stops the thread immediately

D. Creates a new thread

Solution

1. Step 1: Understand thread.join()

   The join() method pauses the current program until the thread finishes its task.

2. Step 2: Identify the effect of join()

   This ensures the program waits for the thread to complete before moving on.

3. Final Answer:

   Waits for the thread to finish before continuing -> Option A

4. Quick Check:

   join() = wait for thread end [OK]

Hint: join() waits for thread to finish before continuing [OK]

Common Mistakes:

• Thinking join() starts the thread
• Confusing join() with stopping the thread
• Believing join() creates a new thread

4. What is wrong with this thread creation code snippet?

thread = createThread(taskFunction)
thread.run()

Choose the best explanation.

medium

A. The thread will start twice

B. run() is the correct way to start a thread

C. The thread will never execute

D. Calling run() runs the task in the current thread, not a new thread

Solution

1. Step 1: Understand difference between run() and start()

   Calling run() directly executes the task in the current thread, not a new thread.

2. Step 2: Identify the problem

   This means no new thread is created, so the program does not run tasks concurrently.

3. Final Answer:

   Calling run() runs the task in the current thread, not a new thread -> Option D

4. Quick Check:

   run() = no new thread [OK]

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

Common Mistakes:

• Thinking run() starts a new thread
• Assuming thread runs twice
• Believing thread never executes

5. You want to create multiple threads to process a list of tasks, but ensure the main program waits until all threads finish. Which approach is best?

hard

A. Create threads but do not start or join them

B. Start each thread and immediately call run() on each

C. Start each thread and call join() on each one after starting all

D. Start one thread and ignore the others

Solution

1. Step 1: Understand thread starting and joining

   Starting each thread runs tasks concurrently. Calling join() waits for each thread to finish.

2. Step 2: Identify correct management

   Starting all threads first allows parallel work, then joining ensures the main program waits for all to complete.

3. Final Answer:

   Start each thread and call join() on each one after starting all -> Option C

4. Quick Check:

   Start all, then join all = proper thread management [OK]

Hint: Start all threads first, then join each to wait [OK]

Common Mistakes:

• Calling run() instead of start()
• Not joining threads, causing premature exit
• Starting only one thread and ignoring others