这门课使用了斯坦福的 Pintos 项目，我觉得是一个很不错且有趣的项目。

Chapter 1, 2, 3, 4, 5

🍺

Chapter 6

1. Common atomic hardware instructions:
   • Test-and-Set: Return the original value of the passed in parameter, set the value of parameter to true;
   • Compare-and-Swap: Return the original value of the passed in parameter, set the value of parameter to new_value if the old value equals expected.
2. Monitor:
   • With Mesa semantics, when a waiting thread’s resource becomes available, it is moved from the signal queue back to the entry queue. The currently executing thread finishes executing, and the other thread will eventually be dispatched from the entry queue;
   • One risk of this implementation is that by the time that the unblocked process begins to execute again, the event it was waiting for has passed and the resource could be again unavailable. The cycle may repeat;
   • Most common, e.g. Java synchronized objects.

   

Chapter 7

🍺

Chapter 8

1. Conditions for deadlock:
   • Mutual exclusion, hold and wait, no preemption, circular wait;
   • Invalidating circular wait is most common: Assign each resource a unique number, and resources must be acquired in order.
2. Banker algorithm:
   • Safe state => no deadlocks; Unsafe state => possible deadlocks; Avoidance => ensure safe state;
   • https://www.geeksforgeeks.org/bankers-algorithm-in-operating-system-2/.

Synchronization Supplement

1. Different locks:
   • Spin lock: Busy wait, must shared among processors, not FIFO or even bounded wait;
   • Ticket lock: Just one atomic instruction to block; Spins on not-atomic instruction, FIFO; But it spins on shared memory;
   • MCS lock: FIFO, locks are acquired and released in O(1) time, spinning is bounded by time it takes to add to queue.

Homework 1

1. Resources can only be access in supervisor mode:
   • Hardware: I/O devices like disk drive, network board, keyboard, …
   • Data structure: PCB (process control block), disk buffer, …
2. Context switch:
   • Process: Register context virtual memory context;
   • Thread: Register context.
3. Difference between “policy” and “mechanism”:
   • A policy is basically a goal. It is something the operating system is designed to achieve;
   • The mechanism is the implementation that achieves this goal;
   • Example: It might be policy to run higher priority processes first. The mechanism for doing this might be to have one list for each priority class and always running processes from the highest priority non-empty list.
4. “process” and “program”: A program is something written by a programmer. It is a specification. A process is an instance of a program in execution. A process is a running model. A program is a description of a model.
5. Key states in PCB & TCB:
   • PCB states: Status (running, runnable, etc), priority, process id, parent process id, accounting information, signal state, file state, and virtual memory state;
   • TCB states: Register state, attached/detached, scheduling priority, accounting information, thread id.
   • PCB and TCB don’t share any key state because it’s no necessary.
6. Gang scheduling: It is the identification of a group of threads as a group that should be run in parallel whenever possible. This is normally done when the threads are highly collaborative and communicate with each other a lot. By running them at the same time, the communication is fluid. Running them in series would result in a lot of blocking for communication while waiting for other threads in the gang to run.
7. Multiprogramming: Make system interactive & allow I/O and CPU overlap.
8. Multi-level feedback queues:
   • A scheduling algorithm that uses multiple queues of different priorities. Jobs in lower-priority queues get executed only if there’s no job in higher-priority queues. Jobs can be moved from one queue to another according to their “feedbacks” and some rules, and each queue can have different scheduling algorithms (round-robin, FCFS, etc);
   • Advantages: Processes might slowly be promoted as they age. They also might get rewarded and promoted for giving up the CPU soon after dispatch.

Homework 2

1. An example of monitor:
   • Worth noticing that there’s no lock because the lock is intrinsic within the monitor construct. The language is offering us the mutual exclusion guarantee and hiding it from us.

    Monitor MultiPurpose {
      cv allThreeCV, anyTwoCV, anyOneCV, stageCV;
      bool section0, section1, section2 = false;
   
      Entry mproom event_begin(event e) {
        switch (e) {
          case PLAY:
            while (section0 || section1 || section2)
              allThreeCV.wait();
            return {true, true, true};
          ...
        }
      }
   
      Entry void event_end(event e, mproom allocated_sections) {
        if (allocated_sections.section0) section0 = false;
        ...
        if (!section0 && !section1 && !section2)
          allThreeCV.signal();
        ...
      }
    }
   

2. The wait() and signal() operation upon a condition variable:
   • wait() is taking mutex as a parameter because: The mutex ensures that the check of the predicate and the wait are atomic. The logic of wait is such that the mutex will be freed before blocking but reacquired before waking up;
   • signal() is not because: Whatever is changing state needs to protect that state. The signal is simply signalling. Any internal state that is changed, i.e. wait list, is protected internally.
3. Kernel data structures:
   • Kernel pages are mapped into all processes into the same address space so they are accessible in the same way, with the same page numbers and virtual addresses regardless of which page table is loaded;
   • The pages are marked as requiring privilege in the page table’s per-process metadata. This is enforced by the MMU. A fault is generated if an access is attempted without sufficient privilege.