0%

博客文章引导

Website

我的博客, 即劳振煜的知識倉儲, 也就是您当前访问的博客.

博客是基于 Hexo 的静态博客, 部署于我的 Github 上.

该博客主要用来记录我在学习以及未来工作中的所感所悟. 留作记录以便自己在未来温故或帮助到正在看博客的你.

博客的内容区别于 Github 的内容, 主要是博客将会记录完整的有体系的内容, 而 Github 上的各个仓库主要是用于记录学习笔记与实验, 自己造轮子, 学习他人的开源项目.


C++

STL

数据结构

计算机网络

操作系统

设计模式

Leetcode

Github仓库引导

我的Github, 也就是上方链接. 你可以搜索 OXygenPanda 访问.

虽然没有很多 star, 但是仍然坚持学习, 坚持记录, 坚持分享.


计算机网络课程学习 - 韩立刚老师

记录计算机网络课程学习的笔记

深入理解操作系统课程学习 - 清华大学

记录清华大学深入理解操作系统课程学习的笔记

Website

进程可能需要频繁和其他进程交流. 比如, shell 管道, 第一个进程的输出必须传递给第二个进程.

接下来, 就讨论有关 进程间通信(Inter Process communication, IPC).

进程通信存在三个问题 :

  1. 一个进程如何传递消息给其他进程.
  2. 如何确保两个或多个线程之间不会相互干扰.
  3. 数据的先后顺序问题.

第一个问题, 在线程中不是问题, 线程共享同一内存空间, 可以很容易地进行通信;

第二个和第三个问题, 同样适用于线程.

竞态条件

两个或多个线程同时对一共享数据进行修改, 从而影响到了程序运行的正确性, 这种被称为竞态条件.

临界区

禁止一个或多个进程在同一个时刻对共享资源(共享内存, 共享文件等)进行读写.

也就是一个互斥条件.

在任何操作系统中, 为了实现互斥操作而选用适当的原语是一个主要的设计问题.

一个好的解决方案, 应当包含四个条件 :

  1. 任何时候, 两个进程不能同时处于临界区
  2. 不应当对CPU的速度和数量做任何假设
  3. 位于临界区外的进程不得阻塞其他进程
  4. 不能使任何进程无限等待进入临界区

忙等互斥

介绍互斥的各种设计.

屏蔽中断

单处理器, 屏蔽中断, 能够屏蔽CPU的时钟中断, 进而阻止进程的切换, 但是如何进程运行时间过长, 可能会导致系统崩溃.

多处理器, 屏蔽中断, 仅一块CPU会受限, 其他CPU仍然能够访问共享内存.

屏蔽中断是一项很有用的技术, 但是不是一项通用的互斥机制.

锁变量

软件层面的解决方案, 锁变量初始化为0, 当一个线程想进入功关键区域, 查看锁的值, 如果是0, 设置为1, 进程进入, 出来后, 恢复为0; 如果是1, 阻塞.

有可能, 一个线程发现是0, 想设置为1, 而另一个线程也发现是0时, 会出现多个线程访问关键区域.

根本原因, 修改锁变量, 不是一种原子性操作, 仍然可能发生竞态.

严格轮询法

先查看一段代码 :

进程 0

1
2
3
4
5
6
7
8
9
while(TRUE){
while(turn != 0){
//进入关键区域
critical_region();
turn = 1;
//离开关键区域
noncritical_region();
}
}

进程 1

1
2
3
4
5
6
7
while(TRUE){
while(turn != 1){
critical_region();
turn = 0;
noncritical_region();
}
}

多个进程, 必须得频繁使用临界区资源, 否则容易长时间阻塞其他进程. while 体现了忙等待, 除非是认为等待时间很短, 否则不使用忙等待.

用于忙等待的锁, 称为 自旋锁.

Peterson 解法

荷兰数学家 T.Dekker 结合锁变量和警告变量, 提出不需要严格轮换的软件互斥算法.

后来, G.L.Peterson 发现了一种简单的互斥算法 :

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
#define FALSE 0
#define TRUE 1

/* 进程数量 */
#define N 2

/* 现在轮到谁 */
int turn;

/* 所有值初始化为 0 */
int interested[N];

/* 进程是 0 或 1 */
void enter_region(int process){
// 另一个进程号
int other;
// 另一个进程
other = 1 - process;

//表示愿意进入临界区
interested[process] = TRUE;
turn = process;

//空循环
while(turn == process && interested[other] == true){}
}

void leave_region(int process){
//表示愿意离开临界区
interested[process] = FALSE;

TSL指令

需要硬件帮助的方案.

多处理器的计算机, 会有这条指令 : TSL RX,LOCK

称为测试并加锁.

实现了原子操作, 锁住内存总线, 防止其他CPU访问内存.

睡眠与唤醒

Peterson, TSL 和 XCHG 都是正确的, 但是都有忙等待的缺点.

解法本质上一样, 检查能否进入临界区, 不允许则原地等待.

进程间原语

sleep : 调用者阻塞, 直到被其他进程唤醒.

wakeup : 唤醒其他进程.

生产者-消费者问题

又称为, 有界缓冲区问题 : 两个进程共享一个公共的固定大小的缓冲区. 一个是生产者, 将信息放入缓冲区, 另一个是消费者, 会从缓冲区取出.

描述 : 生产者可以将数据写入缓冲区, 当写满时, 生产者睡眠, 阻塞; 消费者可以将读取缓冲区数据, 当为空时, 消费者睡眠, 阻塞.

使用一个监听变量, Count 来记录缓冲区的数据量.

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
# define N 100

int count = 0;

void producer(void){
int item;

while(TRUE){
item = produce_item();
if(count == N){
sleep();
}

insert_item(item);
count = count + 1;
if(count == 1){
wakeup(consumer);
}
}
}

void consumer(void){
int item;

while(TRUE){
i(count == 0){
sleep();
}
item = remove_item();
count = count - 1;
i(count == N - 1){
wakeup(producer);
}
consumer_item(item);
}
}

信号量

用信号量解决生产者-消费者问题

互斥量

Futexes

Pthreads中的互斥量

管程

消息传递

用消息传递解决生产者-消费者问题

屏障

避免锁 : 读-复制-更新

Website # 进程和线程

进程

即使可以使用的CPU只有一个, 也支持并发操作.

每个程序运行几十或者几百毫秒, 即使每一个瞬间CPU只能运行一个进程, 在一秒内, 也运行了多个进程. 给人并行的错觉. 也就是伪并行.

进程模型

所有计算机上运行的软件, 包括系统, 被组织为若干顺序进程 (sequential processes), 简称为进程(process).

一个进程就是一个正在执行的程序的实例, 包括程序计数器, 寄存器和变量的当前值.

进程切换的时候, 运行的进程把逻辑程序计数器装载到物理程序计数器中, 程序结束时, 再把物理程序计数器放回逻辑程序计数器.

进程是某一特定活动的总和, 有程序, 输入输出以及状态.

进程创建

以下是创建进程的方式 :

  • 系统初始化
  • 正在运行的程序执行了创建进程的系统调用(fork)
  • 用户请求创建一个新进程
  • 初始化一个批处理工作

系统初始化

启动操作系统的时候, 通常会创建若干进程.

前台进程 : 和用户进行交互完成工作的进程.

守护进程 : 在后台用来处理一些活动, 比如 email, web, 新闻等的进程.

unix中, 使用 ps 可以列出正在运行的进程, 在windows里使用任务管理器.

系统调用创建

一个新的进程可以由其他进程通过系统调用创建, 比如大量数据需要从网络调取并处理, 可以创建一个进程读数据并放到缓冲区, 第二个进程取走并正确处理.

在多处理器中, 让每个进程运行在不同的CPU上也可以使得工作做的更快.

用户请求创建

输入一个命令或者双击图标可以启动程序.

批处理创建

在 UNIX 系统中, 只有一个系统调用来创建一个新的进程, fork() , 调用会创建一个与调用进程相关的副本, 父进程和子进程会有相同的内存映像, 相同的环境字符串和相同的打开文件, 通常子进程会执行 execve() 来改变内存映像并运行一个新的程序.

  • UNIX 中的一些系统调用

有一些 UNIX 系统的实现, 父进程和子进程在不可写的内存区域上是共享的, 而可写内存区域通过 写时赋值(copy-on-write) 共享, 一旦两者之一想要修改部分内存, 则该内存首先被明确的赋值, 以确保修改发生在私有的内存区域.

进程终止

进程终止有几种情况 :

  1. 正常退出 (自愿)
  2. 错误退出 (自愿)
  3. 严重错误 (非自愿)
  4. 被其他进程杀死 (非自愿)

正常退出

调用 UNIX 中的 exit()

错误退出

1
cc foo.c

比如, 想要编译 foo.c 文件, 但是该文件不存在, 就会发生错误退出, 参数不合理.

严重错误

由于程序中的错误导致. 比如, 执行非法指令, 引用不存在的内存, 除数为0等.

被进程杀死

调用 UNIX 中的 kill()

进程层次结构

父进程创建了子进程, 父子进程之间存在一定的关联, 子进程又会创建更多的进程, 从而形成一个进程层次结构.

UNIX 进程体系

在 UNIX 中, 进程和它的所有子进程以及子进程的子进程共同组成一个进程组. 当用户从键盘中发出一个信号后, 该信号会被发送给当前与键盘相关的进程组中的所有成员. 每个进程可以分别捕获信号, 忽略信号 或者 采取默认的动作.

UNIX 在启动时初始化自己, 一个称为 init 的特殊进程是整个操作系统进程树的根.

进程状态

1
cat chapter1 chapter2 chapter3 | grep tree

两个进程, cat 进程将三个文件级联, grep 进程等待输入选择具有 tree 关键词的内容.

当 grep 进程就绪开始运行时, 但是 cat 进程还没有执行, 于是 grep 进程会阻塞, 等待输入完毕.
所以, 进程可能会经历以下状态 :

阻塞 ← 运行 ←→ 就绪

阻塞 → 就绪

具体说明 :

运行 → 阻塞 : 进程因为等待输入而阻塞

运行 → 就绪 : 调度程序选择了另一个进程, 时间片没有轮到自己

就绪 → 运行 : 调度程序选择一个进程开始运行, 时间片轮到了自己

阻塞 → 就绪 : 输入完毕

状态说明 :

  1. 运行态 : 进程实际占用 CPU 时间片
  2. 就绪态 : 可以运行, 但是其他进程正在运行
  3. 阻塞态 : 除非某种外部事件发生, 否则进程不能运行

进程实现

操作系统维护一张进程表(process table).

每个进程占用一个表项, 包含进程的重要信息, 包括程序计数器, 堆栈指针, 内存分配状况, 所打开的文件状态, 账号和调度信息, 状态切换的信息. 从而能够保证进程在随后可以再次启动, 就像从未被中断过.

表项内容 :

  • 进程管理

    寄存器, 程序计数器, 程序状态字, 堆栈指针, 进程状态, 优先级, 调度参数, 进程ID, 父进程, 进程组, 信号, 进程开始的时间, 使用的CPU时间, 子进程的CPU时间, 下次定时器时间

  • 存储管理

    text segment 指针

    data segment 指针

    stack segment 指针

  • 文件管理

    根目录

    工作目录

    文件描述符

    用户ID

    组ID


线程

传统的操作系统中, 每个进程都有一个地址空间和一个控制线程.

事实上, 经常存在同一地址空间中运行多个控制线程的情况.

线程使用

为什么要在进程模型上再创建一个线程的概念, 需要分三步回答 :

  • 多线程之间可以共享一块地址空间和所有可用数据, 这是多进程不具备的 ← 共享
  • 线程比进程轻量化, 创建容易撤销也容易, 创建线程比进程快 10 - 100 倍 ← 轻量
  • 如果存在大量的计算和大量的IO处理, 多线程能够加快执行速度 ←高性能

多线程解决方案

调度线程是从网络中读入工作请求, 检查完之后, 选择一个空闲的(阻塞的)工作线程来处理请求, 通常方式是将消息的指针写入到每个线程关联的特殊字中. 调度线程会唤醒正在睡眠的工作线程, 把工作线程的状态从阻塞态变为就绪态.

这种模型允许服务器编写为顺序线程的集合, 在分派线程的程序中包含一个死循环, 用来获得工作请求并把请求派给工作线程.
每个工作线程的代码包含一个从调度线程接收的请求, 并且检查 web 高速缓存中是否存在所需页面, 如果有, 直接把页面返回给客户, 接着工作线程阻塞, 等待一个新请求的到达. 如果没有, 工作线程就从磁盘调入该页面, 将页面返回给客户, 然后工作线程阻塞, 等待新请求.

下面是调度线程和工作线程的代码, 假设 TRUE 为 1, buf 和 page 分别是保存工作请求和 web 页面的相应结构.

调度线程的大致逻辑

1
2
3
4
while(TRUE){
get_next_request(&buf);
handoff_work(&buf);
}

工作线程的大致逻辑

1
2
3
4
5
6
7
8
while(TRUE){
wait_for_work(&buf);
look_for_page_in_cache(&buf, &page);
if(page_not_in_cache(&page)){
read_page_from_disk(&buf, &page);
}
return _page(&page);
}

单线程解决方案

如果只有单线程来处理请求, 那么在等待磁盘操作时, 服务器空转, 不处理任何到来的其他请求. 导致效率极低, 也说明了多线程能够提高程序的并行性和程序的性能.

状态机解决方案

对比

单线程 - 无并行性, 性能较差, 阻塞系统调用

多线程 - 有并行性, 阻塞系统调用

有限状态机 - 并行性, 非阻塞系统调用, 中断

经典线程模型

进程存放程序正文和数据以及其他资源的地址空间, 资源包括 : 打开的文件, 子进程, 即将发生的定时器, 信号处理程序, 账号信息等. 进程管理资源较为方便.

进程中包含执行的线程 :

  • 线程会有程序计数器, 用来记录接下来要执行哪一条指令;
  • 线程会有寄存器, 用来保存当前正在使用的变量;
  • 线程会有堆栈, 用来记录程序的执行路径.

多个线程中, 各个线程共享同一地址空间和其他资源.

由于每个线程可以访问进程地址空间中的每个内存地址, 因此一个线程可以读取, 写入甚至擦除另一个线程的堆栈. 线程之间除了共享同一内存空间外, 还有以下不同的内容 :

每个进程中的内容(线程共享内容) 进程的属性

  • 地址空间
  • 全局变量
  • 打开文件
  • 子进程
  • 即将发生的定时器
  • 信号和信号处理程序
  • 账户信息

每个线程中的内容 线程的属性

  • 程序计数器
  • 寄存器
  • 堆栈
  • 状态

线程有以下几种状态 : 运行态, 阻塞态, 就绪态和终止态.

线程系统调用

进程通常以单线程开始, 然后这个线程通过调用一个库函数(比如 thread_create)创建新的线程.
线程创建的函数会要求指定新创建线程的名称.
创建的线程通常都返回一个线程标识符, 该标识符就是新线程的名字.

使用, thread_exit 来退出线程.

使用, thread_join 表示一个线程可以等待另一个线程退出.

使用, thread_yield 允许线程自动放弃CPU从而让另一个线程运行.

POSIX线程

IEEE 1003.1c 线程标准

线程包被定义为 Pthreads, 这个标准定义了60多种功能调用.

POSIX线程是一种独立于语言而存在的执行模型, 以及并行执行模型.

线程调用 :

pthread_create : 创建一个新线程

pthread_exit : 结束调用的线程. 释放线程拥有的堆栈.

pthread_join : 等待一个特定的线程退出

pthread_yield : 释放CPU来运行另一个线程

pthread_attr_init : 创建并初始化一个线程的属性结构

pthread_attr_destory : 删除一个线程的属性结构

一个例子 :

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
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUMBER_OF_THREADS 10

void *print_hello_world(void * tid){
/* 输出线程的标识符, 然后退出 */
printf("Hello World. Greeting from thread %d\n", tid);
pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
/* 主程序创建10个线程, 然后退出 */
pthread_t threads[NUMBER_OF_THREADS];
int status, i;
for(int i = 0; i < NUMBER_OF_THREADS; ++ i){
printf("Main here. Creating thread %d\n", i);
status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);
if(status != 0){
printf("Oops. pthread_create returned error code %d\n", status);
exit(-1);
}
}
exit(NULL);
return 0;
}

线程实现

三种实现方式 :

  • 在用户空间中实现线程;
  • 在内核空间中实现线程;
  • 在用户和内核空间中混合实现线程.

在用户空间中实现线程

整个线程包放在用户空间中, 内核对线程一无所知, 不知道线程的存在.
包括以下几个过程 : pthread_create, pthread_exit, pthread_join, pthread_yield.
维护一张线程表, 记录各线程的属性. 由运行时系统统一管理.

在用户空间实现线程的优势

启动比进行内核调用效率更高, 不需要切换到内核, 不需要上下文切换, 不需要对内存高速缓存进行刷新, 线程调度便捷.

在用户空间实现线程的裂势

在内核中实现线程

混合实现

Website

学习自 : 现代 C++

回顾

上一讲中的 shape_wrapper 在某一程度上可以作为智能指针使用。

使用智能指针,可以简化资源的管理,从根本上消除内存泄漏的可能性。

阅读全文 »

Website

学习自 : 现代 C++

这里说的堆是动态分配内存的区域, 与数据结构里的堆不同.

这里的内存必须手动释放, 否则会造成内存泄漏.

阅读全文 »

红黑树

名称 : 红黑树

优点 :

相较AVL树来说, 平衡条件宽松, 减少了很多因插入删除节点导致的调整. 适合于插入删除频繁的情况.

AVL树适合于插入删除较少, 搜索较多的情况.

平衡条件 :

  1. 每个节点非黑即红
  2. 根节点是黑色
  3. 叶节点(NIL)是黑色 NIL : 虚拟空节点
  4. 如果一个节点是红色, 则它的两个子节点都是黑色的
  5. 从根节点触发到所有叶节点路径上, 黑色节点数量相同 (最长是最短路径的2倍 : 长边红黑相间, 短边黑色)

认识 :

平衡条件 4 和 5 限制了红黑树最长边和最短边的2倍长度关系. 本质上, 红黑树也是通过控制树高来保证平衡. 红黑树相比AVL树控制条件更弱, 因此插入删除调整的频次也会低. AVL树更适用于插入删除较少但是访问较多的情况.

快速排序

基础知识

名称 : 快速排序

性质 : 不稳定的排序算法

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 O(1)

代码实现

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
/************************************************************************
> File Name: quick_sort2.cpp
> Author: Lao Zhenyu
> Mail: LaoZhenyu_961112@163.com
> Created Time: 五 1/15 17:48:29 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void quickSort(vector<int> &arr, int left, int right){
if(left >= right) return;
int i,j,base;
base = arr[left];
i = left, j = right;
while(i < j){
while(arr[j] >= base && i < j)
j--;
while(arr[i] <= base && i < j)
i++;
if(i < j)
swap(arr[i], arr[j]);
}
arr[left] = arr[i];
arr[i] = base;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}



int main(){
vector<int> arr{1,3,2,6,5,4,9,7,8,};
quickSort(arr, 0, arr.size() - 1);
for(int n : arr){
cout << n << endl;
}
return 0;
}

归并排序

基础知识

名称 : 归并排序

性质 : 稳定的排序算法

作者 : 冯诺依曼

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 O(n)

代码实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/************************************************************************
> File Name: merge_sort.cpp
> Author: Lao Zhenyu
> Mail: LaoZhenyu_961112@163.com
> Created Time: 四 1/14 20:38:22 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void merge(vector<int> &arr, int left, int mid, int right){
vector<int> L(mid - left + 1);
vector<int> R(right - mid);
int i,j,k;
for(i = 0; i < L.size(); ++ i){
L[i] = arr[left + i];
}
for(j = 0; j < R.size(); ++ j){
R[j] = arr[mid + 1 + j];
}
i = 0;
j = 0;
k = left;
while(i < L.size() && j < R.size()){
if(L[i] >= R[j]){
arr[k] = R[j];
j++;
} else {
arr[k] = L[i];
i++;
}
k++;
}
while(i < L.size()){
arr[k] = L[i];
k++;
i++;
}
while(j < R.size()){
arr[k] = R[j];
k++;
j++;
}
}

void mergeSort(vector<int> &arr, int left, int right){
if(left < right){
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
return;
}


int main(){
vector<int> arr{1,3,2,4,5,6,9,7,8};
mergeSort(arr,0, arr.size() - 1);
for(auto n : arr){
cout << n << endl;
}
return 0;
}