OS: 问题集

什么是进程？进程与线程的区别？操作系统中如何实现进程间的通信？多线程编程中什么是竞态条件，如何避免？什么是死锁？

1. Process: running program. It encapsulates the complete execution state of a running program — including memory, registers (like the program counter and stack pointer), and I/O resources like open files — that allows it to run independently and be managed by the operating system.
2. Thread: a unit of execution within a process. Unlike separate processes, threads share the same address space and can access the same data and resources.
3. Interprocess Communication: It allows processes to exchange data and synchronize their actions. Several common IPC mechanisms:
   1. Primitive IPC: waitpid(), signals — lightweight, limited. Mostly used for simple coordination or notifications.
   2. Sockets: Versatile, supports remote and local communication.
   3. Unix IPC: Pipes, FIFOs, shared memory, semaphores — for local and often high-performance communication.
4. race condition: occurs when two or more threads access shared data at the same time, and at least one thread modifies the data, leading to unpredictable or incorrect results depending on the timing of the thread execution.

// Shared variable
int counter = 0;
void* thread_func() {
    for (int i = 0; i < 1000; i++) {
        counter = counter + 1;  // read-modify-write (not atomic!)
    }
}

1. How to prevent race condition: Use synchronization mechanisms like:
   1. Mutexes (locks) – to enforce exclusive access
   2. Atomic operations – to make updates indivisible
   3. Semaphores or monitors – for higher-level control
2. Deadlock: a collection of threads is blocked, waiting for a condition that will never be true.

并发控制的同步机制——信号量、互斥锁+条件变量等及其历史

早期操作系统需要解决多进程竞争共享资源的问题，其中主要有三大问题：互斥、资源限制和线程通知。1965年Dijkstra提出了信号量这一机制能统一解决这三大问题。信号量的本质就是一个带阻塞/唤醒功能的计数器，用资源计数的方式协同进程间的执行顺序和资源共享。信号量大体由资源计数器和等待队列组成，还提供了P()和V()操作，P代表申请资源、V代表释放资源。但是信号量机制有容易出错、可读性差、性能问题等问题，于是1970年以后科学家又发明了更高级的互斥锁和条件变量。这两者其实就是将信号量机制的实现功能进行拆分，其中互斥锁用于保护共享资源的原子访问、条件变量用于等待复杂事件成立。这些功能当然只用信号量也能做，比如本质上互斥锁就是初始值为1的二进制信号量。但互斥锁和条件变量针对应用层做了更多优化：互斥锁实现了所有制机制、可重入性、性能优化，条件变量实现了避免忙等待、精确唤醒等。在今天，信号量是更为底层的存在，在系统编程方面仍需要使用信号量。

信号量的伪代码实现（简化版）​​：

type Semaphore struct {
    value int          // 资源计数器
    queue []Thread     // 等待队列（阻塞的线程）
}

func (s *Semaphore) P() {
    s.value--
    if s.value < 0 {
        // 阻塞当前线程，加入等待队列
        s.queue.push(currentThread)
        sleep()
    }
}

func (s *Semaphore) V() {
    s.value++
    if s.value <= 0 {
        // 唤醒一个等待的线程
        thread := s.queue.pop()
        wakeup(thread)
    }
}

为什么需要Cache？

To deal with the processor–memory gap, system designers include smaller, faster storage devices called caches that serve as temporary staging areas for information that the processor is likely to need in the near future.

如何避免死锁？

Deadlock avoidance is a strategy that prevents deadlocks by dynamically evaluating the safety of resource allocations. Its core principle involves predicting whether a resource allocation would lead the system into an unsafe state before permitting the allocation. Representative algorithms include the Banker’s Algorithm and the Resource Allocation Graph Algorithm (applicable to single-instance resources).

什么是文件描述符

Unix/Linux 将 ​​一切皆视为文件​​（包括网络套接字、管道、设备等），文件描述符是操作系统对这类资源的统一抽象标识。

• 监听套接字（Listening Socket）和连接套接字（Connected Socket）都通过 fd 操作，简化了编程模型。
• 例如：accept()、read()、write() 等系统调用可直接复用文件操作的接口。

虚拟地址和虚拟内存

• A virtual address is a logical address from a process’s perspective, mapped by the operating system via page tables to either physical memory or disk (virtual memory). This enables each process to have its own independent, contiguous address space, unrestricted by physical memory limitations.
• Virtual memory​​ is a memory management technique​​ implemented by the operating system through the combined use of ​​physical memory (RAM)​​ and ​​disk swap space (Swap/Pagefile)​​. Its core mechanism relies on hardware (MMU) and software (page tables, page faults) collaboration to provide each process with an independent ​​virtual address space​​, while dynamically mapping virtual addresses to data in physical memory or on disk.

比较RR和SJF进程调度算法的优缺点

进程调度算法中，**轮转调度（Round-Robin, RR）和短作业优先（Shortest Job First, SJF）**是两种经典策略，分别适用于不同的场景。以下是它们的优缺点对比：

1. 轮转调度（Round-Robin, RR）

核心思想

• 每个进程分配一个固定的时间片（Time Quantum），按顺序轮流执行。若进程在时间片内未完成，则被抢占并移到就绪队列末尾。

优点

✅ 公平性：所有进程（无论长短）均能获得CPU时间，避免饥饿（Starvation）。
✅ 响应时间短：适合交互式系统（如操作系统、Web服务器），短任务能快速获得响应。
✅ 实现简单：基于队列的调度，无需预测进程执行时间。
✅ 适合多任务并发：时间片划分合理时，能平衡吞吐量和响应时间。

缺点

❌ 高开销：频繁的上下文切换（Context Switch）可能导致性能下降（尤其时间片过短时）。
❌ 长任务延迟：长进程需要多次轮转才能完成，平均周转时间（Turnaround Time）较差。
❌ 依赖时间片大小：
• 时间片过短 → 上下文切换频繁，吞吐量下降。
• 时间片过长 → 退化为FIFO，响应时间变差。

适用场景

• 交互式系统（如分时操作系统、实时性要求不高的场景）。
• 进程执行时间未知或差异较小时。

---

2. 短作业优先（Shortest Job First, SJF）

核心思想

• 优先调度预计执行时间最短的进程（非抢占式），或允许抢占当前进程以运行更短的新进程（抢占式版本称为SRTN，Shortest Remaining Time Next）。

优点

✅ 最优平均周转时间：数学上可证明SJF能最小化平均等待时间和周转时间。
✅ 高吞吐量：短任务快速完成，减少队列中的进程数量。
✅ 减少平均等待时间：长任务不会阻塞短任务的执行。

缺点

❌ 饥饿问题：长任务可能因短任务不断到达而长期得不到执行。
❌ 依赖预测准确性：需预先知道或估计进程的执行时间（实际中难以精确预测）。
❌ 不公平性：对长任务不友好，不适合交互式系统。
❌ 实现复杂：需动态维护进程执行时间的优先级队列（如堆）。

适用场景

• 批处理系统（如科学计算、后台任务）。
• 进程执行时间可预测（如历史数据或用户提交的预估时间）。

---

3. 对比总结

特性	RR（轮转调度）	SJF（短作业优先）
公平性	高（所有进程平等）	低（长任务可能饥饿）
响应时间	短（适合交互式系统）	长（短任务优先，长任务延迟高）
平均周转时间	较差（长任务需多次轮转）	最优（短任务快速完成）
开销	高（频繁上下文切换）	低（非抢占式）或中（抢占式需维护优先级）
适用场景	交互式、多任务	批处理、可预测执行时间的任务
是否需要预知时间	否	是

---

4. 实际应用建议

• 选择RR：当系统需要公平性和快速响应（如桌面操作系统、Web服务器）。
• 选择SJF/SRTN：当任务执行时间可预测且需最小化周转时间（如数据中心批处理作业）。
• 混合策略：现代系统常结合多种算法（如Linux的CFS调度器结合时间片和优先级，类似RR与SJF的折衷）。

两种算法本质上是公平性与效率的权衡，需根据具体需求选择。