View on GitHub

Dmarco-v.github.io

Dmarco_v的技术博客，Java开发相关技术积累、LeetCode刷题笔记

一、操作系统概述

操作系统（OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，是计算机系统中最基本的系统软件。

1.OS的功能和目标

2.OS的特征

3.系统调用

系统调用是操作系统提供给应用程序使用的接口，可供应用程序调用的特殊函数。

4.OS的运行机制

OS的内核

操作系统包括非内核功能和内核，内核更接近硬件。

  1. 与硬件关联紧密的模块：时钟管理、中断处理、原语（一种特殊程序具有原子性，运行不可中断）
  2. 对系统资源进行管理的功能：进程管理、存储器管理和设备管理。

OS的体系结构

包括大内核和微内核两种。

5.中断

中断发生时，CPU会进入核心态。中断是将用户态切换到核心态的唯一途径，而将核心态切换为用户态只需通过执行一个特权指令即可。

二、进程管理

1.进程与线程

进程：

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。或定义为：进程是OS资源分配的基本单位（引入线程后，进程只是资源分配的基本单位，而线程是调度的基本单位）。

进程由程序段、数据段和PCB三部分组成。

进程控制块（PCB，process control block）描述了进程的基本信息和运行状态，包含操作系统对其进行管理所需的各种信息。

进程的组织方式有链接方式和索引方式两种。

线程：

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。因为进程内的各线程之间也可以并发，从而进一步提升了系统并发度，使得一个进程内也可以并发处理各种任务。

进程与线程的关系：一个进程可以有多个线程，他们共享进程资源。如QQ是一个进程，里面有多个线程，如传文件、聊天、视频等等。

进程和线程的区别：

线程的实现方式：用户级线程和内核级线程。

多线程模型：

2.进程的状态及其转换

进程包括三种基本状态：

另两种状态：

进程状态的转换。只有就绪态和运行态可以相互转换，其他都只能单向转换。


进程控制即使用原语实现进程状态的转换。

原语的特点是执行期间不可中断。原语需要运行在核心态，属于OS内核的一部分。

3.进程调度

进程的挂起态与七状态模型：暂时调到外存等待的进程状态为挂起状态，挂起态又可以进一步细分为就绪挂起和阻塞挂起两种状态，补充到无状态模型中成为七状态模型。

注意：挂起态是将进程映像调到外存，而阻塞态下进程映像还在内存中。

处理机调度的三个层次：

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程调度的时机：

进程调度的方式：

调度算法的评价指标：

进程调度算法：

  1. 批处理系统。批处理系统用户没有太多操作，调度算法的目标是保证吞吐量和周转时间。
    • FCFS，先来先服务。非抢占式，按请求顺序进行调度。对短作业不利。
    • SJF，短作业优先。默认为非抢占式，按估计运行时间最短的顺序进行调度。对长作业不利，可能会导致长作业饥饿。
    • HRRN，高响应比优先。非抢占式。是两种算法的权衡，综合考虑等待时间和运行时间。
  2. 交互式系统。有大量用户交互操作，调度算法的目标是快速响应。
    • 时间片轮转。抢占式。为每个进程分配时间片，一个进程时间片用完将其送往就绪队列的末尾。优点是公平、缺点是频繁切换有开销，且无优先级。如果时间片过小，会导致切换过于频繁；时间片过长，实时性就得不到保证。
    • 优先级调度。抢占式和非抢占式都有。为每个进程分配优先级，按优先级进行调度。可能会导致饥饿，可以随着时间的推移提高等待进程的优先级。
    • 多级反馈队列。抢占式。设置多级队列，每个队列设置时间片（如1,2,4,8）和优先级（最上面的队列优先级最高，上一队列没有进程排队，才能调度当前队列），是前两种的结合。
  3. 实时系统。要求响应时间短。分为硬实时和软实时两种。

4.进程通信

进程通信（IPC）是指进程之间的信息交换。各进程拥有的内存地址空间相互独立，为了保证安全，一个进程不能直接访问另一个进程的地址空间，操作系统提供了一些方法来实现进程之间的信息交换。

实现进程通信的方式：

5.进程同步

进程的异步性：各并发执行的进程以各自独立的，不可预知的速度向前推进。

资源共享的两种方式：

进程的同步与互斥：

进程互斥的软件实现方法：

信号量机制。使用一对原语来对信号量操作，从而方便地实现了进程互斥和进程同步。一对原语即wait(s)和signal(s)原语，简称为P和V操作（来自荷兰语proberen和verhogen）。

使用信号量机制实现进程互斥与同步：

6.进程同步与互斥经典问题

生产者消费者问题：

描述：生产者进程每次生产一个产品放入缓冲区，消费者每次从缓冲区取出一个产品并使用（缓冲区大小为n）。

#define N 100
typedef int semaphore;
semaphore mutex = 1;//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = N;//同步信号量，表示缓冲区的空闲空间
semaphore full = 0;//同步信号量，表示缓冲区已占用的空间
void producer(){
    while(1){
        produce();//生产一个产品
        wait(empty);//empty-1,与signal(empty)共同实现进程同步
        wait(mutex);
        add();//放入一个产品到缓冲区
        signal(mutex);//在临界区前后增加一对PV操作实现互斥
        signal(full);//full+1,与wait(full)共同实现进程同步
    }
}
void cosumer(){
    while(1){
        wait(full);//full-1,与signal(full)共同实现进程同步
        wait(mutex);
        remove();//从缓冲区取出一个产品
        signal(mutex);//在临界区前后增加一对PV操作实现互斥
        signal(empty);//empty+1,与wait(empty)共同实现进程同步
        consume();//消费一个产品
    }
}

注意：实现同步的P操作必须放在实现互斥的P操作之前，否则两个进程都被阻塞，出现死锁。而V操作可以交换顺序。

类似的还有多生产者多消费者问题、吸烟者问题（单生产者多消费者）

读者写者问题：

读写两组进程访问共享文件。要求：

互斥关系：写进程-写进程、写进程-读进程

typedef int semaphore;
semaphore count_mutex = 1;//对count变量的互斥访问
semaphore data_mutex = 1;//对读写数据加锁
int count = 0;//记录有几个读进程在访问文件
void writer(){
    while(1){
        wait(data_mutex);//对读写数据加锁
        write();
        signal(data_mutex);//对读写数据解锁
    }
}
void reader(){
    while(1){
        wait(count_mutex);//各个读进程互斥访问count
        if(count==0) wait(data_mutex);//第一个读进程负责加锁，防止写进程访问
        count++;
        signal(count_mutex);
        read();
        wait(count_mutex);//各个读进程互斥访问count
        count--;
        if(count==0) signal(data_mutex);//最后一个读进程负责解锁
        signal(count_mutex);
    }
}

如果一直有读进程访问文件，那么写进程可能会出现饥饿的现象。可以新增一个信号量增加PV操作到合适的位置，用于实现写优先。

哲学家进餐问题：

五个哲学家围着圆桌吃饭，每个哲学家面前放着食物，哲学家有两种操作：吃饭和思考。当一个哲学家要吃饭时，需要先拿起左右两边的筷子，并且一次只能拿起一根筷子。

一个错误的解决方案如下。如果所有哲学家并发的拿起了左手边的筷子，那么每位哲学家循环等待右边的人放下筷子（都进入阻塞态），从而发生死锁。

#define N 5
semaphore chopstick[N]={1,1,1,1,1};
void philosopher(int i) {
    while(1) {
        take(chopstick[i]);       // 拿起左边的筷子,P操作
        take((chopstick[i+1])%N); // 拿起右边的筷子
        eat();
        put(chopstick[i]); 	   // 放下左边的筷子,V操作
        put((chopstick[i+1])%N);
        think();
    }
}

可以设置一个条件防止死锁的发生，即各哲学家拿筷子的事件必须互斥的执行。

#define N 5
semaphore chopstick[N]={1,1,1,1,1};
semaphore mutex=1;	//互斥信号量
void philosopher(int i) {
    while(1) {
        wait(mutex);	//实现的对筷子的互斥访问
        take(chopstick[i]);       // 拿左
        take((chopstick[i+1])%N); // 拿右
        signal(mutex);	
        eat();
        put(chopstick[i]); 	   // 放左
        put((chopstick[i+1])%N);	//放右
        think();
    }
}

每个进程都需要同时持有两个临界资源时，就有出现死锁问题的隐患，这种情况下应参考哲学家问题的思想，分析给出的进程之间是否会发生循环等待，是否会发生死锁。

7.管程

引入管程的原因：信号量机制存在编写程序困难，容易出错。使用管程可以将控制的代码独立出来，不易出错。

管程是一种特殊的软件模块，类似于面向对象中的类。使用管程可以方便的实现互斥和同步。包括以下组成部分：

管程的基本特征：

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者进程
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者进程
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

补充：java中使用synchronized关键字来描述函数，那么这个函数同一时间段内只能被一个线程调用。

8.死锁

死锁是指各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

死锁发生的必要条件

死锁的处理策略

三、内存管理

1.内存和内存管理

程序执行前需要先放到内存中才能被CPU处理。

内存地址有逻辑地址（相对）和物理地址（绝对）。

程序执行过程：

内存管理的主要内容：

2.内存空间分配与回收

连续分配管理方式：为用户进程分配的是连续的内存空间。

非连续分配管理方式：为用户进程分配的可以是一些分散的内存空间。

3.内存空间扩充

4.页面置换算法

页面换入换出需要磁盘IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

  1. 最佳置换算法（OPT，Optimal replacement algorithm）。每次选择淘汰的页面将是以后永不使用，或者最长时间内不再被访问的页面，这样可以保证最低的缺页率。是一种理论上的算法，因为无法准确知道一个页面多长时间不再被访问，实际应用中无法实现。
  2. 先进先出置换算法（FIFO）。每次淘汰的是最早进入内存的页面。性能较差。
  3. 最近最久未使用置换算法（LRU，Least Recently Used）。每次淘汰的页面是最近最久未使用的页面。每次访问都需要维护一个所有页面的链表，因此效率较低。
  4. 时钟置换算法（CLOCK/NRU Not Recently Used）。使用循环链表将页面连接起来，再使用一个指针指向最老的页面。每次淘汰最近未使用（访问位为0）的页面。
  5. 改进型的时钟置换算法。在最近未使用的页面中优先淘汰未被修改过的页面，最多会进行四次扫描。

四、I/O设备管理

1.I/O设备

IO设备就是可以将数据输入计算机或可以接收计算机输出数据的外部设备，属于计算机的硬件部件。

IO设备的分类：

2.I/O控制器与控制方式

IO设备包括机械部件和电子部件。电子部件是机械部件和CPU之间的中介，用于实现CPU对设备的控制。这个电子部件就是IO控制器。

IO控制器的功能包括：接收和识别CPU指令、向CPU报告设备状态、数据交换和地址识别。

IO控制方式：