Test yourself · category 8 of 20

fork, exec, exit, wait, kill

How a process is born as a copy, becomes a new program, dies in two halves as a zombie, is reaped by its parent, and is killed by a flag it checks itself.

1warm-upChoose one

After fork, parent and child run the same code from the same instruction. How does fork() come to return 0 in the child but the child’s pid in the parent?

kernel/proc.c

// copy saved user registers.
*(np->trapframe) = *(p->trapframe);
280
// Cause fork to return 0 in the child.
np->trapframe->a0 = 0;

kfork copies the parent’s trapframe into the child’s and then sets the child’s saved a0 to 0; the parent’s a0 receives kfork’s return value, the pid.The child resumes at a different user instruction, one that loads 0 into a0.forkret sets a0 = 0 for every new process before returning to user mode.The user-space fork() stub compares the returned pid with getpid() and returns 0 if they differ.

2warm-upTrue or false, and why

True or false: a fork child’s kernel stack starts out as a copy of its parent’s kernel stack, so that the child can return through sys_fork, syscall and usertrap just like the parent.

TrueFalse

Why?

The child shares the parent’s kernel stack until it calls exec.The child runs on its slot’s own kernel stack, empty, with a forged context (ra = forkret, sp = top), and forkret goes straight to user space.The child has no kernel stack at all until its first trap into the kernel.

3warm-upChoose all that apply

A child process has called exit and is now a ZOMBIE; its parent has not called wait yet. Which of these does the zombie still hold?

Its p->lock, held until the parent reaps itIts trapframe pageIts reference to the current directoryIts slot in proc[], with its pid and exit statusIts user memory and user page tableIts open files

4solidPut in order

ls (on hart 2) calls exit(0) while its parent, the shell, sleeps in kwait. Put these events in the order they must happen.

Hart 2’s scheduler releases ls’s p->lock
kexit calls wakeup(p->parent)
kexit closes ls’s open files and drops its current directory
kexit releases wait_lock and calls sched
The shell’s kwait acquires ls’s p->lock, sees ZOMBIE and calls freeproc
kexit acquires its own p->lock and sets state = ZOMBIE
kexit acquires wait_lock and calls reparent

5warm-upChoose one

Process A is running in user mode on hart 1. On hart 0, another process calls kill(A's pid), and kkill finds A’s slot. What does kkill do to A?

kernel/proc.c

597// Kill the process with the given pid.
598// The victim won't exit until it tries to return
599// to user space (see usertrap() in trap.c).
600int
601kkill(int pid)
602{
603  struct proc *p;
604
605  if (pid == 0)
606    return -1;
607
608  for (p = proc; p < &proc[NPROC]; p++) {
609    acquire(&p->lock);
610    if (p->pid == pid) {
611      p->killed = 1;
612      if (p->state == SLEEPING) {
613        // Wake process from sleep().
614        p->state = RUNNABLE;
615      }
616      release(&p->lock);
617      return 0;
618    }
619    release(&p->lock);
620  }
621  return -1;
622}

It calls kexit on A’s behalf.It sets A’s state to ZOMBIE.It sets A->killed = 1 under A’s p->lock, and nothing else; A keeps running until its next trap.It sends an interrupt to hart 1 so that A stops at once.

6warm-upTrue or false, and why

True or false: after a successful exec, the process still has the same pid and the same open file descriptors it had before.

TrueFalse

Why?

kexec replaces only the user side (page table, size, the trapframe’s epc, sp and a1, and the name); it never touches pid, ofile, cwd or parent.It is true because sys_exec duplicates each descriptor with filedup before calling kexec.It is true because exec creates a new process that copies the pid and descriptors from the old one.

7warm-upType a number

After loading the program’s segments, kexec calls uvmalloc on line 91. How many pages does that call map in the new page table?

kernel/exec.c

// Allocate some pages at the next page boundary.
// Make the first inaccessible as a stack guard.
// Use the rest as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
if ((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK + 1) * PGSIZE, PTE_W)) ==
    0)
  goto bad;
sz = sz1;
uvmclear(pagetable, sz - (USERSTACK + 1) * PGSIZE);
sp = sz;
stackbase = sp - USERSTACK * PGSIZE;

decimal, 0x hex or 0b binary

8warm-upClick the line

In kfork, click the line at which the child first becomes eligible to be run by a scheduler on any hart.

kernel/proc.c

256// Create a new process, copying the parent.
257// Sets up child kernel stack to return as if from fork() system call.
258int
259kfork(void)
260{
261  int i, pid;
262  struct proc *np;
263  struct proc *p = myproc();
264
265  // Allocate process.
266  if ((np = allocproc()) == 0) {
267    return -1;
268  }
269
270  // Copy user memory from parent to child.
271  if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
272    freeproc(np);
273    release(&np->lock);
274    return -1;
275  }
276  np->sz = p->sz;
277
278  // copy saved user registers.
279  *(np->trapframe) = *(p->trapframe);
280
281  // Cause fork to return 0 in the child.
282  np->trapframe->a0 = 0;
283
284  // increment reference counts on open file descriptors.
285  for (i = 0; i < NOFILE; i++)
286    if (p->ofile[i])
287      np->ofile[i] = filedup(p->ofile[i]);
288  np->cwd = idup(p->cwd);
289
290  safestrcpy(np->name, p->name, sizeof(p->name));
291
292  pid = np->pid;
293
294  release(&np->lock);
295
296  acquire(&wait_lock);
297  np->parent = p;
298  release(&wait_lock);
299
300  acquire(&np->lock);
301  np->state = RUNNABLE;
302  release(&np->lock);
303
304  return pid;
305}

Your pick: none yet (click a line in the code)

9solidChoose one

Near its end, kfork releases the child’s lock (line 294), takes wait_lock to set np->parent, releases it, and only then re-acquires the child’s lock. Why not keep the child’s lock and take wait_lock inside it?

kernel/proc.c

290  safestrcpy(np->name, p->name, sizeof(p->name));
291
292  pid = np->pid;
293
294  release(&np->lock);
295
296  acquire(&wait_lock);
297  np->parent = p;
298  release(&wait_lock);
299
300  acquire(&np->lock);
301  np->state = RUNNABLE;
302  release(&np->lock);
303
304  return pid;
305}

So that a scheduler can start running the child while the parent sets np->parent.Because no hart may hold wait_lock and a p->lock at the same time.Because release must run to publish the child’s memory before its parent is set.The lock order is wait_lock before any p->lock. Taking them the other way round could deadlock with an exiting process that holds wait_lock and walks every p->lock in wakeup.

10solidChoose one

Line 279 copies the parent’s whole trapframe into the child’s. What is in the child’s trapframe->kernel_sp right after that line, and why is it not a problem?

kernel/proc.c

// Copy user memory from parent to child.
if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
  freeproc(np);
  release(&np->lock);
  return -1;
}
np->sz = p->sz;
277
// copy saved user registers.
*(np->trapframe) = *(p->trapframe);
280
// Cause fork to return 0 in the child.
np->trapframe->a0 = 0;

The parent’s kernel-stack top, and that is a real hazard: the child’s first trap would land on the parent’s kernel stack.Zero, because the trapframe page was freshly allocated.The top of the parent’s kernel stack; harmless, because prepare_return in forkret rewrites kernel_sp (and the other kernel fields) before the child can trap.The top of the child’s own kernel stack, which allocproc stored there.

11solidChoose one

In kexit, wakeup(p->parent) (line 353) comes before acquire(&p->lock) (line 355). Why can’t kexit take its own lock first?

kernel/proc.c

347  acquire(&wait_lock);
348
349  // Give any children to init.
350  reparent(p);
351
352  // Parent might be sleeping in wait().
353  wakeup(p->parent);
354
355  acquire(&p->lock);
356
357  p->xstate = status;
358  p->state = ZOMBIE;
359
360  release(&wait_lock);
361
362  // Jump into the scheduler, never to return.
363  sched();
364  panic("zombie exit");
365}

Because the lock order requires p->lock to be taken only after every wakeup.Because wakeup must run with interrupts on, and holding p->lock would turn them off.wakeup acquires every slot’s p->lock in turn, including the exiting process’s own; if this hart already held it, acquire would panic.So that the parent can see the child as a zombie the moment it wakes.

12solidChoose one

kwait holds wait_lock from its scan until after sleep_prepare, and releases it only just before sleep. Why does it register before releasing wait_lock?

kernel/proc.c

acquire(&wait_lock);
377
for (;;) {
  // Scan through table looking for exited children.
  havekids = 0;
  for (pp = proc; pp < &proc[NPROC]; pp++) {
    if (pp->parent == p) {
      // make sure the child isn't still in exit() or swtch().
      acquire(&pp->lock);
385
      havekids = 1;
      if (pp->state == ZOMBIE) {
        // Found one.
        pid = pp->pid;
        if (addr != 0 &&
            copyout(p->pagetable, p->sz, addr, (char *)&pp->xstate,
                    sizeof(pp->xstate)) < 0) {
          release(&pp->lock);
          release(&wait_lock);
          return -1;
        }
        pp->parent = 0;
        freeproc(pp);
        release(&pp->lock);
        release(&wait_lock);
        return pid;
      }
      release(&pp->lock);
    }
  }
406
  // No point waiting if we don't have any children.
  if (!havekids || killed(p)) {
    release(&wait_lock);
    return -1;
  }
412
  // Wait for a child to exit.
  sleep_prepare(p); //DOC: wait-sleep
  release(&wait_lock);
  sleep();
  acquire(&wait_lock);
}
419}

An exiting child needs wait_lock to call wakeup(p->parent), so it cannot wake the parent between the parent’s scan and its registration; otherwise that wakeup could find nobody registered and be lost.To stop other processes from creating new children for this parent while it sleeps.Because sleep_prepare panics unless wait_lock is held.Because sleep requires the caller to hold wait_lock, which it releases while sleeping.

13solidType a number

A process whose user memory is exactly 5 pages, all present, at virtual addresses 0x0–0x4fff, calls fork, and it succeeds. How many pages does the whole kfork take from kalloc (directly or through the functions it calls)?

decimal, 0x hex or 0b binary

14deepType a number

allocproc claims proc[4]. What value does line 147 store in p->context.sp? Use KSTACK(p) = TRAMPOLINE - ((p) + 1) * 2 * PGSIZE, TRAMPOLINE = MAXVA - PGSIZE, MAXVA = 1 << 38 and PGSIZE = 4096. Answer in hex.

kernel/proc.c

// Set up new context to start executing at forkret,
// which returns to user space.
memset(&p->context, 0, sizeof(p->context));
p->context.ra = (uint64)forkret;
p->context.sp = p->kstack + PGSIZE;
148
return p;

decimal, 0x hex or 0b binary

15solidChoose one

Process P is asleep in piperead on an empty pipe whose write end is still open (it slept at line 126). Another process calls kill(P). The pipe stays empty. What happens to P?

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

kkill calls kexit for P, which frees P’s resources right away.kkill makes P RUNNABLE; P returns from sleep(), goes round the loop, finds killed set at line 120 and returns -1, and usertrap calls kexit(-1) on the way out.P stays asleep until someone writes to the pipe or closes it, and dies only then.P wakes, but sleep() reports that it was killed, so piperead returns -1 without re-checking.

16solidChoose all that apply

Some sleep loops check killed each time round, so that a killed process does not wait forever. Which of these do?

piperead, waiting for dataconsoleread, waiting for a line of inputsys_pause, waiting for ticks to passacquiresleep, waiting for a sleep-lockkwait, waiting for a child to exitvirtio_disk_rw, waiting for the disk

17solidClick the line

Click the line at which the process’s user address space becomes the new program’s, the commit point of kexec.

kernel/exec.c

// Save program name for debugging.
for (last = s = path; *s; s++)
  if (*s == '/')
    last = s + 1;
safestrcpy(p->name, last, sizeof(p->name));
131
// Commit to the user image.
oldpagetable = p->pagetable;
p->pagetable = pagetable;
p->sz = sz;
p->trapframe->epc = elf.entry; // initial program counter = ulib.c:start()
p->trapframe->sp = sp;         // initial stack pointer
proc_freepagetable(oldpagetable, oldsz);
139
return argc; // this ends up in a0, the first argument to main(argc, argv)

Your pick: none yet (click a line in the code)

18warm-upMatch the pairs

Match each process state with the code that sets it in the situation described.

USEDRUNNABLE, for a brand-new childZOMBIEUNUSED, after a process has diedSLEEPING

19solidFill in the machine state

ls called exit(0) (a system call). Its kexit has just executed line 358, p->state = ZOMBIE. What is the state of the hart running it?

kernel/proc.c

347  acquire(&wait_lock);
348
349  // Give any children to init.
350  reparent(p);
351
352  // Parent might be sleeping in wait().
353  wakeup(p->parent);
354
355  acquire(&p->lock);
356
357  p->xstate = status;
358  p->state = ZOMBIE;
359
360  release(&wait_lock);
361
362  // Jump into the scheduler, never to return.
363  sched();
364  panic("zombie exit");
365}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

20deepTrue or false, and why

True or false: as soon as a process’s state is ZOMBIE, no hart is executing on its kernel stack any more.

kernel/proc.c

acquire(&p->lock);
356
p->xstate = status;
p->state = ZOMBIE;
359
release(&wait_lock);
361
// Jump into the scheduler, never to return.
sched();
panic("zombie exit");

TrueFalse

Why?

False, because freeproc must run on the zombie’s kernel stack to free it.After setting ZOMBIE, kexit still runs release(&wait_lock), sched and swtch on that stack; that is why its p->lock stays held until the scheduler, off the stack, releases it.False, because a zombie keeps running user code until its parent calls wait.

21solidChoose all that apply

Process A is spinning in user mode on hart 1, making no system calls. On hart 0, another process calls kill(A's pid), and it returns 0. Which of these are true?

A keeps executing user instructions until its next trap into the kernel.kkill sets A to RUNNABLE so that a scheduler can end it.kkill sets A’s killed flag under A’s p->lock and leaves A’s state RUNNING.At that trap, usertrap finds killed set and A calls kexit(-1).Hart 0 sends hart 1 an interrupt so that A stops immediately.A’s parent will see exit status 0 from wait.

22deepChoose one

kexec's argument loop writes ustack[argc] with no check that argc < MAXARG (ustack has MAXARG = 32 entries, on the kernel stack). What stops a user program from overflowing ustack by calling exec with 40 arguments?

kernel/exec.c

// Copy argument strings into new stack, remember their
// addresses in ustack[].
for (argc = 0; argv[argc]; argc++) {
  sp -= strlen(argv[argc]) + 1;
  sp -= sp % 16; // riscv sp must be 16-byte aligned
  if (sp < stackbase)
    goto bad;
  if (copyout(pagetable, sz, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
    goto bad;
  ustack[argc] = sp;
}
ustack[argc] = 0;
111
// push a copy of ustack[], the array of argv[] pointers.
sp -= (argc + 1) * sizeof(uint64);
sp -= sp % 16;
if (sp < stackbase)
  goto bad;
if (copyout(pagetable, sz, sp, (char *)ustack, (argc + 1) * sizeof(uint64)) <
    0)
  goto bad;

The sp < stackbase check on line 104 stops the loop before ustack overflows.Nothing stops it; 40 arguments overflow ustack and corrupt kexec’s kernel stack.copyout fails once more than 32 strings have been written to the new stack.sys_exec copies at most MAXARG pointers, including the terminating null, and fails with -1 otherwise; the only other caller, forkret, passes one argument.

23deepChoose one

Process P in piperead has passed the killed check on line 120 and called sleep_prepare on line 124, but has not yet called sleep(). On another hart, kill(P) runs to completion. Then the pipe’s writer does nothing for an hour, keeping its end open. What happens to P during that hour?

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

P goes to sleep anyway and stays asleep for the hour; it notices killed only after a real wakeup(&pi->nread) (a write or close) or a second kill.sleep() returns at once, because kkill cleared p->chan the way wakeup does.P exits immediately, because kkill made it a ZOMBIE.P goes to sleep, but kkill already made it RUNNABLE, so it is rescheduled at once.

24deepTrue or false, and why

True or false: because first in forkret is a plain static int, read and cleared with no lock and no atomic instruction, two harts could both run the if (first) block and both call fsinit.

kernel/proc.c

510// A fork child's very first scheduling by scheduler()
511// will swtch to forkret.
512void
513forkret(void)
514{
515  extern char userret[];
516  static int first = 1;
517  struct proc *p = myproc();
518
519  // Still holding p->lock from scheduler.
520  release(&p->lock);
521
522  if (first) {
523    first = 0;
524
525    // File system initialization must be run in the context of a
526    // regular process (e.g., because it calls sleep), and thus cannot
527    // be run from main().
528    fsinit(ROOTDEV);
529
530    // We can invoke kexec() now that file system is initialized.
531    // Put the return value (argc) of kexec into a0.
532    p->trapframe->a0 = kexec("/init", (char *[]){"/init", 0});
533    if (p->trapframe->a0 == -1) {
534      panic("exec");
535    }
536  }

TrueFalse

Why?

first is protected by p->lock, which forkret still holds when it reads it.forkret runs only on hart 0.While first is 1, init is the only process in existence, and it clears first before any other process can be created.

25deepChoose one

Process P (a child of the shell) has a child Z that has already exited and is a ZOMBIE; P never called wait. Now P itself calls exit. Who eventually calls freeproc on Z?

kernel/proc.c

307// Pass p's abandoned children to init.
308// Caller must hold wait_lock.
309void
310reparent(struct proc *p)
311{
312  struct proc *pp;
313
314  for (pp = proc; pp < &proc[NPROC]; pp++) {
315    if (pp->parent == p) {
316      pp->parent = initproc;
317      wakeup(initproc);
318    }
319  }
320}

Nobody; Z’s slot leaks until the next reboot.P, inside its own kexit, before it becomes a zombie.The shell, when its wait collects P.init: P’s reparent makes init Z’s parent and calls wakeup(initproc), and init’s kwait rescans, finds Z as its own zombie child, and frees it.