进程

基础

CPU 可以1秒操作好多进程，这叫并发。
CPU 可以从一个进程（做菜）切换到另外一个进程（买可乐），在切换前必须要记录当前进程中运行的状态信息，以备下次切换回来的时候可以恢复执行，这叫并行。

并发与并行

进程的状态

在一个进程的活动期间至少具备三种基本状态

运行状态（Running）：该时刻进程占用 CPU；
就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；

在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

创建状态（new）：进程正在被创建时的状态；
结束状态（Exit）：进程正在从系统中消失时的状态；

描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

进程的数据结构(PCB)

PCB 是进程存在的唯一标识
描述信息：进程标识符，用户标识符
进程当前状态，进程优先级
内存地址信息和虚拟地址空间信息
CPU中寄存器的值，进程重新执行时，可在断点处继续执行

PCB 是通过链表或者索引进行组织的，一般使用链表

组织好后有两种状态，就绪状态和阻塞状态。

进程的控制操作

创建进程

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源。

终止进程

进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

当子进程被终止时，其在父进程处继承的资源应当还给父进程。而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作。

阻塞进程

当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。

唤醒进程

进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。
如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。

进程的上下文切换

一个进程切换到另一个进程运行

同时要学会CPU的上下文切换

发生进程上下文切换有哪些场景？

了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程

线程之间可以并发运行且共享相同的地址空间

什么是线程

线程是进程当中的一条执行流程。

线程的优点：
一个进程中可以同时存在多个线程；
各个线程之间可以并发执行；
各个线程之间可以共享地址空间和文件等资源；
线程的缺点：
当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成进程崩溃

线程与进程的比较

进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位。
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈。
线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系。
线程能减少并发执行的时间和空间开销。

对比而言，线程相比进程能减少开销，体现在以下几个方面：

线程的创建时间比进程快，因为进程在创建的过程中还需要资源管理信息，如内存管理信息、文件管理信息，而线程在创建的过程中不涉及这些资源管理信息，它们是共享的。
线程的终止时间比进程快，因为线程释放的资源相比进程少很多。
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换时不需要切换页表。而对于进程之间的切换，切换时要切换页表，而页表的切换过程开销较大。
由于同一进程的各线程间共享内存和文件资源，线程之间数据传递时无需经过内核，使得线程之间的数据交互效率更高。

线程上下文切换的是什么？

当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

线程的实现

三种线程

用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
轻量级进程（LightWeight Process）：在内核中来支持用户线程；

内存管理

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

我们程序所使用的内存地址叫做虚拟内存地址
实际存在硬件里面的空间地址叫物理内存地址

操作系统是如何管理虚拟地址与物理地址之间的关系？

有以下2种方式

内存分段

操作系统给每一个进程分段，一个进程有一个段ID，然后有一个段表，段表里面有基础物理内存地址，还有偏移量。

缺点

内存碎片
1. 各个程序之间的内存间隔
内存交换的效率低
1. 为了解决内存碎片问题，就要使用内存交换，碎片多，交换的也多，所以时间长，显现的效率低。

内存分页

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。

在 Linux 下，每一页的大小为 4KB。

之间通过页表进行映射。

分页是怎么解决分段的「外部内存碎片和内存交换效率低」的问题？

采用了分页，页与页之间是紧密排列的，所以不会有外部碎片。不过会出现内存浪费的情况，这个叫做内部内存碎片。

如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉。

只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。
什么时候使用，什么时候就加载它。

总结

把虚拟内存地址，切分成页号和偏移量；
根据页号，从页表里面，查询对应的物理页号；
直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

多级页表

一个进程，一个页表

进程多的话，页表就多，这个对内存会有一个很大的消耗。

所以引入多级列表。

64位系统

全局页目录项 PGD
上层页目录项 PUD
中间页目录项 PMD
页表项 PTE

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的
Cache，这个 Cache 就是 TLB，通常称为页表缓存、转址旁路缓存、快表等。

段页式内存管理

先分段，然后分页，先是段表，每个段表里面是页表。

Linux 内存布局

虚拟内存有什么作用？

虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。

malloc 是如何分配内存的？

调度

原则

从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
从运行态 -> 阻塞态：当进程发生 I/O 事件（此时该进程需要等待I/O完成后，才可以重新运行）而阻塞时，操作系统必须选择另外一个进程运行；
从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；
非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程。
抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程，也就是常说的时间片机制。

调度原则

I/O 事件
吞吐量：CPU 在单位时间内完成的进程数量
等待时间：进程处于就绪队列的时间
周期时间：进程运行+阻塞时间+等待时间的总和
响应时间

调度算法

先来先服务调度算法

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

最短作业优先调度算法

会优先选择运行时间最短的进程来运行

时间片轮转调度算法

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

最高优先级调度算法

从就绪队列中选择最高优先级的进程进行运行

小故事:

办理业务的客户相当于进程，银行窗口工作人员相当于 CPU。现在，假设这个银行只有一个窗口（单核 CPU ），那么工作人员一次只能处理一个业务。

那么最简单的处理方式，就是先来的先处理，后面来的就乖乖排队，这就是先来先服务（FCFS）调度算法。但是万一先来的这位老哥是来贷款的，这一谈就好几个小时，一直占用着窗口，这样后面的人只能干等，或许后面的人只是想简单的取个钱，几分钟就能搞定，却因为前面老哥办长业务而要等几个小时，你说气不气人？

有客户抱怨了，那我们就要改进，我们干脆优先给那些几分钟就能搞定的人办理业务，这就是短作业优先（SJF）调度算法。听起来不错，但是依然还是有个极端情况，万一办理短业务的人非常的多，这会导致长业务的人一直得不到服务，万一这个长业务是个大客户，那不就捡了芝麻丢了西瓜

那就公平起见，现在窗口工作人员规定，每个人我只处理 10 分钟。如果 10 分钟之内处理完，就马上换下一个人。如果没处理完，依然换下一个人，但是客户自己得记住办理到哪个步骤了。这个也就是时间片轮转（RR）调度算法。但是如果时间片设置过短，那么就会造成大量的上下文切换，增大了系统开销。如果时间片过长，相当于退化成 FCFS 算法了。

既然公平也可能存在问题，那银行就对客户分等级，分为普通客户、VIP 客户、SVIP 客户。只要高优先级的客户一来，就第一时间处理这个客户，这就是最高优先级（HPF）调度算法。但依然也会有极端的问题，万一当天来的全是高级客户，那普通客户不是没有被服务的机会，不把普通客户当人是吗？那我们把优先级改成动态的，如果客户办理业务时间增加，则降低其优先级，如果客户等待时间增加，则升高其优先级。

那有没有兼顾到公平和效率的方式呢？这里介绍一种算法，考虑的还算充分的，多级反馈队列（MFQ）调度算法，它是时间片轮转算法和优先级算法的综合和发展。它的工作方式：

银行设置了多个排队（就绪）队列，每个队列都有不同的优先级，各个队列优先级从高到低，同时每个队列执行时间片的长度也不同，优先级越高的时间片越短。
新客户（进程）来了，先进入第一级队列的末尾，按先来先服务原则排队等待被叫号（运行）。如果时间片用完客户的业务还没办理完成，则让客户进入到下一级队列的末尾，以此类推，直至客户业务办理完成。
当第一级队列没人排队时，就会叫号二级队列的客户。如果客户办理业务过程中，有新的客户加入到较高优先级的队列，那么此时办理中的客户需要停止办理，回到原队列的末尾等待再次叫号，因为要把窗口让给刚进入较高优先级队列的客户。

多线程冲突了怎么办

对于共享资源，如果没有上锁，在多线程的环境里，那么就可能会发生翻车现场。

互斥

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区，它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是互斥的，也就说这段代码执行过程中，最多只能出现一个线程。

public class Main {
    private static int sharedCounter = 0;
    // Java实现的竞争资源的代码
    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new Thread(new IncrementTask());
        Thread thread2 = new Thread(new IncrementTask());

        thread1.start();
        // thread1.join();// 等待前面线程执行完毕
        System.out.println(sharedCounter);
        thread2.start();
        // thread2.join();
        System.out.println(sharedCounter);
    }

    static class IncrementTask implements Runnable {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++) {
                // 模拟竞争状态
                sharedCounter++;
            }
            System.out.println("Thread " + Thread.currentThread().getName() + " finished. Counter: " + sharedCounter);
        }
    }
}

互斥与同步的实现和使用

两种方法：

锁：加锁、解锁操作；
信号量：P、V 操作；

那什么是原子操作呢？原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态

忙等待锁(自旋锁)

意思就是一直跑while循环，直到前面那个线程传过来解锁消息，我才可以解锁，故而：忙着等待。

无等待锁

那当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

P/V 操作

P(减一) 操作是用在进入临界区之前，V(加一) 操作是用在离开临界区之后，这两个操作是必须成对出现的。

import java.util.concurrent.Semaphore;
// 5个线程给2个通路
public class SemaphoreExample {
    private static final int NUM_THREADS = 5;
    private static Semaphore semaphore = new Semaphore(2); // 允许同时访问的线程数量为2

    public static void main(String[] args) {
        for (int i = 0; i < NUM_THREADS; i++) {
            Thread thread = new Thread(new Worker(i));
            thread.start();
        }
    }
    static class Worker implements Runnable {
        private int id;
        public Worker(int id) {
            this.id = id;
        }
        @Override
        public void run() {
            try {
                System.out.println("Thread " + id + " is waiting to acquire permit.");
                semaphore.acquire(); // 获取许可
                System.out.println("Thread " + id + " has acquired permit.");
                // 执行临界区代码
                Thread.sleep(2000); // 模拟工作
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                System.out.println("Thread " + id + " is releasing permit.");
                semaphore.release(); // 释放许可
            }
        }
    }
}