Memory-mapped files in Operating Systems - Time & Space Complexity

Time Complexity: Memory-mapped files

O(n)

Understanding Time Complexity

When using memory-mapped files, it is important to understand how the time to access data grows as the file size increases.

We want to know how the system's work changes when reading or writing larger files through memory mapping.

Scenario Under Consideration

Analyze the time complexity of accessing data using memory-mapped files.

// Pseudocode for memory-mapped file access
map = mmap(file, size)
for i in 0 to size-1:
    data = map[i]
    process(data)
munmap(map)

This code maps a file into memory, then reads each byte sequentially to process it.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Loop reading each byte from the mapped memory.
• How many times: Once for every byte in the file (size times).

How Execution Grows With Input

As the file size grows, the number of bytes to read grows too, so the work grows proportionally.

Input Size (n)	Approx. Operations
10	10 reads and processes
100	100 reads and processes
1000	1000 reads and processes

Pattern observation: The work grows directly with the file size; doubling the file doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to read and process the file grows in direct proportion to the file size.

Common Mistake

[X] Wrong: "Memory-mapped files always make access instant, so time does not grow with file size."

[OK] Correct: While memory mapping avoids some copying, reading each byte still takes time proportional to the file size because each byte must be accessed and processed.

Interview Connect

Understanding how memory-mapped files scale helps you explain efficient file access in real systems and shows you can reason about performance in practical scenarios.

Self-Check

What if we only accessed every 10th byte instead of every byte? How would the time complexity change?

Practice

1. What is the main advantage of using memory-mapped files in an operating system?

easy

A. They allow programs to access file data as if it were in memory, improving speed.

B. They compress files automatically to save disk space.

C. They encrypt files for security purposes.

D. They convert files into executable programs.

Solution

1. Step 1: Understand what memory-mapped files do

   Memory-mapped files let programs treat file contents like part of the computer's memory.

2. Step 2: Identify the benefit of this approach

   This allows faster and easier access to file data without explicit read/write calls.

3. Final Answer:

   They allow programs to access file data as if it were in memory, improving speed. -> Option A

4. Quick Check:

   Memory-mapped files = fast file access [OK]

Hint: Memory-mapped files map files to memory for speed [OK]

Common Mistakes:

• Confusing memory-mapping with file compression
• Thinking memory-mapping encrypts files
• Assuming memory-mapping creates executables

2. Which system call is commonly used on Unix-like systems to create a memory-mapped file?

easy

A. open()

B. fork()

C. mmap()

D. exec()

Solution

1. Step 1: Recall Unix system calls related to memory mapping

   The mmap() system call is designed to map files or devices into memory.

2. Step 2: Differentiate from other system calls

   open() opens files, fork() creates processes, and exec() runs programs, none map files to memory.

3. Final Answer:

   mmap() -> Option C

4. Quick Check:

   Unix memory mapping = mmap() [OK]

Hint: Unix memory mapping uses mmap() call [OK]

Common Mistakes:

• Choosing open() instead of mmap()
• Confusing fork() with memory mapping
• Thinking exec() maps files

3. Consider this pseudocode using memory-mapped files:

map = mmap(file)
map[0] = 'A'
print(file.read(1))

What will be printed?

medium

A. Nothing, because mmap disables file reading

B. The first byte of the file before mapping

C. An error because file.read() conflicts with mmap

D. 'A', the updated first byte via memory mapping

Solution

1. Step 1: Understand memory-mapped file behavior

   Writing to the mapped memory changes the file content directly.

2. Step 2: Analyze the print statement

   Reading the first byte from the file after mapping reflects the change 'A'.

3. Final Answer:

   'A', the updated first byte via memory mapping -> Option D

4. Quick Check:

   Memory map write updates file content [OK]

Hint: Changes in mmap reflect in file reads immediately [OK]

Common Mistakes:

• Assuming file.read() shows old data
• Thinking mmap disables file reading
• Expecting an error from simultaneous access

4. Identify the error in this memory-mapped file usage snippet:

fd = open('data.txt', 'r')
map = mmap(fd, length=100)
map[0] = 'B'

medium

A. Length parameter must be zero for mmap

B. File opened in read-only mode but writing to map attempted

C. File descriptor should be closed before mmap

D. map[0] cannot be assigned a character

Solution

1. Step 1: Check file open mode

   The file is opened with 'r' (read-only), so writing to mapped memory is not allowed.

2. Step 2: Understand mmap write restrictions

   Writing to a read-only mapped area causes an error or undefined behavior.

3. Final Answer:

   File opened in read-only mode but writing to map attempted -> Option B

4. Quick Check:

   Read-only file + write mmap = error [OK]

Hint: Write to mmap needs writable file open mode [OK]

Common Mistakes:

• Ignoring file open mode when writing
• Thinking length=0 is required
• Believing file must be closed before mmap

5. You want to share data between two running processes efficiently. Which feature of memory-mapped files helps achieve this?

hard

A. Mapping the same file into both processes' memory spaces to share data

B. Compressing the file to reduce memory usage

C. Encrypting the file to secure shared data

D. Automatically syncing file changes to a remote server

Solution

1. Step 1: Understand inter-process communication needs

   Sharing data between processes requires a common memory area accessible to both.

2. Step 2: Identify memory-mapped file feature for sharing

   Mapping the same file into both processes' memory allows them to read/write shared data efficiently.

3. Final Answer:

   Mapping the same file into both processes' memory spaces to share data -> Option A

4. Quick Check:

   Memory-mapped files enable shared memory between processes [OK]

Hint: Shared mapping = shared data between processes [OK]

Common Mistakes:

• Confusing compression with sharing
• Assuming encryption shares data
• Thinking syncing to server shares memory