操作系统面试相关问题汇总

发表于

进程VS线程

进程

  • 一个程序至少有一个进程
  • 私有地址空间
  • 进程间切换更耗时
  • 操作系统进行资源分配的最小单元

线程

  • 一个进程至少有一个线程，线程是轻量级的进程
  • 共享地址空间
  • 线程间切换不如进程间切换耗时
  • CPU调度的基本单位

进程间通信

https://zh.wikipedia.org/wiki/%E8%A1%8C%E7%A8%8B%E9%96%93%E9%80%9A%E8%A8%8A

https://www.ibm.com/developerworks/cn/linux/l-ipc/

  • 管道：具有亲缘关系进程间通信
  • 有名管道：允许无亲缘间关系进程间通信
  • 信号
  • 消息队列
  • 共享内存
  • 信号量
  • 套接字

进程同步

  • 信号量
  • 自旋锁
  • 栅栏

线程同步

  • 互斥量
  • 信号量
  • 条件变量
  • 读写锁

死锁

《现代操作系统》 P246

四个条件

  • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的
  • 占有和等待：已经得到了某个资源的进程可以再请求新的资源
  • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它地进程显式地释放
  • 环路等待：死锁发生时，系统中一定有由两个或两个以上地进程组成地一条环路，该环路中地每个进程都在等待着下一个进程所占有的资源

生产者消费者

使用Object的wait()和notify()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class ProducerConsumer {
    private Queue<Integer> queue = new LinkedList<Integer>();
    private final static int SIZE = 3;
    class Producer implements Runnable {
        @Override
        public void run() {
            synchronized (queue) {
                while (queue.size() == SIZE) {
                    try {
                        queue.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                queue.add(new Random().nextInt(100));
                queue.notifyAll();
            }
        }
    }
    class Consumer implements Runnable {
        @Override
        public void run() {
            synchronized (queue) {
                while (queue.isEmpty()) {
                    try {
                        queue.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                queue.poll();
                queue.notifyAll();
            }
        }
    }
}

使用Lock的Condition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class ProducerConsumer {
    private Lock lock = new ReentrantLock();
    private Condition notFull = lock.newCondition();
    private Condition notEmpty = lock.newCondition();
    private Queue<Integer> queue = new LinkedList<Integer>();
    private final static int SIZE = 3;
    class Producer implements Runnable {
        @Override
        public void run() {
            lock.lock();
            try {
                while (queue.size() == SIZE) {
                    notFull.await();
                }
                queue.add(new Random().nextInt(100));
                notEmpty.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            finally {
                lock.unlock();
            }
        }
    }
    class Consumer implements Runnable {
        @Override
        public void run() {
            lock.lock();
            try {
                while (queue.isEmpty()) {
                    notEmpty.await();
                }
                queue.poll();
                notFull.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    }
}

缓存

程序需要第k+1层某个数据对象d时：

  • 缓存命中：d刚好缓存在第k层中
  • 缓存不命中：第k层中没有缓存数据对象d

计算机系统每个存储器地址有m位，形成M=2^m个不同的地址。组织成S=2^s个告诉缓存组的数组，每个组包含E个高速缓存行，每个行是由一个B=2^b字节的数据块组成的，一个有效位指明这个行是否包含有意义的 信息，还有t=m-(b+s)个标记位唯一地标识存储在这个高速缓存行中的块。

地址：t位（标记）+ s位（组索引）+ b位（块偏移）

  • write through：立即将w的高速缓存块写回到紧接着的低一层中
  • write back：只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层

虚拟内存

页表

页表将虚拟页映射到物理页，每次地址翻译时硬件将一个虚拟地址转换成物理地址时，都会读取页表。

页表就是一个页表条目（PTE）的数组

地址翻译

虚拟地址：虚拟页号（VPN）+ 虚拟页偏移量（VPO）

VPN作为到页表中的索引，获得物理页号；虚拟页偏移量 -> 物理页偏移量

物理地址：物理页号（PPN）+ 物理页偏移量（PPO）

  1. 处理器生成一个虚拟地址，并把它传送给MMU（Memory Management Unit）
  2. MMU生成PTE地址，并从高速缓存/主存请求得到它
  3. 高速缓存/主存向MMU返回PTE
  4. MMU构造物理地址，并把它传送给高速缓存/主存
  5. 高速缓存/主存返回所请求的数据字给处理器

TLB加速地址翻译

  1. CPU产生一个虚拟地址
    1. MMU从TLB中取出相应的PTE
    2. MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存
    3. 高速缓存/主存返回所请求的数据字给CPU