操作系统.md

用户态与内核态

• 内核态：在内核态下代码拥有硬件的所有权限,可以任意访问物理内存地址,拥有外围设备的绝对控制权。同时这也是非常不安全的,错误的代码可能会导致系统崩溃,恶意代码可能会导致灾难性的后果。
• 用户态：用户态下的代码只能进行有限的操作,不能直接访问物理内存与外围设备。用户态下的操作被系统监视和限制。相对与内核态更加的安全,即使代码出错也不会对系统造成灾难性的后果。
• 系统调用：操作系统通过提供系统调用使得进程可以从用户态进入内核态,从而完成一些只有在内核态下才能完成的操作。
• 用户态与内核态的转换：CPU通过trap指令将进程从用户态切换为内核态,为了限制进程在内核态的行为,操作系统在启动时建立一个trap table其中包含着trap handler,根据trap进内核态的目的执行相应的trap handler。
  1. 系统调用
  2. 上下文切换

内存管理

虚拟内存（Virtual Memory）

操作系统为每个进程虚拟化出独立的逻辑地址空间,这个空间大小与操作系统位数有关（如：2^32bytes或2^64bytes）

分页（Page）

操作系统将内存划分为固定大小的页,分配内存时按页分配。

• 页表（Page Table）
  操作系统将物理内存划分为多个页框（Page Frame）每个页框有自己的页框号（Page Frame Number）页框内为一片连续存储的内存。
  操作系统将每个进程的虚拟内存地址划分为两部分：高位为虚拟页号（VPN）低位为在虚拟页中的偏移（Offset）
  每个进程都有自己的页表（Page Table）,页表由页表入口（Page Table Entry）组成,PTE不仅包含VPN与PFN的对应关系,还有一些功能位分别表示这个页是否时可读的（protection bit）、是否是有效的（valid bit）、是否被更改过（dirty bit）、对应的数据是在硬盘还是在内存中（present bit） 等等。
  当进程用虚拟内存地址访问内存时,硬件中的内存管理单元（MMU）将VPN翻译为PFN,offset不变。由于虚拟内存并不完全对应物理内存,一部分虚拟内存可能对应在磁盘空间上。当访问的虚拟内存地址不再物理内存上时,将发生缺页中断,此时会将数据从硬盘加载到物理内存当中。
• 快表(Translation-Lookaside-Buffer)
  如果每次访问内存都需要MMU将虚拟内存转化为物理内存,会一定程度上影响效率。所以引入TLB这个概念,TLB是MMU的一部分,功能可以理解为内存地址翻译的cache。每当MMU进行地址翻译的时候先查找TLB中是否有VPN-PFN对应关系,如果TLB中没有这个对应关系再去页表中查找对应关系并对TLB进行替换。
• 多级页表
  如果每个页框中包含的内存较多,那么就更容易造成内存碎片。如果包含的内存较小,那么就需要更多的VPN-PFN对应关系也就需要更大的页表。我们假设在一个32位系统中,意味着我们有4GB（2^32字节）的地址空间,每个页的大小为4KB,则offset为12位VPN为20位,每个PTE为4字节,那么每个进程便需要4MB大小的页表,如果系统运行100个进程,那么仅仅为了内存翻译就需要400MB！
  多级页表可以说是由增加时间复杂度降低空间复杂度的思想而来。简单来说我们将VPN进行划分,高位VPN对应高级页表,地位VPN对应低级页表,高级页表中包含低级页表位置的对应关系,最低级的页表包含PFN的对应关系,类似于数据库的B+树。
  例如，如果我们要访问虚拟地址0x12345000，我们可以这样理解：1.将地址0x12345拆分为两部分，其中0x123（十进制表示为291）是外部页表索引，0x45（十进制表示为69）是内部页表索引。2.操作系统首先使用这个外部索引291来在外部页表中找到对应的内部页表。3.接下来，操作系统使用内部索引69在找到的内部页表中找到对应的实际物理地址。
• 替换算法
  • FIFO（First In First Out）：
    页被存放在队列当中,每次加入新页都将其置于队头,当需要替换时将队尾的页淘汰掉（即最先进入的页）。
  • LRU（Least Recently Used）：
    页被存放在链表中,每次加入新页都将其置于链头,每当页命中时将命中页插入链头,当需要替换时将链尾的页淘汰掉（即最近一段时间访问次数最少的页）。
  • LFU（Least Frequently Used）：
    记录每个页的命中次数,当需要替换时将命中次数最少的页淘汰掉（即访问次数最少的页）。
  • Clock算法：
    页被存放在环形链表中,链表中有一个指针指向页,每当页命中时将页的引用位（reference bit）置为1（默认为0）,当需要替换时如果指针指向的页引用位为0将此页替换并将指针前移,如果指向的页引用位为1便将引用位设为0并前移指针。

分段（Segment）

分配内存时操作系统根据请求的大小,在合适的位置划分出一块制定大小连续的内存段。

• 段表（Segment Table） 段表内包含所有被分配的段,每个段有两部分组成：基础地址（Base Address）表示这个段的起始物理地址,界（Bound）表示这个段的长度。
  操作系统将每个进程的虚拟内存地址划分为两部分：高位为段号（Segment Number）低位为在段中的偏移（Offset）。
  当进程用虚拟内存地址访问内存时,根据段号在段表中找到相应的段,物理内存地址为此段的基础地址+偏移。
• 分配策略
  当当内存经过多次分配与释放后,空闲内存被各个内存段所隔离开,这就是外部内存碎片。为了减少内存碎片我们需要使用合适的分配策略。
  • 最佳适应法（Best Fit）
    遍历整个空闲内存表,找到满足分配需求的最小空闲内存块。
    特点：每次分配给文件的都是最合适该文件大小的分区。
    缺点：内存中留下许多难以利用的小的空闲区。
  • 最差适应法（Worst Fit）
    遍历整个空闲内存表,找到内存表中最大的空闲内存块。
    特点：给文件分配分区后剩下的空闲区不至于太小,产生碎片的几率最小。
    缺点：使存储器中缺乏大的空闲区,对大型文件的分区分配不利。
  • 首次适应法（First Fit）
    从空闲内存表的首位按顺序查找,找到第一个能满足分配需求的空闲内存块。
    优点：该算法倾向于使用内存中低地址部分的空闲区,从而保留了高地址部分的大空闲区,为之后的大块分配请求创造条件。
    缺点：低地址部分不断被划分,留下许多难以利用、很小的空闲区,而每次查找又都从低地址部分开始,会增加查找的开销。
  • 循环首次适应法（Next Fit）
    从上一次分配内存的位置开始按顺序查找,找到第一个能满足分配需求的空闲内存块。
    特点：使内存中的空闲分区分布的更为均匀,减少了查找时的系统开销。
    缺点：缺乏大的空闲分区,从而导致不能装入大型作业。
  • 分离链表（Segregated List）
    由于每次分配时都要对空闲列表进行遍历,如果分配请求的大小比较固定,那么就可以从空闲列表中分离出一部分。那么特殊大小的分配请求就可以从分离链表中遍历,从而减小遍历时的开销。
  • Buddy分配
    例如：buddy算法将所有空闲页框分组为10个块链表,每个块链表的每个块元素表示分别包含1,2,4,8,16,32,64,128,256,512个连续的页框（2^n）。
    假设要请求一个128个页框的块,算法先检查128个页框的链表是否有空闲块,如果没有则查256个页框的链表,有则将256个页框的块分裂两份,一份使用,一份插入128个页框的链表。
    假设要请求一个128个页框的块,算法先检查128个页框的链表是否有其伙伴块,如果有就将它们两个合并并存储到256个页框的链表。

Linux内存分配API

int brk(void *addr)
brk()将进程的program break改变为参数addr指定的位置,成功时返回0,失败时返回-1。该系统调用可以用来改变堆内存中堆顶的大小。
void *sbrk(intptr_t increment)
sbrk()将program break的值加上increment(有符号整数)作为新的program break,并返回原先的program break值。该系统调用可以用来改变堆内存中堆顶的大小。
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset)
mmap()可以将一个文件映射到进程的虚拟内存空间上并非堆上,文件被映射到进程地址空间后,进程可以向访问普通内存一样对文件进行访问,不必再调用read()、write()。mmap有两大作用,一是改变文件的IO方式一定程度上降低开销,二是实现内存共享。
addr：映射区的开始地址,设置为0时表示由系统决定映射区的起始地址。
length：映射区的长度。
prot：期望的内存保护标志,如PROT_EXEC、PROT_READ、PROT_WRITE、PROT_NONE。
flags：指定映射对象的类型。
fd：文件描述符。一般是由open()函数返回,其值也可以设置为-1,此时需要指定flags参数中的MAP_ANONYMOUS,表明进行的是匿名映射。
offset：被映射对象内容的起点。
成功时,mmap()返回映射区的指针,失败时返回-1（MAP_FAILED）
int munmap(void *addr, size_t length)
进程调用munmap()解除一个该进程虚拟内存空间上的一个映射关系,addr指向映射区（即mmap返回的指针）,length为映射区大小。

进程与线程

进程

简单的说进程就是一个运行中的程序（可执行文件）

• 进程内存布局
  
  1. 栈（stack）
     位于高地址,空间向低地址增长,用来存储进程的局部变量。
  2. 堆（heap）
     空间向高地址增长,用来存储进程运行时分配的内存。
  3. bss段
     大小固定,用来存储未初始化的静态变量与全局变量。
  4. data段
     大小固定,用来存储已经初始化的静态变量与全局变量。
  5. text段
     大小固定,一般为只读,用来存储进程的代码。
  • 堆溢出与栈溢出
    • 缓冲区溢出
      在调用某些函数(如:gets(),scanf(),strcpy(),sprintf())向缓冲区写入数据时,在缓冲区无法承载这些数据的时候这些函数并不作出检查而是继续越界写入数据,并且不会导致段错误。如果缓冲区是栈中的数据还可能会导致函数的返回地址被破坏。
    • 栈溢出
      每个进程的最大栈空间有一定限制,一般为几MB,如果超出这个限制将会导致段错误。比如定义的数组过大,或者函数无限递归导致不断的定义局部变量。可以使用ulimit -s命令查看栈的大小也可以修改栈的大小。
• 进程属性
  操作系统为每个进程设定一组特定属性,用来描述进程。
  1. pid
     每个进程都有一个独一无二的进程号,用来识别进程。
  2. ppid
     用来记录创建这个进程的pid。
  3. 文件描述符
     16位无符号整数,用来表示进程打开的文件（套接字、I/O设备、等等）。
  4. 进程状态
     表示进程当前的状态,一般分为运行、就绪、阻塞。
  5. CPU寄存器
     如程序计数器（PC）：记录当前执行的指令。
  6. 调度信息
     记录进程的调度优先级等等。
• 孤儿进程
  当父进程退出后如果子进程还没有退出,此时子进程变会成孤儿进程。孤儿进程被托付给init进程（内核启动的第一个进程）,此时init进程为孤儿进程的父进程,由init进程对孤儿进程进行回收。
• 僵尸进程
  当子进程退出后如果还未被父进程回收,此时子进程便会成僵尸进程。此时父进程会收到SIGCHLD信号,表示有子进程需要被回收。
• 守护进程
  守护进程是脱离终端并在后台运行的进程,执行过程中信息不会显示在终端上并且也不会被终端发出的信号打断。
  1. 创建子进程,终止父进程：fork();if(pid > 0){exit(0);},使子进程称为孤儿进程被init进程收养。
  2. 在子进程中创建新会话：setsid();。
  3. 改变当前目录结构为根：chdir("/");。
  4. 重设文件掩码：umask(0);。
  5. 关闭文件描述符：for(int i = 0; i < 65535; ++i){close(i);}。
• Linux进程API
  pid_t fork(void)
  父进程调用fork()创建一个与自己完全一样（包括当前执行到的位置）的子进程。子进程在创建时会复制父进程的页表,在之后进行写操作的时候再复制父进程的内存（copy-on-write）。
  void exit(int status)
  当进程调用exit()时,进程执行之前使用atexit()注册的exit回调,刷新stdio缓冲区,进程的终止状态被更改为参数status（0表示成功,非0表示失败）。
  pid_t wait(int *status)
  父进程调用wait()后会阻塞在wait()中,检查自己是否有子进程退出,如果有wait()会收集这个子进程的状态并返回pid,如果没有,父进程会一直阻塞在wait()中。
  int execv(const char *path, char *const argv[])
  当进程调用execv()时,进程以argv作为参数加载path指定的程序,当前进程内存中的所有数据都将被替换。当返回-1时代表错误发生。
  pid_t vfork(void)
  在早期的版本中调用fork()时需要对父进程的内存数据进行完全复制,但有的时候fork()之后子进程就调用execv()执行别的程序了,这样一来完全复制就显得很浪费。vfork()为了解决这个问题,使得子进程的创建完全共享父进程的内存不进行复制。调用vfork()后父进程会挂起,直到子进程调用execv()或exit()才会恢复执行。注意vfork由于完全共享父进程的内存,有时候可能会造成一些很难发现的bug,比如当在vfork()出的子进程主函数调用return返回,那么这时父进程的调用栈也会被影响,此时当父进程继续执行时父进程就会崩溃。

线程

线程在进程之内,一个进程可以包含多个线程,线程与创建它的进程共享一部分资源,线程时操作系统调度的基本单位。

• 线程内存布局
  
  可以看出线程有自己独立的栈空间,与进程共享全局变量,共享一部分内存空间与包含的头文件,执行的代码包含在进程的代码内。
• linux线程API
  int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg)
  调用pthread_create()创建线程,线程tid保存在参数thread内,attr表示线程的属性（如是否分离,调度策略等）,线程执行start_routine函数指针指向的函数,arg作为函数的参数。函数返回0时为成功其它为错误并改变errno。
  int pthread_join(pthread_t thread, void **value_ptr)
  调用pthread_join()会阻塞在函数中,等待参数thread指定的线程执行完毕,并将线程的返回值存在value_ptr中。函数返回0时为成功其它为错误并改变errno。
  int pthread_detach(pthread_t thread)
  使参数thread指定的线程与它的创建者分离,此时当分离线程执行完毕后自动销毁创建者不再等待并回收它的返回值。函数返回0时为成功其它为错误并改变errno。

线程与进程

在C语言中我们通过pthread_create()创建线程,而pthread_create()底层调用Linux系统API clone(),而clone()正是一种创建进程的函数,只不过clone()创建出的进程与父进程共享很多资源。在Linux内核中调度时并没有对线程与进程进行区分,只有内核调度实体（Kernal Scheduling Entry）这个概念。
线程的出现解决的最大的问题就是它可以更简单的进行资源共享,因为进程和它创建的线程处在同一个虚拟内存空间内,也就是说线程共享进程的页表,这样一来线程看到的物理资源与进程是一样的。并且当上下文切换时,如果上文线程和下文线程是一个进程创建的,那么它们之间共享的资源就不需要进行切换,从而减少上下文切换的开销。

调度策略

对于多任务操作系统一般有多个进程运行在操作系统上,以什么样的策略来执行这些进程就叫做调度。

• FIFO（First In First Out）
  即先到达的任务先执行,直到执行完毕后再执行下一个任务。FIFO为非抢占式调度。如果先到达的任务执行时间过长,那么后面的任务就得不到执行,平均周转时间较长。
• SJF（Shortest Job First）
  即每次先执行当前等待任务中完成时间最短的任务,正在执行的任务不受影响。SJF为非抢占式调度。由于时非抢占式调度,如果长任务提前于短任务到达,那么短任务依然得不到执行,平均周转时间仍旧较长。
• STCF（Shortest Time to Completion First）
  STCF可以理解为抢占式的SJF,即每次先执行当前所有任务中剩余完成时间最短的任务。但是这又带来了新的问题,长任务可能会长时间得不到响应,平均响应时间较长。
• RR（Round-Robin）
  每当执行一个任务时启动一个定时器（时间片）,当定时器超时后以同样的超时时长重置定时器并执行下一个任务。平均响应时间较低,但平均周转时间较长。
• MLFQ（Multi-Level Feedback Queue）
  MLFQ由多个不同优先级的队列组成,以以下方式进行调度：
  1. 如果任务A的优先级大于任务B,那么任务A先执行。
  2. 如果任务A的优先级等于任务B,任务A、B以RR的方式执行。
  3. 新任务到达时被置于最高优先级的队列。
  4. 每个队列都有一个时间片（高优先级队列时间片小,低优先级时间片大）,当一个任务用完它的时间片（时间片不包含IO时间,CPU在任务进行IO时执行其它的任务）它的优先级会被降低一个级别。
  5. 每隔一段时间就把所有的任务都置于最高优先级的队列。

并发

并发执行与顺序执行相对应。顺序执行为：后面的任务需要等待前面的任务执行完毕才能够被执行。并发执行为：在一个时间段这些任务可以被同时执行,如果处理单元数量小于任务数量那么这些任务将会交错的被执行。如果处理单元数大于任务数量那么这些任务就可以在统一时刻被执行,这就是并行。

竞争条件（Race Condition）

当多个任务并发的操作共享对象时,如果结果与这行任务的执行顺序有关,那么这就是竞争条件。
一般来说如果上述的操作包含写操作,那么很可能会发生竞争条件。如果共享对象是只读的,那么一般不会发生竞争条件。
例如进程内有两个线程并发的对一个全局变量递增10000次,但执行后全局变量的结果可能并不是20000。因为一个递增语句在x86平台下可能会被编译成如下指令：

mov 0x8049a1c %eax  
add 0x01 %eax  
mov %eax 0x8049a1c

第一步现将位于地址0x8049a1c的全局变量加载到寄存器eax中,第二步将寄存器eax内的值加1,第三步将寄存器eax中的值移回全局变量中。
假设线程1在执行到第二步的时候发生上下文切换,此时线程2执行一段时间后线程1执行,当线程1执行完第三步后之前线程2进行的递增便都被覆盖掉了,此时全局变量中的值是无法预测的。

锁

我们可以看出,发生竞争条件的主要原因是因为并发操作共享对象时,由于执行某些操作时被系统打断,从而导致执行结果不确定。锁通过互斥的方式来保证一个任务操作共享对象时不会被别的任务打断。
一般来说锁大部分都是基于test-and-set这种原子操作下实现的。可以理解为以下代码的行为：

int test_and_set(int *ptr, int new)
{
    int old = *ptr;
    *ptr = new;
    return old;    
}

锁的实现可以简单理解为：

void init(lock_t *lock)
{
    test_and_set(lock, 0);
}

void lock(lock_t *lock)
{
    while(test_and_set(lock, 1) == 1) { //waiting }
}

void unlock(lock_t *lock)
{
    test_and_set(lock, 0);    
}

• 自旋锁
  自旋锁采用busy-waiting的策略,即在进行lock操作时如果锁已被lock那么就陷入while循环中,一直等待到锁被unlock。与互斥锁相比较更适合执行相对较快的临界区加锁,因为自旋锁不主动放弃cpu资源,一定程度上减少了由上下文切换导致的开销。
• 互斥锁
  互斥锁采用sleep-waiting的策略,即在进行lock操作时如果锁已被lock那么就放弃cpu资源进入阻塞状态。与自旋锁相比较更适合执行相对较慢的临界区加锁,因为互斥锁主动放弃cpu,避免cpu资源的浪费。
• 读写锁
  读写锁将对共享对象的操作分为读操作和写操作。在进行读操作的时候对读写锁加读锁,如果当前读写锁没被加写锁则加读锁,如果有则等待写锁释放;在进行写操作时加写锁,如果当前读写锁没被加写锁与读锁则加写锁,如果有则等待所有读锁写锁释放。

条件变量

有些时候我们希望一个任务等待另一个任务的执行满足某种条件后再执行,这时候就需要条件变量来实现不同任务之间的同步,从而使得不同任务的执行有一定的次序。条件变量的一般使用方式为：

while(condition_not_satisfy)
{
    cond_wait(&condition_variable, &mutex);
}

在任务A中,如果某个条件暂时不满足那么就阻塞在与变量condition_variable关联的wait操作中并解锁互斥锁mutex,等待被另一任务唤醒。
与互斥量同时使用的原因是为了确保检验条件是否满足这个操作本身的原子性。 使用while语句检查条件而不使用if语句的原因是,当任务从wait中被唤醒时再次检查条件是否满足,如果不满足就继续wait。如果使用if语句,当任务A被任务B唤醒后并没有立刻开始执行,由于系统调度的随机性此时任务C开始执行,而任务C的执行又导致条件不满足,由于使用if语句此时任务A不再检查条件是否满足便执行接下来的代码,这样就失去了我们使用条件变量的意义。

cond_signal(&condition_variable);

任务B调用cond_signal()来随机唤醒一个阻塞在与condition_variable关联的wait操作中的任务,具体哪个任务被唤醒由系统的调度决定。

信号量

信号量可以用来限制进入临界区的线程数量,也可以用来做资源数量管理。信号量有两个主要操作。

sem_wait(&semaphore);

如果semaphore参数大于0,将semaphore减1并返回。如果semaphore等于0,任务被阻塞直到semaphore大于0,此时将semaphore减1并返回。sem_wait()也叫做P操作。

sem_post(&semaphore);

将semaphore参数加1,如果先前semaphore参数为0,那么就随机唤醒一个阻塞在sem_wait中的任务。sem_post()也叫做V操作。

死锁

当任务A在直接或间接的在等待任务B,而任务B在直接或间接的在等待任务A,那么任务A、B都无法继续执行,这就是死锁。

• 死锁的产生
  1.互斥条件：当一个任务使用某一资源时,其他任务不得使用。
  2.请求和持有条件：一个任务在持有资源的同时又请求新的资源。
  3.不可抢占条件：在一个任务使用完资源之前,其他任务不能抢占该资源只能等待其被主动释放。
  4.循环等待条件：一个集合的任务以循环的方式互相等待对方。
• 死锁的预防
  1.破坏互斥条件：使资源可以被共享,即多个任务可同时使用某一资源。
  2.破坏请求和持有条件：当一个任务持有一个资源时不得请求其它资源。
  3.破坏不可抢占条件：在一个任务使用资源的同时设定一个时间阀值,达到阀值后主动释放资源。
  4.破坏循环等待条件：以固定的顺序分配资源。
• 银行家算法

进程间通信（InterProcess Communications）

通信

通过IPC实现不同进程间数据的交换

• PIPE
  int pipe(int fd[2])
  fd[0]用来读取数据,fd[1]用来写入数据。
  • PIPE又叫作无名管道,位于内存当中。
  • PIPE以字节流的方式传输数据,PIPE内的数据不会被分割成消息段。
  • PIPE只能用来单向传输数据,以半双工的方式工作。
  • PIPE只能在有祖辈关系的进程间使用,因为子进程创建时会复制父进程的文件资源。
    
• FIFO
  int mkfifo(const char *pathname, mode_t mode)
  在pathname指定的位置创建一个文件,以mode作为文件的权限（如果pathname指定的位置已存在文件则函数执行失败）。
  成功创建FIFO后便可以用访问普通文件的方式进行open(),read(),write(),close。
  • FIFO又叫作有名管道,位于文件同当中。
  • 由于FIFO位于文件系统当中,即使使没有祖辈关系的进程也可以使用。
• 消息队列
  mqd_t mq_open(const char *name, int oflag)
mqd_t mq_open(const char *name, int oflag, mode_t mode, struct mq_attr *attr)
  mq_open打开一个已存在的消息队列或新建一个消息队列。name表示消息队列的名字,oflag为位掩码表示对消息队列的控制方式（O_RDWR,O_EXECL,O_NONBLOCK）,如果是创建新的消息队列mode表示新消息队列的权限,attr表示新消息队列的属性。执行成功时返回消息队列描述符。
  int mq_send(mqd_t mqdes, const char *msg_ptr, size_t msg_len, unsigned int msg_prio)
  mqdes表示要添加到的消息队列,msg_ptr表示消息的内容,msg_len表示消息的长度,msg_prio表示消息的优先级,消息以优先级降序的方式排列0最低,新到达的消息位于同优先级消息的后面。成功时返回0。消息队列已满且没有O_NONBLOCK flag时阻塞在该函数中。
  ssize_t mq_receive(mqd_t mqdes, char *msg_ptr, size_t msg_len, unsigned int *msg_prio)
  mqdes表示要添加到的消息队列,msg_ptr表示消息的接收缓冲区,msg_len表示缓冲区的长度,msg_prio用来存储接收消息的优先级。成功时返回接受消息的字节。消息队列为空且没有O_NONBLOCK flag时阻塞在该函数中。
  int mq_close(mqd_t mqdes)
  将mqdes指定的消息队列关闭,消息队列被关闭后依然能被其它进程使用。
  int mq_unlink(const char *name)
  将name指定的消息队列删除,消息队列被删除后不能被任何进程使用。
  • 消息队列的生命周期与内核相关,进程的终止不会导致消息队列被删除,可以被所有的进程使用。
  • 消息队列以消息段的方式存储消息,每次发送必须发送一个完整的消息段,每次接收只能接收一个完整的消息段。
• 共享内存
  通过shm_open()创建或打开一个共享内存对象,并使用mmap()对该对象建立内存映射,此时可以调用msync()来确保共享内存对象中的数据与内存映射中的数据完全一致,使用完毕后调用munmap()解除映射,最终可调用shm_unlink()删除共享内存对象。
  int shm_open(const char *name, int oflag, mode_t mode)
  创建一个共享内存对象,name为共享内存对象的名字,oflag为位掩码表示对共享内存对象的控制方式,mode为共享内存对象的权限。成功时返回共享内存对象的文件描述符。
  int shm_unlink(const char *name)
  将name指定的共享内存对象删除,共享内存对象被删除后并不影响那些仍就存在的内存映射。
  • 新创建的共享内存对象以文件的形式存储在/dev/shm目录下。
  • 共享内存对象的生命周期与内核相关,进程的终止不会导致其被删除,可以被所有的进程使用。
• 套接字
  可以使用unix域名套接字来进行IPC,与internet域名套接字不同之处在于：
  调用socket函数时函数的第一个参数是AF_UNIX而不是AF_INET。
  调用bind和connect函数时第二个参数的实际类型是struct sockaddr_un而不是struct sockaddr_in。

  struct sockaddr_un 
  {
       sa_family_t sun_family;   /* Always AF_UNIX */
       char sun_path[108];       /* Null-terminated socket pathname */
  };
  

  sun_path一般为一个文件目录如"/tmp/unix_socket",进程间以这个文件作为数据缓冲区进行通信。

同步

通过IPC实现不同进程间执行的同步

• 信号量
  sem_t* sem_open(const char *name, int oflag)
sem_t* sem_open(const char *name, int oflag, mode_t mode, unsigned int value)
  打开或创建一个有名信号量,value表示信号量的初始值。成功时返回一个指向有名信号量的指针可用它作为PV操作的参数。
  int sem_close(sem_t *sem)
  将sem指向的信号量关闭,信号量被关闭后依然能被其它进程使用。
  int sem_unlink(const char *name)
  将name指定的信号量删除,信号量被删除后不能被任何进程使用。
  • 新创建的有名信号量以文件的形式存储在/dev/shm目录下。
  • 有名信号量的生命周期与内核相关,进程的终止不会导致其被删除,可以被所有的进程使用。
• 文件锁
  多进程并发的操作文件同样会造成竞争条件,所以需要加锁保护。
  int flock(int fd, int operation)
  对fd指定的文件执行operation指定的操作,operation有以下4个掩码：
  LOCK_SH：对文件加一个共享锁。
  LOCK_EX：对文件加一个独占锁。
  LOCK_NB：以非阻塞的方式对文件加锁。
  LOCK_UN：对文件解锁。
  共享锁与独占锁的关系如下：
  
  int fcntl(int fd, int cmd, struct flock *flockstr)
  不同于flock()对整个文件加锁,fcntl()可以对指定的段落加锁。 cmd的以下3个掩码与文件锁有关：
  F_RDLCK：对指定文件指定段落加读锁。
  F_WRLCK：对指定文件指定段落加写锁。
  F_UNLCK：解除当前进程加的锁。
  参数flockstr表示具体的段落,struct flock的代码如下：

  struct flock 
  {
       short l_type;    /* Type of lock: F_RDLCK, F_WRLCK, F_UNLCK */
       short l_whence;  /* How to interpret l_start:SEEK_SET, SEEK_CUR, SEEK_END */
       off_t l_start;   /* Starting offset for lock */
       off_t l_len;     /* Number of bytes to lock */
       pid_t l_pid;     /* PID of process blocking our lock(set by F_GETLK and F_OFD_GETLK) */
  };
  

信号

信号是软件中断,无论合适何时进程收到信号,进程都会被立刻打断并由内核执行相应的回调函数,执行完毕后回复进程的执行。信号(signal)机制是Unix系统中最为古老的进程之间的通信机制。它用于在一个或多个进程之间传递异步信号,异步表示进程预先不知道信号准确发生的时刻。
void ( *signal(int sig, void (*handler)(int)) ) (int)
将sig指定的信号的信号回调函数设置为handler指向的函数,返回原信号回调函数指针。当第二个参数为SIG_IGN时忽略除了SIGKILL与SIGSTOP之外的信号,为SIG_DFL时执行默认回调函数。
int kill(pid_t pid, int sig)
向pid指定的进程发送sig指定的信号。
int raise(int sig)
向自身发送sig指定的信号。
int pause(void)
将进程挂起直到捕捉到信号为止。
unsigned int alarm(unsigned int seconds)
在进程中设置一个定时器,到时会向进程发送SIGALARM信号。一个进程只能有一个闹钟时间,如果调用alarm()之前已经设置了闹钟时间,那么任何以前的闹钟时间都会被新值所代替。

文件系统

一个硬盘往往被划分为多个分区,每个分区都由一个文件系统管理,文件系统负责组织文件。

Boot block

Boot block为文件系统的第一个block,Boot block不被文件系统使用。Boot block中包含boot操作系统所需要的信息。每个文件系统都有一个Boot block,但操作系统只使用其中一个Boot block。

Super block

Super block是文件系统的第二个block,Super block负责记录,每个data block的大小,所有data block的大小的和,inode表的大小。

I-node table

I-node表负责记录所有的I-node(大小固定),每个文件/目录都与一个I-node一一对应,每个I-node都有一个I-node号,I-node记录文件的以下信息:

• 文件的字节数
• 文件拥有者的User ID
• 文件的Group ID
• 文件的读、写、执行权限
• 文件的时间戳,共有三个：ctime指inode上一次变动的时间,mtime指文件内容上一次变动的时间,atime指文件上一次打开的时间。
• 链接数,即有多少文件名指向这个inode
• 文件所有的block的指针
  由于I-node的大小固定,当文件较大,block数较多时,仅凭一个I-node将无法存储所有的block指针。此时通过间接block指针记录文件的block,即I-node存储一级block指针,一级block存储二级block指针,二级block存储三级block指针,三级block存储数据block的指针。

Data blocks

Data block用来存储文件的实际数据,每个Data block的大小固定,一般为4KB。

• 打开一个文件的过程
  例如打开文件/home/data.txt 首先根据/的I-node找到/的data block的指针访问/的data block找到home的文件名与I-node号的对应;再根据home的I-node找到home的data block的指针访问home的data block找到data.txt的文件名与I-node号的对应;再根据data.txt的I-node找到data.ext的data block的指针访问data.txt的data block。
• 创建一个文件的过程
  首先在I-node表中分配一个空闲的I-node并记录文件的信息,在上级目录的data block中记录文件名与I-node号的对应关系,此时该文件的data block指针为空,当向文件写入数据时文件系统为其分配data block。
• 删除一个文件的过程
  删除I-node表中该文件的I-node,再删除上级目录中该文件名与I-node的对应关系,当硬链接数为0时释放文件的data blocks。
• 链接
  
  • 硬链接
    当我们执行ln file filehl命令后,在当前目录的data block中添加一个文件名 I-node号对应,文件名为filehl,I-node号为file的I-node号。这时就有两个文件file与filehl分别对应这同一个I-node号。
  • 软链接
    当我们执行ln -s file filesl命令后,在当前目录创建一个文件filesl,通过文件filesl可以访问到原文件file

硬件

寄存器(Register)

是中央处理器（CPU）内部的小型存储区,可用于存储指令、数据和地址。寄存器是计算机中最快速的存储区,因为它们是直接在 CPU 内部实现的。然而,寄存器的数量有限且存储容量小,因此只用于存放 CPU 当前正在使用的数据。
在x86-64架构中,每个核心的寄存器配置大致如下：

• 一组16个64位的通用寄存器,每个可以存储一个64位整数或指针。这些寄存器被称为RAX、RBX、RCX、RDX、RBP、RSP、RSI、RDI,以及R8到R15。
• 一组8个80位的浮点寄存器,每个可以存储一个80位的浮点数。这些寄存器被称为ST（0）到ST（7）。
• 一组16个128位寄存器,每个可以存储一个128位的包含多个整数或浮点数的向量。这些寄存器被称为XMM0到XMM15。
• 在支持AVX（存储在YMM寄存器中）和AVX-512（存储在ZMM寄存器中）指令集的新一代处理器中,还有更多、更大的向量寄存器。

以上所述是逻辑寄存器的数量,实际的物理寄存器（即重命名寄存器）的数量通常要大得多,但对于程序员和高级语言编译器来说,这是透明的,因为他们只与这些逻辑寄存器打交道。具体的物理寄存器数量取决于CPU的设计,可以达到几百到上千个。这是用于支持超线程技术的一部分,如指令流水线的并发执行、指令级并行等技术。

SRAM(Static Random Access Memory)

用于CPU 的高速缓存,比如 L1、L2 和 L3 缓存,这些都是 CPU 内部或接近 CPU 的高速缓存存储区,用于临时存储正在使用或预计会使用的数据和指令,以减少访问主内存的时间。L1 缓存最接近 CPU（访问速度最快）,L2 缓存次之,L3 缓存再次之。一般来说,缓存级别越低,大小越大,但访问速度越慢。SRAM 的访问速度非常快,但其制造成本高,密度低（相对于 DRAM）,因此缓存的大小通常受到限制。在将内存中的数据加载到寄存器时,硬件(CPU和内存管理单元)和操作系统内核负责数据在DRAM和SRAM之间的移动和同步。

DRAM(Dynamic Random Access Memory)

是计算机的主内存,用于存储运行中的程序和正在使用的数据。DRAM 的容量比寄存器和缓存大,但访问速度较慢。DRAM 需要周期性刷新来维持存储的数据。使用汇编语言中的mov指令可以将内存中的数据加载到寄存器中。movl source_address, %eax。

DMA(Direct Memory Access)

或者称为"直接内存访问",是一种在计算机中用于控制高速设备如硬盘、图形硬件等,将数据直接从一个内存区域移动到另一个内存区域,而无需经常性地通过CPU进行数据的中转操作。在没有DMA的系统中,当CPU需要从一个I/O设备读取数据存储到内存,或者将数据从内存写入到I/O设备时,CPU需要逐个字节地移动数据,这需要大量的CPU的时间和资源。然而,当使用DMA时,一旦启动数据传输,DMA控制器会直接控制系统总线,在没有CPU介入的情况下,直接将数据从一个设备传输到另一个设备。在传输完成后,DMA控制器会触发一个中断来通知CPU数据传输已完成。
优势: 节省CPU资源：DMA技术使CPU无需昂贵的时间来进行数据传输，从而使CPU可以继续执行其他计算或处理任务。提升总体性能：由于DMA可以无需CPU的介入进行数据传输，它可以提高系统的数据处理速度和整体性能。
DMA控制器: DMA控制器可能集成在芯片组的南桥或北桥部分。在某些高性能系统或者一些特定的IO设备上(如网卡、显卡),可能会单独集成一个自身的特定DMA控制器。