What is an operating system?

What are examples of abstractions that the OS maintains that make using computer hardware easier?

What is multiprogramming?

What are some challenges of designing/implementing an OS that supports multi-programming?

What are the two main purposes of the operating system?

What is the difference between an interrupt and a trap?

What features do interrupts and traps implement in an OS?

What is the advantage of using interrupts and traps for an OS implementation. In other words, if an OS were not designed with these features, how would it change the design of modern operating systems.

What is the kernel?

What is the difference between kernel mode and user mode?

What is a system call? How are system calls different from user-defined functions?

How are errors reported with most system calls?

What is a function pointer?

What is a void* pointer?

What is a bit field?

What is the output of the following program?

#include <stdio.h>

typedef void (*functionType)(int a, int b);

void example(int a, int b) {
  printf("This is a function stored as data! %d %d\n", a, b);
}

int main() {
  functionType myFunction = example;
  (*myFunction)(10, 3);
}

Draw the stack diagram for the following program. Then indicate which of the following dereferences are safe.

#include <stdio.h>

int main()
{
  void* generic = NULL;
  int a = 3;
  double b = 4.5;
  generic = &a;
  generic = &b;

  printf("test %f\n", *generic);

  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  generic = &a;

  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  return 0;
}

Draw the stack diagram for the following program. What is the output?

#include <stdio.h>
#include <string.h>

char* foo(char* str, char c)
{
  int n = strlen(str);
  for(int i = 0; i < n; i++)
  {
    if (str[i] == c)
    {
      str[i] = '\0';
      return str;
    }
  }
  return NULL;
}

int main()
{
  char buffer[8];
  strcpy(buffer, "a,b,c");

  char* s = foo(buffer, ',');
  printf("%s\n", s);
}

Consider the following code. Assume that sigset_t is a 32-bit unsigned integer. Express your answers as a hexadecimal value.

1 sigset_t newset;
2 sigemptyset(&newset);
3 sigaddset(&newset, SIGTTIN);
4 sigaddset(&newset, SIGTTOU);
5 sigfillset(&newset);

What is the output of the following program?

void f(){
  int i = 0;
  while (i < 3) {
    printf("i = %d\n", i);
    i++;
  }
  swapcontext(&uc, &mainc);
  while (i < 6) {
    printf("i = %d\n", i);
    i++;
  }
}

int main(int argc, char * argv[]){

  getcontext(&uc); // initialize context

  // setup stack and signal handling
  void* stack = malloc(STACKSIZE);
  uc.uc_stack.ss_sp = stack;
  uc.uc_stack.ss_size = STACKSIZE;
  uc.uc_stack.ss_flags = SS_DISABLE;
  sigemptyset(&(uc.uc_sigmask));
  uc.uc_link = &mainc;
  makecontext(&uc, f, 0);

  swapcontext(&mainc, &uc);
  printf("Back in main 1\n");
  swapcontext(&mainc, &uc);
  printf("Back in main 2\n");
  return 0;
}

What is a file? A directory?

What are some common file types?

What is the difference between text and binary files?

How do we distinguish between file types?

In a file system, what is a path?

What is the difference between an absolute and relative path?

What is the current working directory?

What is the difference between a foreground and background process in the terminal?

What is a pipe? Give an example of a bash command that uses pipes.

How is redirected input/output different from reading/writing a file?

What is job control in regards to the bash terminal?

How do you redirect output to a file in terminal?

What do the file descriptors corresponding to values 0, 1, and 2 represent in terminal?

What is a process group?

What is a session?

What is the controlling terminal for a process?

What do the following symbols mean when they are in a path?

Suppose a file system has the following hierarchy

root
+ home
++ ren
+++ A
++ stimpy
+++ B
+++ C
++++ hello.txt

Draw the directory hierarchy after the following commands

$ pwd
/home/alinen
$ mkdir A
$ cd A
$ mkdir Z
$ touch talk.c
$ cd ..
$ touch listen.c
$ cd
$ touch sing.c

Consider the following file properties listed with ls -l

-rw-r--r--  0 alinen alinen   70 Dec 10  2023 README.md

Consider the following commands and associated diagram.

What is a process?

What is the difference between a process and a C program?

What are the different states that a process might be in?

Why might a processed be in a blocked state?

Why do we need special mechanisms, such as pipes or sockets, to communicate between processes?

How can you kill a process using ps ?

What is a zombie process?

What is an orphan process?

What is a signal? what is a signal handler?

Some signals cannot be ignored. Name a signal that cannot be ignored and explain why a program cannot ignore it.

Why might we want to register a signal handler?

When a signal arrives to a process, list three ways the process can respond to the signal.

What happens when multiple signals arrive to a process before a process is able to process them?

When does the OS send the SIGSEGV signal?

When does the OS send the SIGINT signal?

When does the OS send the SIGCHD signal?

What signal is sent when the user types Ctrl-Z at the terminal?

What happens when a process calls fork?

What happens when a signal arrives for a process?

What type of event does SIGINT represent? Sketch a program that registers a signal handler for SIGINT?

What does the execv family of commands do? How do fork and execv compare?

What different regions are present within the memory layout of a process?

What is the process control block?

What is the program counter?

When are processes created? destroyed? blocked?

How many processes are created for the command ls *.c | grep apple?

The following program creates a zombie process. Why?

void main() {
  if (fork() == 0) { /*child */
    printf("Child, PID = %d\n", getpid());
    exit(0);
  } else { /*parent */
    printf("Parent, PID = %d\n", getpid());
    while(1) {
    }
  }
}

Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)?

int main() {
  pid_t ret;

  printf("A\n");

  ret = fork();
  if(ret == 0) {
    printf("B\n");

    ret = fork();
    if(ret == 0) {
      printf("C\n");
    }
    printf("D\n");
  } else {
    printf("E\n");

    ret = fork();
    printf("F\n");
  }

  printf("G\n");
  return 0;
}

Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  printf("A\n");

  for (int i = 0; i < 3; i++)
  {
     ret = fork();
     if (ret == 0) // child
     {
        printf("B%d\n", i);
     }
  }

  printf("Z\n");
  return 0;
}

Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  printf("A\n");

  for (int i = 0; i < 3; i++)
  {
     ret = fork();
     if (ret == 0) // child
     {
        printf("B%d\n", i);
        exit(0);
     }
  }

  printf("Z\n");
  return 0;
}

Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  int value = 10;
  printf("A%d\n", value);

  ret = fork();
  if (ret == 0) // child
  {
     value--;
  }
  else
  {
     value++;
  }

  printf("Z%d\n", value);
  return 0;
}

Implement a program whose behavior matches the given timeline.

What is a thread? How does a thread differ from a process? How are threads similar?

Why and when might we want to use multiple threads to implement a program?

Why and when might we want to use multiple processes to implement a program?

Explain how threads might improve the implementation of a word processor.

Explain how threads might improve the implementation of a web server.

Explain how threads might improve the implementation of a web server.

How do threads created in user space differ from threads created in kernel space?

What is a critical section?

What is a race condition?

What is mutual exclusion?

What is deadlock? livelock?

What is bounded liveness?

What four criteria must be met to ensure mutual exclusion?

Why is disabling interrupts not ideal for enforcing mutual exclusion?

Sketch a multi-threaded program (N threads) that computes the average of a list of numbers. You can assume that the size of the list can be evenly divided by N.

Draw the stack diagram for the following program with two threads.

struct foo {
   long id;
   char message[16];
};

void *HelloWorld(void *id) {
  struct foo *holder = (struct foo *) id;
  printf("%s world! I am thread %ld\n", holder->message, holder->id);
  return NULL;
}

int main(int argc, char **argv) {
  struct foo holder1, holder2;
  holder1.id = 1;
  strcpy(holder1.message, "caio");

  holder2.id = 2;
  strcpy(holder2.message, "aloha");

  long* retval1 = NULL, *retval2 = NULL;
  pthread_t thread1, thread2;
  pthread_create(&thread1, NULL, HelloWorld, &holder1);
  pthread_create(&thread2, NULL, HelloWorld, &holder2);
  pthread_join(thread1, NULL);
  pthread_join(thread2, NULL);
  return 0;
}

Explain why the following program does not compute the correct answer for count.

#define MAX 100000
int count=0;

void interleave() {
  pthread_t th0, th1;
  pthread_create(&th0,0,test,0);
  pthread_create(&th1,0,test,0);
  pthread_join(th0,0);
  pthread_join(th1,0);
  printf(“%d\n”, count);
}

void test() {
  for(int j=0;j<MAX;j++) count=count+1;
}

For the following sets of assembly instructions for processes 1 and 2, give an interleaving of instructions that results in v having the value 2.

P1. MOVE V, r0			Q1. MOVE V, r1
P2. INCR r0			    Q2. INCR r1
P3. MOVE r0, V			Q3. MOVE r1, V

For the following sets of assembly instructions for processes 1 and 2, give an interleaving of instructions that results in v having the value 3.

P1. MOVE V, r0			Q1. MOVE V, r1
P2. INCR r0			    Q2. INCR r1
P3. MOVE r0, V			Q3. MOVE r1, V

Consider the following code for a process P0. Assume that the code for P1 is symmetric. Is it possible for both P0 and P1 to be in the same critical section at the same time?

Shared variable: turn :{0,1}
while (TRUE) {
  while (turn != 0);  /* busy waiting */
  CS();
  turn = 1; /* let the other enter */
  Non_CS();
}

Consider the following code for a process P0. Assume that the code for P1 is symmetric. Is it possible for both P0 and P1 to be in the same critical section at the same time?

Shared variable: interested[i] : int, init 0
while (TRUE) {
  interested[0] = 10;
  while (interested[1] > 0) interested[0]--;
  CS();
  interested[0] = 0;
  Non_CS();
}

Consider the following code for a process P0. Assume that the code for P1 is symmetric.

Shared variables: interested[i] :boolean;
                  turn :{0,1}
interested[0] = FALSE;
while (TRUE) {
  interested[0] = TRUE;  /* declare interest */
  turn = 0; /* takes care of race condition */
  repeat if /* busy wait */
   (interested[1] == TRUE && turn == 0);
  CS();
  interested[0] = FALSE; /* unblock P1 */
  Non_CS();
}

Consider the producer/consumer problem discussed in class. Suppose the buffer has size 8 and contains the values -2,3,4,-5; that in = 7 and out = 3.

Consider the following implementation for two threads, one a producer and the other a consumer. Does the code below contain a race condition? If yes, explain how the current implementation can lead to inconsistent buffer state.

//Producer Threads:
int item;
while(1) {
  item = produce_item();
  pthread_mutex_lock(&mux);
  buff[in] = item;
  in = (in+1)%N;
  pthread_mutex_unlock(&mux);
  num_items++;
}
//Consumer thread
int item;
while(1) {
  pthread_mutex_lock(&mux);
  item = buff[out];
  out = (out+1)%N;
  pthread_mutex_unlock(&mux);
  num_items--;
  consume_item(item);
}

How does a CPU-bound process differ from an IO-bound process?

What does it mean for a scheduling algorithm to be preemptive? non-preemptive?

What are the advantages and disadvantages of the FCFS scheduling algorithm. Give a class of applications where FCFS is the best scheduling policy.

What are the advantages and disadvantages of the SJF scheduling algorithm. Give a class of applications where FCFS is the best scheduling policy.

What are the advantages and disadvantages of the RR scheduling algorithm. Give a class of applications where FCFS is the best scheduling policy.

How do the needs of real-time systems differ from other application domains?

What is priority inversion? How can we avoid it?

Suppose we have a batch system with the following jobs, scheduled with FCFS. Job 1: 15 units, Job 2: 8 units, Job 1: 1 units.

Suppose we have a batch system with the following jobs, scheduled with SJF. Job 1: 15 units, Job 2: 8 units, Job 1: 1 units.

Suppose we have a batch system with the following jobs, scheduled with RR and a quantum of 5. Job 1: 15 units, Job 2: 8 units, Job 1: 1 units.

Suppose we have a batch system with the following jobs, scheduled with HPF and a quantum of 5. Assume all jobs start with the same priority. Job 1: 15 units, Job 2: 8 units, Job 1: 1 units.

Suppose we have a batch system with the following jobs, scheduled with HPF and a quantum of 5. Assume Job 2 has higher priority than Jobs 1 and 2. Job 1: 15 units, Job 2: 8 units, Job 1: 1 units.

Suppose we are scheduling three tasks for a real-time system using EDF. What is the utilization of these tasks? Show the scheduling order.

What is a deadlock?

Name four conditions for deadlock.

List four ways to deal with deadlock.

Under what circumstances is ignoring deadlock a reasonable strategy? Under what circumstances is it unacceptable?

What factors does the OS need to keep track of in order to detect deadlocks?

List three ways that the OS can recover from deadlock if it is detected.

Give an example of deadlock recovery through preemption.

Give an example of deadlock recovery through rollback.

Give an example of deadlock recovery through killing a process.

Give an example of deadlock prevention by removing the need for "mutual exclusion".

Give an example of deadlock prevention by avoid the need for "hold and wait" of resources.

Give an example of deadlock prevention by allowing resources to be "preempted".

Give an example of deadlock prevention by avoid the need for "circular wait" of resources.

What is a safe state?

Does an unsafe state guarantee a deadlock will occur? Why or why not?

Consider 5 dining philosophers. Can the following code deadlock? Why or why not?

pthread_mutex_t mutex[N]
struct thread_data {
  int id;
};

void Philosophize(void* usr)
{
  struct thread_data* data = (struct thread_data*) usr;
  printf("%d is hungry\n", data->id);

  int leftFork = data->id;
  int rightFork = (data->id + 1) % N;

  pthread_mutex_lock(&mutex[leftFork]);
  pthread_mutex_lock(&mutex[rightFork]);
  printf("%d is eating\n", data->id);
  sleep(duration);
  pthread_mutex_unlock(&mutex[leftFork]);
  pthread_mutex_unlock(&mutex[rightFork]);
}

Consider 5 dining philosophers. Can the following code deadlock? Why or why not. Is the given solution fair?

pthread_mutex_t mutex[N]
struct thread_data {
  int id;
};

void Philosophize(void* usr)
{
  struct thread_data* data = (struct thread_data*) usr;
  printf("%d is hungry\n", data->id);
  if (data->id % 2 == 0) return;

  int leftFork = data->id;
  int rightFork = (data->id + 1) % N;

  pthread_mutex_lock(&mutex[leftFork]);
  pthread_mutex_lock(&mutex[rightFork]);
  printf("%d is eating\n", data->id);
  sleep(duration);
  pthread_mutex_unlock(&mutex[leftFork]);
  pthread_mutex_unlock(&mutex[rightFork]);
}

Consider 5 dining philosophers. Can the following code deadlock? Why or why not. Is the given solution fair?

pthread_mutex_t mutex[N]
struct thread_data {
  int id;
};

void Philosophize(void* usr)
{
  struct thread_data* data = (struct thread_data*) usr;
  printf("%d is hungry\n", data->id);
  if (data->id % 2 == 0) return;

  int leftFork = data->id;
  int rightFork = (data->id + 1) % N;

  pthread_mutex_lock(&mutex[leftFork]);
  pthread_mutex_lock(&mutex[rightFork]);
  printf("%d is eating\n", data->id);
  sleep(duration);
  pthread_mutex_unlock(&mutex[leftFork]);
  pthread_mutex_unlock(&mutex[rightFork]);
}

Visualize the following requests for resources using a resource allocation graph. Does deadlock occur?

A requests R
B requests S
C requests T
A requests S
B requestsT
C requests R

Visualize the following resource/usage state using matrices. Is there deadlock?

Is the following a safe state?

Process     Holding     Max
A           4           6
B           4           11
C           2           7

Unallocated: 2

Is the follow state with multiple resources safe? If so, show the sequence of allocations that avoid deadlock. If so, show the sequence of allocations that avoid deadlock. Otherwise, show why deadlock is possible.