System calls and their role in Operating Systems - Time & Space Complexity

Time Complexity: System calls and their role

O(n)

Understanding Time Complexity

System calls let programs ask the operating system to do tasks like reading files or creating processes.

We want to understand how the time taken by system calls grows as the number of calls increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    int fd = open("file.txt", O_RDONLY);
    read(fd, buffer, size);
    close(fd);
}
    

This code opens, reads, and closes a file n times in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs n times, each time making three system calls: open, read, and close.
• How many times: Each system call happens once per loop iteration, so n times total.

How Execution Grows With Input

As n grows, the total system calls grow directly with n because each iteration does the same fixed work.

Input Size (n)	Approx. Operations
10	30 system calls (10 open, 10 read, 10 close)
100	300 system calls (100 open, 100 read, 100 close)
1000	3000 system calls (1000 open, 1000 read, 1000 close)

Pattern observation: The total work grows steadily and directly with n.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line as the number of system calls increases.

Common Mistake

[X] Wrong: "System calls are instant, so their time cost doesn't add up."

[OK] Correct: Each system call involves switching from user mode to kernel mode, which takes time, so many calls add up to more time.

Interview Connect

Understanding how system calls scale helps you reason about program efficiency and resource use in real systems.

Self-Check

"What if we opened the file once before the loop and only read and closed inside the loop? How would the time complexity change?"

Practice

1. What is the main purpose of a system call in an operating system?

easy

A. To write code that runs only on specific hardware

B. To directly access hardware without OS intervention

C. To compile programs into machine code

D. To allow programs to request services from the operating system

Solution

1. Step 1: Understand what system calls do

   System calls provide a way for programs to ask the operating system to perform tasks on their behalf, such as reading files or managing processes.

2. Step 2: Compare options with this role

   Only To allow programs to request services from the operating system correctly describes this role. Other options describe unrelated actions like direct hardware access or compilation.

3. Final Answer:

   To allow programs to request services from the operating system -> Option D

4. Quick Check:

   System call = request OS service [OK]

Hint: System calls let programs ask OS for help [OK]

Common Mistakes:

• Thinking system calls bypass the OS
• Confusing system calls with compiling
• Assuming system calls are hardware instructions

2. Which of the following is the correct way a program typically uses a system call?

easy

A. By calling a special function provided by the operating system

B. By directly writing machine code instructions

C. By modifying the operating system kernel

D. By sending signals to hardware devices

Solution

1. Step 1: Identify how programs interact with system calls

   Programs use system calls by calling special functions (APIs) provided by the OS, which then perform the requested service.

2. Step 2: Eliminate incorrect options

   Direct machine code writing or kernel modification is not how normal programs use system calls. Sending signals to hardware is also not the typical method.

3. Final Answer:

   By calling a special function provided by the operating system -> Option A

4. Quick Check:

   System call usage = OS function call [OK]

Hint: System calls are accessed via OS functions, not direct code [OK]

Common Mistakes:

• Thinking programs write machine code for system calls
• Believing programs modify the OS kernel directly
• Confusing hardware signals with system calls

3. Consider this pseudocode using a system call to open a file:

fd = open_file("data.txt")
if fd == -1:
    print("Error opening file")
else:
    print("File opened successfully")

What will be printed if the file does not exist?

medium

A. No output

B. File opened successfully

C. Error opening file

D. System crash

Solution

1. Step 1: Understand the system call behavior

   The open_file system call returns a file descriptor if successful, or -1 if it fails (e.g., file not found).

2. Step 2: Follow the conditional logic

   If fd == -1, the program prints "Error opening file". Since the file does not exist, fd will be -1.

3. Final Answer:

   Error opening file -> Option C

4. Quick Check:

   File missing -> fd = -1 -> error message [OK]

Hint: Open returns -1 on failure, triggers error print [OK]

Common Mistakes:

• Assuming file opens successfully even if missing
• Expecting no output on failure
• Thinking system calls cause crashes on errors

4. A program tries to read from a file using this code snippet:

bytes_read = read_file(fd, buffer, 100)
if bytes_read == 0:
    print("End of file reached")
elif bytes_read < 0:
    print("Read error")
else:
    print(f"Read {bytes_read} bytes")

But it always prints "Read error" even when the file exists. What is the likely problem?

medium

A. The print statement syntax is incorrect

B. The file descriptor fd is invalid or not opened properly

C. The file is empty

D. The buffer size is too large

Solution

1. Step 1: Analyze the meaning of bytes_read < 0

   A negative return value from read_file indicates an error, often caused by an invalid file descriptor.

2. Step 2: Check other options for plausibility

   Buffer size being large or file empty would not cause a read error. Print syntax errors cause compile/runtime errors, not read errors.

3. Final Answer:

   The file descriptor fd is invalid or not opened properly -> Option B

4. Quick Check:

   Read error -> invalid fd [OK]

Hint: Negative read means invalid file descriptor [OK]

Common Mistakes:

• Blaming buffer size for read errors
• Assuming empty file causes read error
• Confusing print syntax with read errors

5. You want to write a program that creates a new file, writes data to it, and then closes it using system calls. Which sequence correctly represents these steps?

hard

A. Open file -> Write data -> Close file

B. Write data -> Open file -> Close file

C. Close file -> Open file -> Write data

D. Open file -> Close file -> Write data

Solution

1. Step 1: Understand the logical order of file operations

   You must first open the file to get a handle, then write data to it, and finally close it to save and release resources.

2. Step 2: Match the correct sequence

   Only Open file -> Write data -> Close file follows this logical order. Other options have steps in wrong order, which would cause errors or no effect.

3. Final Answer:

   Open file -> Write data -> Close file -> Option A

4. Quick Check:

   Open before write, close last [OK]

Hint: Always open before writing, close after done [OK]

Common Mistakes:

• Trying to write before opening file
• Closing file before writing
• Skipping the close step