Frank's blogs

永远好奇

0%

发表于 更新于
本文字数： 22k 阅读时长 ≈ 40 分钟

操作系统

操作系统是什么

  • 操作系统（Operating System，简称 OS）是计算机系统中的核心软件之一，它是一个管理计算机硬件和提供用户与应用程序之间接口的系统软件。
  • 进程管理：Linux 也支持多任务和多线程，并使用进程标识符（PID）来管理进程。
  • 内存管理：Linux 使用分页机制和交换空间来管理内存，允许多个程序在同一时间运行。
  • 文件系统管理：Linux 支持多种文件系统，包括Ext4、XFS、和Btrfs等，以管理文件和存储设备。
  • 设备管理：Linux 的设备管理通过文件系统提供，一切皆文件的理念使得硬件管理变得更加统一。
  • 用户管理：Linux 使用用户账户和权限管理，允许多用户在系统上进行安全访问和控制。

进程和线程有什么区别？

  • 进程（Process）是系统进行资源分配和调度的基本单位，线程（Thread）是CPU调度和分派的基本单位；
  • 线程依赖于进程而存在，一个进程至少有一个线程；
  • 进程有自己的独立地址空间，线程共享所属进程的地址空间；
  • 进程切换的开销远大于线程切换的开销； 在进程切换时，涉及到整个当前进程CPU环境的保存环境的设置以及新被调度运行的CPU环境的设置，而线程切换只需保存和设置少量的寄存器的内容.
  • 线程之间的通信更方便，同一进程下的线程共享全局变量等数据，而进程之间的通信需要以进程间通信(IPC)的方式进行；
  • 多进程更加健壮:多线程程序只要有一个线程崩溃，整个程序就崩溃了，但多进程程序中一个进程崩溃并不会对其它进程造成影响，因为进程有自己的独立地址空间
  • 进程的进程ID，进程的状态，分配的内存，打开的文件描述符，CPU使用时间等都记录在进程控制块PID中
同一进程中的线程可以共享哪些数据？
  • 进程代码段
  • 进程的公有数据（全局变量、静态变量…）
  • 进程打开的文件描述符
  • 进程的当前目录
  • 信号处理器/信号处理函数：对收到的信号的处理方式
  • 进程ID与进程组ID
线程独占哪些资源？
  • 线程ID
  • 一组寄存器的值
  • 通用寄存器（General-Purpose Registers）：这些寄存器用于存储计算过程中的临时数据、中间结果以及指针。它们在执行指令时被频繁使用，可以加速指令的执行。
  • 程序计数器（Program Counter）：程序计数器是一个特殊的寄存器，它存储了当前线程执行的指令的地址。当线程切换到另一个函数或线程时，程序计数器的值会被保存和恢复，以确保程序从正确的位置继续执行。
  • 栈指针寄存器（Stack Pointer Register）：栈指针寄存器存储了线程栈的顶部地址，用于管理栈上的数据的入栈和出栈操作。
  • 线程自身的栈（堆是共享的）
  • 栈帧（Stack Frame）：线程栈由多个栈帧组成，每个栈帧表示函数的调用或执行。当线程调用一个函数时，会创建一个新的栈帧，包含了函数的局部变量、参数、返回地址等信息。
  • 错误返回码：线程可能会产生不同的错误返回码，一个线程的错误返回码不应该被其它线程修改；
  • 信号掩码/信号屏蔽字(Signal mask)：表示是否屏蔽/阻塞相应的信号（SIGKILL,SIGSTOP除外）

进程间通信有哪些方式？

  1. 无名管道(Pipe)
  • 管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；
  • 一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据；
  • 只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程)
  1. 命名管道
  • 可以用于非亲缘关系进程通信
  1. 消息队列
    允许进程之间交换消息，可以不是父子进程，是按照消息报文交换的
    可以区分消息的优先级
  2. 信号(Signal)
  • 一个进程通过操作系统向另一个进程发送信号
  1. 共享内存
  • 效率高
  1. 套接字(Socket)
  • 可以TCP或者UDP

更详细的可以参考（待整理）：

生产者-消费者问题

  • 问题描述：使用n个缓冲区来存放数据，只有缓冲区没有满，生产者才可以写入数据；只有缓冲区不为空，消费者才可以读出数据
  • 一共需要三个信号量，一个代表此时的空余空闲位置的数量，初始值是n，另一个代表此时已经存在的产品的数量，初始为0，另外还有一个是mutex，初始是1
  • 生产者需要先P空闲位置，然后P操作mutex存放产品，生产完之后先V操作mutex释放锁，然后V已经存在的产品加1
  • 消费者则是先P已经存在的产品，然后P操作mutex获取锁，然后取走产品，然后V操作mutex释放锁，然后V操作空闲位置加一
  • 对mutex加锁的操作一定要在对空间和产品的操作之后，防止死锁

代码实现：

// 伪代码描述 
// 定义信号量 full记录缓冲区物品数量 empty代表缓冲区空位数量 mutex为互斥量
semaphore full = 0, empty = n, mutex = 1;

// 生产者进程
void producer(){
	do{
   	  P(empty);
	  P(mutex);

     // 生产者进行生产
   	
   	  V(mutex);
   	  V(full);
 	} while(1);
}

void consumer(){
	do{
	  P(full);
	  P(mutex);

    	// 消费者进行消费

	  V(mutex);
	  V(empty);
 	} while(1);
}

  • 注意信号量实际上具有排队的功能，条件满足的时候先唤醒先来的进程

吸烟者问题

  • 只有一张桌子，卷烟需要三种原料，每个卷烟者具有一种但是需要另外两种
  • 有一个供应者，随机往桌上放某二种原料的组合
  • 只有桌子有空的时候才能放置
  • 此时需要将三种原料中的任意两种看成一个整体的组合（一共三种），分别对组合和桌子设置条件变量控制

读者-写者问题

  • 同时可以有多个读者

  • 但是只能有一个写者

  • 写的时候不能读

  • 读的时候不能写

  • 需要设置一个读计数变量记录当前有几个读者在读，一个互斥锁用于保护计数变量，一个读写锁，一个写锁

  • 写者写之前分别P操作写锁和读写锁，写之后则分别V操作读写锁和写锁

  • 读者读之前先P操作写锁，然后P操作计数变量的mutex，如果自己当前是第一个读的人（也就是计数变量为0）那么P操作读写锁，然后无论是不是都将读者计数+1，释放保护计数变量的mutex，释放写锁，然后读文件，读完之后同样的获取保护计数变量的mutex，将其减一，如果此时自己是最后一个读者（计数变量等于0），则释放读写锁，然后释放mutex

  • 设置读者计数器的操作是防止读者之间互斥，实现多个同时读操作

  • 写锁单独存在的意义是保证每个读者对于读者计数变量的操作不被打断，防止改到一半切换到写者导致问题

    哲学家就餐问题

  • 问题描述：有五位哲学家围绕着餐桌坐，每一位哲学家要么思考，要么吃饭。为了吃饭，哲学家必须拿起两双筷子（分别放于左右两端）不幸的是，筷子的数量和哲学家相等，所以每只筷子必须由两位哲学家共享。

  • 解决方法：一次最多只允许四位哲学家同时进餐，也就是设置一个初始值为4的信号量进行控制

  • 或者要求奇数号的哲学家先拿左边的筷子，偶数号的先拿右边的之类的

  • 或者使用一个公用的mutex保护哲学家拿左边和右边的筷子的操作，防止被打断，避免循环等待

临界区的概念？

各个进程中对临界资源（互斥资源/共享变量，一次只能给一个进程使用）进行操作的程序片段

同步与互斥的概念？

  • 同步：多个进程因为合作而使得进程的执行有一定的先后顺序。比如某个进程需要另一个进程提供的消息，获得消息之前进入阻塞态；
  • 进程同步：多个进程因为合作而使得进程的执行有一定的先后顺序，进程同步就是要保证进程执行顺序正确，并且有序访问共享资源。
  • 互斥：多个进程在同一时刻只有一个进程能进入临界区

并发、并行、异步的区别？

并发：在一个时间段中同时有多个程序在运行，但其实任一时刻，只有一个程序在CPU上运行，宏观上的并发是通过不断的切换实现的；

多线程：并发运行的一段代码。是实现异步的手段

并行（和串行相比）：在多CPU系统中，多个程序无论宏观还是微观上都是同时执行的

异步（和同步相比）：同步是顺序执行，异步是在等待某个资源的时候继续做自己的事

Linux下的线程同步

  • 互斥锁(Mutex)

    • 互斥锁是最基本的线程同步机制之一。它确保同一时间只有一个线程可以访问共享资源或执行临界区代码,从而避免了竞争条件和数据不一致的问题。Linux下使用POSIX线程库中的pthread_mutex系列函数来操作互斥锁。

  • 条件变量(Condition Variable)

    • 条件变量提供了线程间通信和同步的机制。一个线程可以等待某个条件变为真,而另一个线程可以通知条件已经满足,从而唤醒等待线程。条件变量通常与互斥锁一起使用,Linux下使用pthread_cond系列函数操作条件变量。条件变量（pthread_cond）是通过等待（pthread_cond_wait）和通知（pthread_cond_signal或pthread_cond_broadcast）的方式实现线程间的协作

  • 信号量(Semaphore)

    • 信号量是一种计数器,用于控制对有限资源的访问。线程可以通过原子操作来获取或释放资源。信号量常用于限制可以同时访问某个资源的线程数量。Linux下使用POSIX信号量API(sem_系列函数)操作信号量。

  • 自旋锁(Spin Lock)

    • 自旋锁是一种在等待获取锁时,线程不会进入睡眠状态,而是持续循环检测锁的状态,直到获取到锁。自旋锁适用于锁定时间较短的情况,否则会浪费大量CPU资源。C11使用atomic_flag_test_and_set和atomic_flag_clear或者gcc提供的原子操作__sync_lock_test_and_set和__sync_lock_release

  • 读写锁(Read-Write Lock)

    • 读写锁允许多个线程同时获取读锁(共享访问),但同一时间最多只能有一个线程获取写锁(独占访问)。这种机制在读操作远多于写操作的情况下可以提高并发性能。Linux下使用pthread_rwlock系列函数操作读写锁。

  • 屏障(Barrier)

    • 屏障用于阻塞一组线程,直到所有线程都到达屏障时,才允许所有线程继续执行。它常用于并行计算中,确保所有线程完成当前阶段的工作后再进入下一阶段。Linux下使用pthread_barrier系列函数操作屏障。

  • 信号(Signal)

    • 信号是一种软件中断,可用于在线程之间传递异步事件。线程可以发送信号给另一个线程,或者捕获由其他线程发送的信号。大多数时候并不使用，而是使用锁和信号量、条件变量等

linux下mutex是如何实现的

  • 获取互斥锁 (pthread_mutex_lock)
    尝试锁定：线程首先在用户空间使用原子操作（如compare-and-swap，CAS）尝试锁定互斥锁。如果锁未被占用，获取成功，进入临界区。
    锁定失败：如果锁已被其他线程持有，线程会进入内核，通过 futex 系统调用将自己挂起，进入等待队列。
  • 释放互斥锁 (pthread_mutex_unlock)
    解锁：持锁线程使用原子操作将互斥锁状态从“锁定”改为“未锁定”。
    唤醒线程：如果有其他线程在等待，通过 futex 唤醒其中一个线程，使其可以尝试获取锁。
  • 快速路径：大多数锁操作在用户空间完成，只有竞争时才进入内核。
  • 等待和唤醒：锁被占用时，线程通过 futex 进入等待，锁释放时通过 futex 唤醒。

多线程同时使用同一个socket描述符可行吗

  • 在 Linux 下，对 TCP socket 的写操作是原子的，但这是有限制的。对于较小的数据（通常是小于或等于 64 KB 的数据），系统能够保证多个线程同时向同一个 TCP socket 写入时，数据不会交错。如果写入的数据量较大，数据可能会被分片，导致数据出现交错等问题
  • 读操作可能发生竞争：多个线程从同一个 TCP socket 读取数据时，文件描述符中的数据是共享的。

进程有哪几种状态？

  • 创建状态：进程正在被创建的状态，创建完之后进入就绪态
  • 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源
  • 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
  • 阻塞状态：进程等待某个事件的发生，在条件满足之前无法执行
  • 终止状态：进程请求操作系统结束自己，进入终止态，系统回收资源

进程调度的时机一般有什么

  • 时间片到期
  • 进程阻塞
  • 进程终止
  • 有更高优先级的进程就绪抢占

切换进程做了什么

  • 保存当前进程的上下文

    • 当操作系统决定暂停当前进程时，它需要保存这个进程的所有状态信息，以便在将来重新调度这个进程时能够恢复其执行状态。这些信息包括：

    • CPU寄存器：所有通用寄存器（如eax、ebx等）、程序计数器（PC）、栈指针（SP）、基址指针（BP）等。

    • 程序状态字 (PSW)：包括条件码和控制信息。

    • 内存管理信息：如页表基址寄存器等，涉及进程的地址空间。

    • 其他硬件状态：如浮点运算寄存器、控制寄存器等。

    • 这些信息通常存储在进程控制块（PCB）中。

  • 更新进程状态

    • 操作系统将当前进程的状态更新为“就绪”或“等待”，以反映其当前状况。

  • 选择下一个进程

    • 调度器根据调度算法选择下一个要运行的进程。选择过程涉及对进程队列的管理。

  • 恢复新进程的上下文

    • 操作系统需要恢复即将运行的进程的上下文，这包括：

    • CPU寄存器：从新进程的PCB中恢复寄存器值。

    • 程序计数器 (PC)：设置为新进程的下一条指令地址。

    • 栈指针 (SP) 和 基址指针 (BP)：指向新进程的栈。

    • 内存管理信息：加载新进程的页表或段表，配置地址转换硬件。

  • 切换内存地址空间

    • 操作系统需要更改内存管理单元（MMU）中的页表或段表基址寄存器，以便CPU能够正确访问新进程的地址空间。

  • 恢复硬件状态

    • 如果有专用的硬件状态（如浮点寄存器、SIMD寄存器），也需要恢复。

  • 转移控制权

    • 最后，操作系统将控制权交给新进程的下一条指令，使其继续执行。这通常通过恢复程序计数器（PC）和执行返回指令来完成。

  • 用户模式和内核模式切换

    • 在用户模式运行的进程通常通过系统调用或中断进入内核模式。上下文切换涉及在这两种模式之间切换，并确保正确的模式和权限设置。

进程调度策略有哪些？

  1. 批处理系统：
先来先服务 first-come first-serverd（FCFS）

按照请求的顺序进行调度。非抢占式，开销小，无饥饿问题，响应时间不确定（可能很慢）；

对短进程不利，对IO密集型进程不利。

最短作业优先 shortest job first（SJF）

按估计运行时间最短的顺序进行调度。非抢占式，吞吐量高，开销可能较大，可能导致饥饿问题；

对短进程提供好的响应时间，对长进程不利。

最短剩余时间优先 shortest remaining time next（SRTN）

按剩余运行时间的顺序进行调度。(最短作业优先的抢占式版本)。吞吐量高，开销可能较大，提供好的响应时间；

可能导致饥饿问题，对长进程不利。

最高响应比优先 Highest Response Ratio Next（HRRN） 响应比 = 1+ 等待时间除以处理时间。同时考虑了等待时间的长短和估计需要的执行时间长短，很好的平衡了长短进程。非抢占，吞吐量高，开销可能较大，提供好的响应时间，无饥饿问题。
  1. 交互式系统
    交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。
时间片轮转 Round Robin

将所有就绪进程按 FCFS 的原则排成一个队列，用完时间片的进程排到队列最后。抢占式（时间片用完时），开销小，无饥饿问题，为短进程提供好的响应时间；

若时间片小，进程切换频繁，吞吐量低；若时间片太长，实时性得不到保证。

优先级调度算法 为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。 多级反馈队列调度算法 Multilevel Feedback Queue

设置多个就绪队列1、2、3…，优先级递减，时间片递增。只有等到优先级更高的队列为空时才会调度当前队列中的进程。如果进程用完了当前队列的时间片还未执行完，则会被移到下一队列。

抢占式（时间片用完时），开销可能较大，对IO型进程有利，可能会出现饥饿问题。

什么叫优先级反转？如何解决？

高优先级的进程等待被一个低优先级进程占用的资源时，就会出现优先级反转，即优先级较低的进程比优先级较高的进程先执行。此处详细解释优先级反转带来的问题：如果有一个中等优先级的进程将低优先级的进程抢占，那么此时低优先级的进程无法正常进行并在后续释放被占用的资源，导致高优先级的任务一直被挂起，直到中等优先级的进程完成后，低优先级的进程才可以继续并在后续释放占用的资源，最后高优先级的进程才可以执行。导致的问题就是高优先级的进程在中等优先级的进程调度之后。

解决方法：

  • 优先级天花板(priority ceiling)：当任务申请某资源时，把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级，这个优先级称为该资源的优先级天花板。简单易行。
  • 优先级继承(priority inheritance)：当任务A申请共享资源S时，如果S正在被任务C使用，通过比较任务C与自身的优先级，如发现任务C的优先级小于自身的优先级，则将任务C的优先级提升到自身的优先级，任务C释放资源S后，再恢复任务C的原优先级。

什么是僵尸进程？

  • 一个子进程结束后，它的父进程并没有等待它（调用wait或者waitpid），那么这个子进程将成为一个僵尸进程。僵尸进程是一个已经死亡的进程，但是并没有真正被销毁。它已经放弃了几乎所有内存空间，也不能被调度，仅仅在进程表中保留一个位置，记载该进程的进程ID、终止状态以及资源利用信息(CPU时间，内存使用量等等)供父进程收集，除此之外，僵尸进程不再占有任何内存空间。这个僵尸进程可能会一直留在系统中直到系统重启
  • 父进程可以通过wait得到子进程的返回码，可以对其调用一些系统提供的宏得知子进程的死因

危害：占用进程号，而系统所能使用的进程号是有限的；占用内存。

以下情况不会产生僵尸进程：

  • 该进程的父进程先结束了。每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用Init进程接管，成为该进程的父进程，并且会调用wait等待其结束。
  • 父进程调用wait或者waitpid等待子进程结束（需要每隔一段时间查询子进程是否结束）。wait系统调用会使父进程暂停执行，直到它的一个子进程结束为止。waitpid则可以加入WNOHANG(wait-no-hang)选项，如果没有发现结束的子进程，就会立即返回，不会将调用waitpid的进程阻塞。同时，waitpid还可以选择是等待任一子进程（同wait），还是等待指定pid的子进程，还是等待同一进程组下的任一子进程，还是等待组ID等于pid的任一子进程；
  • 子进程结束时，系统会产生SIGCHLD(signal-child)信号，可以注册一个信号处理函数，在该函数中调用waitpid，等待所有结束的子进程（注意：一般都需要循环调用waitpid，因为在信号处理函数开始执行之前，可能已经有多个子进程结束了，而信号处理函数只执行一次，所以要循环调用将所有结束的子进程回收)；
  • 也可以用signal(SIGCLD, SIG_IGN)(signal-ignore)通知内核，表示忽略SIGCHLD信号，那么子进程结束后，内核会进行回收。
什么是孤儿进程？

一个父进程已经结束了，但是它的子进程还在运行，那么这些子进程将成为孤儿进程。孤儿进程会被Init（进程ID为1）接管，当这些孤儿进程结束时由Init完成状态收集工作。

线程同步有哪些方式？

为什么需要线程同步：线程有时候会和其他线程共享一些资源，比如内存、数据库等。当多个线程同时读写同一份共享资源的时候，可能会发生冲突。因此需要线程的同步，多个线程按顺序访问资源。

  • 互斥量 Mutex：互斥量是内核对象，只有拥有互斥对象的线程才有访问互斥资源的权限。因为互斥对象只有一个，所以可以保证互斥资源不会被多个线程同时访问；当前拥有互斥对象的线程处理完任务后必须将互斥对象交出，以便其他线程访问该资源；
  • 信号量 Semaphore：信号量是内核对象，它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。信号量对象保存了最大资源计数和当前可用资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就减1，只要当前可用资源计数大于0，就可以发出信号量信号，如果为0，则将线程放入一个队列中等待。线程处理完共享资源后，应在离开的同时通过ReleaseSemaphore函数将当前可用资源数加1。如果信号量的取值只能为0或1，那么信号量就成为了互斥量；
  • 事件 Event：允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。事件分为手动重置事件和自动重置事件。手动重置事件被设置为激发状态后，会唤醒所有等待的线程，而且一直保持为激发状态，直到程序重新把它设置为未激发状态。自动重置事件被设置为激发状态后，会唤醒一个等待中的线程，然后自动恢复为未激发状态。
  • 临界区 Critical Section：拥有临界区对象的线程可以访问该临界资源,任意时刻只允许一个线程对临界资源进行访问。，其它试图访问该资源的线程将被挂起，直到临界区对象被释放。

线程安全是什么，怎么实现

  • 线程安全（Thread Safety）是指在多线程环境中，多个线程访问和操作同一资源（如数据结构、文件、变量等）时，不会引发竞争条件（race condition）、数据不一致或程序崩溃等问题
  • 怎么实现
    • 各种锁
    • 原子操作
    • 线程本地存储

互斥量和临界区有什么区别？

互斥量是可以命名的，可以用于不同进程之间的同步；而临界区只能用于同一进程中线程的同步。创建互斥量需要的资源更多，因此临界区的优势是速度快，节省资源。

什么是协程？

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

协程与线程进行比较？

  1. 一个线程可以拥有多个协程，一个进程也可以单独拥有多个协程

  2. 线程进程都是同步机制，而协程则是异步

  3. 协程能保留上一次调用时的状态，每次过程重入时，就相当于进入上一次调用的状态

    C++20引入的协程

  • C++20引入了协程（coroutines），这是一种强大的语言特性，可以简化异步编程和生成器模式
  • 协程的关键组件
    • co_await：暂停协程执行，等待一个值或者任务完成。
    • co_yield：生成一个值并暂停协程执行，稍后可以恢复执行。
    • co_return：结束协程并返回一个值。

进程的异常控制流：陷入、中断、异常和信号

中断是系统从用户态到内核态的唯一方式

陷入(trap)是有意造成的“异常”，是执行一条指令的结果。陷入是同步的。陷入的主要作用是实现系统调用。比如，进程可以执行 syscall n 指令向内核请求服务。当进程执行这条指令后，会中断当前的控制流，陷入到内核态，执行相应的系统调用。内核的处理程序在执行结束后，会将结果返回给进程，同时退回到用户态。进程此时继续执行下一条指令。

故障是由错误条件引起的，可能可以修复（比如缺页），修复之后会将CPU使用权交还给用户进程继续执行

外中断由处理器外部的硬件产生，CPU在每条指令执行的末尾会自动查询是否有待处理的外中断，外中断不是执行某条指令的结果，也无法预测发生时机。由于中断独立于当前执行的程序，因此中断是异步事件。中断包括 I/O 设备发出的 I/O 中断、各种定时器引起的时钟中断、调试程序中设置的断点等引起的调试中断等。

异常是一种错误情况，是执行当前指令的结果，可能被错误处理程序修正，也可能直接终止应用程序。异常是同步的。这里特指因为执行当前指令而产生的错误情况，比如除法异常无法恢复、缺页异常就可能可以恢复等。有些书上为了区分，也将这类“异常”称为“故障”。

信号是一种更高层的软件形式的异常，同样会中断进程的控制流，可以由进程进行处理。一个信号代表了一个消息。信号的作用是用来通知进程发生了某种系统事件。

更详细的可以参考

用户空间程序和内核空间程序通信的方式

  • 系统调用，使用系统调用传递特定的支持的信息
  • 信号，内核在特定情况下可以向用户程序发送信号
  • 读写/proc目录，可以读取和修改内核部分信息和设置
  • 读写指定的文件实现通信
  • 使用netlink类似于socket，可以与内核互传大量数据
  • 使用ioctl，在数据量较少的时候实现通信

处理中断的流程

  • 中断发生

    • 当CPU正在执行程序时,如果发生了中断事件(如硬件中断、软件中断等),会触发中断信号,CPU暂停当前程序的执行。

  • 中断向量表查询

    • CPU根据中断类型查询中断向量表(Interrupt Vector Table),获取相应中断处理程序的入口地址。

  • 保护现场

    • CPU将当前程序的执行现场(如程序计数器、寄存器等)主要是寄存器，压入内核堆栈,以便中断处理完成后能恢复执行。

  • 关中断

    • 保证整个中断处理程序不被打断，在中断服务结束之后才再次开中断

  • 也存在多重中断

    • 只在保护现场和恢复现场的时候关闭中断防止被打断，其他步骤均开启中断允许打断

  • 切换到内核态

    • CPU切换到内核态(特权模式),准备执行中断处理程序。

  • 执行中断处理程序

    • CPU跳转到中断处理程序的入口地址,开始执行中断处理程序。中断处理程序会根据中断类型进行相应的处理,如读取数据、发送数据等。

  • 中断处理完成

    • 中断处理程序完成相应的工作后,会执行”中断返回”指令。

  • 恢复现场

    • CPU从内核堆栈中恢复被中断程序的执行现场。

  • 切换到用户态

    • 如果被中断的是用户程序,CPU切换回到用户态(非特权模式)。

  • 继续执行

    • CPU继续执行被中断的程序,就像中断从未发生过一样。

  • 以上是中断处理函数的上半部分，一般执行中断处理中比较快，用时较短的部分

  • 如果中断处理函数中有一些执行时间较长但是本身对实时性不是很敏感的任务，可以在中断处理函数以外的部分执行，以保证中断处理函数快进快出。可以在上半部中将数据拷贝到内存，在下半部分处理。不希望被打断、对时间敏感和硬件相关的一般都在中断处理函数中执行

什么是IO多路复用？怎么实现？

IO多路复用（IO Multiplexing）是指单个进程/线程就可以同时处理多个IO请求。

实现原理：用户将想要监视的文件描述符（File Descriptor）添加到select/poll/epoll函数中，由内核监视，函数阻塞。一旦有文件描述符就绪（读就绪或写就绪），或者超时（设置timeout），函数就会返回，然后该进程可以进行相应的读/写操作。

select/poll/epoll三者的区别？
  • select：将文件描述符放入一个集合中，调用select时，将这个集合从用户空间拷贝到内核空间（缺点1：每次都要复制，开销大），由内核根据就绪状态修改该集合的内容。（缺点2）集合大小有限制，32位机默认是1024（64位：2048）；采用水平触发机制。select函数返回后，需要通过遍历这个集合，找到就绪的文件描述符（缺点3：轮询的方式效率较低），当文件描述符的数量增加时，效率会线性下降；
  • poll：和select几乎没有区别，区别在于文件描述符的存储方式不同，poll采用链表的方式存储，没有最大存储数量的限制；
  • epoll：通过内核和用户空间共享内存，避免了不断复制的问题；支持的同时连接数上限很高（1G左右的内存支持10W左右的连接数）；文件描述符就绪时，采用回调机制，避免了轮询（回调函数将就绪的描述符添加到一个链表中，执行epoll_wait时，返回这个链表）；支持水平触发和边缘触发，采用边缘触发机制时，只有活跃的描述符才会触发回调函数。

总结，区别主要在于：

  • 一个线程/进程所能打开的最大连接数
  • 文件描述符传递方式（是否复制）
  • 水平触发 or 边缘触发
  • 查询就绪的描述符时的效率（是否轮询）
什么时候使用select/poll，什么时候使用epoll？

当连接数较多并且有很多的不活跃连接时，epoll的效率比其它两者高很多；但是当连接数较少并且都十分活跃的情况下，由于epoll需要很多回调，因此性能可能低于其它两者。

什么是文件描述符？

文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。

内核通过文件描述符来访问文件。文件描述符指向一个文件。

什么是水平触发？什么是边缘触发？
  • 水平触发（LT，Level Trigger）模式下，只要一个文件描述符就绪，就会触发通知，如果用户程序没有一次性把数据读写完，下次还会通知；
  • 边缘触发（ET，Edge Trigger）模式下，当描述符从未就绪变为就绪时通知一次，之后不会再通知，直到再次从未就绪变为就绪（缓冲区从不可读/写变为可读/写）。
  • 区别：边缘触发效率更高，减少了被重复触发的次数，函数不会返回大量用户程序可能不需要的文件描述符。
  • 为什么边缘触发一定要用非阻塞（non-block）IO：避免由于一个描述符的阻塞读/阻塞写操作让处理其它描述符的任务出现饥饿状态。
有哪些常见的IO模型？
  • 同步阻塞IO（Blocking IO）：用户线程发起IO读/写操作之后，线程阻塞，直到可以开始处理数据；对CPU资源的利用率不够；
  • 同步非阻塞IO（Non-blocking IO）：发起IO请求之后可以立即返回，如果没有就绪的数据，需要不断地发起IO请求直到数据就绪；不断重复请求消耗了大量的CPU资源；
  • IO多路复用
  • 异步IO（Asynchronous IO）：用户线程发出IO请求之后，继续执行，由内核进行数据的读取并放在用户指定的缓冲区内，在IO完成之后通知用户线程直接使用。

什么是用户态和内核态？

  • 为了限制不同程序的访问能力，防止一些程序访问其它程序的内存数据，CPU划分了用户态和内核态两个权限等级。

  • 任何共享资源都需要通过系统调用进行处理，比如外接设备，文件，内存，进程等

  • 用户态只能受限地访问内存，且不允许访问外围设备，没有占用CPU的能力，CPU资源可以被其它程序获取；

  • 内核态可以访问内存所有数据以及外围设备，也可以进行程序的切换。

  • 所有用户程序都运行在用户态，但有时需要进行一些内核态的操作，比如从硬盘或者键盘读数据，这时就需要进行系统调用（程序向操作系统请求服务的方式），使用陷入指令，CPU切换到内核态，执行相应的服务，再切换为用户态并返回系统调用的结果。

  • 注意CPU在用户态和内核态之间转换也是有一定时间成本的

为什么要分用户态和内核态？

（我自己的见解：）

  • 安全性：防止用户程序恶意或者不小心破坏系统/内存/硬件资源；
  • 封装性：用户程序不需要实现更加底层的代码；
  • 利于调度：如果多个用户程序都在等待键盘输入，这时就需要进行调度；统一交给操作系统调度更加方便。
如何从用户态切换到内核态？
  • 系统调用：本质上还是通过中断实现
  • 用户程序发生异常时：比如缺页异常
  • 外围设备的中断：外围设备完成用户请求的操作之后，会向CPU发出中断信号，这时CPU会转去处理对应的中断处理程序

什么是死锁？

在两个或者多个并发进程中，每个进程持有某种资源而又等待其它进程释放它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁(deadlock)。

死锁产生的必要条件？

  • 互斥：一个资源一次只能被一个进程使用；
  • 占有并等待：一个进程至少占有一个资源，并在等待另一个被其它进程占用的资源；
  • 非抢占：已经分配给一个进程的资源不能被强制性抢占，只能由进程完成任务之后自愿释放；
  • 循环等待：若干进程之间形成一种头尾相接的环形等待资源关系，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁有哪些处理方法？

鸵鸟策略 直接忽略死锁。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。 死锁预防

基本思想是破坏形成死锁的四个必要条件：

  • 破坏互斥条件：允许某些资源同时被多个进程访问。但是有些资源本身并不具有这种属性，因此这种方案实用性有限；
  • 破坏占有并等待条件：
    • 实行资源预先分配策略（当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行）；
    • 或者进程申请资源前先释放占有的资源
    • 缺点：很多时候无法预知一个进程所需的全部资源；同时，会降低资源利用率，降低系统的并发性；
  • 破坏非抢占条件：允许进程强行抢占被其它进程占有的资源。会降低系统性能；
  • 破坏循环等待条件：对所有资源统一编号，所有进程对资源的请求必须按照序号递增的顺序提出，即只有占有了编号较小的资源才能申请编号较大的资源。反向是不允许得
死锁避免

动态地检测资源分配状态，以确保系统处于安全状态，只有处于安全状态时才会进行资源的分配。所谓安全状态是指：即使所有进程突然请求需要的所有资源，也能存在某种对进程的资源分配顺序，使得每一个进程运行完毕。

银行家算法 的关键思想是在分配资源之前进行安全性检查， 系统在运行时必须知道每种类型资源的总数量以及每个进程的最大资源需求。

  1. 当一个进程请求资源时，系统会检查是否有足够的资源可供分配。如果有足够的资源，则分配给进程，并且系统更新资源的可用数量。
  2. 如果没有足够的资源可供分配，系统会将请求的进程置于等待状态，直到有足够的资源可用。
  3. 当进程完成任务并释放其占用的资源时，系统会将这些资源返回到资源池，并通知等待的进程。
死锁解除

如何检测死锁：检测有向图是否存在环；

死锁解除的方法：

  • 利用抢占：挂起某些进程，并抢占它的资源。但应防止某些进程被长时间挂起而处于饥饿状态；
  • 利用回滚：让某些进程回退到足以解除死锁的地步，进程回退时自愿释放资源。要求系统保持进程的历史信息，设置还原点；
  • 利用杀死进程：强制杀死某些进程直到死锁解除为止，可以按照优先级进行。

程序装入方式（装入确定的是物理地址）

  • 绝对装入：编译器直接负责地址转换
  • 可重定位装入（静态重定位）：装入的时候将逻辑地址转换为物理地址
  • 动态运行时装入（动态重定位）：运行时才进行地址转换，需要设置重定位寄存器，执行到命令的时候由硬件进行转换

程序链接方式（链接确定的是逻辑地址）

  • 动态链接库是位置无关代码，可以被存储在内存的任何位置而不影响执行
  • 使用动态链接库，可以让用户在不更新整个程序文件的同时更新其用到的库函数
  • 静态链接
    • 在程序运行之前，将程序运行所需的各个模块连接成一个完整的可执行文件
  • 装入时动态链接
    • 也就是各个模块装入内存的时候边装入边链接
  • 运行时动态链接
    • 在用到某个模块的时候才将某个模块调入内存，调入内存的时候实现链接操作，能够提升堆内存的利用率
    • 而且多个程序引用同一个动态库的时候，可以不在内存中拷贝形成副本

内部碎片和外部碎片

  • 内部碎片，分配给某进程的内存区域中，有些部分没有用上
  • 外部碎片，指内存中的某些空闲分区由于太小而难以利用

存储管理方式

内存管理方式分为连续分配管理和非连续分配管理。连续分配管理分为单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配四种；非连续分配管理又叫离散分配方式，如果离散分配的基本单位是页Page，则称为分页存储管理方式；如果离散分配的基本单位是段Segment，则称为分段存储管理方式。

连续分配管理方式允许一个用户程序分配一个连续的内存空间。

  • 单一连续分配：多用于单用户单任务的操作系统中，是一种简单的存储管理方式。单一连续分配中，会将存储空间分配为系统区和用户区。系统区存放系统进程，用户区存放用户进程，这样的管理可以避免用户进程影响到系统进程。这种分配方式中，比如0-a的地址空间存放系统区，那么a+1-n的地址空间都存放用户区。
  • 固定分区分配：是一种最简单的可运行多道程序的存储管理方式。固定分区分配首先要划分分区，之后进行内存分配。
    • 内存分区分为分区大小相等和分区大小不等两种。分区大小相等的情况下，如果进程大小不相等容易造成内存浪费或者内存不够进程无法运行的问题，所以通常用于进程内存大小相等的情况中。分区大小不相等，就是根据常用的大小（较多的小分区，适量的中分区，少量的大分区）进行分区，这样就可以更好地利用内存空间，但是这样的方式需要维护一个分区使用表。
    • 内存分配要维护一张分区使用表，通常按照进程大小进行排序。每次在进行内存分配的时候，要查看哪些分区能够容纳该进程。

  • 动态分区分配：根据进程的需要，动态地分配内存空间。这样的分配方式涉及到分区中的数据结构、分区分配算法以及分区的分配和回收操作三个问题。

    • 分区分配中的数据结构主要分为空闲分区表和空闲分区链两种。空闲分区表维护空闲分区的序号、空闲分区的起始地址以及空闲分区的大小数据。空闲分区链相当于一个双向链表，维护空闲分区；为了方便检索在分区尾部设置一个分区的状态位以及分区大小。
    • 分区分配算法主要有五种方法。首次适应算法（First Fit），利用空闲分区链实现，将空闲分区按照地址递增（注意与后面的最佳适应区分，这里按照的是地址递增）进行排序，然后根据进程的大小从链首查找空闲分区链，第一个能够适应的就分配。循环首次适应算法（Next Fit），不是每次都从链首开始查找，而是从上一次找到的空闲分区的下一个空闲分区开始查找，直到查找到一个能够使用的分区，之后动态地分配内存（会导致后续大空闲分区变少）。最佳适应算法（Best Fit），将空闲分区链按照大小进行排序，找到第一个适应的空闲分区即可（最大限度利用空闲分区）。最坏适应算法（Worst Fit），与最佳适应相反，排序之后每次挑选最大的分区使用，对中小作业有利，不易产生碎片。快速适应算法（Quick Fit），根据大小将空闲分区进行分类，维护多个空闲分区链；这样的好处是可以加快检索，相比一条链能够更快地检索目标进程。
    • 分区分配和回收：主要操作是内存的分配和内存的回收。内存分配中，若空闲分区内存大小-用户进程内存大小<=预设不可切分内存大小，则进行一次内存的分配；否则将剩余的内存空间放到空闲内存链中，继续下次的使用。内存回收，主要看是否和空闲分区相邻，如果相邻就直接合并；否则就建立新的表项，维护回收区的内存起始地址和大小。

  • 动态重定位分区分配：在连续分配方式中，必须把系统进程或者用户进程装入一个连续的内存空间中。这个时候可能会因为程序的大小与分区的大小不一致的问题产生内存碎片。这个时候我们要想插入新的进程，即使碎片空间总和支持进程，也无法再分配空间，所以我们要把内存空间进行一个整理。

  • 在程序装入内存的时候根据程序的大小动态分配内存，程序运行过程中可以动态修改程序在物理内存中的位置

  • 整理内存地址，是将程序的内存地址整理成在物理上相邻的状态。程序使用的地址在分区装载之后仍然是相对地址，要想将相对地址转换为相邻物理地址，必然会影响到程序的执行。为了不影响程序的执行，需要在硬件上提供对程序的内存地址转换支持，于是引入重定位寄存器，用它来存放程序在内存中的起始地址。

非连续分配管理方式允许将一个程序分散地装入不相邻的内存分区。根据内存分区的大小分为分页式存储管理方式和分段式存储管理方式。

  • 页存储：页存储首先需要将一个进程的逻辑内存空间划分为多个内存大小相等的页，然后将物理内存空间划分为相等的大小个数的物理块Block（页框Frame）。分配的时候将多个页面放入多个不相邻的物理块中。这样的划分之后，通常进程的最后一页存不满，会产生内存碎片——”页内碎片“。

    • 页面大小：页面大小的选定需要适当。如果过小，虽然可以减少页内碎片的产生，但是需要更大的页表，而且页面切换更频繁；如果太大就会产生较大的内存碎片。所以大小的选择应该适中，通常为2的整数次幂，范围为512B至8KB。

    • 页表：页表主要保存进程占用的页数，同时存储逻辑内存空间页到物理内存块的映射。

  • 地址转换：页表要存储地址映射，那么首先得有一个地址变换机构。基本地址变换机构，主要用来建立逻辑地址到物理内存空间地址的映射。传统系统中，主要使用寄存器来存放页表（寄存器速度快，有利于变换地址），那么每一个页表都需要寄存器来存放，成本过高。进程数量过多的情况下，首先将页表的起始地址和页表长度存放在PCB中，之后在进程运行的时候再将数据读取到PTR（Page-Table Register，页表寄存器）。读取数据的时候，地址转换机构会将相对地址转换为页号以及页内地址两部分，之后根据页号检索页表。检索之前会将页号和页表长度进行比较，如果页号大于或等于页表长度，则说明出现了访问越界，会出现越界中断。

  • 具有块表的地址转换机构：页表存放在内存中，那么将要先查页表，计算得出物理地址之后访问物理地址，是两次检索过程。

  • 为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速 缓冲寄存器，用来存放最近放问过的页表项的副本，又称为“联想寄存器”(Associative Memory)，或称为“快表”。

    对于32位操作系统，使用两级页表结构式合适的；但是对于64位操作系统，建议采用多级页表。

  • 段存储：使用段存储而不再使用页存储，第一个原因是提高内存的利用率，第二个原因是满足开发者在编程中的多种需求。主要是满足编程中的几个新的需求：方便编程（简化逻辑地址访问方式）、信息共享（段式信息的逻辑单位）、信息保护（对信息的逻辑单位实现保护）、动态增长（分段更加满足动态增长的需求）、动态链接（链接装载使用段更符合需求）。

    • 分段：作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。
    • 段表：为每个分段分配一个连续的分区，进程每个段可以离散地存放到不同分区中，所以也需要维护一张段表，使得进程能够查到逻辑地址对应的物理地址，这个表就是段映射表，简称段表。
    • 地址变换机构：为了实现逻辑地址到物理地址的映射，系统设置了一个段表寄存器，用于存放段表地址和段表长度，如果段号大于段表长度，则表示发生了越界访问，产生越界中断；若未越界，找出该段对应段表项的位置，读出内存中的起始地址；再检查段内地址是否超过段长，如果超过段长，发出越界中断；否则将基址与段内地址相加，得出内存的物理地址。
    • 分段和分页的主要区别：①页是信息的物理单位，段是信息的逻辑单位；②页的大小由系统决定，段的大小不固定；③分页作业地址空间是一维的，分段作业地址空间则是二维的。即页的地址空间可以用一个符号来标识，而段的地址空间不仅要知道段名还要知道段内地址。

  • 段页存储：分页存储能提高内存利用率，分段存储能满足用户的更多需求。为了各取所长，产生了段页存储的管理方式。

    • 基本原理：段页存储，就是既分段也分页，先分段再分页。地址结构由段号、段内页号、页内地址三部分组成。
    • 地址变换过程：首先也需要准备一个段表寄存器，存放段表起始地址和段表长。首先将段号和段表长相比较是否越界；再利用段表起始地址和段表号来找到段表项在段表中的位置，从而得到页表地址；再之后使用段内页号来获取页表项的位置，找出物理块号，用物理块号和页内地址来构成物理地址。

分页和分段有什么区别？

  • 页式存储：用户空间划分为大小相等的部分称为页（page），内存空间划分为同样大小的区域称为页框，分配时以页为单位，按进程需要的页数分配，逻辑上相邻的页物理上不一定相邻；
  • 段式存储：用户进程地址空间按照自身逻辑关系划分为若干个段（segment）（如代码段，数据段，堆栈段），内存空间被动态划分为长度不同的区域，分配时以段为单位，每段在内存中占据连续空间，各段可以不相邻；
  • 段页式存储：用户进程先按段划分，段内再按页划分，内存划分和分配按页。
  • 分段对用户是可见的，但是分页对用户是不可见的，是系统自动分配的
    • 段页式管理的地址结构是二维的，既要给出段号又要给出段内偏移量
    • 用段表找页表，页表找页框

区别：

  • 目的不同：分页的目的是管理内存，用于虚拟内存以获得更大的地址空间；分段的目的是满足用户的需要，使程序和数据可以被划分为逻辑上独立的地址空间；
  • 大小不同：段的大小不固定，由其所完成的功能决定；页的大小固定，由系统决定；
  • 地址空间维度不同：分段是二维地址空间（段号+段内偏移），分页是一维地址空间（每个进程一个页表/多级页表，通过一个逻辑地址就能找到对应的物理地址）；
  • 分段便于信息的保护和共享；分页的共享收到限制；
  • 碎片：分段没有内碎片，但会产生外碎片；分页没有外碎片，但会产生少量的内碎片（一个页填不满）

单级页表和多级页表

  • 假如只有单级的页表的话，必须使用一个连续的空间存储所有的页表项，但是很难分配
  • 进程大部分时候都只需要访问部分页表，没必要整个页表常驻内存
  • 可以将一定数量的页表项分为一组，每个组之间独立离散的存放在内存中，此时再建立一个上级页表用于寻找这些页表
  • 利用地址的最高几位部分在顶层页表中找到自己属于哪个二级页表，再利用地址的中间几位在二级页表中找到自己属于哪个页框，然后利用地址的最低几位找到自己在页框中的偏移量

什么是虚拟内存？

每个程序都拥有自己的地址空间，这个地址空间被分成大小相等的页，这些页被映射到物理内存；但不需要所有的页都在物理内存中，当程序引用到不在物理内存中的页时，由操作系统将缺失的部分装入物理内存。这样，对于程序来说，逻辑上似乎有很大的内存空间，只是实际上有一部分是存储在磁盘上，因此叫做虚拟内存。

虚拟内存的优点是让程序可以获得更多的可用内存。

虚拟内存的实现方式、页表/多级页表、缺页中断、不同的页面淘汰算法：答案。

  • 特点：
    • 多次性，无需一次将作业装入内存
    • 对换性，作业可以在不运行的时候换出内存，运行的时候再换入
    • 虚拟性，用户看得到的内存容量远大于实际上的物理内存容量

      缺页中断

  • 某个页面被访问但是这个页面尚且没有被调入内存，此时需要触发一个缺页中断使得系统将对应的页面调入内存供访问
  • 是一种故障，可以被修复的
  • 是一种内中断

CPU高速缓存

  • 在一个多核CPU中，每个核心都有自己的一级（L1，几十几百kb）和二级（L2几MB）缓存，这些缓存只能被相应的核心访问。这种设计可以使每个核心快速访问其私有缓存中的数据，而不需要与其他核心争用资源。然而，这也意味着如果一个核心需要访问另一个核心的数据，它必须通过更慢的通道（比如主内存或者其他某种形式的互连）来获取。

  • 此外，多核CPU通常还有一个三级（L3几十MB）缓存，这是一个共享缓存，所有的核心都可以访问。这使得一个核心可以相对快速地访问另一个核心的数据，但是这也意味着核心之间可能会发生资源争用。

    如何实现缓存一致性

  • MESI（修改、独占、共享、无效）：这是最常见的缓存一致性协议之一。每个缓存行可以处于四种状态之一：修改（Modified）、独占（Exclusive）、共享（Shared）或无效（Invalid）。当一个处理器需要写入数据时，它必须首先获取该数据的独占访问权限，这意味着所有其他处理器的相应缓存行都必须变为无效状态。

伪共享

  • 伪共享（False Sharing）是多线程编程中的一个问题，它发生在多个线程并发地访问同一缓存行（Cache Line）中的不同数据时。尽管这些线程访问的数据在逻辑上是独立的，但由于它们位于同一缓存行中，CPU会将它们视为“共享”的，这可能导致性能显著下降
  • 一个线程访问缓存行之前，需要先获取缓存行的所有权，并发访问会导致并行性能下降
  • 每次缓存行的所有权改变时，CPU都必须将缓存行的内容写回到主内存，并从主内存中加载新的内容
  • 避免伪共享，可以尽量确保并发访问的数据位于不同的缓存行中。例如，可以通过添加填充（Padding）来调整数据的布局

如何进行地址空间到物理内存的映射？

内存管理单元（MMU）管理着逻辑地址和物理地址的转换，其中的页表（Page table）存储着页（逻辑地址）和页框（物理内存空间）的映射表，页表中还包含包含有效位（是在内存还是磁盘）、访问位（是否被访问过）、修改位（内存中是否被修改过）、保护位（只读还是可读写）。逻辑地址：页号+页内地址（偏移）；每个进程一个页表，放在内存，页表起始地址在PCB/寄存器中。

有哪些页面置换算法？

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘中来腾出空间。页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

  • 最佳页面置换算法OPT（Optimal replacement algorithm）：置换以后不需要或者最远的将来才需要的页面，是一种理论上的算法，是最优策略但是不可能实现
  • 先进先出FIFO：置换在内存中驻留时间最长的页面。缺点：有可能将那些经常被访问的页面也被换出，从而使缺页率升高；
  • 时钟算法 Clock：将所有存在在内存中的页面组织为一个循环链表，给访问过的页面置为1，需要替换的时候进行遍历，将遇到的非0页面置零，零页面则替换为新的页面，如果都是1，则再循环一次，此时必然可以找到可替换的页面
    • 改进版，操作系统应该尽可能的考虑到没有被修改过的页面换出，因为这个页面换出不需要写回外存，先找没有被修改过的页面，再找被修改过的
  • 最近未使用算法NRU（Not Recently Used）：检查访问位R、修改位M，优先置换R=M=0，其次是（R=0, M=1）；
  • 最近最少使用算法LRU（Least Recently Used）：置换出未使用时间最长的一页；实现方式：维护时间戳，或者维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
  • 最不经常使用算法LFU（Least Frequently Used）：置换出访问次数最少的页面
局部性原理
  • 时间上：最近被访问的页在不久的将来还会被访问；
  • 空间上：内存中被访问的页周围的页也很可能被访问。
什么是颠簸现象

颠簸本质上是指频繁的页调度行为。进程发生缺页中断时必须置换某一页。然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。因此会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸。内存颠簸的解决策略包括：

  • 修改页面置换算法；
  • 降低同时运行的程序的数量；
  • 终止该进程或增加物理内存容量。

缓冲区溢出问题

  • 什么是缓冲区溢出
  • C 语言使用运行时栈来存储过程信息。每个函数的信息存储在一个栈帧中，包括寄存器、局部变量、参数、返回地址等。C 对于数组引用不进行任何边界检查，因此对越界的数组元素的写操作会破坏存储在栈中的状态信息，这种现象称为缓冲区溢出。缓冲区溢出会破坏程序运行，也可以被用来进行攻击计算机，如使用一个指向攻击代码的指针覆盖返回地址。

缓冲区溢出的防范方式

防范缓冲区溢出攻击的机制有三种：随机化、栈保护和限制可执行代码区域。

  • 随机化：包括栈随机化（程序开始时在栈上分配一段随机大小的空间）和地址空间布局随机化（Address-Space Layout Randomization，ASLR，即每次运行时程序的不同部分，包括代码段、数据段、栈、堆等都会被加载到内存空间的不同区域），但只能增加攻击一个系统的难度，不能完全保证安全。
  • 栈保护：在每个函数的栈帧的局部变量和栈状态之间存储一个随机产生的特殊的值，称为金丝雀值（canary）。在恢复寄存器状态和函数返回之前，程序检测这个金丝雀值是否被改变了，如果是，那么程序异常终止。
  • 限制可执行代码区域：内存页的访问形式有三种：可读、可写、可执行，只有编译器产生的那部分代码所处的内存才是可执行的，其他页限制为只允许读和写。

更详细的可以参考

磁盘调度

过程：磁头（找到对应的盘面）；磁道（一个盘面上的同心圆环，寻道时间）；扇区（旋转时间）。为减小寻道时间的调度算法：

  • 先来先服务
  • 最短寻道时间优先
  • 电梯算法：电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

字节对齐

  • 从偏移为0的位置开始存储
  • 如果没有定义#pragma pack(n)
    • sizeof的最终结果必然是结构内部最大成员的整数倍，不够补齐
    • 结构内部各个成员的首地址必然是自身大小的整数倍
  • 如果定义了#pragma pack(n)
    • sizeof的最终结果必然必然是min[n,结构内部最大成员]的整数倍，不够补齐
    • 结构内部各个成员的首地址必然是min[n,自身大小]的整数倍

软连接和硬链接的区别

  • 类似于文件本身和快捷方式的区别
  • 软连接是个独立的文件
  • 硬链接和它的文件指向相同的inode，所有硬链接被删除之后才会真的删除文件
  • 软链接是否删除与文件无关

零拷贝

  • “零拷贝”（Zero Copy）是一种优化技术，用于在数据传输和处理过程中减少或消除数据的拷贝操作，以提高性能和降低资源消耗。零拷贝的核心思想是尽量减少不必要的数据拷贝，而不是在数据传输的过程中将数据从一个缓冲区复制到另一个缓冲区。

  • 内存管理：在操作系统和运行时库中，零拷贝可以用于减少内存分配和释放操作。例如，内存池可以通过重用先前分配的内存块来避免频繁的内存分配和释放。

  • 文件传输：在文件传输中，零拷贝可以通过直接将文件从磁盘映射到内存中

  • 管道和套接字通信：在进程间通信中，零拷贝可以通过使用共享内存（Shared Memory）或使用 sendfile/sendfilev 等系统调用来避免将数据从一个进程的地址空间复制到另一个进程的地址空间。

Volatile

  • 它用于告诉编译器不要对某个变量进行优化，以确保每次访问该变量都从内存中读取，而不是使用缓存中的值。
  • 常见于硬件寄存器访问和多线程编程

malloc函数

  • 底层是如何实现的，会不会分配内存空间 以及如何分配内存空间
    后者是内存管理方式
    1. 内存池初始化：当程序启动时，操作系统会分配一块内存池(memory pool),用于后续的内存分配请求。这个内存池通常包含物理内存的一部分。
    1. 分配内存：当调用malloc函数时，会先在自身的堆空间中找一个没有被分配的足够大小的内存块，如果没找到，会调用sbrk函数将堆向上生长，扩大堆的区域。这个内存块的大小通常要大于请求的大小，因为malloc可能会分配4字节内存用于管理（例如，存储分配的内存块的大小等信息，通过这个内存块的大小计算出下个内存块的起始位置），这个存储内存块信息的部分一般在申请到的内存块的头部之前紧邻的位置存放，类似地，申请到的一个内存块在尾部也会有一个存放相关信息的区域（4字节），类似于双向链表，方便查找。
    1. 返回指针：一旦操作系统成功分配了内存块，malloc会返回一个指向该内存块起始地址的指针。这个指针可以用于访问和操作这块内存。
    1. 释放内存：当程序调用free函数来释放先前分配的内存块时，内存块将被标记为未分配，以便将来的`malloc“调用可以再次使用这块内存。注意，释放内存并不会立即返还给操作系统，而是由C/C+运行时库来管理。

待完成

  • IPC
  • 进程同步问题：生产者-消费者问题…
  • 银行家算法
  • 文件与文件系统、文件管理？

参考

发表于 更新于
本文字数： 12k 阅读时长 ≈ 22 分钟

计算机网络

什么是三次握手 (three-way handshake)？

  • 第一次握手：Client将SYN置1，随机产生一个初始序列号seq发送给Server，进入SYN_SENT状态；
  • 第二次握手：Server收到Client的SYN=1之后，知道客户端请求建立连接，将自己的SYN置1，ACK置1，产生一个acknowledge number=sequence number+1，并随机产生一个自己的初始序列号，发送给客户端；进入SYN_RCVD状态；
  • 第三次握手：客户端检查acknowledge number是否为序列号+1，ACK是否为1，检查正确之后将自己的ACK置为1，产生一个acknowledge number=服务器发的序列号+1，发送给服务器；进入ESTABLISHED状态；服务器检查ACK为1和acknowledge number为序列号+1之后，也进入ESTABLISHED状态；完成三次握手，连接建立。
  • 注意，ACK字段在正常传输过程中一般都是1，只要包含对对方发送的数据的确认序号的，ACK都是1，包括连接建立除了第一次握手之外的部分
TCP建立连接可以两次握手吗？为什么?

不可以。有两个原因：

首先，可能会出现已失效的连接请求报文段又传到了服务器端。

client 发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达 server。本来这是一个早已失效的报文段。但 server 收到此失效的连接请求报文段后，就误认为是 client 再次发出的一个新的连接请求。于是就向 client 发出确认报文段，同意建立连接。假设不采用 “三次握手”，那么只要 server 发出确认，新的连接就建立了。由于现在 client 并没有发出建立连接的请求，因此不会理睬 server 的确认，也不会向 server 发送数据。但 server 却以为新的运输连接已经建立，并一直等待 client 发来数据。这样，server 的很多资源就白白浪费掉了。采用 “三次握手” 的办法可以防止上述现象发生。例如刚才那种情况，client 不会向 server 的确认发出确认。server 由于收不到确认，就知道 client 并没有要求建立连接。

其次，两次握手无法保证Client正确接收第二次握手的报文（Server无法确认Client是否收到），也无法保证Client和Server之间成功互换初始序列号。

还有就是两次握手会给SYN flood攻击提供机会。
扩展阅读： 什么是SYN攻击？参考

可以采用四次握手吗？为什么？

可以。但是会降低传输的效率。

四次握手是指：第二次握手：Server只发送ACK和acknowledge number；而Server的SYN和初始序列号在第三次握手时发送；原来协议中的第三次握手变为第四次握手。出于优化目的，四次握手中的二、三可以合并。

第三次握手中，如果客户端的ACK未送达服务器，会怎样？

Server端：
由于Server没有收到ACK确认，因此会重发之前的SYN+ACK（默认重发五次，之后自动关闭连接进入CLOSED状态），Client收到后会重新传ACK给Server。

Client端，两种情况：

  1. 在Server进行超时重发的过程中，如果Client向服务器发送数据，数据头部的ACK是为1的，所以服务器收到数据之后会读取 ACK number，进入 establish 状态
  2. 在Server进入CLOSED状态之后，如果Client向服务器发送数据，服务器会以RST包应答。
如果已经建立了连接，但客户端出现了故障怎么办？

服务器每收到一次客户端的请求后都会重新复位一个计时器，时间通常是设置为2小时，若两小时还没有收到客户端的任何数据，服务器就会发送一个探测报文段，以后每隔75秒钟发送一次。若一连发送10个探测报文仍然没反应，服务器就认为客户端出了故障，接着就关闭连接。

初始序列号是什么？

TCP连接的一方A，随机选择一个32位的序列号（Sequence Number）作为发送数据的初始序列号（Initial Sequence Number，ISN），比如为1000，以该序列号为原点，对要传送的数据进行编号：1001、1002…三次握手时，把这个初始序列号传送给另一方B，以便在传输数据时，B可以确认什么样的数据编号是合法的；同时在进行数据传输时，A还可以确认B收到的每一个字节，如果A收到了B的确认编号（acknowledge number）是2001，就说明编号为1001-2000的数据已经被B成功接受。

什么是四次挥手？

  • 第一次挥手：Client将FIN置为1，发送一个序列号seq给Server；进入FIN_WAIT_1状态；
  • 第二次挥手：Server收到FIN之后，发送一个ACK=1，acknowledge number=收到的序列号+1；进入CLOSE_WAIT状态。此时客户端已经没有要发送的数据了，但仍可以接受服务器发来的数据。
  • 第三次挥手：Server将FIN置1，发送一个序列号给Client；进入LAST_ACK状态；
  • 第四次挥手：Client收到服务器的FIN后，进入TIME_WAIT状态；接着将ACK置1，发送一个acknowledge number=序列号+1给服务器；服务器收到后，确认acknowledge number后，变为CLOSED状态，不再向客户端发送数据。客户端等待2*MSL（报文段最长寿命）时间后，也进入CLOSED状态。完成四次挥手。
为什么不能把服务器发送的ACK和FIN合并起来，变成三次挥手（CLOSE_WAIT状态意义是什么）？

因为服务器收到客户端断开连接的请求时，可能还有一些数据没有发完，这时先回复ACK，表示接收到了断开连接的请求。等到数据发完之后再发FIN，断开服务器到客户端的数据传送。

如果第二次挥手时服务器的ACK没有送达客户端，会怎样？

客户端没有收到ACK确认，会重新发送FIN请求。

客户端TIME_WAIT状态的意义是什么？

第四次挥手时，客户端发送给服务器的ACK有可能丢失，TIME_WAIT状态就是用来重发可能丢失的ACK报文。如果Server没有收到ACK，就会重发FIN，如果Client在2*MSL的时间内收到了FIN，就会重新发送ACK并再次等待2MSL，防止Server没有收到ACK而不断重发FIN。

MSL(Maximum Segment Lifetime)，指一个片段在网络中最大的存活时间，2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL，Client都没有再次收到FIN，那么Client推断ACK已经被成功接收，则结束TCP连接。

TCP如何实现流量控制？

使用滑动窗口协议实现流量控制。防止发送方发送速率太快，接收方缓存区不够导致溢出。接收方会维护一个接收窗口 receiver window（窗口大小单位是字节），接受窗口的大小是根据自己的资源情况动态调整的，在返回ACK时将接受窗口大小放在TCP报文中的窗口字段告知发送方。发送窗口的大小不能超过接受窗口的大小，只有当发送方发送并收到确认之后，才能将发送窗口右移。

发送窗口的上限为接受窗口和拥塞窗口中的较小值。接受窗口表明了接收方的接收能力，拥塞窗口表明了网络的传送能力。

什么是零窗口（接收窗口为0时会怎样）？

如果接收方没有能力接收数据，就会将接收窗口设置为0，这时发送方必须暂停发送数据，但是会启动一个持续计时器(persistence timer)，到期后发送一个大小为1字节的探测数据包，以查看接收窗口状态。如果接收方能够接收数据，就会在返回的报文中更新接收窗口大小，恢复数据传送。

TCP的拥塞控制是怎么实现的？

拥塞控制主要由四个算法组成：慢启动（Slow Start）、拥塞避免（Congestion voidance）、快重传 （Fast Retransmit）、快恢复（Fast Recovery）

  1. 慢启动：刚开始发送数据时，先把拥塞窗口（congestion window）设置为一个最大报文段MSS的数值，每收到一个ACK之后，就把拥塞窗口加1个MSS。这样每经过一个传输轮次（或者说是每经过一个往返时间RTT），拥塞窗口的大小就会加倍

  1. 拥塞避免：当拥塞窗口的大小达到慢开始门限(slow start threshold)时，开始执行拥塞避免算法，拥塞窗口大小不再指数增加，而是线性增加，即每收到一个ACK只增加1MSS.

    无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。（这是不使用快重传的情况）

  2. 快重传：快重传要求接收方在收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时捎带确认。快重传算法规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计时器时间到期。

  1. 快恢复：当发送方连续收到三个重复确认时，就把慢开始门限减半，然后执行拥塞避免算法。不执行慢开始算法的原因：因为如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方认为现在网络可能没有出现拥塞。
    也有的快重传是把开始时的拥塞窗口cwnd值再增大一点，即等于 ssthresh + 3*MSS 。这样做的理由是：既然发送方收到三个重复的确认，就表明有三个分组已经离开了网络。这三个分组不再消耗网络的资源而是停留在接收方的缓存中。可见现在网络中减少了三个分组。因此可以适当把拥塞窗口扩大些。

TCP如何最大利用带宽？

TCP速率受到三个因素影响

  • 窗口：即滑动窗口大小，见TCP如何实现流量控制？
  • 带宽：这里带宽是指单位时间内从发送端到接收端所能通过的“最高数据率”，是一种硬件限制。TCP发送端和接收端的数据传输数不可能超过两点间的带宽限制。发送端和接收端之间带宽取所通过线路的带宽最小值（如通过互联网连接）。
  • RTT：即Round Trip Time，表示从发送端到接收端的一去一回需要的时间，TCP在数据传输过程中会对RTT进行采样（即对发送的数据包及其ACK的时间差进行测量，并根据测量值更新RTT值），TCP根据得到的RTT值更新RTO值，即Retransmission TimeOut，就是重传间隔，发送端对每个发出的数据包进行计时，如果在RTO时间内没有收到所发出的数据包的对应ACK，则任务数据包丢失，将重传数据。一般RTO值都比采样得到的RTT值要大。
带宽时延乘积 带宽时延乘积=带宽*RTT，实际上等于发送端到接收端单向通道的数据容积的两倍，这里单向通道的数据容积可以这样来理解，单向通道看成是一条单行道马路，带宽就是马路的车道数，路上跑的汽车就是数据（不过这里所有汽车的速率都是一样的，且不会有人想超车，大家齐头并进），那么单向通道的数据容积就是这条单行道上摆满车，一共可以摆多少辆。带宽就是马路的车道数，带宽数乘以单向通道的数据容积就是路面上所能容纳的全部数据量。当路面上已经摆满的时候，就不能再往里面放了。

设滑动窗口大小为W ， 发送端和接收端的带宽为B

  • 前面已经说过了，TCP发送数据时受滑动窗口的限制，当TCP将滑动窗口中的数据都发出后，在收到第一个ACK之前，滑动窗口大小是0，不能再发送数据了，必须等待ACK包使滑动窗口移动。那么在理想情况下，ACK包应该在什么时候到达呢？显然，就是在数据发出后的RTT时间后，ACK包到达。这也就是说，现在在不考虑丢包和拥塞情况下，TCP在一个RTT时间内能发出的最大数据量为 W也就是一个滑动窗口的大小，所以不考虑带宽限制下，TCP一个时刻能达到的最大速度V是窗口大小除以RTT

现在再考虑带宽限制，前面说过当马路上摆满车的时候，就无法再往里放车了，同理，TCP发送端在RTT除以2
时间内，能往通道上放的最大数据量为V乘RTT除以2，通过带宽时延乘积得到的容积限制为带宽B乘RTT除以2。当V乘RTT除以2小于带宽乘RTT除以2时，单向通道容积不构成瓶颈，速率的限制主要来源于窗口大小限制。而当V乘RTT除以2大于带宽乘RTT除以2时，则就受到容积限制，即此时速率限制来源于带宽限制。

  • 因此，TCP的最大速率为滑动窗口的大小除以RTT的值和网络带宽中的最小值
  • 在我们平时生活中使用的宽带网络，ADSL等环境下，因为带宽都比较小，从而带宽与RTT的乘积也比较小，再加上网络情况比较复杂，拥塞情况比较常见，所以这些网络环境下，TCP速率的主要限制因素在于带宽，丢包率等。长肥管道一般不太常见，多见于一些单位使用的专线网络，在这些网络中速率的主要限制因素就是窗口大小了，这也是传统TCP在这些网络环境中不能充分利用带宽的原因所在（因为传统TCP的窗口大小是用2字节表示的，所以最大只有65535（不考虑窗口扩大选项）），除了专线网络外，随着网络硬件技术的发展，万兆交换机的出现，局域网中也可能会出现带宽时延乘积较大的情况。

TCP与UDP的区别

  1. TCP是面向连接的，UDP是无连接的；
什么叫无连接？

UDP发送数据之前不需要建立连接

  1. TCP是可靠的，UDP不可靠；
什么叫不可靠？ UDP接收方收到报文后，不需要给出任何确认
  1. TCP只支持点对点通信，UDP支持一对一、一对多、多对一、多对多；
  2. TCP是面向字节流的，UDP是面向报文的；
什么意思？

面向字节流是指发送数据时以字节为单位，一个数据包可以拆分成若干组进行发送，而UDP一个报文只能一次发完。

  1. TCP有拥塞控制机制，UDP没有。网络出现的拥塞不会使源主机的发送速率降低，这对某些实时应用是很重要的，比如媒体通信，游戏；
  2. TCP首部开销（20字节）比UDP首部开销（8字节）要大
  3. UDP 的主机不需要维持复杂的连接状态表
什么时候选择TCP，什么时候选UDP？

对某些实时性要求比较高的情况，选择UDP，比如游戏，媒体通信，实时视频流（直播），即使出现传输错误也可以容忍；其它大部分情况下，HTTP都是用TCP，因为要求传输的内容可靠，不出现丢失

HTTP可以使用UDP吗？

HTTP不可以使用UDP，HTTP需要基于可靠的传输协议，而UDP不可靠
注：http 3.0 使用udp实现

面向连接和无连接的区别

无连接的网络服务（数据报服务） – 面向连接的网络服务（虚电路服务）

虚电路服务：首先建立连接，所有的数据包经过相同的路径，服务质量有较好的保证；

数据报服务：每个数据包含目的地址，数据路由相互独立（路径可能变化）；网络尽最大努力交付数据，但不保证不丢失、不保证先后顺序、不保证在时限内交付；网络发生拥塞时，可能会将一些分组丢弃；

TCP如何保证传输的可靠性

  1. 数据包校验
  2. 对失序数据包重新排序（TCP报文具有序列号）
  3. 丢弃重复数据
  4. 应答机制：接收方收到数据之后，会发送一个确认（通常延迟几分之一秒）；
  5. 超时重发：发送方发出数据之后，启动一个定时器，超时未收到接收方的确认，则重新发送这个数据；
  6. 流量控制：确保接收端能够接收发送方的数据而不会缓冲区溢出

HTTP和HTTPS有什么区别？

  1. 端口不同：HTTP使用的是80端口，HTTPS使用443端口；
  2. HTTP（超文本传输协议）信息是明文传输，HTTPS运行在SSL(Secure Socket Layer)之上，添加了加密和认证机制，更加安全；
  3. HTTPS由于加密解密会带来更大的CPU和内存开销；
  4. HTTPS通信需要证书，一般需要向证书颁发机构（CA）购买
Https的连接过程？
  1. 客户端向服务器发送请求，同时发送客户端支持的一套加密规则（包括对称加密、非对称加密、摘要算法）；
  2. 服务器从中选出一组加密算法与HASH算法，并将自己的身份信息以证书的形式发回给浏览器。证书里面包含了网站地址，加密公钥（用于非对称加密），以及证书的颁发机构等信息（证书中的私钥只能用于服务器端进行解密）；
  3. 客户端验证服务器的合法性，包括：证书是否过期，CA 是否可靠，发行者证书的公钥能否正确解开服务器证书的“发行者的数字签名”，服务器证书上的域名是否和服务器的实际域名相匹配；
  4. 如果证书受信任，或者用户接收了不受信任的证书，浏览器会生成一个随机密钥（用于对称算法），并用服务器提供的公钥加密（采用非对称算法对密钥加密）；使用Hash算法对握手消息进行摘要计算，并对摘要使用之前产生的密钥加密（对称算法）；将加密后的随机密钥和摘要一起发送给服务器；
  5. 服务器使用自己的私钥解密，得到对称加密的密钥，用这个密钥解密出Hash摘要值，并验证握手消息是否一致；如果一致，服务器使用对称加密的密钥加密握手消息发给浏览器；
  6. 浏览器解密并验证摘要，若一致，则握手结束。之后的数据传送都使用对称加密的密钥进行加密

总结：非对称加密算法用于在握手过程中加密生成的密码；对称加密算法用于对真正传输的数据进行加密；HASH算法用于验证数据的完整性。

输入 www.baidu.com，怎么变成 https://www.baidu.com 的，怎么确定用HTTP还是HTTPS？

你访问的网站是如何自动切换到 HTTPS 的？
一种是原始的302跳转，服务器把所有的HTTp流量跳转到HTTPS。但这样有一个漏洞，就是中间人可能在第一次访问站点的时候就劫持。
解决方法是引入HSTS机制，用户浏览器在访问站点的时候强制使用HTTPS。

HTTPS连接的时候，怎么确定收到的包是服务器发来的（中间人攻击）？

1.验证域名、有效期等信息是否正确。证书上都有包含这些信息，比较容易完成验证；
2.判断证书来源是否合法。每份签发证书都可以根据验证链查找到对应的根证书，操作系统、浏览器会在本地存储权威机构的根证书，利用本地根证书可以对对应机构签发证书完成来源验证；
3.判断证书是否被篡改。需要与 CA 服务器进行校验；
4.判断证书是否已吊销。通过CRL（Certificate Revocation List 证书注销列表）和 OCSP（Online Certificate Status Protocol 在线证书状态协议）实现，其中 OCSP 可用于第3步中以减少与 CA 服务器的交互，提高验证效率

什么是对称加密、非对称加密？区别是什么？
  • 对称加密：加密和解密采用相同的密钥。如：DES、RC2、RC4
  • 非对称加密：需要两个密钥：公钥和私钥。如果用公钥加密，需要用私钥才能解密。如：RSA
  • 区别：对称加密速度更快，通常用于大量数据的加密；非对称加密安全性更高（不需要传送私钥）
数字签名、报文摘要的原理
  • 发送者A用私钥进行签名，接收者B用公钥验证签名。因为除A外没有人有私钥，所以B相信签名是来自A。A不可抵赖，B也不能伪造报文。
  • 摘要算法:MD5、SHA

GET与POST的区别？

  1. GET是幂等的，即读取同一个资源，总是得到相同的数据，POST不是幂等的；
  2. GET一般用于从服务器获取资源，而POST有可能改变服务器上的资源；
  3. 请求形式上：GET请求的数据附在URL之后，在HTTP请求头中；POST请求的数据在请求体中；
  4. 安全性：GET请求可被缓存、收藏、保留到历史记录，且其请求数据明文出现在URL中。POST的参数不会被保存，安全性相对较高；
  5. GET只允许ASCII字符，POST对数据类型没有要求，也允许二进制数据；
  6. GET的长度有限制（操作系统或者浏览器），而POST数据大小无限制

Session与Cookie的区别？

Session是服务器端保持状态的方案，Cookie是客户端保持状态的方案

Cookie保存在客户端本地，客户端请求服务器时会将Cookie一起提交；Session保存在服务端，通过检索Sessionid查看状态。保存Sessionid的方式可以采用Cookie，如果禁用了Cookie，可以使用URL重写机制（把会话ID保存在URL中）。

从输入网址到获得页面的过程 (越详细越好)？

  1. 浏览器查询 DNS，获取域名对应的IP地址:具体过程包括浏览器搜索自身的DNS缓存、搜索操作系统的DNS缓存、读取本地的Host文件和向本地DNS服务器进行查询等。对于向本地DNS服务器进行查询，如果要查询的域名包含在本地配置区域资源中，则返回解析结果给客户机，完成域名解析(此解析具有权威性)；如果要查询的域名不由本地DNS服务器区域解析，但该服务器已缓存了此网址映射关系，则调用这个IP地址映射，完成域名解析（此解析不具有权威性）。如果本地域名服务器并未缓存该网址映射关系，那么将根据其设置发起递归查询或者迭代查询；
  2. 浏览器获得域名对应的IP地址以后，浏览器向服务器请求建立链接，发起三次握手；
  3. TCP/IP链接建立起来后，浏览器向服务器发送HTTP请求；
  4. 服务器接收到这个请求，并根据路径参数映射到特定的请求处理器进行处理，并将处理结果及相应的视图返回给浏览器；
  5. 浏览器解析并渲染视图，若遇到对js文件、css文件及图片等静态资源的引用，则重复上述步骤并向服务器请求这些资源；
  6. 浏览器根据其请求到的资源、数据渲染页面，最终向用户呈现一个完整的页面。

HTTP请求有哪些常见状态码？

  1. 2xx状态码：操作成功。200 OK
  2. 3xx状态码：重定向。301 永久重定向；302暂时重定向
  3. 4xx状态码：客户端错误。400 Bad Request；401 Unauthorized；403 Forbidden；404 Not Found；
  4. 5xx状态码：服务端错误。500服务器内部错误；501服务不可用

什么是RIP (Routing Information Protocol, 距离矢量路由协议)? 算法是什么？

每个路由器维护一张表，记录该路由器到其它网络的”跳数“，路由器到与其直接连接的网络的跳数是1，每多经过一个路由器跳数就加1；更新该表时和相邻路由器交换路由信息；路由器允许一个路径最多包含15个路由器，如果跳数为16，则不可达。交付数据报时优先选取距离最短的路径。

（PS：RIP是应用层协议：参考）

优缺点
  • 实现简单，开销小
  • 随着网络规模扩大开销也会增大；
  • 最大距离为15，限制了网络的规模；
  • 当网络出现故障时，要经过较长的时间才能将此信息传递到所有路由器

计算机网络体系结构

  • 物理层，链路层，网络层，传输层，应用层

  • 七层模型：物理层，链路层，网络层，传输层，会话层，表示层，应用层

  • 应用层：常见协议：

    • FTP(21端口)：文件传输协议
    • SSH(22端口)：远程登陆
    • SMTP(25端口)：发送邮件
    • POP3(110端口)：接收邮件
    • HTTP(80端口)：超文本传输协议
    • DNS(53端口)：运行在UDP上，域名解析服务
    • RIP 运行在UDP上

  • 传输层：TCP/UDP

  • 网络层：IP、ARP、NAT、RIP…

路由器、交换机位于哪一层？
  • 路由器网络层，根据IP地址进行寻址；
  • 交换机数据链路层，根据MAC地址进行寻址

IP地址的分类？

路由器仅根据网络号net-id来转发分组，当分组到达目的网络的路由器之后，再按照主机号host-id将分组交付给主机；同一网络上的所有主机的网络号相同。

什么叫划分子网？

从主机号host-id借用若干个比特作为子网号subnet-id；子网掩码：网络号a和子网号都为1，主机号为0；数据报仍然先按照网络号找到目的网络，发送到路由器，路由器再按照网络号和子网号找到目的子网：将子网掩码与目标地址逐比特与操作，若结果为某个子网的网络地址，则送到该子网。

什么是ARP协议 (Address Resolution Protocol)？

  • arp是链路层协议

ARP协议完成了IP地址与物理地址的映射。每一个主机都设有一个 ARP 高速缓存，里面有所在的局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。当源主机要发送数据包到目的主机时，会先检查自己的ARP高速缓存中有没有目的主机的MAC地址，如果有，就直接将数据包发到这个MAC地址，如果没有，就向所在的局域网发起一个ARP请求的广播包（在发送自己的 ARP 请求时，同时会带上自己的 IP 地址到硬件地址的映射），收到请求的主机检查自己的IP地址和目的主机的IP地址是否一致，如果一致，则先保存源主机的映射到自己的ARP缓存，然后给源主机发送一个ARP响应数据包。源主机收到响应数据包之后，先添加目的主机的IP地址与MAC地址的映射，再进行数据传送。如果源主机一直没有收到响应，表示ARP查询失败。

如果所要找的主机和源主机不在同一个局域网上，那么就要通过 ARP 找到一个位于本局域网上的某个路由器的硬件地址，然后把分组发送给这个路由器，让这个路由器把分组转发给下一个网络。剩下的工作就由下一个网络来做。

什么是NAT (Network Address Translation, 网络地址转换)？

用于解决内网中的主机要和因特网上的主机通信。由NAT路由器将主机的本地IP地址转换为全球IP地址，分为静态转换（转换得到的全球IP地址固定不变）和动态NAT转换。

ipv4和ipv6的区别

  • v4使用32位地址，地址总数为约43亿
  • v6使用128位地址，地址总数为约340兆亿
  • ipv4地址手动配置：需要管理员手动分配IP地址或DHCP
  • ipv6地址自动配置（SLAAC，状态无连接自动配置）：设备可以自行生成IPv6地址。
  • 或者DHCPv6：自动分配IPv6地址。
  • 头部结构
  • IPv4：
    • 头部较复杂，包含13个字段，总长度为20-60字节。
    • 需要校验和字段来校验头部。
  • IPv6：
    • 头部简化，固定长度为40字节，包含8个字段。
    • 不需要校验和字段，简化了路由处理。
  • 内置安全
  • IPv4：
    • 安全性不强，IPSec（Internet Protocol Security）是可选的。
  • IPv6：
    • 内置IPSec支持，提供更强的安全性。
  • 广播和多播
  • IPv4：
    • 支持广播（发送到子网中的所有节点）。
  • IPv6：
    • 不支持广播，使用多播和单播替代。
    • 支持任播（发送到最近的一个节点）。

如何判断一个IP地址是否有效

  • 检查格式
    • IPv4地址必须由四个十进制数（0-255）组成，每个数之间用点（.）分隔。
  • 检查数值范围
    • 每个数值必须在0到255之间。
  • 排除无效地址
    • 全零地址：0.0.0.0 通常表示默认路由。
    • 回环地址：127.0.0.0 到 127.255.255.255，用于环回测试。
    • 全一地址：255.255.255.255，用于广播。
    • 保留地址：特定于私有网络、实验和其他用途的保留地址。
  • 检查私有地址
    • A类私有地址：10.0.0.0 到 10.255.255.255
    • B类私有地址：172.16.0.0 到 172.31.255.255
    • C类私有地址：192.168.0.0 到 192.168.255.255

      HTTP各版本

  • HTTP 0.9版本

    • HTTP协议的第一个版本，功能简单，已弃用
    • 仅支持纯文本数据的传输，虽然支持HTML，但是不支持图片插入
    • 仅支持GET请求方式，且不支持请求头
    • 无状态，短连接。没有对用户状态的管理；每次请求建立一个TCP连接，响应之后关闭TCP连接。

  • HTTP 1.0版本

    • 支持POST、GET、HEAD三种方法
    • 支持长连接keep-alive（但默认还是使用短连接：浏览器每一次请求建立一次TCP连接，请求处理完毕之后断开）。
    • 服务器不跟踪用户的行为也不记录用户过往请求。

  • HTTP 1.1版本

    • 新增PUT、DELETE、CONNECT、TRACE、OPTIONS方法，是现今使用最多的版本。
    • 支持长连接，在一次TCP连接中可以发送多个请求或响应，且默认使用长连接。
    • 支持宽带优化、断点续传。请求的对象部分数据，可以不必发送整个对象；文件上传下载支持续传。
    • 因为长连接产生的问题：队头阻塞。长连接中，发送请求和响应都是串行化的，前面的消息会造成后面的消息也阻塞。解决方法是创建多个TCP连接，这样就可以基本保证了可用性，浏览器默认的最大TCP连接数是6个。

  • HTTP 2.0版本

    • 二进制分帧，所有帧都是用二进制编码，节省了空间
    • 多路复用：HTTP 2.0中所有的连接都是持久化的。相比1.1版本可以不用维护更多的TCP连接，在处理并发请求的时候，可以将多个数据流中互不依赖的帧可以乱序发送，同时还支持优先级。接收方接收之后可以根据帧头部信息将帧组合起来。（解决了1.1版本中的队头阻塞问题）
    • 头部压缩：1.1版本每次传输都需要传输一份首部，2.0让双方各自缓存一份首部字段表，达到更快传输的目标。

  • HTTP 3.0版本

    • 基于UDP的QUIC多路复用：处理并发请求的时候, 且如果各个数据包互不依赖，那么就不会造成使用TCP带来的队头阻塞问题。
    • 这个问题源头上是因为TCP连接，TCP连接的性质决定了重传会影响队后的数据发送，所以干脆选用UDP来解决这个方案。
    • 0RRT建链：RRT表示Round-Trip Time，3.0可以实现0RRT建链。一般来说HTTPS协议要建立完整链接包括TCP握手和TLS握手，总计需要至少2-3个RTT，普通的HTTP协议也需要至少1个RTT才可以完成握手。基于UDP的QUIC协议可以在第一次发送包的时候直接发送业务数据。但是由于首次连接需要发送公钥数据，所以首次连接并不使用这一方法。

    参考文档：[图解 | 为什么HTTP3.0要弃用TCP协议，而改用UDP协议？_涛哥聊Python-CSDN博客](

参考

发表于 更新于
本文字数： 849 阅读时长 ≈ 2 分钟

matplotlib

  • 基本框架
    import numpy as np
    from matplotlib import pyplot as plt

    plt.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
    plt.rcParams['axes.unicode_minus'] = False  # 解决保存图像时符号-显示为方块的2问题
    plt.plot(xs, yx, label="x随迭代次数的变化")
    plt.plot(xs, yy, label="y随迭代次数的变化")
    plt.legend()
    plt.xlabel("迭代次数")
    plt.ylabel("x以及f(x)的数值")
    plt.title(r"$x_0$ = 1")
    plt.show()
  • 使用latex语法：r"$<latex语法>$"

    pycharm配置项目的python解释器

  • 设置下面找到项目然后更改解释器
    • picture 1
  • 注意单独更改此处没有用
    • picture 2
  • python得到当前路径
    • os.getcwd().replace('\\','/')此处将/替换为了\\，实际上是单斜线

      数组切片

  • 参考链接
  • 注意数组[begin:end]切到的是begin到end-1的内容

    重启程序

    # 获取当前解释器路径
    p = sys.executable
    # 启动新程序(解释器路径, 当前程序)
    os.execl(p, p, *sys.argv)
    # 关闭当前程序
    sys.exit()

    pycharm内存不足

  • 教程
  • picture 3

import numpy的时候出错

  • 有时候在一些非x86的设备上使用numpy会报错 Illegal instruction (core dumped)
  • picture 3
  • 此时需要设置环境变量~/.bashrc追加一句export OPENBLAS_CORETYPE=ARMV8然后source ~/.bashrc
  • 此时不再报错
    • picture 4

发表于
本文字数： 889 阅读时长 ≈ 2 分钟

Unity学习笔记

先安装hub再安装Unity！！！

环境变量配置（建议用VS一步到位，VSCode配置环境太麻烦）

  • 右键文件管理器->属性->picture 5
  • 然后环境变量，添加picture 6 看这俩有没有，然后试一下命令行输入dotnet --info

教程

  • 入门教程

  • 官方文档

    笔记

  • 用将对象拖拽到这个位置picture 4
    的方式给public对象赋值，包括GameObject和RigidBody，这两个得分开赋值

  • RigidBody的AddForce不能开启picture 2

  • 刚体的教程

  • is Kinematic的教程

    • isKinematic不会对碰撞和力做出反应，不受物理系统影响，但依然会对其他刚体产生物理影响（比如可以阻挡其他刚体）。
    • isKinematic只能在脚本中修改物体的Transform属性来移动。
    • 用在经常需要移动等变化物理状态的碰撞体上。一个刚体碰撞体，可以随时开启或关闭Is Kinematic选项，不会像静态碰撞体的enabled开启或关闭那样引起物理系统的问题。

  • 给一个物理系统的刚体添加一个瞬时的速度的方法

    • wbRd.AddForce(new Vector3(x, y, z) * 1.0f, ForceMode.Impulse);
    • 或者ForceMode设置为VelocityChange，可以直接改变速度，类似于碰撞的效果

  • 获取时间用Time类，unity有支持

  • 复位一个场景用SceneManager.LoadScene(index);，index是这个scene在最终的序列里拍第几个，从0开始

  • 一个Vector3.normalized给出同方向的一个单位向量

  • transform.LookAt(transform)是让当前对象的z轴指向目标对象（z轴是相机的拍照方向）

  • 不规则物体生成碰撞体：picture 3

  • 数学计算用Mathf对象下面的操作函数，其中的三角函数是角度制（0-360°）的

  • 鼠标位置用Input.mousePosition得到一个Vector2

  • 键盘用Input.GetKeyDown(KeyCode.按键名)或者其他，可以查手册，KeyCode包含的内容也查手册

  • Transform.translate()函数可以指定运动的坐标系是自身的还是世界的

发表于 更新于
本文字数： 686 阅读时长 ≈ 1 分钟

线性回归

  • 梯度下降法

  • 正规方程法(最小二乘法)

    逻辑回归

  • 逻辑回归

    交叉熵

  • 在逻辑回归中，最常用的是代价函数是交叉熵(Cross Entropy)，交叉熵是一个常见的代价函数，在神经网络中也会用到。下面是《神经网络与深度学习》一书对交叉熵的解释：

  • 交叉熵是对「出乎意料」（译者注：原文使用suprise）的度量。神经元的目标是去计算函数x→y=y(x)。但是我们让它取而代之计算函数x→a=a(x)。假设我们把a当作y等于1的概率，1−a是y等于0的概率。那么，交叉熵衡量的是我们在知道y的真实值时的平均「出乎意料」程度。当输出是我们期望的值，我们的「出乎意料」程度比较低；当输出不是我们期望的，我们的「出乎意料」程度就比较高。

  • 在1948年，克劳德·艾尔伍德·香农将热力学的熵，引入到信息论，因此它又被称为香农熵(Shannon Entropy)，它是香农信息量(Shannon Information Content, SIC)的期望。香农信息量用来度量不确定性的大小：一个事件的香农信息量等于0，表示该事件的发生不会给我们提供任何新的信息，例如确定性的事件，发生的概率是1，发生了也不会引起任何惊讶；当不可能事件发生时，香农信息量为无穷大，这表示给我们提供了无穷多的新信息，并且使我们无限的惊讶

  • [交叉熵](https://blog.csdn.net/rtygbwwwerr/article/details/50778098

  • picture 1

    • 上述式子是熵的期望（不同情况的熵的加权和）

  • 代价函数

    SVM

  • SVM原理

    KMeans

  • KMeans

    Dueling DQN

  • Dueling DQN

    文章链接

  • openai用强化学习玩我的世界

发表于 更新于
本文字数： 8.2k 阅读时长 ≈ 15 分钟

PPO调参实录

采用甄别reward的replay buffer

def store(self, transition):

    if len(self.buffer)>=self.buffer_capacity:
        tmp = np.random.randint(low=0, high=len(self.buffer))
        if self.buffer[tmp].r > transition.r:
            if np.random.randint(low=0, high=2) == 1:  # 一半的概率 替换的时候会保留reward更高的
                self.buffer[tmp] = transition
        self.buffer[tmp] = transition
    else:
        self.buffer.append(transition)
    self.counter += 1
    return self.counter % self.buffer_capacity == 0

  • 结果

    • image.png 1

  • 甄别的比率降到1/3之后

    • picture 4

优化（22年11月13日）的网络

import argparse
import math
import pickle
import random
from collections import namedtuple

import matplotlib.pyplot as plt

import gym
import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
from torch.distributions import Normal
from torch.utils.data.sampler import BatchSampler, SubsetRandomSampler
import numpy as np
import time

torch.set_num_threads(12)

parser = argparse.ArgumentParser(description='Solve the Pendulum-v0 with PPO')
parser.add_argument(
    '--gamma', type=float, default=0.9, metavar='G', help='discount factor (default: 0.9)')
parser.add_argument('--seed', type=int, default=0, metavar='N', help='random seed (default: 0)')
parser.add_argument('--render', action='store_true', help='render the environment')
parser.add_argument(
    '--log-interval',
    type=int,
    default=10,
    metavar='N',
    help='interval between training status logs (default: 10)')
args = parser.parse_args()

torch.manual_seed(args.seed)

TrainingRecord = namedtuple('TrainingRecord', ['ep', 'reward'])
Transition = namedtuple('Transition', ['s', 'a', 'a_log_p', 'r', 's_'])


class ActorNet(nn.Module):

    def __init__(self):
        super(ActorNet, self).__init__()
        self.fc = nn.Linear(3, 200)
        self.mu_head = nn.Linear(200, 1)
        self.sigma_head = nn.Linear(200, 1)

    def forward(self, x):
        x = F.relu(self.fc(x))
        mu = 2.0 * torch.tanh(self.mu_head(x))
        sigma = F.softplus(self.sigma_head(x))
        return (mu, sigma)


class CriticNet(nn.Module):

    def __init__(self):
        super(CriticNet, self).__init__()
        self.fc = nn.Linear(3, 200)
        self.hidden = nn.Linear(200, 200)
        self.v_head = nn.Linear(200, 1)

    def forward(self, x):
        x = F.relu(self.fc(x))
        x = F.relu(self.hidden(x))
        state_value = self.v_head(x)
        return state_value


class Agent():
    clip_param = 0.1
    max_grad_norm = 0.5
    ppo_epoch = 5
    buffer_capacity, batch_size = 1000, 32

    def __init__(self):
        self.training_step = 0
        self.anet = ActorNet().float()
        self.cnet = CriticNet().float()
        self.buffer = []
        self.counter = 0

        self.optimizer_a = optim.Adam(self.anet.parameters(), lr=4e-5)
        self.optimizer_c = optim.Adam(self.cnet.parameters(), lr=6e-5)

    def select_action(self, state):
        state = torch.from_numpy(state).float().unsqueeze(0)
        with torch.no_grad():
            (mu, sigma) = self.anet(state)
        dist = Normal(mu, sigma)
        action = dist.sample()
        action_log_prob = dist.log_prob(action)
        action = action.clamp(-2.0, 2.0)
        return action.item(), action_log_prob.item()

    def get_value(self, state):

        state = torch.from_numpy(state).float().unsqueeze(0)
        with torch.no_grad():
            state_value = self.cnet(state)
        return state_value.item()

    def save_param(self):
        torch.save(self.anet.state_dict(), 'param/ppo_anet_params.pkl')
        torch.save(self.cnet.state_dict(), 'param/ppo_cnet_params.pkl')

    def store(self, transition):

        if len(self.buffer)>=self.buffer_capacity:
            tmp = np.random.randint(low=0, high=len(self.buffer))
            if self.buffer[tmp].r > transition.r:
                if np.random.randint(low=0, high=3) == 1:  # 一半的概率 替换的时候会保留reward更高的
                    self.buffer[tmp] = transition
            self.buffer[tmp] = transition
        else:
            self.buffer.append(transition)
        self.counter += 1
        return self.counter % self.buffer_capacity == 0

    def update(self):
        self.training_step += 1
        self.counter = 1
        s = torch.tensor([t.s for t in self.buffer], dtype=torch.float)
        a = torch.tensor([t.a for t in self.buffer], dtype=torch.float).view(-1, 1)
        r = torch.tensor([t.r for t in self.buffer], dtype=torch.float).view(-1, 1)
        s_ = torch.tensor([t.s_ for t in self.buffer], dtype=torch.float)

        old_action_log_probs = torch.tensor(
            [t.a_log_p for t in self.buffer], dtype=torch.float).view(-1, 1)

        r = (r - r.mean()) / (r.std() + 1e-5)
        with torch.no_grad():
            target_v = r + args.gamma * self.cnet(s_)

        adv = (target_v - self.cnet(s)).detach()

        for _ in range(self.ppo_epoch):
            # indexArray = []
            # dist = Normal(self.buffer_capacity, self.buffer_capacity / 4)
            # sampleList = []
            # cntArray = [0 for i in range(self.buffer_capacity)]
            # # print(cntArray)
            # dist = Normal(self.batch_size*2/3, self.batch_size)
            # for i in range(self.batch_size):
            #     cnt = 0
            #     samples = []
            #     while cnt < self.batch_size:
            #         # print(dist.sample())
            #         # print(cnt)
            #         tmp = round(float(dist.sample()))
            #         if 0 <= tmp and tmp < self.buffer_capacity:
            #             if not tmp in samples:
            #                 if not cntArray[tmp]>4:
            #                     cnt += 1
            #                     samples.append(tmp)
            #                     cntArray[tmp]+=1
            #     sampleList.append(samples)
            for index in BatchSampler(
                    SubsetRandomSampler(range(self.buffer_capacity)), self.batch_size, False):
            # for index in sampleList:
                # print(len(index))
                (mu, sigma) = self.anet(s[index])
                # print(mu)
                dist = Normal(mu, sigma)
                action_log_probs = dist.log_prob(a[index])
                ratio = torch.exp(action_log_probs - old_action_log_probs[index])

                surr1 = ratio * adv[index]
                surr2 = torch.clamp(ratio, 1.0 - self.clip_param,
                                    1.0 + self.clip_param) * adv[index]
                action_loss = -torch.min(surr1, surr2).mean()

                self.optimizer_a.zero_grad()
                action_loss.backward()
                nn.utils.clip_grad_norm_(self.anet.parameters(), self.max_grad_norm)
                self.optimizer_a.step()

                value_loss = F.smooth_l1_loss(self.cnet(s[index]), target_v[index])
                self.optimizer_c.zero_grad()
                value_loss.backward()
                nn.utils.clip_grad_norm_(self.cnet.parameters(), self.max_grad_norm)
                self.optimizer_c.step()

        # del self.buffer[:]


flagVar = False

pendulumGoal = [1.0, 0.0, 0.0]


def rewardFunc(goal, state, absMax):
    tmp = -(np.power(state[0] - goal[0], 2) + 1*np.power(state[1] - goal[1], 2) + 0.1 * np.power(state[2] - goal[2], 2))
    return (tmp + absMax)/absMax
def main():
    global flagVar
    # env = gym.make('Pendulum-v1', render_mode="human")
    env = gym.make('Pendulum-v1')
    # env.seed(args.seed)
    # env.render()
    agent = Agent()

    training_records = []
    running_reward = -1000
    # state = env.reset()
    TRAIN_EPISODE = 1000
    EPISODE_LENGTH = 200
    for i_ep in range(TRAIN_EPISODE):
        score = 0
        state = np.array(env.reset()[0])
        # if i_ep % 100 == 0:
        #     print('!')
        #     env.render()
        # print(type(state))
        start = time.time()
        if i_ep == 0:
            firstY = []
        if i_ep == TRAIN_EPISODE-1:
            lastX = [i for i in range(EPISODE_LENGTH)]
            lastY = []
        for t in range(EPISODE_LENGTH):
            action, action_log_prob = agent.select_action(state)
            # if i_ep%100 == 0:
                # print('!')
                # env.render()
            envRet = env.step([action])
            # print(envRet)
            state_, reward, done, _, _ = envRet
            if i_ep == TRAIN_EPISODE-1:
                lastY.append(math.acos(state_[0]))
                # lastY.append(state_[0])
            elif i_ep == 0:
                firstY.append(math.acos(state_[0]))
                # firstY.append(state_[0])
            # print(state_)
            # if args.render:
            #     env.render()
            if agent.store(Transition(state, action, action_log_prob, (reward + 8) / 8, state_)):
                agent.update()

            # reward = rewardFunc(pendulumGoal, state_, 8)
            # if agent.store(Transition(state, action, action_log_prob, reward, state_)):
            #     agent.update()

            score += reward
            state = state_

        running_reward = running_reward * 0.85 + score * 0.1
        training_records.append(TrainingRecord(i_ep, running_reward))

        if i_ep % args.log_interval == 0:
            print('Ep {}\tMoving average score: {:.2f}\t'.format(i_ep, running_reward))
            time_ = time.time()
            print("time used is {:.5f}".format(time_ - start))
            # start = time_
        # if running_reward > -200:
        #     print("Solved! Moving average score is now {}!".format(running_reward))
        #     env.close()
        #     agent.save_param()
        #     with open('log/ppo_training_records.pkl', 'wb') as f:
        #         pickle.dump(training_records, f)
        #     break


        # if running_reward > -850 and not flagVar:  # 减小学习率防止波动
        #     flagVar = True
        #     print("-------------------------------")
        #     agent.optimizer_a = optim.Adam(agent.anet.parameters(), lr=1e-5)
        #     agent.optimizer_c = optim.Adam(agent.cnet.parameters(), lr=2e-5)

    plt.figure(figsize=(8, 5))
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
    plt.rcParams['axes.unicode_minus'] = False  # 解决保存图像时符号-显示为方块的2问题
    plt.subplot(2,1,1)
    plt.plot([r.ep for r in training_records], [r.reward for r in training_records])
    plt.title('PPO')
    plt.xlabel('Episode')
    plt.ylabel('Moving averaged episode reward')
    # plt.savefig("img/ppo.png")
    plt.subplot(2,1,2)
    plt.plot(lastX, firstY, label="第一次")
    plt.plot(lastX, lastY, label="最后一次")
    plt.ylabel("cos("+r'$\theta$'+")")
    plt.xlabel("time")
    plt.legend()
    plt.tight_layout()
    plt.show()


if __name__ == '__main__':
    main()
    # example = [i for i in range(100)]
    # print(len([i for i in BatchSampler(SubsetRandomSampler(range(100)), 20, False)]))
  • 效果picture 4

发表于 更新于
本文字数： 921 阅读时长 ≈ 2 分钟

Hindsight Experience Replay

  • 原文
    • Hindsight experience replay
    • Advances in neural information processing systems
  • 参考链接

    方法

  • 你得知道从状态S到目标goal的映射关系（以机械臂为例，状态可能是多个关节的角度，目标是三维空间一个点的坐标，如果知道状态，那么也能推算出机械臂末端在空间中的坐标）；
  • 你得建立一个新的reward计算机制，它取决于目标goal和状态S，一般当状态S映射的goal’与goal相近时给予奖励；
  • 你得创建一个记录每个episode transition的列表，它的作用是在每个episode结束后进行事后经验回放，具体回放方法之后讲；
  • RL算法接受的状态维度相较于原始的维度增加了目标goal的维度，也就是RL接受：
    • picture 2

      举例的github

  • HER举例
  • 这里episode_cache为存储transition的列表((s1,a1,r1,s1’),(s2,a2,r2,s2’)…)，枚举这个列表的元素。在第二句根据每个transition产生HER_SAMPLE_NUM个新的目标点new_goals，这些目标点时根据之后的transition的state推算得到的，当然一种简单的情况就是state。之后对这些new_goals做遍历，对每一个new_goal都重新计算reward，并将transition中s和s’的goal部分替换为new_goal，之后将这个新的transition存储入经验池buffer。这里之所以可以这么做是因为在动作a不变的情况下，改变goal是不会改变从原来的s转移到s’的转移概率的。
  • 先对每个回合中的所有输入做一个reward的评价
  • 然后在整个回合的数据后处理时，循环到i时，从i之后的数据里随机选出一部分作为新的goal，然后利用这些新的goal重新计算i这个数据的reward，然后将其放入到replay buffer中，可能导致replay buffer中包含多条由同一条数据而来但是reward不同的数据条目
  • 可以在每训练一个回合之后更换初始的goal（也就是在筛选之前针对所有对象的goal）达到多目标训练的效果
  • 示例代码
  • picture 5

发表于 更新于
本文字数： 6.2k 阅读时长 ≈ 11 分钟

  • 基于pytorch实现的强化学习网络

    • 这个的PPO写的似乎有问题

  • 强化学习网络集合

  • 集合 2

  • PPO

  • PPO是基于Actor-Critic的算法

  • 参考链接

    import argparse
    import pickle
    from collections import namedtuple

    import matplotlib.pyplot as plt

    import gym
    import torch
    import torch.nn as nn
    import torch.nn.functional as F
    import torch.optim as optim
    from torch.distributions import Normal
    from torch.utils.data.sampler import BatchSampler, SubsetRandomSampler

    parser = argparse.ArgumentParser(description='Solve the Pendulum-v0 with PPO')
    parser.add_argument(
        '--gamma', type=float, default=0.9, metavar='G', help='discount factor (default: 0.9)')
    parser.add_argument('--seed', type=int, default=0, metavar='N', help='random seed (default: 0)')
    parser.add_argument('--render', action='store_true', help='render the environment')
    parser.add_argument(
        '--log-interval',
        type=int,
        default=10,
        metavar='N',
        help='interval between training status logs (default: 10)')
    args = parser.parse_args()

    torch.manual_seed(args.seed)

    TrainingRecord = namedtuple('TrainingRecord', ['ep', 'reward'])
    Transition = namedtuple('Transition', ['s', 'a', 'a_log_p', 'r', 's_'])


    class ActorNet(nn.Module):

        def __init__(self):
            super(ActorNet, self).__init__()
            self.fc = nn.Linear(3, 100)
            self.mu_head = nn.Linear(100, 1)
            self.sigma_head = nn.Linear(100, 1)

        def forward(self, x):
            x = F.relu(self.fc(x))
            mu = 2.0 * F.tanh(self.mu_head(x))
            sigma = F.softplus(self.sigma_head(x))
            return (mu, sigma)


    class CriticNet(nn.Module):

        def __init__(self):
            super(CriticNet, self).__init__()
            self.fc = nn.Linear(3, 100)
            self.v_head = nn.Linear(100, 1)

        def forward(self, x):
            x = F.relu(self.fc(x))
            state_value = self.v_head(x)
            return state_value


    class Agent():

        clip_param = 0.2
        max_grad_norm = 0.5
        ppo_epoch = 10
        buffer_capacity, batch_size = 1000, 32

        def __init__(self):
            self.training_step = 0
            self.anet = ActorNet().float()
            self.cnet = CriticNet().float()
            self.buffer = []
            self.counter = 0

            self.optimizer_a = optim.Adam(self.anet.parameters(), lr=1e-4)
            self.optimizer_c = optim.Adam(self.cnet.parameters(), lr=3e-4)

        def select_action(self, state):
            state = torch.from_numpy(state).float().unsqueeze(0)
            with torch.no_grad():
                (mu, sigma) = self.anet(state)
            dist = Normal(mu, sigma)
            action = dist.sample()
            action_log_prob = dist.log_prob(action)
            action = action.clamp(-2.0, 2.0)
            return action.item(), action_log_prob.item()

        def get_value(self, state):

            state = torch.from_numpy(state).float().unsqueeze(0)
            with torch.no_grad():
                state_value = self.cnet(state)
            return state_value.item()

        def save_param(self):
            torch.save(self.anet.state_dict(), 'param/ppo_anet_params.pkl')
            torch.save(self.cnet.state_dict(), 'param/ppo_cnet_params.pkl')

        def store(self, transition):
            self.buffer.append(transition)
            self.counter += 1
            return self.counter % self.buffer_capacity == 0

        def update(self):
            self.training_step += 1

            s = torch.tensor([t.s for t in self.buffer], dtype=torch.float)
            a = torch.tensor([t.a for t in self.buffer], dtype=torch.float).view(-1, 1)
            r = torch.tensor([t.r for t in self.buffer], dtype=torch.float).view(-1, 1)
            s_ = torch.tensor([t.s_ for t in self.buffer], dtype=torch.float)

            old_action_log_probs = torch.tensor(
                [t.a_log_p for t in self.buffer], dtype=torch.float).view(-1, 1)

            r = (r - r.mean()) / (r.std() + 1e-5)
            with torch.no_grad():
                target_v = r + args.gamma * self.cnet(s_)

            adv = (target_v - self.cnet(s)).detach()

            for _ in range(self.ppo_epoch):
                for index in BatchSampler(
                        SubsetRandomSampler(range(self.buffer_capacity)), self.batch_size, False):

                    (mu, sigma) = self.anet(s[index])
                    dist = Normal(mu, sigma)
                    action_log_probs = dist.log_prob(a[index])
                    ratio = torch.exp(action_log_probs - old_action_log_probs[index])

                    surr1 = ratio * adv[index]
                    surr2 = torch.clamp(ratio, 1.0 - self.clip_param,
                                        1.0 + self.clip_param) * adv[index]
                    action_loss = -torch.min(surr1, surr2).mean()

                    self.optimizer_a.zero_grad()
                    action_loss.backward()
                    nn.utils.clip_grad_norm_(self.anet.parameters(), self.max_grad_norm)
                    self.optimizer_a.step()

                    value_loss = F.smooth_l1_loss(self.cnet(s[index]), target_v[index])
                    self.optimizer_c.zero_grad()
                    value_loss.backward()
                    nn.utils.clip_grad_norm_(self.cnet.parameters(), self.max_grad_norm)
                    self.optimizer_c.step()

            del self.buffer[:]


    def main():
        env = gym.make('Pendulum-v0')
        env.seed(args.seed)

        agent = Agent()

        training_records = []
        running_reward = -1000
        state = env.reset()
        for i_ep in range(1000):
            score = 0
            state = env.reset()

            for t in range(200):
                action, action_log_prob = agent.select_action(state)
                state_, reward, done, _ = env.step([action])
                if args.render:
                    env.render()
                if agent.store(Transition(state, action, action_log_prob, (reward + 8) / 8, state_)):
                    agent.update()
                score += reward
                state = state_

            running_reward = running_reward * 0.9 + score * 0.1
            training_records.append(TrainingRecord(i_ep, running_reward))

            if i_ep % args.log_interval == 0:
                print('Ep {}\tMoving average score: {:.2f}\t'.format(i_ep, running_reward))
            if running_reward > -200:
                print("Solved! Moving average score is now {}!".format(running_reward))
                env.close()
                agent.save_param()
                with open('log/ppo_training_records.pkl', 'wb') as f:
                    pickle.dump(training_records, f)
                break

        plt.plot([r.ep for r in training_records], [r.reward for r in training_records])
        plt.title('PPO')
        plt.xlabel('Episode')
        plt.ylabel('Moving averaged episode reward')
        plt.savefig("img/ppo.png")
        plt.show()


    if __name__ == '__main__':
        main()

  • 产生动作的方式与一般的PG类似，就是使用PG输出一个μ和σ然后使用正态分布，然后进行采样输出真正的动作

    网络更新

  • reward归一化，将reward-平均数/标准差

  • 计算target价值，使用当前回合的reward+系数×Critic对于下一状态的分析

  • 估计价值和实际价值的差：直接用估计当前状态的价值与上一步计算的价值做差

  • 计算actor网络的loss的方法是

    (mu, sigma) = self.anet(s[index])
    dist = Normal(mu, sigma)
    action_log_probs = dist.log_prob(a[index])
    ratio = torch.exp(action_log_probs - old_action_log_probs[index])

    surr1 = ratio * adv[index]
    surr2 = torch.clamp(ratio, 1.0 - self.clip_param,
                        1.0 + self.clip_param) * adv[index]
    action_loss = -torch.min(surr1, surr2).mean()

  • 先利用当前的网络采样输出μ和σ，然后计算之前action的log_prob，，然后利用表达式e^(这次网络计算出的log可能性-上次网络计算出的log可能性)，实际上就是这次网络计算出的可能性/上次网络计算出的可能性与上一步算出的估计价值和实际价值的差值修正这个值，主要目的是用合理的方法利用其他时刻动作的输出，增加一个动作的利用效率

  • picture 1

  • 然后用一个参数×上面的数值，处理之后得到最终需要反向传播的值（actor）

    value_loss = F.smooth_l1_loss(self.cnet(s[index]), target_v[index])
    self.optimizer_c.zero_grad()
    value_loss.backward()
    nn.utils.clip_grad_norm_(self.cnet.parameters(), self.max_grad_norm)
    self.optimizer_c.step()

  • 更新Critic的参数操作是将现在的Critic网络对价值的判断与前面算出的目标价值判断进行比较，将二者的差进行反向传播

    BatchSampler和SubsetRamdomSampler

  • SubsetRandomSampler实际上是将数据的顺序打乱做一个全排列

  • BatchSampler实际上是根据设置的batch_size给数据分成一个个的batch

发表于 更新于
本文字数： 187 阅读时长 ≈ 1 分钟

找不到.condarc文件

  • 先执行一次conda config就能找到了

    配置Anaconda使用clash代理

  • 链接

    修改Anaconda安装环境的默认位置

  • 链接

    手动添加Anaconda到环境变量

  • 链接

    配置pytorch使用CPU的多线程

  • torch.set_num_threads(8)
  • 参考
  • 作用不大

    GYM 官方文档

  • 链接

    word中插入代码

  • https://highlightcode.com/