[toc]
书1：现代操作系统，答案
- 工作原理和实现方法
- 技术含量最高的系统软件
- 将硬件的复杂性与程序员分离开
- 定义：系统软件， 程序模块的集合，资源管理和用户接口功能
作用：
- 作为扩展机器
- 裸机添加
- 理解“抽象”，如文件
- 作为资源管理者／作业管理（大型机）
- 多路复用，时间与空间
- 软硬件接口
- system call
-
批处理操作系统
改进主存和I/O设备之间的吞吐量
特征：用户脱机使用，无法交互
-
多道程序设计 multiprogramming 需要硬件保护
宏观上并行，微观上串行
-
系列机思想与IBM System/360系统 统一的体系结构、指令集 -> 软件危机
-
分时系统：轮流使用time slice
unix操作系统：多用户、多任务、分时
unix前身是Multics系统，内外环设计
-
大规模集成电路时代 分布式、嵌入式
寄存器分类：
-
用户可见寄存器: 高级语言编译器通过算法分配并使用之，以减少程序访问主存次数
- 数据寄存器、地址寄存器、条件码寄存器（溢出、符号）
-
控制和状态寄存器: 用于控制处理器的操作，由OS的特权代码使用, 以控制其他程序的执行
- PC、IR、PSW(program status word)
- PSW中有一位CPU的状态工作码, PSW在系统调用和I/O中很重要
核心态=管态、用户态=目态
- I/O不在用户态内
- 用户态->核心态: trap 核心态->用户态：修改PSW
- e.g. x86: R0 R1 R2 R3
层次化存储体系结构 ～ 容量、速度、成本
存储访问局部性原理
cpu访问寄存器不存在延时，操作系统不访问cache
磁带光盘价格极其低廉，作为磁盘的备份
shell 、GUI
多线程和多核芯片 书1p13
I/O：控制器+设备本身 device driver
- 实现I/O的三种方式
轮询、中断、DMA芯片（总线竞争、大量I/O数据传送）
中断系统的两大组成部分: 硬件中断装置和软件中断处理程序 (中断设备的设备驱动程序的一部分)
中断向量 中断向量表IVT
启动计算机：主板BIOS
进程、地址空间、进程间通信
虚拟内存
UNIX：特殊文件、管道
rwx r-x --x p25
“个体重复系统发育”，很深刻
1.6 系统调用~执行“trap” 功能号和参数
大多采用在内存中开辟专用堆栈区来传递参数
linux系统调用：
system_call() sys_call_table
Linux系统调用利用了x86体系结构中的软件中断，即调用了int $0x80汇编指令。这条汇编指令将产生向量为128的软件中断， CPU被切换到内核态，并将控制权交给系统调用过程的起点system_call()处理函数
系统调用与内核函数（即服务例程，e.g. sys_getpid()）
封装例程 ppt2-p56
用于进程管理、文件管理、目录管理 书1p32
UID、GID、PID
PID～fork，waitpid指令
fork不可继承的有:进程标识符，父进程标识符
execve：替换一个进程的核心映像
POSIX过程调用 ：进程管理(fork, execve, waitpid, exit(status) )、文件管理(open, ...)、目录管理（mkdir, rmdir, ..., umount, unlink）、其它(chmod, kill, chdir, time)
<->
WIN32 API:
- 单体系统（模块组合结构）
- 层次式系统
- 分层：全序、偏序、半序
- 虚拟机结构: VM/370
会话监控系统CMS
这是1型超级监控程序（cons：用户态不能陷入）
2型：VMWare，主机/客户操作系统
- 微内核结构：
- 运行在核心态的内核提供最基本的操作系统功能，包括中断处理、处理机调度、进程间通信。这些部分只供了一个很小的功能集合，通常称为微内核
- 特点：Mechanism和policy分离=>使内核更小
- 微内核结构的变体：客户-服务器模型
- 客户进程与服务器进程之间使用消息进行通信
顺序进程模型
- 有时须考虑严格的实时要求
并发：次序不是事先确定的
进程是具有独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位
-
资源分组处理与执行
-
进程的组成:程序+数据+PCB进程控制块+堆栈
-
进程上下文
- 用户级上下文:进程的用户地址空间(包括用户栈各层次)，包括用户正文(code)段、用户数据段和用户栈;
- 寄存器级上下文:程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值;
- 系统级上下文:
- 静态部分(PCB和资源表格)
- 动态部分:核心栈 (核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈)
-
注意有两种register saves/restores:
- timer interrupt: 用hardware，kernel stack，implicitly，存user registers
- OS switch：用software，process structure，explicitly，存kernel registers
NOTE：
- 守护进程daemon
- windows没有进程层次的概念 书p51
- shell p26
调度进程： 进程表=PCB表 p53
- 并发度：PCB表的大小
- 链表结构、索引结构
- 多道（内存层面）!=系统并发度（OS层面）
- windows进程无状态，只是宿主，真正运行的是线程（调度单位）
- UNIX中，OS作为进程的一部分
- struct task_struct 双向循环链表
- 调度针对就绪进程 run_list
- 运行->阻塞：OS、I/O、资源、IPC（其它进程输入）
- 运行->就绪：时间片用完、因为高优先级进程就绪而中断
- 就绪->运行：调度程序
- 阻塞->就绪
其它：
- initial和final（五状态）：
- initial态：等待资源；
- final态（在UNIX称作zombie state）等待子进程return 0，parent进程 wait()子进程
- 表格和其它信息暂时由辅助程序保留，例如为处理用户帐单而累计资源使用情况的财务 程序
- suspend（挂起）状态（七状态）：进程映像在磁盘上，不占用内存空间
- 激活的概念：阻塞挂起->阻塞, 就绪挂起->就绪
- 进程控制原语：创建、撤销、阻塞、唤醒
- 系统调用不一定是原语：两进程，read()重入
- 创建进程
- fork——创建新进程，复制现有进程上下文
- exec——加载新程序并覆盖自身
- 可继承(inherit):子进程可以从父进程中继承用户标识符、环境变量、打开文件、 文件系统的当前目录、控制终端、已经连接的共享存储区、信号处理例程入口表等
- 不可继承:进程标识符，父进程标识符
- exit：exit()向父进程给出一个退出码(8位的整数)，父进程终止时如何影响子进程:
- 子进程从父进程继承了进程组ID和终端组ID(控制终端)，因此子进程对发给该进程组或终端组的信号敏感。终端关闭时，以该终端为控制终端的所有进程都收到SIGHUP信号。
- 子进程终止时，向父进程发送SIGCHLD信号，父进程截获此信号并通过wait()系统调用来释放子进程PCB
- wait() waitpid() waitid()等待子进程修改状态
#include <cstdlib>
#include <iostream>
#include <sys/types.h>
#include<sys/wait.h>
#include <unistd.h>
#include <vector>
using namespace std;
int main(){
int pid;
for (int i = 0; i < 3; i++){
pid = fork();
if (pid == 0){ //子进程
cout << "pid=" << pid << getpid() << ", hello world" << endl;
return 0;
}
else{
cout << "pid=" << pid << " forked" << endl;
}
}
int ret = 0;
while (ret!=-1){
ret = wait(NULL);
cout << "pid=" << ret << " exited" << endl;
};
return 0;
}/*
BOOL CreateProcess(
LPCWSTR pszImageName, LPCWSTR pszCmdLine, LPSECURITY_ATTRIBUTES psaProcess, LPSECURITY_ATTRIBUTES psaThread, BOOL fInheritHandles,
DWORD fdwCreate, LPVOID pvEnvironment, LPWSTR pszCurDir,
LPSTARTUPINFOW psiStartInfo, LPPROCESS_INFORMATION pProcInfo
);
*/
#include <stdio.h>
#include <windows.h>
int main() {
TCHAR szCmdLine[]={TEXT("C:\\oscourse\\test.exe")};
STARTUPINFO si;
PROCESS_INFORMATION pi;
memset(&si, 0, sizeof(STARTUPINFO));
si.cb = sizeof(STARTUPINFO);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow = SW_SHOW;
if(!CreateProcess(NULL, szCmdLine, NULL, NULL, FALSE, 0, NULL, NULL, &si, &pi))
{
printf("Create process fail!\n");
ExitProcess(1);
}
else {
printf("Create process success!\n");
ExitProcess(0);
}
}进程是资源分配单位 ～ 并发执行
- 1-p^n 内存与吞吐量
线程是CPU调度单位 ～ 时空开销
- 多线程Multithreading
- 线程：并行实体共享同一地址空间和所有可用数据，线程比进程更容易创建和撤销
- 轻量级进程=Lightweight process=LWP
- TCB与PCB
- e.g. 书p56 三线程、文字处理
- 在支持线程的操作系统中，进程只作为资源分配单位，而线程则作为CPU调度单位，可读取全局变量来实现通信，比进程间通信简单不少，无需调用内核
NOTE：
- 服务器与cache，分派线程、工作线程，c代码
- 线程改善了web服务器的性能
- 有限状态机实现，非阻塞系统调用<->顺序进程模型的保留 书p57
- “阻塞非阻塞"与"同步异步”: 线程可以异步，因为有状态共享；同步是两个对象之间的关系，而阻塞是一个对象的状态。
在用户空间／内核中实现线程
- 线程库（运行时系统 run-time system）：POSIX的pthread
- pros：
- 线程切换不调用操作系统内核，性能良好
- 调度是应用程序特定的，可针对应用优化
- ULT可运行在任何操作系统上 (仅需线程库)
- cons:
- 调度通常采用非抢先式和更简单的规则（线程没有时间中断=>只能用非抢占式）
- 阻塞系统、缺页中断，进程中所有线程将被阻塞
- 操作系统内核只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
- pros：
- 对于多处理器，内核可以同时调度同一进程的多个线程
- 阻塞是在线程一级完成
- 内核例程是多线程的
- cons：
- 线程管理代价大：在同一进程内的线程切换调用内核，导致速度下降
- 时间片分配给线程，所以多线程的进程获得更多CPU时间
Solaris
在线程的混合实现机制中，线程创建、调度、 同步在用户级线程中完成，应用程序的多个ULT将被映射到一些KLT上
- KLT
- 惰性进程，必须有一个线程（自动创建主线程）
- Windows线程由执行体线程块ETHREAD表示，即线程对象，其中包含内核线程块 KTHREAD，即线程控制块TCB
#include <windows.h>
#include <stdio.h>
#define MAX_THREADS 3
typedef struct _MyData {
int val1;
int val2;
} MYDATA, *PMYDATA;
DWORD WINAPI ThreadProc(LPVOID lpParam){
PMYDATA pData;
pData = (PMYDATA)lpParam;
printf("This is thread %d, the parameter is %d\n", pData->val1, pData->val2);
// Free the memory allocated by the caller for the thread
// data structure.
HeapFree(GetProcessHeap(), 0, pData);
return 0;
}
void main() {
PMYDATA pData;
DWORD dwThreadId[MAX_THREADS]; //线程ID
HANDLE hThread[MAX_THREADS]; //线程句柄 int i;
// Create MAX_THREADS worker threads.
for( i=0; i<MAX_THREADS; i++ ) {
// Allocate memory for thread data.
pData = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(MYDATA));
if( pData == NULL ) ExitProcess(2);
// Generate unique data for each thread.
pData->val1 = i;
pData->val2 = i+100;
hThread[i] = CreateThread(
NULL, // default security attributes
0, // use default stack size
ThreadProc, // thread function
pData, // argument to thread function
0, // use default creation flags
&dwThreadId[i]); // returns the thread identifier
// Check the return value for success.
if (hThread[i] == NULL) {
ExitProcess(i);
}
}
// Wait until all threads have terminated. WaitForMultipleObjects(MAX_THREADS, hThread, TRUE, INFINITE); // Close all thread handles upon completion.
for(i=0; i<MAX_THREADS; i++) {
CloseHandle(hThread[i]);
}
}内核和用户空间实现均可
- pthread_yield阻塞线程
#define _REENTRANT
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#define NUM_THREADS 5
#define SLEEP_TIME 10
void *sleeping(void *); /* thread routine */
int i;
pthread_t tid[NUM_THREADS]; /* array of thread IDs */
int main()
{
int sleep_time = SLEEP_TIME;
for (i = 0; i < NUM_THREADS; i++)
pthread_create(&tid[i], NULL, sleeping, (void *)&sleep_time);
for (i = 0; i < NUM_THREADS; i++)
pthread_join(tid[i], NULL); //逐个等待线程结束
printf("main() reporting that all %d threads have terminated\n", i);
return (0);
} /* main */
void *sleeping(void* arg)
{
int sleep_time = *(int *)arg;
printf("thread %u sleeping %d seconds ...\n", pthread_self(), sleep_time);
sleep(sleep_time);
printf("\nthread %u awakening\n", pthread_self());
pthread_exit(0);
}- 从内核的角度，Linux只有进程而没有线程的概念，Linux没有准备特别的调度算法或定义特别的数据结构来表征线程
- 在Linux中，线程仅仅被视为使用某些共享资源的进程，每个线程都拥有自己的task_struct，所以在内核看来它就是一个普通的进程，但是该进程与其他进程共享某些资源，例如地址空间
- Linux下的pthread_create是通过clone系统调用实现的
#define _GNU_SOURCE
#include <stdio.h>
#include <errno.h>
#include <sched.h>
#include <sys/types.h>
#define STACK_SIZE 4096 //4k
int flag;
void *test(void *arg)
{
int childnum;
flag = 1;
childnum = *(int *)arg;
printf("Thread %d work cycle\n", childnum);
sleep(3);
}
int main()
{
pid_t pid;
int childno = 1, mainnum = 0;
void *csp, *tcsp;
csp = (char *)malloc(STACK_SIZE);
if (csp)
{
tcsp = csp + STACK_SIZE;
}
else
{
exit(errno);
}
flag = 0;
childno = 1;
if ((pid = clone((void *)&test, tcsp, CLONE_VM, (void *)&childno)) < 0)
{
printf("Couldn't create new thread!\n");
exit(1);
}
else
{ //we're in main
while (flag == 0); //利用全局变量进行Linux线程间通信
printf("Just created thread %d\n", pid);
}
test(&mainnum);
sleep(3);
printf("Main program is now shutting down\n\n");
return 0;
}进程间关系：互斥、同步、通信
- 同步是通过共享协作
概念：
- 竞争条件 (race condition)
- 临界资源 (critical resource)
- 临界区(critical section): 进程中访问临界资源的代码片断
- 进入区->临界区->退出区->剩余区(remainder section)
目的: 避免竞争条件，同时保证使用临界资源的进程能够正确和高效地进行协作
解决互斥问题应遵循的条件
- 任何两个进程不能同时处于临界区
- 不应对CPU的速度和数量做任何假设
- 临界区外运行的进程不得阻塞其他进程
- 不得使进程无限期等待进入临界区
- 简单
- 把禁止中断的权利交给用户进程导致系统可靠性较差
- 不适用于多处理器(违反条件2)
- 可能错过其它interrupts，比如disk的read request
- 对于现代CPU，这个实现速度慢
while(lock==1);
lock=1;
//critical region
lock=0;
//non_critical region;- 可能违反条件1
- 忙等待（自旋锁spin lock）
- Murphy's law
- 整型变量turn
- 可能违反条件3（该算法要求两个进程严格轮流进入临界区）
- 忙等待
- e.g. spooler directory 假脱机程序
丢失则进入临界区; 解决了互斥访问的问题，而且克服了强制轮转法的缺点，可以正常地工作.
忙等待
#define FALSE 0
#define TRUE 1
#define N 2 /* 进程数量 */
int turn=0; /* 现在轮到谁？*/
int interested[N]; /* 所有值初始化为0（FALSE）*/
void enter_region(int process) /* 进程是0或1 */
{
interested[process] = TRUE; /* 表名所感兴趣的*/
turn = 1-process; /* 设置标志 */
while(turn == 1-process && interested[1-process] ==TRUE); /* 空语句 */
}
void leave_region(int process)
{
interested[process] = FALSE; /* 表示离开临界区*/
}- test and set lock：X86的BTS/BTR命令
- swap：XCHG OP1 OP2
- 优点：
- 适用于任意数目的进程
- 简单，容易验证其正确性
- 可以支持进程中存在多个临界区，只需为每个临界区设立一个布尔变量
- 缺点：忙等待，耗费CPU时间
priority inversion problem：两个进程H、L，H优先级高于L，调度规则: 只要H处于就绪态它就可以运行。若某一时刻L处于临界区中，此时H变成就绪态并被调度，从而开始忙等待;但是由于H的优先级高于L，使得L不会被调度，也就无法离开临界区
- 信号量是OS提供的管理共享资源的有效手段
- s.count(), s.queue()，OS核心代码
- dijkstra:信号量、原子操作
- 原语P、V来自荷兰语的proberen(降低)和verhogen(升起)
- 利用信号量实现互斥（mutex）、进程间同步（$$S_{12}$$）
- 同步P操作在互斥P操作前
- 信号量的缺点：同步操作分散、易读性差、不利于修改和维护、正确性难以保证
- mutex互斥锁适用于用户级线程包; 快速用户区互斥量futex，书p76
- 生产者消费者问题
empty=n; full=0;
\\producer \\consumer
P(empty); P(full);
P(mutex); P(mutex);
...
V(mutex); V(mutex);
V(full); V(empty);
分析：有两个层面的进程间通信，一是生产者和生产者的互斥，二是生产者和消费者的同步，所以必须要有两个信号量。
- 1973年，由Hoare和Hansen提出
- 管程的基本思想是把信号量及其操作原语封装在一个对象内部。即:将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，解决临界区分散所带来的管理和控制问题
- 管程的定义:管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块
- 引入管程可提高代码的可读性，便于修改和维护，正确性易于保证
- 模块化:一个管程是一个基本程序单位，可以单独编译
- 抽象数据类型:管程是一种特殊的数据类型， 其中不仅有数据，而且有对数据进行操作的代码
- 信息封装:管程是半透明的，进程可调用管程中实现了某些功能(函数) ，至于这些功能是怎样实现的，在其外部则是不可见的
- 共享变量外部不可见
- 互斥进入（为了数据完整性）
- 等待问题：可以规定唤醒是最后操作
- queue，等待和唤醒操作；入口等待序列，紧急等待队列（多个等待进程）
- 条件变量：与互斥锁不同，条件变量是用来等待而不是用来上锁的
- 管程是一个编程语言概念，编译器必须要识别管程并用某种方式对其互斥做出安排
- Java支持管程。但是，C及多数程序设计语言都不支持管程
- C及多数语言也没有信号量，但是增加信号量十分容易——编译器甚至不需知道它们的存在，系统只需提供P、V系统调用即可
- 针对分布式系统的高级机制
- 消息传递原语：send(destination, &message)和receive(source, &message)，它们是系统调用而不是语言成分
#define N 100 /* buffer 中槽的数量 */
void producer(void){
int item;
message m; /* buffer 中槽的数量 */
while(TRUE){
item = produce_item(); /* 生成放入缓冲区的数据 */
receive(consumer,&m); /* 等待消费者发送空缓冲区 */
build_message(&m,item); /* 建立一个待发送的消息 */
send(consumer,&m); /* 发送给消费者 */
}
}
void consumer(void){
int item,i;
message m;
for(int i = 0;i < N;i++){ /* 循环N次 */
send(producer,&m); /* 发送N个缓冲区 */
}
while(TRUE){
receive(producer,&m); /* 接受包含数据的消息 */
item = extract_item(&m); /* 将数据从消息中提取出来 */
send(producer,&m); /* 将空缓冲区发送回生产者 */
consume_item(item); /* 处理数据 */
}
}- 消息传递系统的设计问题
- 不可靠消息传递的成功通信问题(网络)
- 进程命名问题
- 身份认证问题
- 性能问题
semaphore rmutex = 1; // 读进程互斥信号量
semaphore wmutex = 1; // 写进程互斥信号量
int readcount = 0; // 读进程计数
semaphore S = 1; // S的意义在于保证读和写能够公平竞争
cobegin
process reader_i() { // 读进程
while(true) {
P(S);
P(rmutex);
readcount++;
if(readcount == 1) P(wmutex);
V(rmutex);
V(S);
read_data_base();
P(rmutex);
readcount--;
if(readcount == 0)V(wmutex);
V(rmutex);
}
}
process writer_i() { // 写进程
while(true) {
P(S);
P(wmutex);
write_data_base();
V(wmutex);
V(S);
}
}#define CHAIRS 5 /*为等待的顾客准备的椅子数*/
typedef int semaphone; /*运用你的想象力*/
semaphore customers = 0; /*等待服务的顾客数*/
semaphore barbers = 0; /*等待顾客的理发师数*/
semaphore mutex = 1; /*用于互斥*/
int waiting = 0; /*等待的顾客(还没理发的)*/
void barber(void)
{
while (TRUE)
{
down(customers);
/*如果顾客数是0，则睡眠*/
down(mutex); /*要求进程等待*/
waiting = waiting - 1; /*等待顾客数减1*/
up(barbers);
/*一个理发师现在开始理发了*/
up(mutex); /*释放等待*/
cut_hair(); /*理发(非临界区操作)*/
}
}
void customers(void)
{
down(mutex); /*进入临界区*/
if (waiting < CHAIRS)
{ /*如果没有空椅子，就离开*/
waiting = waiting + 1; /*等待顾客数加1*/
up(customers); /*如果必要的话，唤醒理发师*/
up(mutex); /*释放访问等待*/
down(barbers); /*如果barbers为0，就入睡*/
get_haircut(); /*坐下等待服务*/
}
else
up(mutex); /*店里人满了，走吧*/
}Windows支持三种同步对象
- 互斥对象(Mutex)
- 信号量对象(Semaphore)
- 事件对象(Event)
- 同步对象等待：
DWORD WaitForSingleObject(
HANDLE hHandle, // handle of object to wait for
DWORD dwMilliseconds // time-out interval in milliseconds
);
DWORD WaitForMultipleObjects(
DWORD nCount, //对象句柄数组中的句柄数;
CONST HANDLE *lpHandles, // 指向对象句柄数组的指针，数组中可包括多种对象句柄;
BOOL bWaitAll, // 等待标志:TRUE表示所有对象同时可用,FALSE表示至少一个对象可用;
DWORD dwMilliseconds // 等待超时时限;
);- 其它同步方法：
- 临界区对象(Critical Section)：只能在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的
- 互锁变量访问：相当于硬件指令，对一个整数(进程内的变量或进程间的共享变量)进行操作。其目的是避免线程间切换的影响
- 初始化
- 调用pthread_mutex_init()
- 或者静态赋值pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIER
- 加锁: lock()——阻塞等待锁
- 解锁: unlock()
- 清除锁：destroy()——此时锁必需unlock，否则返回EBUSY
- 用来等待而非上锁
- 函数：pthread_cond_init/wait/timewait/destroy/signal/broadcast
- #include <semophore.h>
- 有名（named）信号量和无名（memory-based, unnamed）信号量
- 无名信号量：
- 创建：sem_t sem_id;
- sem_init/getvalue/wait/post/destroy
- 有名信号量：
- 特点是把信号量的值保存在文件中。这决定了它的用途非常广:既可以用于线程，也可以用于相关进程间，甚至是不相关进程
- 有名信号量在使用的时候，和无名信号量共享 sem_wait和sem_post函数;两者的区别是有名信号量使用sem_open代替sem_init，另外在结束的时候要像关闭文件一样去关闭这个有名信号量
Unix早期的进程间通信机制:信号和管道
- e.g. 键盘中断，硬件条件（浮点溢出，segmeatation fault），软件条件（如Socket中有加急数据到达），Shell向子进程发送作业控制命令
- linux与进程控制相关的命令：&, ctrl-z, fg, bg, ...
- 进程也可以忽略指定的信号(SIG_IGN), SIGKILL信号(无条件终止进程)和SIGSTOP(使进程暂停)不能被忽略（不能被相关的系统调用阻塞）
- 由内核执行与该信号相关的默认处理例程(SIG_DFL)
- 信号的实现：整型，一个字，32位，32种信号，信号是1-index（SIGINT编号是1）
- task_struct:利用两个字分别记录当前未决的信号(signal)以及当前阻塞的信号(blocked)，917行,sigaction存储处理方式
/* Signal handlers: */
struct signal_struct *signal;
struct sighand_struct __rcu *sighand;
sigset_t blocked;
sigset_t real_blocked;
/* Restored if set_restore_sigmask() was used: */
sigset_t saved_sigmask;
struct sigpending pending;
unsigned long sas_ss_sp;
size_t sas_ss_size;
unsigned int sas_ss_flags;捕捉signal的实例（shell.md里也有）：
#include <signal.h>
void catchint(int signo) {
printf("\n CATCHINT; signo=%d;", signo);
printf("CATCHINT returning\n");
}
void main() {
int i;
signal(SIGINT, catchint);
for(i=0; i<5; i++) {
// 修改sigaction结构
printf("Sleep call #%d\n", i);
sleep(5);
}
printf("Exiting.\n");
}- 管道类型：pipe、named pipe(还允许无亲缘关系进程通信)
- 适合数据量大的情况
- 通过将两个file结构指向同一个临时的VFS索引节点，而 VFS索引节点又指向同一个物理页而实现管道
- 内核必须利用一定的机制同步对管道的访问， 为此，内核使用了锁、等待队列和信号
- int pipe(int fildes[2]); fildes[0]是读端，fildes[1]是写端
- 只适用于父子进程之间；或父进程安排的各个子进程之间 （其它情况用命名管道）
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
int f_des[2];
static char message[BUFSIZ];
if (argc != 2)
{
fprintf(stderr, "Usage: %s message\n", *argv);
exit(1);
}
if (pipe(f_des) == -1)
{
perror("pipe");
exit(2);
}
switch (fork())
{
case -1:
perror("fork");
exit(3);
case 0: // 子进程
close(f_des[1]);
if (read(f_des[0], message, BUFSIZ) != -1)
{
printf("Message received by child:[%s]\n", message);
fflush(stdout);
}
else
{
perror("read");
exit(4);
}
break;
default: // 父进程
close(f_des[0]);
strcpy(message, argv[1]);
if (write(f_des[1], message, BUFSIZ) != -1)
{
printf("Message sent by parent:[%s]\n", argv[1]);
fflush(stdout);
}
else
{
perror("write");
exit(5);
}
}
}- 命名管道：FIFO，和匿名管道的区别在于它是文件实体而不是匿名对象
- 命名管道可通过mknod系统调用建立：指定mode为S_IFIFO
int mknod(const char *path, mode_t mode, dev_t dev);
-
IPC对象（访问必须经过类似文件访问的许可检验）、引用标识符、访问键（定位引用标识符）
- ipc_perm结构：包含了作为对象所有者和创建者的进程之用户标识符和组标识符，以及对象的 访问模式和对象的访问键。
-
消息队列
- 客户/服务器模型，微内核结构，克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点
- Linux 为系统中所有的消息队列维护一个msgque链表，该链表中的每个指针指向一个msgid_ds结构，该结构完整描述一个消息队列。当建立一个消息队列时，系统从内存中分配一个msgid_ds结构并将指针添加到msgque链表
- 与消息队列相关的系统调用
- msgget——依据用户给出的键值key，创建新消息队列或打开现有消息队列，返回一个消息队列ID
- msgsnd——发送消息;
- msgrcv——接收消息，可以指定消息类型;没有消息时，返回-1
- msgctl——对消息队列进行控制，如删除消息队列
- 消息队列不随创建它的进程的终止而自动撤销，须调用 msgctl(msgqid, IPC_RMID, 0)
-
snd.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <sys/msg.h>
#define MAX_TEXT 512
#define TRUE 1
struct msgbuf
{
long int msgtype;
char msgtext[MAX_TEXT];
};
int main()
{
struct msgbuf msgdata;
int msgid;
char buffer[MAX_TEXT];
if ((msgid = msgget((key_t)1234, 0666 | IPC_CREAT)) == -1)
{
fprintf(stderr, "msgget failed with error: %d\n", errno);
exit(EXIT_FAILURE);
}
printf("msgid = %d\n", msgid);
while (TRUE)
{
printf("Enter message text: ");
fgets(buffer, MAX_TEXT, stdin);
msgdata.msgtype = 1;
strcpy(msgdata.msgtext, buffer);
if (msgsnd(msgid, (void *)&msgdata, MAX_TEXT, 0) == -1)
{
fprintf(stderr, "msgsnd failed\n");
exit(EXIT_FAILURE);
}
if (strncmp(buffer, "end", 3) == 0)
{
break;
}
}
exit(EXIT_SUCCESS);
}rcv.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <sys/msg.h>
#define MAX_TEXT 512
#define TRUE 1
struct msgbuf
{
long int msgtype;
char msgtext[MAX_TEXT];
};
int main()
{
int msgid;
struct msgbuf msgdata;
if ((msgid = msgget((key_t)1234, 0666 | IPC_CREAT)) == -1)
{
fprintf(stderr, "msgget failed with error: %d\n", errno);
exit(EXIT_FAILURE);
}
printf("msgid = %d\n", msgid);
while (TRUE)
{
if (msgrcv(msgid, (void *)&msgdata, MAX_TEXT, 0, 0) == -1)
{
fprintf(stderr, "msgrcv failed with error: %d\n", errno);
exit(EXIT_FAILURE);
}
printf("Received message: %s", msgdata.msgtext);
if (strncmp(msgdata.msgtext, "end", 3) == 0)
{
break;
}
}
if (msgctl(msgid, IPC_RMID, 0) == -1)
{
fprintf(stderr, "msgctl(IPC_RMID) failed\n");
exit(EXIT_FAILURE);
}
exit(EXIT_SUCCESS);
}- 信号量
- semid_ds 结构表示System V IPC信号量
- sem_base:信号量数组；系统调用参数：信号量索引、操作值和操作标志
- 操作：semget, semop, semctl
- 如果系统调用中指定的所有操作中有一个操作不能成功 时，则 Linux会挂起这一进程。但是，如果操作标志指定这种情况下不能挂起进程的话，系统调用返回并指明 信号量上的操作没有成功，而进程可以继续执行
- 如果进程被挂起，Linux必须保存信号量的操作状态并 将当前进程放入等待队列。为此，Linux在堆栈中建立一个sem_queue结构并填充该结构。新的sem_queue结构添加到信号量对象的等待队列中(利用 sem_pending 和sem_pending_last指针)。当前进程放入sem_queue结构的等待队列中(sleeper)后调用调度程序选择其他的进程运行
-
共享内存
- 对共享内存的访问同步需要由其他 IPC机制，例如信号量来实现
- 访问键，访问权限，锁定到物理内存
- 系统调用
- shmget——创建或打开共享内存:依据用户给出的整数值key，创建新内存区或打开现有内存区，返回 一个共享内存ID
- shmat——连接共享内存:连接共享内存到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享内存首地址。父进程已连接的共享内存可被fork 创建的子进程继承
- shmdt——拆除共享内存连接:拆除共享内存与本进 程地址空间的连接
- shmctl——共享内存控制:对共享内存进行控制。如共享内存的删除需要显式调用shmctl(shmid, IPC_RMID, 0)
- shmget——创建或打开共享内存:依据用户给出的整数值key，创建新内存区或打开现有内存区，返回 一个共享内存ID
-
套接字（Socket）
- 套接字(Socket)是一种网络通信机制，它通过网 络在不同计算机上的进程间进行双向通信。套接字所采用的数据格式可为可靠的字节流或不可靠的报文，通信模式可为client-server模式或 peer-to-peer模式
- UNIX套接字API(基于TCP/IP):send, sendto, recv, recvfrom
- 信号量、互斥量、临界区
- 共享内存：文件映射机制
- CreateFileMapping/OpenFileMapping
- MapViewOfFile
- FlushViewOfFile可把映射地址空间的内容写到物理文件中
- UnmapViewOfFile, CloseHandle
- 管道
- Windows 提供了匿名管道和命名管道两种管道 机制
- 利用CreatePipe可创建匿名管道，得到两个读写句柄;利用ReadFile和WriteFile可进行匿名管道的读写
- 命名管道：一个服务器端与一个客户进程间的通信通道;可用于不同机器上进程通信；作为客户方(连接到一个命名管道实例的一方)时，可以是"\serverName\pipe\pipename"；作为服务器方(创建命名管道的一方)时，只能取 serverName为\.\pipe\PipeName，不能在其它机器上创建管道
- 邮件槽mailslot（消息队列）：一种不定长、不可靠的单向消息机制，通常采用client-server模式
- 套接字Winsock: 实现了一个与协议独立的应用编程接口，可支持多种网络通信协议
死锁(Deadlock)是指系统中多个进程无限制地等待永远不会发生的条件
死锁发生的原因: 与不可抢占资源有关
- 对互斥资源的共享
- 并发执行的顺序不当
进程使用的资源分为可抢占资源和不可抢占资源两类
- 可抢占资源(preemptable resource)：可以从拥有它的进程中抢占而不会产生任何副作用 的资源。例如 CPU、存储器
- 不可抢占资源(nonpreemptable resource)：在不引起相关的计算失败的情况下，无法把它从占有的进程抢占过来的资源。例如打印机
死锁发生的必要条件
- 互斥:任一时刻只允许一个进程使用资源
- 请求和保持:进程在请求其余资源时，不主动释放已经占用的资源
- 非剥夺:进程已经占用的资源，不会被强制剥夺
- 环路等待:环路中的每一条边是进程在请求另一进程已经占有的资源(充分条件)
处理死锁问题的四种方法：
- 鸵鸟算法：大多数操作系统忽略死锁
- 死锁预防：预先静态分配法，有序资源使用法
- 死锁检测：保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁
- 资源分配图（有向图检测循环）
- 死锁避免：分配资源时判断
- 银行家算法（书p258）：核心是在试探性分配之前进行安全性检查
- 允许互斥、部分分配和不可抢占，可提高资源利用率;
- 要求事先说明最大资源要求，在现实中很困难
- 银行家算法（书p258）：核心是在试探性分配之前进行安全性检查
处理机调度要解决的问题
- 按什么原则分配CPU——进程调度算法
- 何时分配CPU——进程调度的时机
- 如何分配CPU——进程的上下文切换
调度的开销
- 从一个进程切换到另一个进程需一定的时间
- 上下文切换之后，指令和数据高速缓存通常需要更新，执行速度降低 (缺失损失)
非抢先式／抢先式调度算法（时间片+中断）
调度的层次：作业、swap、进程线程
调度算法的目标：
- 批处理系统
- 吞吐量——每小时最大作业数
- 周转时间——从提交到终止的最小时间 CPU利用率——保持CPU忙碌
- 交互式系统
- 响应时间——发出命令到得到响应之间的时间(快速响应请求)
- 均衡性——满足用户的期望
- 实时系统
- 满足截止时间——避免丢失数据
- 可预测性——在多媒体系统中避免品质降低
2.3.8 消息传递
消息传递接口MPI “会合”的概念
屏障barrier：
e.g. 大型矩阵运算的分治
避免锁：读-复制-更新 RCU
2.4 调度
处理机调度
I/O活动的含义：阻塞 p85 I/O密集型～多道程序设计 批处理／交互式／实时
系统需要“平衡” p87 公平、平衡、策略强制执行
批处理系统的调度 FCFS 最短作业优先 最短剩余时间优先
轮转调度～上下文切换 https://baike.baidu.com/item/%E4%B8%8A%E4%B8%8B%E6%96%87%E5%88%87%E6%8D%A2/4842616 时间片长度：进程切换用时～响应时间，通常设为20-50ms
关键：衡量指标，用户公平／进程公平／随机／最短进程／CTSS
实时系统的可调度条件 p92
速率单调调度RMS 最早截止时限优先EDF 最小裕度算法 laxity
将调度策略（用户态）和调度机制（内核态）分离：参数化
windows：实时优先级线程、可变优先级线程 https://blog.csdn.net/zhiquan/article/details/4240400
线程时间配额 ppt p58
Linux将线程分为三类：
- 实时FIFO
- 实时轮转
- 分时
runqueue 自旋锁 查找O(n)
O(1)调度 亲和性 多核->负载均衡 楼梯调度 抛弃了动态优先级的概念，完全公平 RSDL调度算法 旋转楼梯最终时限调度 (The Rotating Staircase Deadline Schedule) CFS Completely Fair Schedule(完全公平调度)
应用：
- 分子动力学：求解牛顿运动方程的积分算法
- 量子化学计算：用波函数计算薛定谔方程
- 计算流体力学：Navier-Stokes(NS)方程
- 计算电磁学：麦克斯韦方程(Maxwell's equation)
体系结构特征：
- 高性能计算物理结点
- 单机/双机，不使用虚拟化
- 并行：向量/多核/大规模异构
- 体系结构层面：处理并行度、减少数据移动、降低数据精度（比如 TPU bf16，尾数表示和计算机功耗密切相关）
- 全局共享的并行文件系统
- Burst Buffer
- SSD实现，在 IO Nodes 和 Compute Nodes 之间
- 处理对IO突发访问需求：比如 checkpoint
- relaxed posix semantics, 和资源管理系统对接
- 要求：一半 memory 的检查点要在 5min 内做完
- Parallel File System (Lustre 为代表)
- 全局单个命名空间，符合POSIX标准
- MDS/MDT管理和存储所有的元数据
- 多个OSS/OST以对象的方式分布式存储数据
- 分布式锁管理机制：优化了POSIX语义，以优化并行IO
- 元数据和文件数据的通信链路分开管理
- HPSS (High Performance Storage System)
- 冷数据长期存储
- Burst Buffer
- 高速互连网络 RDMA
| RDMA | TCP | |
|---|---|---|
| 传输方式 | 消息 | 数据流 |
| 延迟 | 0.6us | 5-50us |
| 带宽 | 200Gb/s | 40Gb/s |
| 流控 | Credit based机制 | 滑动窗口机制 |
IO软件栈
-
实现 IO 方法
- Scientific IOlib
- MPI IO
- POSIX
-
IO 模式
- N进程 --- 1个共享文件
- N进程 --- M个文件
典型超算系统 —— Fugaku
-
基于arm V8处理器的同构系统
- 48 cores + 4 assisted cores(4 CMGs)
- 2*512bit SIMD
- HBM2 Memory, 1024GB/s bandwidth
- SoC设计：集成互连网络Tofu
- 7nm 台积电工艺，表面水冷散热
- 目前最强性能arm V8处理器，融合AI计算操作
- 3.37Tflops DP(2.2GHz)
-
Fugaku互连网络TofuD
- Port 带宽：6.8GB/s * 6 RDMA engines = 40.8GB/s
- Network Interface on Chip
-
Fugaku存储系统
- 三级层次存储
- GFS Cache + Temp FS(25~30PB NVMe)
- Lustre-based GFS
- Off-site Cloud Storage
- 三级层次存储
-
Fugaku系统组成: 158976结点，414机柜
典型超算系统 —— Summit
- 2 * Power9 CPU <-------- NVLINK --------> 6 * V100 GPU，CPU+GPU异构融合
HPC & AI
-
hpc
- CPU计算为中心
- 单进程控制一个GPU
-
ai
- GPU计算为中心
- 单进程+多个GPU
-
hpc->ai
- 应用：使用HPC处理训练数据；加速并行训练；推理加速
- e.g. Fugaku
-
ai->hpc
- 应用：用于迭代方法挑战收敛参数；减少多目标优化结果的参数空间；当物理模型不清楚或者计算量很大时，AI替代仿真
- 希望GPU尽可能独立工作，如 gpu direct storage 的设计
- tpu做科学计算
- 混合精度解决hpc应用
两种发展思路
- 共享内存 ～ OpenMP runTime：高性能系统工程量大
<->
分布式系统 内存瓶颈， scaling不好（跨节点延迟高，微秒级） -> nvme ssd