operating system

schedule algorithm

round robin

轮询, 任务到达就放到队列中, 对于在队列中的进程按顺序执行, 执行完立即执行下一个任务, 循环直到结束

FCFS

先到先执行

SJF

优先执行剩余时间短的任务, 中途到达的任务不可抢占

SRTF

任务到达后如果剩余时间比当前任务的剩余时间短则可以抢占当前任务, 优先执行短的任务

process synchronzation

semaphores

bounding-buffer

如果不用 mutex 结果错误

如果只使用一个 mutex 信息量和 count 整数, 会使得结果正确但效率降低

使用 empty 和 full 可以允许 consumer, producer 并发, 只在更新缓存区时互斥

而且只用一个 count 也很难设计状态

monitor / condition variables

dining-philosopher

等待公共资源 (筷子) 会导致死锁

尽管特定的访问顺序 (如优先访问/等待编号小的筷子) 能防止死锁, 但是这样不好

所以使用条件变量, 每个哲学家等待自己

条件变量 signal 一定唤醒一个进程, 信号量不一定

other examples

// thread 1
while(1){
    P(mutex_Y1);
    w = add(x, y);
    V(mutex_Y1);
}
// thread 2
while(1){
    P(mutex_Y2);
    P(mutex_Z);
    w = add(y, z);
    V(mutex_Z);
    V(mutex_Y2);
}
//thread 3
while(1){
    P(mutex_Z);
    z = add(z, w);
    V(mutex_Z);
    P(mutex_Y1);
    P(mutex_Y2);
    y = add(y, w);
    V(mutex_Y2);
    V(mutex_Y1);
}

注意 thread 3 一定要先释放 mutex_Z 再等待 mutex_Y2, 不然与 thread 2 死锁

linux

启动 linux 内核

BIOS: 写在 ROM 中, 先进行开机硬件自查, 之后根据 boot sequence 选择存储设备
MBR: 读取存储设备的第一个分区的第一个扇区 (即设备的第一个扇区), 512 字节内容为 MBR (主引导记录), 里面有引导机器码, 分区表和签名
VBR/Grub: 控制权转交给分区 / Grub, 如果是分区则读取 VBR (卷引导记录), 确定操作系统的位置; 如果是 Grub, 直接从文件系统选择操作系统
启动内核...

memory

optimal

最优性证明:

FIFO

有可能出现 Belady 现象: 缓存容量增大, 命中率反而降低

\(\underline{例}:\)

\(1,2,3,4,1,2,5,1,2,3,4,5\)

\(C=3: 9\text{ page faults}\)

\(C=4: 10\text{ page faults}\)

LRU

不会有 Belady 现象, 因为容量小的缓存中数据始终是容量大的缓存中数据的子集

当前考虑第 \(i\) 个元素, 最近访问的是 reference sequence 从 \(i-1\) 往前 \(k\) 个不重复元素, 这 \(k\) 个元素一定都在缓存中

所以缓存的数据集合始终为前 \(k\) 个不重复元素, 这使得子集关系成立

Second Chance

clock, 转一圈, 把 R = 1 变成 R = 0, 第二次遇到时, 把 R = 0 替换出去

file

软连接/硬链接

软连接: 一边修改影响另一边

硬链接: 拷贝 FCB File Control Block, 不是文件本体; 两边修改可能不一致

filesystem

每个 disk 由 MBR 规定了至多 4 个主分区 / 3 主分区 + 1 扩展分区

逻辑分区都存放在扩展分区中

每个分区有一个文件系统管理, 里面有 directory + files

linux 只有一个目录树, 即根目录树 /

在 MBR + BIOS 的操作系统中:

/boot 必须放主分区，因为 BIOS 引导链只能访问主分区
/ 放主分区因为启动过程依赖它, 主分区更简单可靠
swap 放主分区因为 EBR 链表不稳定和性能考量

所以一般可以把 3 个主分区 (的文件系统) 挂载到 /, /boot, swap

其他逻辑分区挂载到挂载点即可通过目录树访问该分区的文件系统

在 linux 中应用

查看磁盘分区/文件系统
```
lsblk -f
fdisk -l
```

创建分区

使用 parted 工具

parted [Enter]
(parted) select /dev/sdb
(parted) mklabel gpt
(parted) mkpart [Enter]
Partition name?  []? sdb1
File system type?  [ext2]? ext4 
Start? 1 
End? 1024
(parted) print # 查看分区

创建文件系统

mkfs.ext4 /dev/sdb1

3. 挂载

mount /dev/sdb1 /mnt
blkid /dev/sdb1 # UUID
vim /etc/fstab # 设置开机自动挂载