木慕的博客

Stay naive, stay simple.

0%

操作系统总结

发表于 分类于 Valine：

《modern operating systems> 我看的是第四版，主要介绍了操作系统相关的理论性的东西，为了防止遗忘，记录下重点备查。

1 进程和线程

进程

进程是程序的一个正在执行的实例，包括相关的PC（program counter），寄存器和变量等。理论上说，每一个进程都有属于自己的虚拟CPU。

进程模型

  • 多道程序设计（multiprogramming）: 指仅使用一个CPU（单核），在进程中来回切换，造成多个进程同时进行的效果。

进程与程序的区别：
书中类比食谱和做饭的活动，食谱就是程序（program），而做饭的过程（读食谱，拿食材，做饭）就是进程的概念

进程创建

引起创建进程的事件：

  • 系统初始化
  • 正在运行的进程执行了系统调用
  • 用户请求创建进程
  • 启动批处理作业(batch job),在大型机的批处理操作系统中

在Linux中，只有一个系统调用可以创建新进程: fork.

进程终止

  • 正常退出
  • 错误退出
  • 严重错误退出
  • 被其他进程kill

进程层次结构

  • 一个进程只有一个父进程，但可以有0-N个子进程。
  • Unix是通过init进程进行初始化的
  • Windows在创建进程时，父进程得到子进程的句柄(handle)，但是handle可以传递，故没有进程层次结构的概念。

进程状态

  • 运行态（正在使用CPU）
  • 就绪态（可以运行）
  • 阻塞态（不能运行，需要条件）

阻塞状态可能是还没有得到运行的条件，例如在进程中读文件没有可用的输入时，就blocked。当万事俱备时，就可以转入就绪态等待进程调度。
从运行态到就绪态相互的过程是进程调度程序引起的，例如分时系统中时间到了就调度正在运行的程序进入就绪状态。

进程实现

在具体的实现中，OS维持一张进程表：process table，每一个项成为进程控制块（process control block），包含了关于进程的重要信息：PC: program counter，栈指针，内存分配，打开文件的状态，调度信息等等。

如图所示，IO对于CPU利用率影响很大：
image

线程

  • 为什么要有线程
  • 线程实现

内存是重要资源，操作系统的存储管理主要是针对内存的管理。

直接引入内存地址带来的问题（在multiprogramming 计算机中）：

  • 保护问题 protection
  • 重定位问题（需要用到的地址未知） relocation

保护问题IBM 360机是通过加入保护键解决的，重定位问题如果使用加入初始地址解决，但是会比较麻烦，因为要判断每个地址需不需要更改。

地址空间： 一种存储器抽象

每个进程有自己的地址空间，并且独立于其他进程。

  • 解决重定位问题：每个CPU配置两个特殊的寄存器，base 和 limit，分别对应物理空间的初始地址和长度（单位byte）。CPU会自动把base加载到进程发出的地址上，同时做界限检查

交换技术

把空闲进程存储在磁盘上，不过不够好，因为RAM和磁盘之间速度太低，swap一次时间很长，在后面的虚拟内存技术更好。

空闲内存管理

  • 位图
  • 空闲链表

虚拟内存

问题：软件需要的内存更大

交换技术不是很好的解决方案，使用虚拟内存的方法更好（1961）：

  • 每个程序有自己的地址空间
  • 地址空间分成多个块，每块称为页面（page）
  • 每一个page映射到物理地址的page中
  • 用到的时候再装入内存

分页

Paging技术：内存管理单元（MMU）把虚拟地址映射到物理内存地址。

虚拟地址空间分成以page大小的若干单元，在物理内存中对应的称为页框（page frame）。RAM和磁盘之间的交换是以页框为单位。 页号作为页表的索引，找到对应的页框号（实际物理地址）。

页表

页表：每一项标记了在/不再内存中和对应的页框号（对应的物理页框号）

页框号+页内偏移 = 真实物理地址

页表项

  • 页框号
  • 在/不在位，不在就直接缺页中断
  • 保护位
  • 修改位，有时称为脏位（dirty bit）

改进

  • 加速虚拟地址到物理地址的转换
    • TLB（快表）
  • 解决巨大的虚拟地址空间的问题
    • 多级页表
    • 倒排页表

页面置换算法

  • 最优页面置换算法
  • NRU 算法（Not Recently Used， 最近未使用）
    • 想法：淘汰一个访问修改最少的页面
  • FIFO
    • 最新进入的页面放表尾，最久进入的表头，当却也中断时淘汰表头（很少使用）
  • second chance 算法（改进）
    • 最老页面的R位（访问位）如果是1，那么再给它一次机会，置零后放入队尾
  • clock 算法
    • 避免经常在链表里移动页面
    • 所有页面保存在一个环形链表里，表指针指向最老的页面
    • R=0，淘汰页面，新页面加入此地，之后移位，R=1就置零后移位
  • LRU算法
    • 最近最少使用： 缺页中断发生时，置换未使用时间最长的页面
    • NFU时一种近似算法，性能不是很好，老化算法更接近LRU，更有效

文件是对disk的抽象，以名称存取

文件

文件命名

  • Case Sensitive
    • Linux/UNIX
  • Case Insensitive
    • DOS
  • Case Insensitive， Case Preserving
    • Windows
    • Mac

文件结构

三种文件结构：

a. 字节序列： UNIX，DOS，Windows采用
b. 记录序列：读操作返回一个记录，写操作重写或者追加一个记录，大型机常用
c. 记录树：树按照键字段进行排序，好处是可以针对特定的键进行快速查找

文件类型

  • 普通文件
    • ASCII 文件
    • 二进制文件
  • 目录文件
  • 字符特殊文件（Unix）
    • 用于串行IO设备
  • 块特殊文件（Unix）
    • 用于磁盘类设备

文件属性

文件操作

  • create
  • delete
  • open
  • close
  • read
  • write
  • append
  • seek
  • get attributes
  • set attributes
  • rename

一个简单的复制文件的例子：

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
43
44
45
46
47
48
49
#include <sys/types.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
int main(int argc, char *argv[]);

// 一个4096B的缓冲区
#define BUF_SIZE 4096
// 输出文件的保护位
#define OUTPUT_MODE 0700
#define TRUE 1

int main(int argc, char *argv[])
{

    int in_fd, out_fd, rd_count, wt_count;

    char buffer[BUF_SIZE];

    if (argc != 3)
        exit(1);

    in_fd = open(argv[1], O_RDONLY); // 打开源文件
    if (in_fd < 0)
        exit(2);

    out_fd = creat(argv[2], OUTPUT_MODE); //创建目标文件

    if (out_fd < 0)
        exit(3);

    while (TRUE)
    {
        rd_count = read(in_fd, buffer, BUF_SIZE);

        if (rd_count <= 0) // 文件结束或者读时出错，则退出
            break;
        wt_count = write(out_fd, buffer, rd_count);
        if (wt_count <= 0)
            exit(4);
    }

    close(in_fd);
    close(out_fd);
    if (rd_count == 0)
        exit(0);
    else
        exit(5);
}