# Operating system hw4
In this homework I use ChatGPT to translate chinese to english frequently.
## 1 More on spinlocks
### Question-1
When a hardware interrupt occurs, such as from a timer or I/O device, the CPU stops executing the current thread and traps into the kernel, entering the interrupt context to run the appropriate Interrupt Service Routine (ISR). While in this context, the system does not immediately resume the interrupted thread because the interrupt might have changed the overall system state—for example, it could have made another thread ready to run. Since the ISR executes outside of any specific thread's context, the kernel must wait until the interrupt is fully handled before invoking the scheduler to make a fair and informed decision about which thread should run next. This ensures that thread scheduling considers all updated states in the system, rather than blindly resuming the interrupted thread.
### Question-2
In this question, I think the key is this part:
> The interaction of spinlocks and interrupts raises a potential danger. Suppose sys_sleep holds tickslock, and its CPU is interrupted by a timer interrupt. clockintr would try to acquire tickslock, see it was held, and wait for it to be released. In this situation, tickslock will never be released: only sys_sleep can release it, but sys_sleep will not continue running until clockintr returns. So the CPU will deadlock, and any code that needs either lock will also freeze.

https://github.com/mit-pdos/xv6-riscv/blob/riscv//kernel/spinlock.c#L100

We can see that `push_off` disables interrupts, while `pop_off` enables interrupts.
Additionally, acquire calls `push_off`, and release calls `pop_off`
As shown in the diagram above, a deadlock occurs, and the cause of this deadlock is essentially the same as the one described in the xv6 book — it happens because one of the threads unintentionally enables interrupts, which leads to the deadlock.

Let me briefly explain what the diagram is trying to convey. In thread 2, we release the t1 lock, which causes interrupts that were previously disabled to be enabled. When an interrupt occurs and the ISR (Interrupt Service Routine) attempts to acquire the lk lock, a problem arises: thread 2 has not yet released the lk lock, but the ISR is trying to acquire it. As a result, the ISR gets blocked, waiting for the lock. Meanwhile, thread 1 cannot be scheduled and is also stuck. This ultimately leads to a deadlock.
### Question-3
In a multi-core system, using a spinlock instead of a sleep-lock can be advantageous when the critical section is very short, because spinlocks avoid the overhead of context switching.
When a thread tries to acquire a spinlock and the lock is not available, it will "spin"—that is, continuously check the lock in a loop until it becomes free. This consumes CPU cycles, but on a multi-core system, other cores can continue doing useful work in parallel, and the core that owns the lock may release it very soon (especially if the critical section is tiny). In such cases, spinning for a short while is usually faster than putting the thread to sleep and performing a full context switch, which involves saving the CPU state, modifying scheduling queues, switching to another thread, and later restoring the state—all of which are expensive.
Therefore, spinlocks are ideal for protecting quick operations where waiting briefly in a loop is cheaper than sleeping and waking up again.
On the other hand, sleep-locks (which cause the waiting thread to block and yield the CPU) are better for longer critical sections, because spinning for a long time wastes CPU resources.

## 2 Learning by teaching
1. Why do we need to synchronize producers and consumers?
I told my friend that the producer/consumer problem is like having a single mailbox between two people: one person puts letters in (the producer), and the other takes them out (the consumer). Since the mailbox can only hold one letter at a time, they need to take turns—if the producer puts in a letter while the mailbox is full, they must wait; and if the consumer tries to take a letter when it’s empty, they must also wait. Without proper coordination, they might both try to access the mailbox at the same time, which could cause problems like losing a letter or reading an empty mailbox.

2. Why would the use of semaphore help synchronize the producers and the consumers?
I explained that a semaphore is like a traffic signal. It keeps track of whether the mailbox is full or empty, and allows only the right person to go at the right time. For example, one semaphore could track whether the mailbox is empty (so the producer knows it can put something in), and another semaphore could track whether it's full (so the consumer knows it can take something out). This way, the producer and consumer won’t interfere with each other.

3. How could an incorrect use of semaphores cause deadlock?
I described deadlock as a situation where both people are stuck waiting forever. For example, if the producer waits for the consumer to take the letter, and the consumer waits for the producer to put the letter in, and both are waiting on the wrong signals because the semaphores were set up incorrectly or in the wrong order, then nothing happens—they’re both stuck. That’s a deadlock.

Question from the listener:
Q: So if semaphores are so useful, why can't they just fix everything automatically?

My answer:
I explained that semaphores are powerful tools, but they’re also very low-level and require careful design. It’s like giving someone a tool kit—if you don’t use the tools correctly, you might make the problem worse. Semaphores don’t "think" for you; they only do what you tell them. That’s why understanding when and how to use them properly is so important to avoid issues like deadlocks or race conditions.

## 3 Multi-thread programming

After entering the `hw0403/` directory, you can compile our code successfully by running make. Please remember to run `make clean` before each `make`.
Once compiled, execute the program by running `./main`. It will automatically write the data from each execution into a file named `data.txt`.
The `correct` message shown on the screen indicates that I compared the result calculated using multiple threads with the result computed using a single thread to ensure correctness. You can check the code for more details.

In this task, I implemented a thread pool. Each time, our main thread sends a request, and the backend threads manage the tasks themselves, using multithreading to speed up the process.
I implemented this multithreaded programming assignment entirely on my own, without using any AI tools. I did look up some information online during the process. There was a bug that took me five hours to resolve, which made this assignment especially time-consuming. As a result, I didn’t have enough time to write a detailed report.

In this task, the frontend main thread sends tasks to the backend thread pool’s worker threads for execution. I’m quite proud of my implementation. I not only handled thread creation and destruction properly to avoid resource waste, but also used mutex locks and condition variables correctly, ensuring there were no race conditions or deadlocks. I carefully verified all of this. In addition, I made sure to free all dynamically allocated memory to avoid memory leaks.

I spent a lot of time designing this multithreaded program, so I hope the TA can directly review the code. I believe my code is well-organized and highly readable.
You can read `main.c`, `tpool.c`, `tpool.h`, `Makefile` for detail.
As mentioned above, I wrote a program that I’m quite proud of, so I specifically enabled `-Wall` and `-Wextra` to ensure code quality. However, this may cause warnings for unused variables: for example, `int argc, char *argv[]`.
To suppress these warnings cleanly, I used `[[maybe_unused]]`, which is a feature introduced in C23. As a result, you’ll notice that my Makefile explicitly specifies the C23 standard.

This is the resulting graph. The x-axis represents powers of 2, and it can be seen that multithreading improves the speed.

Finally, I’ve included some information about my system setup:
- I’m using Arch Linux

Linux arch 6.10.7-arch1-1 #1 SMP PREEMPT_DYNAMIC Thu, 29 Aug 2024 16:48:57 +0000 x86_64 GNU/Linux

- My CPU is an Intel(R) Core(TM) i7-10700F @ 2.90GHz
- It has 8 cores and 16 threads
- I have 32GB of RAM
BTW, I use Arch.

Given my system has an Intel Core i7-10700F CPU with 8 physical cores and 16 threads, using multithreading significantly improves the performance of matrix multiplication. This is because matrix multiplication is a computationally intensive task that can be easily parallelized—each row of the resulting matrix can be computed independently.

By dividing the work among multiple threads, we can fully utilize the available CPU cores, reducing the total computation time. On a single thread, all operations are executed sequentially, but with multiple threads, operations can be performed in parallel, leading to better CPU utilization and faster execution. This is especially effective on a system like mine, which supports high parallelism with 16 threads and sufficient memory (32GB RAM) to handle large matrices efficiently.

### Reference
- https://stackoverflow.com/questions/53708076/what-is-the-proper-way-to-use-clock-gettime
## 4 Xv6 kernel programming
I implemented the history functionality using a fixed-size array as a circular queue, supporting up to 5 previous commands. The implementation was added inside console.c.
To avoid confusion with question three, I placed the patch file for this question in the `hw0404/` directory.
I've provide a file `hw04.patch` which you can type

$ git apply hw04.patch

in the xv6 folder to apply the change of my design.

### Introduction

#define HISTORY_COUNT 5
#define HISTORY_LENGTH 128

char history[HISTORY_COUNT][HISTORY_LENGTH];
int history_start = 0;
int history_size = 0;
int history_pos = -1;

These variables simulate a queue with a circular buffer:
- history stores up to 5 strings.
- history_start is the index of the oldest command.
- history_size tracks how many commands are stored.
- history_pos tracks the current position when navigating history.

if(c == '\n' || c == C('D') || cons.e-cons.r == INPUT_BUF_SIZE){
  int len = 0;
  int i = cons.w;
  while(i < cons.e && len < HISTORY_LENGTH - 1){ 
    char ch = cons.buf[i % INPUT_BUF_SIZE];
    if(ch != '\n')
      history[(history_start + history_size) % HISTORY_COUNT][len++] = ch; 
    i++;
  }   
  history[(history_start + history_size) % HISTORY_COUNT][len] = '\0';

  if(history_size < HISTORY_COUNT){
    history_size++;
  }   
  else{
    history_start = (history_start + 1) % HISTORY_COUNT;
  }   

  history_pos = -1;  // reset
// wake up consoleread() if a whole line (or end-of-file)
// has arrived.
cons.w = cons.e;
wakeup(&cons.r);
}

When the user presses Enter ('\n'), the typed command is saved into the history buffer, excluding the newline character:

case C('W'):
  if(history_size == 0 || history_pos + 1 >= history_size){
    consputc('\a');  // Beep
  }
  else{
    history_pos++;
    int idx = (history_start + history_size - 1 - history_pos) % HISTORY_COUNT;
    show_history(history[idx]);
  }
  break;

case C('S'):
  if(history_pos <= -1){
    consputc('\a');  // Beep
  }
  if(history_pos <= 0){
    history_pos = -1;
    clear_line();
  }
  else{
    history_pos--;
    int idx = (history_start + history_size - 1 - history_pos) % HISTORY_COUNT;
    show_history(history[idx]);
  }
  break;

I added support for:
- Ctrl+W to recall previous commands
- Ctrl+S to move forward in history

void clear_line(){
  while(cons.e != cons.w &&
         cons.buf[(cons.e - 1) % INPUT_BUF_SIZE] != '\n'){
    cons.e--;
    consputc(BACKSPACE);
  }
}

void show_history(const char *cmd){
  clear_line();
  int i = 0;
  while(cmd[i] && cons.e - cons.r < INPUT_BUF_SIZE){
    consputc(cmd[i]);
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = cmd[i];
    i++;
  }
}

I implemented two functions:
- clear_line(): Erase the current input line.
- show_history(const char *cmd): Displays a previous command on the console.

Finally, the command history feature works successfully. Users can navigate through up to 5 previous commands using Ctrl+W and Ctrl+S. If the navigation goes beyond the available history, or too many Ctrl+S, a beep sound is emitted.