Copy-on-write technique in Operating Systems - Time & Space Complexity

Time Complexity: Copy-on-write technique

O(n)

Understanding Time Complexity

Analyzing time complexity helps us understand how the copy-on-write technique affects system performance as data size grows.

We want to know how the number of operations changes when copying memory using this technique.

Scenario Under Consideration

Analyze the time complexity of the following simplified copy-on-write process.

function copyOnWrite(originalPage):
    if originalPage is shared:
        create newPage
        copy data from originalPage to newPage
        update reference to newPage
    else:
        use originalPage directly
    return page

This code copies memory only when a shared page is modified, otherwise it reuses the original page.

Identify Repeating Operations

Look for operations that repeat as input size grows.

• Primary operation: copying data from the original page to a new page.
• How many times: once per write to a shared page, and the copy size depends on the page size.

How Execution Grows With Input

The time to copy grows with the size of the page being copied, but only when a write occurs.

Input Size (page size in KB)	Approx. Operations (copying data)
4	4 units of copy work
16	16 units of copy work
64	64 units of copy work

Pattern observation: The copying work grows linearly with the page size, but only happens on writes, not on reads.

Final Time Complexity

Time Complexity: O(n)

This means the time to copy data grows directly with the size of the memory page being copied.

Common Mistake

[X] Wrong: "Copy-on-write always copies data immediately when a copy is made."

[OK] Correct: Copy-on-write delays copying until the data is actually modified, saving time and resources on simple copies.

Interview Connect

Understanding copy-on-write time complexity shows you can reason about efficient memory use and performance, a valuable skill in system design discussions.

Self-Check

What if the system used smaller page sizes for copy-on-write? How would that affect the time complexity?

Practice

1. What is the main idea behind the copy-on-write technique in operating systems?

easy

A. Data is copied only when it is modified, not when initially shared

B. Data is copied immediately when a process is created

C. Data is never copied, only referenced

D. Data is copied multiple times to improve speed

Solution

1. Step 1: Understand the purpose of copy-on-write

   Copy-on-write delays copying data until a modification is made, saving resources.

2. Step 2: Compare options with the concept

   Only Data is copied only when it is modified, not when initially shared correctly states that copying happens only on modification, not immediately.

3. Final Answer:

   Data is copied only when it is modified, not when initially shared -> Option A

4. Quick Check:

   Copy-on-write = Copy on modification [OK]

Hint: Copy happens only when data changes, not before [OK]

Common Mistakes:

• Thinking data copies immediately on sharing
• Believing data is never copied
• Assuming multiple copies improve speed

2. Which of the following best describes when a copy is made in a copy-on-write system?

easy

A. When the original data is read

B. When the data is modified

C. When the system boots

D. When the data is deleted

Solution

1. Step 1: Identify the trigger for copying in copy-on-write

   Copy-on-write means copying happens only when data is changed or written to.

2. Step 2: Match the correct event

   Only When the data is modified correctly states copying occurs on modification.

3. Final Answer:

   When the data is modified -> Option B

4. Quick Check:

   Copy-on-write triggers on modification [OK]

Hint: Copy only on write, not on read [OK]

Common Mistakes:

• Confusing read with write triggers
• Thinking copy happens at system start
• Assuming copy on deletion

3. Consider a process creation using copy-on-write. If the parent process has 100MB of memory, and the child process is created but does not modify any data, how much memory is used by both processes together?

medium

A. 0MB

B. 200MB

C. 50MB

D. 100MB

Solution

1. Step 1: Understand memory sharing in copy-on-write

   Initially, both processes share the same memory pages without copying.

2. Step 2: Calculate total memory usage

   Since no modifications occur, memory is shared, so total used is 100MB, not doubled.

3. Final Answer:

   100MB -> Option D

4. Quick Check:

   Shared memory means total = original size [OK]

Hint: No changes mean no extra memory used [OK]

Common Mistakes:

• Assuming memory doubles immediately
• Thinking child process uses zero memory
• Confusing copy-on-write with full copy

4. A system uses copy-on-write for file snapshots. A snapshot is taken, but later the original file is modified. What is the likely error if the snapshot also changes unexpectedly?

medium

A. Copy-on-write was not properly implemented, causing shared data to change

B. Snapshot was created after modification

C. The file system does not support snapshots

D. The snapshot was deleted accidentally

Solution

1. Step 1: Analyze snapshot behavior with copy-on-write

   Snapshots should remain unchanged because copy-on-write protects original data by copying on modification.

2. Step 2: Identify cause of snapshot changing

   If snapshot changes, it means copy-on-write failed and data was shared incorrectly.

3. Final Answer:

   Copy-on-write was not properly implemented, causing shared data to change -> Option A

4. Quick Check:

   Snapshot changes mean copy-on-write failure [OK]

Hint: Snapshot changes mean copy-on-write error [OK]

Common Mistakes:

• Assuming snapshot created after modification
• Blaming unsupported file system without evidence
• Confusing deletion with modification

5. In a system using copy-on-write, a parent process forks a child. The child modifies a small 1MB part of a 500MB memory space. How much additional memory is used after the modification?

hard

A. 500MB

B. 501MB

C. 1MB

D. 0MB

Solution

1. Step 1: Understand copy-on-write memory allocation on modification

   Only the modified part is copied, so only 1MB is newly allocated.

2. Step 2: Calculate total additional memory used

   The rest of the 499MB remains shared, so additional memory is exactly 1MB.

3. Final Answer:

   1MB -> Option C

4. Quick Check:

   Copy-on-write copies only changed data [OK]

Hint: Only changed data uses extra memory [OK]

Common Mistakes:

• Assuming entire memory is copied
• Adding modified size to total incorrectly
• Thinking no memory is used on modification