日志-2021-3

2月第4周

整型

学习了C语言中整型的表示与运算。

有无符号和有符号两种,其中有符号类型使用二进制补码存储。相同的n位二进制数用无符号和补码解释可能有完全不同的结果,取值范围也不同。要特别注意参数传递时类型匹配的问题,以及隐式类型转换。

无符号运算和补码运算可以使用相同的算术规则,算术运算超出范围时也会产生有规律的溢出。

进程

进程的状态大致可分为ready、running、block/wait。进程的信息存储在PCB中,此数据结构中包含描述程序此次运行时的各种信息。

进程控制包含了进程的创建、撤销、阻塞、唤醒。这些控制都有各自的步骤。原语则是由若干指令构成的具有特定功能的函数,为最小单位不可在分割。以上4个操作对应进程控制的4个原语。父进程可以创建子进程,构成进程树,也可以在一定情况下终止子进程。

进程的切换/上下文切换。context是程序运行的环境,如CPU内各个寄存器的值。

进程调度可以分为长调度/作业调度和短调度/CPU调度。长调度需要组合I/O型进程和CPU型进程。另外还有中程调度,缓解内存紧张的问题,它将内存中处于阻塞状态的进程换到外存上挂起。进程调度队列有作业队列、就绪队列、设备队列等。

进程间通信可以通过共享存储区或消息传递的方式实现。消息传递时可以直接传递或间接传递。

线程

进程的控制开销大,为了提高并发度和减小系统开销,引入线程。用更小的开销提高进程内的并发程度。作为CPU的调度单位。线程进一步提高系统并发的程度。

线程只拥有必不可少的资源,如线程状态和上下文。同个进程的各个线程共享资源。

一个进程中的多个线程可以并发执行。线程在创建、撤销的开销更小,线程调度切换上下文的开销更小。同进程的各个线程之间共享数据段,不需要IPC。系统资源利用率更高,资源可以共享、开销更小、适合多处理器结构。

内核级线程在内核空间创建、调度和管理,确实是cpu调度的基本单位。用户级线程由线程库管理,无需内核支持,此时进程仍是CPU调度的单位。

多线程模型中的多对多模型不限制应用的线程数、多个线程可以并发,不会因为一个线程阻塞而阻塞整个所有线程。此外两极模型除了允许多对多,也允许一对一。

CPU调度

CPU空闲时,OS选择内存就绪队列中某就绪进程,给它分配CPU。提高CPU利用率。

进程状态切换时(有4种情况)可能会发生CPU调度。CPU调度的方案可分为非抢占式和抢占式。非抢占方式不允许其他进程抢占已分配的处理机,系统开销小但不适合实时、分时系统。抢占式根据调度原则,停止某个正在执行的进程,将处理机分配给另一个进程,抢占原则主要有:时间片原则、优先权原则、短作业优先原则。

FCFS按照作业到达就绪队列的先后次序选择作业,是非抢占方式、有利于长作业和CPU型进程,有护航效应。

SJF根据估计的每个进程下次运行的CPU脉冲长度,调度最短的进程。有最短的平均等待时间,可抢占也可非抢占。它吞吐量高、但实现(估计时间)困难,并且存在饥饿现象。

优先级算法根据进程的优先级进行调度。SJF就是它的一个特例。有静态优先权和动态优先权。动态优先权随着进程推进而改变,以便获得更好调度性能,改变的因素有:进程等待时间、已使用处理机的时间、资源使用情况。

RR主要用于分时系统,多个用户/进程共享同一台主机。OS为它们分配时间片,时间片用完后插入就绪队列尾。RR相比于SJF平均周转时间较长,响应时间短。时间片长度较大时类似FCFS,较短时上下文切换开销变大。

多级队列,一个进程处于一个固定的队列,每个队列有自己的调度规则,队列间也需要调度。多级队列间的调度可以有固定优先级调度或时间片轮转调度等。

多级反馈队列调度,多个就绪队列优先级不同,优先级越高时间片越小。进程在队列间移动,进程执行完一个时间片后被抢占,进入低一级的就绪队列。进程从阻塞变为就绪时要提高优先级,I/O型进程会留在较高优先级的队列。每个队列有自己的调度算法,要有决定进程改变队列、进程升降级的规则。

3月第1周

个人的想法

本周走马观花式学习操作系统原理,跟进了一点毕设。

有许多算法值得注意,比如为了实现CPU调度、磁盘调度、页面置换,它们各自都有许多特点的算法:最易实现的、理论最优的、折中的,并不断改进。在评价算法性能时,使用假定的一组/多组序列来进行评估。

内存管理和文件管理都用到了许多数据结构来存储管理信息,它们也往往需要同时考虑逻辑上的需要和硬件的物理特性。

内存管理中的分页、分段,文件管理中将磁盘划分为块,使离散地管理成为可能。但如何消除块内和块间的碎片,如何高效地组织这些块也是需要考虑的。

文件物理结构中使用的索引,十分灵活,充分利用空间的同时能随机存取,值得借鉴。

多级目录和多级索引,使用分层的方法提高了查找效率,方便了数据的组织和管理。

合理设置缓冲可以解决速度的不匹配的问题,提高并行度和系统工作效率。

同步和互斥

多个并发进程/线程可能访问同一共享数据,为保证数据一致性,需要有同步机制保证多个进程对共享数据的互斥访问。进程交互的关系有:互斥,多个进程不能同时使用同一个资源;同步,进程之间协作;死锁,多个进程互不相让,都得不到充足的资源。

使用临界区解决进程间互斥问题。临界区是进程中访问临界资源的一段代码,不同进程的临界区的执行在时间上是互斥的,进程必须请求允许进入临界区。它需要满足互斥、有空让进、有限等待这三个条件。

使用信号量与P、V操作有效解决进程同步。信号量S代表可用资源实体的数量,P(S)表示申请资源、V(s)表示释放资源。实现互斥:为临界区设置初值为1的互斥信号,每个进程的临界区代码都放于P(S)、V(S)原语中;实现同步;设置同步信号初始值为0,前驱进程中执行完前驱代码后进行V操作,后驱进程中先P再执行后驱代码。

用P-V操作解决问题时要关注:同步、互斥的约束条件;互斥的临界资源的抽象/同步关系同步信号量;初始条件;正确的P-V操作。合理设置避免死锁。P-V操作必须成对,可以不在同一进程中。同步P操作应该放在互斥P操作前。

死锁

多个进程由于竞争资源而相互等待,并永远不能再向前推进。等待的进程们都持有资源,并等待其他的进程所持有的资源。产生死锁的原因:竞争资源引起死锁、进程推进顺序不当。

4个条件同时满足时会出现死锁:互斥、进程占有并等待、资源不可抢占、循环等待。对死锁可以采取5个策略:忽略、预防、避免、检测、接触。

  • 忽略:鸵鸟策略
  • 预防:通过限制进程资源请求的方式,打破死锁的4个条件
  • 避免:判断分配资源后是否安全而决定是否分配资源,确保系统不进入不安全状态。可以使用资源分配图,将需求边转换为分配边,看是否有环;银行家算法(用安全检测算法判断是否能找到一个安全序列)判断。
  • 检测:维护等待图,定期检查是否有环;类似银行家算法的检测算法。
  • 恢复:人工处理、终止进程、资源抢占。可以按一定顺序一次终止一个进程直到死锁被打破;可以逐步抢占一些进程的资源,直到打破死锁,但一个进程可能总是被选中产生饥饿。

地址重定位

程序放入内存才可正确运行。可在三个阶段将指令和数据绑定到内存。地址重定位将程序的逻辑地址转换成物理地址。有静态和动态地址重定位,后者需要硬件支持。

内存分配

连续内存分配,为一个程序分配连续的内存空间。单一连续分配和多分区分配。多分区分配有固定分区分配和动态分区分配。

固定分区分配维护一张分区表记录分区大小和使用情况,将内存划分为固定数目和大小的分区。这样易于实现开销小,但是会产生内碎片并且限制并发进程数量。

动态分区分配,分区划分是动态而不预先确定的。使用分区分配算法来寻找并分配内存,有首次适应算法、最佳适应算法等。通过碎片的拼接/紧凑来减少外碎片。只有动态重定位时才能紧凑,并要注意I/O的问题。

分页、分段

离散地管理内存,将程序分为不同的页,将内存的物理地址分为不同的块/页帧,将页放到页帧中。使一个程序能够在内存中离散地存储,不必连续存放,没有外碎片。

分页将程序地址划分成大小相等的页,将内存划分成大小相等的块。有效地址包含页号和偏移,从页表寄存器获得页表始址和页表长度,找到页表的位置。页表中有页号到物理地址中块号的映射,得知块号后再加上偏移,就得到了物理地址。有亮相寄存器TLB做缓存,存储最近用过的页表映射。

分段允许划分大小不等的段和块。有效地址包含段号和偏移,从段表寄存器中获得段表始址和长度,找到段表的位置。段表中存储了从段号和段长到物理地址基址的映射。用有效地址的段号通过段表获得物理基址,加上偏移得到物理地址。完成了程序在内存中的离散存放。

虚拟内存相关

根据局部性原理,一段时间内程序的执行仅局限于某个部分。使用虚拟内存,进程部分装入内存就可以执行。

请求调页,进程需要的页不在内存,请求OS把该页从外存装入内存。主要的过程包含:处理缺页中断,从磁盘读入所需的页(高I/O开销),重新开始被中断的进程/指令。

页面置换,内存空间可能放满,需要在内从空间中找一个空闲帧把它换出去,再换进请求的页。页面置换算法有OPT、FIFO、LRU和LRU的近似,使用特殊的内存访问序列来评价他们的性能。

给进程分配的页数不能小于其所需的最小页数,否则进程不能正常运行。给进程分配页/帧的策略有:平均分配、按比例分配、按优先级分配。该分配可以是一次性固定的分配,也可以是可变分配。进行页面置换时,可以局部替换或全局替换。

频繁地缺页和调页换页导致颠簸。为了防止颠簸,应该给进程提供做够多的帧,降低缺页率。OS要跟踪并为进程分配大于其工作集的物理块数,如果内存还有空闲块,则可启动另外的进程。如果所有进程的工作集之和超过可用物理块总数,OS选择暂停一个进程,换出该进程,释放的物理块可分配给其他进程,防止颠簸/抖动。

文件

文件是记录在外存上的具有名字的相关信息的集合。文件的访问有顺序存取和直接存取。

文件的存储方式与文件逻辑结构和物理存储设备有关。文件在外存的存放组织形式称为文件的物理结构,文件的物理结构取决于外存的分配方式。文件的存储设备划分为大小相等的物理块,是基本单位。

物理结构有连续结构、链接结构、索引结构。FAT文件分配表记录文件所在的各个块,实现随机存取。类似,为每一个文件建立一个索引表,存放该文件的块号。索引表较大时,用链接模式和多级索引解决。

磁盘每个分区中所有文件的信息存放在目录中。文件控制块FCB是用于描述和控制文件的数据结构。文件目录是FCB的有序集合。组织目录的逻辑结构有:单级目录、两级目录、树形目录、无环图结构目录、普通图结构目录等。目录的结构需要考虑:查找效率、命名、共享等问题。

对空闲空间的管理有位图法、空闲块表、空闲块链表、组成链接法等。

文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构(如目录和索引表等)的集合。文件系统分层实现各功能。需要磁盘上和内存中各数据结构的支持。

磁盘

提高I/O速度,硬件:选择高性能的磁盘、设置高速缓冲区;软件:磁盘调度算法。磁盘访问时间由寻道时间+旋转延迟时间+传输时间组成。硬件性能决定了访问时间的大部分,除了寻道时移动的道数。适当的集中数据,并且降低寻道时在不同磁道间移动的距离。

磁盘I/O请求的服务调度算法,目标是更小的寻道时间(寻道距离)。在给定一个请求序列的情况下讨论不同算法的性能。磁盘调度算法有:FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK等。

I/O

I/O设备与设备控制器通信,设备控制器与CPU通信。一般以中断驱动或者DM的A方式驱动I/O,进一步提高CPU和设备的并行程度,提高资源利用率。

OS通过缓冲解决速度不匹配的问题,并且提高CPU和I/O设备间的并行度。有单缓冲、双缓冲、循环缓冲、缓冲池。

设备独立软件解决设备命名、设配分配、设备独立性的问题。设备分配中需要系统设备表、设备控制表、控制器控制表等数据结构。引入逻辑设备和物理设备解决设备独立性的问题,使用逻辑设备表LUT。

设备驱动程序是I/O进程与设备控制器之间的通信程序,使OS以统一的标准和方式对待I/O设备。

通过spooling技术,用一道程序模拟脱机的外围控制机,外围操作与CPU对数据的处理同时进行。提高了I/O速度,实现设备共享,实现了逻辑设备功能(一台物理设备看成是多台逻辑设备)

3月第2周

3月第3周

实习课。本以为回学校后学习氛围浓厚些更容易学习,结果自控力不足,和大家一起都不听课了。没认真听实习课,有些后悔。

浮点数

IEEE的浮点数表示规则。4种舍入方式,默认向偶数舍入。会向无穷溢出。浮点数运算不满足结合性。注意floatdoubleint间的类型转换时的精度损失。

机器级程序基础

以下为AT&T格式汇编

寄存器带有%r,为64位;寄存器带有%e,为32位寄存器。例如:%rax(64bits),%eax(32bits), %ax(16bits), %ah, %al。

8086中,long word为4字节,quad word为8字节。movq中的q指quad

1
movq (%rdi), %rax

注意源和目的的顺序

1
shrq Src, Dest    Dest = Dest >> Src   logical

一种寻址方式:D(Rb, RI, S),选中Men[Reg[Rb]+S*Reg[Ri]+D]中的内容。其中D是偏移常量,S即Scale。使用它可以实现乘k操作:

1
2
leaq (%rdi, %rdi, 2), %rax
# 将3倍%rdi(作为地址)放进%rax

3月第4周

记住比较函数

STL中,如setpriority_queue等需要按一定规则排序,用到了比较函数。常用的默认比较函数是less和greater,却难以记忆。

记忆方法:使用一个数组来辅助记忆,假设有一个数组,从索引为0(在左)开始,向索引增大的方向看(从左向右看)。less使左侧值<右侧值,greater使左侧值>右侧值。

1
2
3
4
5
6
7
8
// STRUCT TEMPLATE less
template <class _Ty = void>
struct less {
...
constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const {
return _Left < _Right;
}
};

set中,默认less,左<右,升序排列。

1
2
// CLASS TEMPLATE set
template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>

priority_queue中,默认less,左<右。左侧为队尾,右侧为队首。将其看做堆的话,右侧为堆顶较大,因此默认的less构成大顶堆。

1
2
// CLASS TEMPLATE priority_queue
template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
1
2
3
4
5
6
7
vector<int> v{ 2, 1, 33, 3 };
priority_queue <int> q{ v.begin(), v.end() };
while (!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
//33 3 2 1

algorithm库中的sort函数也是类似,他有一个重载默认用less(与前面的less不是同一个),也是左<右,升序排列。

1
2
template <class _RanIt, class _Pr>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred)
1
2
vector<int> v{ 2, 0, 1, 2, 2 };
std::sort(v.begin(), v.end()); //0 1 2 2 2

建立连接示例tcp socket

go的示例

client方,使用 DialTCP建立连接,使用返回的TCPConnReadWrite函数进行读写

1
2
3
4
5
6
7
8
//pacakage net
func DialTCP(network string, laddr, raddr *TCPAddr) (*TCPConn, error) //建立连接

//TCPConn是conn的“派生类”
//package net
func (c *conn) Read(b []byte) (int, error) //read
func (c *conn) Write(b []byte) (int, error) //write

例如

1
2
3
4
conn, err := net.DialTCP("tcp", nil, tcpAddr)
checkError(err)
_, err = conn.Write([]byte("xxx"))
checkError(err)

server方,使用ListenTCP监听端口,用Accept()建立连接

1
2
3
4
// package net
func ListenTCP(network string, laddr *TCPAddr) (*TCPListener, error)

func (l *TCPListener) Accept() (Conn, error)

例如

1
2
3
4
5
6
7
8
9
listener, err := net.ListenTCP("tcp", tcpAddr)
checkError(err)
for {
conn, err := listener.Accept()
if err != nil {
continue
}
go doSomething(conn)
}

websocket

使用“轮询”的浏览器要不断地对服务器发送请求。二者使用websocket则可以在握手后一直保持连接,一对c/s只建立一个tcp连接,服务端也可以推送数据到客户端。

url的协议字段使用ws://或wss://

1
2
var url = "ws://localhost:9989";
sock = new WebSocket(url);