操作系统笔记

Processes

内存排布

进程的状态 (State)

进程控制器 (Process Control Block, PCB)

进程调度器 (Process Scheduler)

上下文切换 (context switch)

进程停止时要保存something到PCB中，继续进行要恢复

something有PC，寄存器,stack…

继续进行时要把PCB中的something恢复到内存中

一次上下文切换大约几十微秒，占用时间片时间千分之几

挂起 (suspended)

与ready和wating的进程相比，挂起的进程的资源可能会被回收，存储在内存的东西被写到磁盘

进程操作

创建进程 (Process Creation)
fork() 会新建一个子进程，并用父进程初始化子进程
进程终止

主动终止 exit()

异常终止 signal

SIGTERM (Ctrl + C)

SIGABRT abort()

SIGSEGV 访问了不能访问的资源，指针

SIGKILL=9 直接终止 kill -9 pid

进程通信(Interprocess Communication)

消息传递: blocking(阻塞，同步),non-blocking(非阻塞,异步)

Threads

进程是资源分配管理的最小单位，线程是调度的最小单位

多核编程

用户线程和内核线程

内核线程可以被抢占，用户线程不可以，用户进程主动释放CPU
多对一

绑定在同一内核线程的用户进程交替进行，因为只占用一个CPU核
用户线程切换不需要内核参与，速度更快

进程创建和销毁(Pthreads)

线程池(Thread Pools)

在进程创建的时候，就创建一堆线程，让他们在获取任务的地方阻塞，当来一个任务，就从线程池中取出一个线程，完成这个任务之后，线程在放回线程池

线程的问题

CPU调度

基本概念

进程的概念

CPU密集型和IO密集型程序

CPU burst一般很短

CPU调度器

在上下文切换时发挥作用

调度算法

目标
先到先服务(FCFS)
最短作业调度(Shortest-Job-First (SJF))
选择执行时间最短的作业

shortest-remaining-time-first

有个问题：执行时间不一定能提前知道
可以预测这个线程的执行时间

轮转算法

时间片时间必须大于上下文切换时间

时间片越小，越倾向于短执行时间的作业

时间片越大，越类似于先来先服务算法

优先级调度

优先级调度+轮转

多级队列

多核调度（Multiple-Processor Scheduling）

亲和性（Processor Affinity）

让线程保持在某一个CPU核上运行

同步机制

race condition

并发线程对共享变量的使用引发错误

临界区问题（Critical Section Problem）

临界区

临界区在同一时刻只允许被一个线程执行

解决措施的要求
基于中断的解决方法

Entry section: disable interrupts 进入时禁止中断
Exit section: enable interrupts 结束时开启中断

但是对于多核处理器来说，问题依然会有
软件的解决（过时）
Peterson’s Solution（过时）

同步硬件（忙等）

test_and_set 指令

原子型命令

示例
compare_and_swap 指令

这俩会有不断循环，没解决内存可见性

信号量（Semaphore）

定义

Implementation with no Busy waiting

大于0，代表无阻塞的调用wait的次数，被保护的这个资源可以同时被多少个进程访问
小于0，代表有多少的个进程阻塞在等待队列

管程（Monitors）

定义
1. 变量都为私有变量
2. 同一时刻只有一个线程在管程中
条件变量

实际上是一个等待队列
带有条件变量的管程

例子

int count = 8;
condition x;

void borrow (int n) {
    while (count < n) {
        x.wait();
    }
    count -= n;
}

void returm (int n) {
    count += n;
    //x.signal();
    x.signalAll();
}

活性（Liveness）

死锁
饥饿

同步案例

生产者-消费者问题（Bounded-Buffer Problem）

Semaphore 做法

Item buffer[N];
int in = 0, out = 0;
int count = 0;

Semaphore empty = N, full = 0, mutex = 1;

void put (o) {
    empty.wait();
    
    mutex.wait();
    buffer[in] = o;
    in = (in + 1) % N;
    count++;
    mutex.signal();
    
    full.signal();
}

void get () {
    full.wait();
    
    mutex.wait();
    o = buffer[out];
    out = (out + 1) % N;
    count--;
    mutex.signal();
    
    empty.signal();
    return o;
}

假设5个消费者，N = 6，4个消费者
empty 范围 [-5, 6]
full 范围 [-4, 6]
mutex 范围 [(-5), 1]

Monitors做法

Item buffer[N];
int in = 0, out = 0;
int count = 0;

condition notFull, notEmpty;

put (o) {
    while (count == N) {
        notFull.wait();
    }
    buffer[in] = o;
    in = (in + 1) % N;
    count++;
    notEmpty.signal();
}

get () {
    while (count == 0) {
        notFull.wait();
    }
    o = buffer[out];
    out = (out + 1) % N;
    count--;
    notFull.signal();
    return o;
}

读者-写者问题(Readers-Writers Problem)

Semaphore 做法

Semaphore mutex = 1, ,
int cnt = 0;

beginWrite() {
    mutex.wait();
}

endWrite() {
    mutex.signal();
}

beginRead() {
    x.wait();
    cnt++;
    if (cnt == 1) {
        mutex.wait();
    }
    x.signal();
}

endRead() {
    x.wait();
    cnt--;
    if (cnt == 0) {
        mutex.signal();
    }
    x.signal();
}

这个解法对读者是优先的

Monitors做法

condition r, w;
int rc = 0, wc = 0;//读写者的计数器

beginWrite() {
    while (rc > 0 || wc > 0) {
        w.wait();
    }
    wc++;
}

endWrite() {
    wc--;
    w.signal();
    r.signalAll();//要唤醒所有读者
}

beginRead() {
    while(wc > 0) {
        r.wait();
    }
    rc++;
}

endRead() {
    if (rc == 0) {
        w.signal();
    }
}

哲学家进餐问题(Dining-Philosophers Problem)

Semaphore 做法

Semaphore C[S] = {1,1,1,1,1};

P(i) {
    C[i].wait();
    C[(i+1) % 5].wait();
    eat();
    C[i].signal();
    C[(i+1) % 5].signal();
} 

死锁问题

Monitors做法

condition r[5];
int c[S] = {1,1,1,1,1};

beginEat(i) {
    while (c[i] == 0 || c[(i + 1) % 5] == 0) {
        r[i].wait();
    }
    c[i] = 0;
    c[(i + 1) % 5] = 0;
}

endEat(i) {
    c[i] = 1;
    c[(i + 1) % 5] = 1;
    r[(i + 4) % 5].signal();
    r[(i + 1) % 5].signal();
}