同步机制

在使用共享内存时，必须注意保护共享资源，多线程并发访问共享资源，在内核中也要特别留意。

1. 临界区和竞争条件

临界区(Critical section)就是访问和操作共享数据的代码段。竞争条件(race conditions)指多个执行线程可能同时执行同一个临界区，出现竞争情况。避免并发和防止竞争条件称为同步(Synchronization)。

中断下半部的处理

因为中断对时限的要求，也不能阻塞，因此整个中断处理流程被分成两部分，上半部分执行对时限要求高的、不能被中断的任务，很多能推迟执行的工作则被放在下半部分。

1. 下半部

下半部执行与中断处理密切相关但中断处理程序本身不执行的工作。中断处理程序会异步执行，并且在最好的情况下也会锁定当前的中断线。对上半部和下半部的划分，有一些提示：

• 如果一个任务对时间非常敏感，将其放入中断处理程序
• 如果一个任务和硬件相关，将其放入中断处理程序
• 如果一个任务要保证不被其他中断（特别是相同中断）打断，将其放入中断处理程序
• 其他任务考虑放入下半部执行

内核2.6以后，提供三种下半部实现机制：软中断(softirq)、tasklets、工作队列(work queues)

中断和中断处理

处理器和外部硬件的速度往往不在一个数量级，如何高效地让处理器和这些外部设备协调工作？

1. 中断

处理器和外部设备协调的方式，从处理器出发，很容易想到的是轮询的方式，但是轮询肯定会做很多无用功；所以应该从外部设备角度，让硬件在需要的时候向内核发出信号，即中断机制。

中断本质上是一种特殊电信号，由硬件设备产生，直接送入中断控制器输入引脚，再发向处理器，处理器接收到中断马上向操作系统反映信号的到来，然后由操作系统执行对应的中断处理程序。

每个中断都有一个中断号，被称为中断请求IRQ。

中断与异常

异常产生需要考虑处理器时钟同步，常常被称为同步中断。这样我们可以把中断分为异步中断和同步中断.

内核数据结构

内核中实现了很多通用数据结构，包括Linked list、Queue、Map、Binary tree等

1. 链表

Linux内核中链表随处可见，它将链表节点塞入数据结构中。

链表在linux/types.h中声明，只有两个指针next、prev，是很简单的双向链表，linux/list.h中实现了很多链表操作的宏。

1
2
3

struct list_head {
	struct list_head *next, *prev;
};

在使用的时候只需要在自己的结构中加上struct list_head list,如

1
2
3
4
5
6

struct person
{
    int age;
    char* name;
    struct list_head list;
};

内核常用的一个宏，获得包含member的结构体的指针：

1
2
3

#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

利用这个宏，可以方便地得到包含链表的结构体：

1
2
3
4
5
6
7
8

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

系统调用

内核提供给用户进程与内核交互的接口

1. 与内核通信

系统调用是用户空间进程与硬件设备间的中间人，它为用户空间提供了硬件的抽象接口；保证系统的稳定和安全；帮助实现多任务和虚拟内存。在Linux中，系统调用是用户空间访问内核的唯一手段(除了异常和trap)

• 应用编程接口API
• POSIX
• libc

2. 系统调用

系统调用syscall，通常通过C库中定义的函数调用进行

函数getpid()的一个实现:

1
2
3
4
5
6
7

SYSCALL_DEFINE0(getpid)
{
    return task_tgid_vnr(current); // return current->tgid
}
//宏展开为：
asmlinkage long sys_getpid(void)

编译指令asmlinkage限定词在定义系统调用时使用。

系统调用号
在Linux中，每个系统调用都有一个系统调用号，通过这个号就可以联系系统调用，进程实际上用这个号来指明执行哪个系统调用。

内核会记录一张sys_call_table。

用户空间程序无法直接执行内核代码，因此需要一种方式通知系统，自己需要执行一个系统调用，这种机制靠软中断实现：通过引发一个异常促使系统切换到内核态去执行异常处理程序，此时的异常处理程序实际上就是系统调用处理程序。

3. 系统调用的实现

• 实现系统调用：明确用途，系统调用的语义和行为，考虑兼容和未来。”Provide mechanism, not policy”
• 参数验证：系统调用必须仔细检查参数的合法和有效，最重要的检查就是指针：
  • 指针指向的内存区域属于用户空间
  • 指针指向的内存区域在进程的地址空间
  • 进程不能绕过内存访问限制，必须要有相关的rwx权限

绑定一个系统调用的步骤：

• 1.在系统调用表最后加上一个表项
• 2.在中定义系统调用号
• 3.系统调用必须编译进内核(不能是编译成模块)，这需要把它放进kernel/下的一个相关文件中。

在用户空间访问系统调用：
Linux提供一组宏，用于直接访问系统调用，他们会设置好寄存器并调用陷入指令，这些宏是_syscalln()，其中n的范围是0-6。

x86可以用 INT 0x80执行系统调用，这就是一个中断

Linux System Calls
Linux System Call Table

1. 进程调度

Linux作为多任务处理系统，同一时刻肯定会有多个任务进程存在于内存，因此内核的调度程序需要决定为哪些进程运行，哪些进程等待，以及决定进程运行的时间(时间片)。调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。

Linux是抢占式的内核调度，进程有优先级的，Linux最出名的调度程序被称为完全公平调度算法——CFS

2. 策略

• 进程分为I/O bond和CPU bond
• 调度策略通常在进程响应速度和系统吞吐量之间平衡
• 优先级：根据进程的价值和对CPU时间的需求赋予进程优先级概念，在Linux下，优先级一种称为nice值，范围[-20,19]，默认为0，nice越大优先级越低，nice代表时间片的比例；第二种是实时优先级，其值可以配置，默认范围[0,99]，值越高优先级越高，实时进程优先级高于普通进程。实时优先级比nice高，一个进程的优先级动态地改变：设想一个低优先级的进程，如果一直有高优先级的进程在，它可能饿死，因此有一种改进方式就是这个动态增加进程的优先级
• 时间片：进程被抢占前所能持续运行的时间，回想I/O bond型和CPU bond型，前者不需要长的时间片，后者则希望时间片越长越好。Linux的CFS调度器将处理器的使用比划分给进程，这样一来进程获得的处理器时间和系统负载密切相关，这个比例受nice值影响

3. Linux调度算法

Linux调度器以模块方式提供，这样可以针对不同进程类型选择合适的调度算法，这种模块化结构被称为[scheduler classes]。

每个调度器都有一个优先级，调度器代码在kernel/sched，调度器策略uapi/linux/sched.h

• 公平调度
  • http://www.cnblogs.com/tianguiyu/articles/6091378.html
  • https://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html

4. 抢占和上下文切换

• 抢占
  • 用户抢占
    • 从系统调用返回用户空间时
    • 从中断处理程序返回用户空间时
  • 内核抢占
    • 中断处理程序正在执行，且返回内核空间之前
    • 内核代码再一次具有可抢占性的时候
    • 如果内核中的任务显示调用schedule()
    • 如果内核中的任务阻塞(这会导致调用schedule())
• 上下文切换

5. 实时调度策略

Linux提供的实时调度策略：

• SCHED_FIFO
• SCHED_RR

参考资料：

• http://stackoverflow.com/questions/9392415/linux-sched-other-sched-fifo-and-sched-rr-differences
• https://lwn.net/Articles/296419/
• SCHED_DEADLINE
• 处理器绑定
• http://www.cs.montana.edu/~chandrima.sarkar/AdvancedOS/CSCI560_Proj_main/

进程管理

进程是操作系统抽象概念中最基本的一种

1. 进程和线程

进程是程序运行的实例，是操作系统分配资源的基本单元，因此，进程除了可执行代码(代码段，text section)外，还包括其他资源，如打开的文件、信号、数据段、堆栈等，一个进程包含一个多个执行线程(thread of execution)，对进程的管理由内核完成。

执行线程，简称线程，线程属于某个进程中的活动对象，线程共享进程的地址空间和数据，但每个线程有自己的程序计数器、线程栈和寄存器，内核调度的对象是线程，而不是进程。

Linux内核不区分线程和进程，而是称task，对应task_struct结构体。

进程提供了2种虚拟机制：虚拟处理器和虚拟内存，每个进程有独立的虚拟处理器和虚拟内存，每个线程有独立的虚拟处理器，线程间可能共享虚拟内存。

1. 获取源码

获取Linux的源码常见方式：
https://github.com/torvalds/linux
https://www.kernel.org/
https://mirrors.tuna.tsinghua.edu.cn/ 清华大学
https://mirrors.aliyun.com/ 阿里云

2. 源码目录结构

在线查看：http://lxr.free-electrons.com/ 没有好的2.6版本的在线查看地址，还是下载源码用Source Insight工具查看方便。

内核源码一般在/usr/src/linux目录

• 打补丁： patch -pl < ../patch-x.y.z

“do one thing, do it well.” —— Linus Torvalds

1. Linux简介

Linux诞生于1991年，由芬兰的大神Linus开发，现在Linux这个词主要指内核。
每个处理器在任何指定的时间点上的活动为下列情况之一：

• 运行于用户态，执行用户进程
• 运行于内核态，处于进程上下文，执行某个特定进程
• 运行于内核态，处于中断上下文，处理某个中断

维基百科：Linux kernel
Linux 内核剖析

2. 单内核与微内核

Linux是单内核，运行在单独的地址空间上，同时吸收微内核有点，支持模块化设计、抢占式内核、内核线程、动态加载内核模块、内核态与用户态等，与传统Unix相比：

• 支持动态加载内核模块
• 支持对称多处理(SMP)机制
• 内核可以抢占(preemptive)，进程优先级
• Linux内核不区分线程和进程，称task
• 提供具有设备类的面向对象的设备模型、热插拔事件，用户空间的设备文件系统sysfs

3. 内核版本

linux内核分为：stable和development，举例说明：Linux-2.6.26.1
2：主版本号
6：副版本号
26：修订版本号
1：稳定版本号
副版本号为奇数表示开发版，为偶数表示稳定版

4. 常用社区

https://www.kernel.org/ 内核源码
http://lxr.free-electrons.com/ 内核源码在线阅读推荐
https://kernelnewbies.org/ 内核开发基础知识
https://lkml.org/ 内核 Mailing List
https://github.com/torvalds/linux github

System.map文件和/proc/kallsyms

System.map

该文件是是一份内核符号表kernel symbol table，包含了内核中的变量名和函数名地址，在每次编译内核时，自动生成。
相关资料：
GNU Binutils wiki
GNU Binutils
What Are Symbols?

System.map文件格式：地址 类型 符号

类型是小写表示local symbol，大写表示global(external)
重点了解几个类型：
T The symbol is in the text(code) section
D The symbol is in the initialized data section
R The sysbol is in a read only data section
t static
d static
R const
r static const

使用nm命令可以查看更多信息：
nm - list symbols from object files