CS310 note — Processes, IPC, and Interrupts(Generated by chatgpt)

Course notes on xv6 / RISC-V Key concepts: Process · fork() · wait() · Zombie · Pipe · FD · dup() · exec() · Interrupt

1. Process

A process is a running program together with the state and resources required for execution.

A process contains:

• Address space
  • Code
  • Data
  • Heap
  • Stack
• CPU context
  • Registers
  • Program Counter (PC)
  • Stack Pointer (SP)
• File Descriptor (FD) table
• PID
• Parent process
• Process state

A useful mental model:

Process
├── Address Space
│   ├── Code
│   ├── Data
│   ├── Heap
│   └── Stack
│
├── CPU Context
│   └── Registers / PC / SP
│
├── FD Table
│   ├── 0 → stdin
│   ├── 1 → stdout
│   └── 2 → stderr
│
├── PID
└── State

2. fork()

fork() creates a new child process based on the calling process.

int pid = fork();

After fork():

                 fork()
                   │
           ┌───────┴───────┐
           ↓               ↓
        Parent            Child
       pid > 0             pid = 0

The return value is different in the two processes:

• Parent: receives the child’s PID
• Child: receives 0
• Failure: negative value

This is why one fork() call can appear to “return twice”:

int pid = fork();

printf("hello\n");

Both processes continue execution after fork() and therefore both execute the printf.

Memory after fork()

The child gets its own address space, initially containing a copy of the parent’s memory.

Parent memory              Child memory

counter = 10               counter = 10
     │                           │
     └── separate ───────────────┘
         memory spaces

Therefore, changing a normal variable in the child does not change the parent’s copy.

3. File Descriptors

A file descriptor (FD) is an integer used by a process to refer to a resource managed by the kernel.

Each process has its own FD table:

Process A                    Process B

FD Table                     FD Table
────────                     ────────
0 → stdin                    0 → stdin
1 → stdout                   1 → stdout
2 → stderr                   2 → stderr
3 → file                     3 → pipe

So an FD is not a pointer.

It is better to think of it as a handle / index into the current process’s FD table.

read(3, ...)
     │
     ↓
current process
     │
     ↓
FD table[3]
     │
     ↓
kernel-managed resource

The important distinction is:

The FD number is local to a process. The actual resource is managed by the kernel.

4. wait()

wait() allows a parent to synchronize with its child.

If the child has not exited yet, the parent blocks:

Parent
   │
 wait()
   │
   ↓
BLOCKED

The parent is not continuously checking:

while (child_not_finished)
    check();

That would be busy waiting.

Instead, the parent sleeps until the kernel has a reason to wake it.

When the child exits, the kernel changes the child’s state and can wake a parent waiting for that child.

5. Zombie Process

⭐ ZOMBIE — Important

A process does not disappear completely the instant it calls exit().

Suppose:

Parent
   │
   └── Child
          │
        exit()

The child has finished executing, but the parent may still need information about it, such as:

• its PID
• its exit status

Therefore, the kernel temporarily keeps a small amount of information about the terminated process.

The child enters the ZOMBIE state:

Child

RUNNING
   │
 exit()
   ↓
ZOMBIE
   │
   │  parent calls wait()
   ↓
CLEANED UP

Why do we need ZOMBIE?

Imagine the child disappears immediately after exit().

Then when the parent later calls:

wait(&status);

the kernel would have nowhere to obtain the child’s exit information.

Instead:

Child exits
    ↓
Child becomes ZOMBIE
    ↓
Kernel keeps exit information
    ↓
Parent calls wait()
    ↓
Kernel gives information to parent
    ↓
Child's remaining process resources are cleaned up

The key idea

Zombie does NOT mean the child is still running.

It means:

The child has finished running, but the kernel is temporarily keeping its process information because the parent has not collected it yet.

Also, wait() is not a separate process and is not continuously running in the background.

6. Pipe — Inter-Process Communication

⭐ PIPE — Important

A pipe is a mechanism for Inter-Process Communication (IPC).

Its basic purpose is:

Process A  ───────→  Process B

A pipe contains a kernel-managed buffer:

             PIPE
       ┌───────────────┐
write  │    buffer     │  read
──────→│               │──────→
       └───────────────┘

Data written into the pipe stays in the buffer until another process reads it.

6.1 pipe(p)

In C:

int p[2];

pipe(p);

p is just a normal array containing two integers.

The kernel fills the array with two file descriptors:

p[0] → read end
p[1] → write end

For example:

p[0] = 3
p[1] = 4

So:

read(p[0], buf, n);
write(p[1], buf, n);

means:

p[0]                     p[1]
  │                        │
  ↓                        ↓
read end                write end
  │                        │
  └─────── PIPE ───────────┘

Is p[0] a pointer?

No.

p[0] is just an integer FD.

It feels like a pointer because the FD allows the kernel to find the corresponding resource:

p[0] = 3

3
│
↓
FD table[3]
│
↓
pipe read end

7. Why pipe() Usually Comes Before fork()

This is one of the most important details.

Correct:

int p[2];

pipe(p);
fork();

Why?

Because fork() gives the child a separate copy of the parent’s FD table.

Before fork():

Parent FD table

0 → stdin
1 → stdout
2 → stderr
3 → pipe read
4 → pipe write

After fork():

Parent                         Child

0 → stdin                      0 → stdin
1 → stdout                     1 → stdout
2 → stderr                     2 → stderr
3 → pipe read                  3 → pipe read
4 → pipe write                 4 → pipe write

The FD tables are separate, but the inherited descriptors refer to the same underlying kernel pipe.

So:

The p array is copied. The pipe resource is shared through inherited file descriptors.

This distinction is extremely important.

8. close() and dup()

After fork(), both processes initially have both ends of the pipe.

Usually, each process closes the end it does not need.

For example:

Parent                         Child

write to pipe                  read from pipe

close(p[0])                    close(p[1])
use p[1]                       use p[0]

close(fd) removes that FD from the process’s FD table.

dup()

dup(oldfd) creates another FD referring to the same underlying resource.

For example:

close(1);
dup(p[1]);

If FD 1 is now the lowest available FD, dup() will return 1.

The result is:

Before:

1 → stdout
4 → pipe write

After:

1 → pipe write
4 → pipe write

Now FD 1 and FD 4 refer to the same underlying resource.

9. Connecting Two Processes with a Pipe

This is the key idea behind shell pipelines.

Suppose we want:

cat a.txt | head -5

Conceptually:

       Process A                    Process B
          cat                         head
           │                            │
       stdout (1)                    stdin (0)
           │                            ↑
           ↓                            │
      pipe write ──── PIPE ────→ pipe read

The shell can arrange this using close() and dup().

cat

close(1);
dup(p[1]);

Therefore:

FD 1 (stdout)
      ↓
pipe write end

When cat does:

write(1, ...);

the data goes into the pipe.

head

close(0);
dup(p[0]);

Therefore:

FD 0 (stdin)
      ↓
pipe read end

When head does:

read(0, ...);

it reads from the pipe.

So the two processes become connected:

cat
 │
 │ write(1)
 ↓
┌─────────────┐
│    PIPE     │
│   buffer    │
└─────────────┘
      │
      │ read(0)
      ↓
    head

The beautiful part is that cat and head do not need to know about the pipe.

They simply use their normal interfaces:

cat  → write(1, ...)
head → read(0, ...)

The shell changed what those FDs refer to.

10. Pipe Is Usually One-Way

A normal pipe is used for one-way communication:

A ─────────→ B

If we need communication in both directions:

A ←────────→ B

we can use two pipes:

Pipe 1:
A ─────────→ B

Pipe 2:
A ←───────── B

11. exec()

exec() does not create a new process.

Instead, it replaces the current process’s program image.

Before:

Process
└── program A

        exec()

After:

Process
└── program B

The process itself remains the same:

• same PID
• same process identity
• new program image

A common shell pattern is:

fork()
  │
  ├── Parent → wait()
  │
  └── Child  → exec()

This allows the shell to create a child and then turn that child into the program the user requested.

12. Traps

A trap is a mechanism for transferring control from the currently running program to the kernel.

Common examples include:

• System calls
• Exceptions
• Interrupts

For a system call:

User program
     │
     │ ecall
     ↓
   CPU trap
     ↓
   Kernel
     │
     ↓
system call handler

The CPU changes privilege level and transfers control to the kernel’s trap-handling code.

13. Interrupt

⭐ INTERRUPT — Important

An interrupt is an event that causes the CPU to transfer control to the operating system.

The crucial difference is who/what causes the event.

Synchronous vs. asynchronous

A system call is caused by the currently running program:

Program
   │
   │ ecall
   ↓
Kernel

This is synchronous: the program explicitly performs the operation.

An interrupt can come from hardware independently of the current program:

Hardware device
      │
      │ interrupt
      ↓
     CPU
      ↓
    Kernel

This is asynchronous.

For example, a timer interrupt can occur while a process is running.

Interrupt ≠ Polling

The CPU does not need to constantly ask:

"Did something happen?"
"Did something happen?"
"Did something happen?"

That would be polling / busy waiting.

Instead:

CPU runs normally
      │
      │
      ↓
Hardware event occurs
      │
      ↓
Interrupt
      │
      ↓
CPU transfers control to kernel

This allows the CPU to do useful work instead of continuously checking whether an event has happened.

14. Big Picture

The most useful way to connect these concepts is:

                 OPERATING SYSTEM

      ┌─────────────────────────────────┐
      │                                 │
      │          Process Management     │
      │                                 │
      │   fork() ──→ create child      │
      │   wait() ──→ synchronize       │
      │   exit() ──→ terminate         │
      │                                 │
      │   ZOMBIE ──→ terminated but     │
      │              not yet collected  │
      │                                 │
      ├─────────────────────────────────┤
      │                                 │
      │          IPC / File I/O         │
      │                                 │
      │   pipe() ──→ connect processes  │
      │   dup()  ──→ rearrange FDs     │
      │   close()→ remove FD            │
      │   exec() ─→ replace program     │
      │                                 │
      ├─────────────────────────────────┤
      │                                 │
      │          Traps / Interrupts     │
      │                                 │
      │   ecall ──→ user → kernel       │
      │   interrupt → hardware → kernel │
      │                                 │
      └─────────────────────────────────┘

Three concepts to remember especially well

1. Zombie

The child has already stopped running. The kernel keeps a small amount of information until the parent collects it with wait().

2. Pipe

p[0] and p[1] are FD numbers, not pointers. p[0] is the read end and p[1] is the write end. fork() gives parent and child their own FD tables, whose inherited entries can refer to the same underlying pipe.

3. Interrupt

The CPU does not continuously check whether an external event happened. Hardware can trigger an interrupt, causing the CPU to transfer control to the kernel.

MATH371 NOTE

Tricks in mapping

There are three identical red tiles, four identical blue tiles, and two identical yellow tiles.

How many distinct arrangements can be made by choosing eight of these nine tiles and arranging them in a row?

So the idea is there is a one to one mapping between choosing the first eight tiles and choosing the nine tiles.

Stars and bars

How many positive integer solutions are there to the equation

$$x_1+x_2+x_3+x_4=100$$

such that $x_1+x_2<50?$

The observation is that it is generally symmetric.

We can claim that the number of $x_1+x_2<50$ is equivalent to say $x_3+x_4<50$. There is no difference between the four variables. Then we notice $x_1+x_2<50$ is the same as saying $x_3+x_4> 50$. So the number of cases that $x_3+x_4<50$ is equivalent to $x_3+x_4>50$, which generally reaches the space of all solutions. However, excluding the case that $x_1+x_2=x_3+x_4=50$.

There are 9 identical candles in a row. Alice wants to blow out three of them, but no two blown-out candles can be adjacent.

Additionally, the candles at both ends must remain lit.

How many ways can Alice blow out 3 candles?

Since there are restrictions on the differentiation between the neighbors. Why don’t we look for the differentiation of the adjacent chosen candle? Same as saying “focus on NON-blown candles”!

So there would be 6 non-blown candles and we have to divides them into 4 groups with each group has at least 1 candles.

You have 10 identical candies. You must eat at least one candy each day until they’re all gone.

How many ways can you distribute the candies over the days?

Most confusing one.

Actually you have

ways if finishing in $k$ days.

It is actually,

Then you will find:

Each situation is mapped to a 9-digits binary, where 1 refers to 隔板, and 0 refers candy.

So the total ways is $2^9$