Project 02 Practice Problems

Shell History

Question 1 (Easy)

What data structure is used to store command history in the xv6 shell implementation? How many commands are stored in the history?

Question 2 (Easy)

Explain the purpose of the !<num> and !<text> commands in the shell history implementation. Provide an example of how each would be used.

Question 3 (Moderate)

Consider the following code snippet from the shell history implementation:

void
history_add(char *buf)
{
  struct history_line *hlp;
  struct list_elem *e;
  int off = 1;

  hlp = (struct history_line *)malloc(sizeof(struct history_line));
  if(hlp == 0)
    panic("history_add(): malloc");
  hlp->line_str[0] = '\0';

  if(buf[strlen(buf)-1] == '\n')
    off += 1;

  hlp->line_num = history_index;
  strncpy(hlp->line_str, buf, strlen(buf) - off);

  list_push_back(&history, &hlp->elem);
  if(history_index > MAX_HISTORY_LEN){
    e = list_pop_front(&history);
    hlp = list_entry(e, struct history_line, elem);
    free(hlp);
  }

  history_index += 1;
}

Explain what happens when the history list exceeds the maximum number of entries. Why is this approach necessary?

Question 4 (Moderate)

The history_run function is responsible for executing commands from the history:

void
history_run(char *buf)
{
  struct list_elem *e;
  struct history_line *hlp;
  int ascii = 1;
  int index = 0;
  int found = 0;
  int len = 0;

  if(buf[1] >= '0' && buf[1] <= '9'){
    ascii = 0;
    index = atoi(&buf[1]);
  }

  for(e = list_end(&history); e != list_head(&history); e = list_prev(e)){
    hlp = list_entry(e, struct history_line, elem);

    if(ascii){
      len = strlen(buf) - 2;
      if(strncmp(hlp->line_str, &buf[1], len) == 0){
        found = 1;
        break;
      }
    }else if(hlp->line_num == index){
      found = 1;
      break;
    }
  }

  if(found){
    printf("%s\n", hlp->line_str);
    runcmd_builtin(hlp->line_str);
  }else{
    buf[strlen(buf) - 1] = '\0';
    printf("-sh: %s: event not found\n", buf);
  }
}

Explain how it determines which command to run when a user enters !<text> versus !<num>. What happens if the specified command is not found in the history?

Question 5 (Difficult)

Implement a function called history_clear() that would clear all entries from the command history. Your implementation should properly free all allocated memory and reset the history index. Then, modify the shell to add a new built-in command history -c that calls this function. Here are the history data types:

struct history_line {
  struct list_elem elem;
  int line_num;
  char line_str[MAX_LINE_LEN];
};

struct list history;
int history_index = 1;

Free Kernel Memory

Question 1 (Easy)

What is the purpose of the kmem() system call in xv6? What information does it return to the user?

Question 2 (Easy)

In the kmem user program, what is the significance of the constant 4096? Why is this value used in the calculation?

Question 3 (Moderate)

Describe the steps required to add a new system call to xv6. What files need to be modified to implement the kmem() system call?

Question 4 (Moderate)

The kmem() system call returns the number of free kernel pages. Explain how the kernel tracks free memory pages and how the system call would access this information.

Question 5 (Difficult)

Extend the kmem program to also display the total amount of kernel memory (both free and used) and calculate the percentage of memory that is currently in use. What additional system call(s) would you need to implement to support this functionality?

Pipe Count

Question 1 (Easy)

What is the purpose of the pipect(int fd) system call? What does it return when the file descriptor is not a pipe?

Question 2 (Easy)

When running the command echo foo | pipect, the output is 4. Explain why the count is 4 and not 3, given that “foo” is only 3 characters.

Question 3 (Moderate)

Describe how pipes are implemented in xv6. What data structures are used to represent pipes, and how is data stored in them?

Question 4 (Moderate)

The pipect(int fd) system call needs to determine if a file descriptor refers to a pipe. Explain how the system call would check this and access the pipe’s data structure to determine the number of bytes available.

Process Status

Question 1 (Easy)

What information does the ps command display about each process in xv6? List the fields shown in the output.

Question 2 (Easy)

Explain the purpose of the struct procinfo defined in getproc.h. Why is this structure needed for the getprocs() system call?

struct procinfo {
  int pid;                // Process ID
  enum procstate state;   // Process state
  uint64 sz;              // Size of process memory (bytes)
  char name[16];          // Process name
};

Question 3 (Moderate)

The ps program defines an array of strings called states to map process state values to human-readable strings. Explain why this mapping is necessary and how it’s used in the program.

char *states[] = {
  [UNUSED]    "unused",
  [USED]      "used",
  [SLEEPING]  "sleep ",
  [RUNNABLE]  "runble",
  [RUNNING]   "run   ",
  [ZOMBIE]    "zombie"
};

Question 4 (Moderate)

Describe how the getprocs() system call works. How does it collect information about all processes in the system and make it available to user programs?

int
getprocs(uint64 addr, int max)
{
  struct proc *p;
  struct procinfo pi;
  int count = 0;

  // Iterate through the process table
  for(p = proc; p < &proc[NPROC] && count < max; p++){
    acquire(&p->lock);

    if(p->state != UNUSED){
      // Fill in the procinfo structure
      pi.pid = p->pid;
      pi.state = p->state;
      pi.sz = p->sz;
      safestrcpy(pi.name, p->name, sizeof(pi.name));

      // Copy to user space
      if(copyout(myproc()->pagetable, addr + count * sizeof(pi),
        (char *)&pi, sizeof(pi)) < 0){
        release(&p->lock);
        return -1;
      }

      count++;
    }

    release(&p->lock);
  }

  return count;
}

Question 5 (Difficult)

Extend the ps command to add a new option -p <pid> that displays detailed information about a specific process identified by its PID. The detailed information should include all the standard fields plus the parent PID and the number of open file descriptors. What modifications would you need to make to the struct procinfo, the getprocs() system call, and the ps program to implement this feature?