4 Linux处理器及内存管理

Linux 进程/线程管理控制 #

进程与线程 #

为什么要引入进程？

  • 单道环境 => 多道环境
  • 单道环境及计算机系统各类资源的利用率
  • 多道环境及计算机系统资源利用率的提高
  • 计算机不同部件成本与运行速度的差异性、计算机处理任务本身所需操作部件的差异性以及由此导致的计算机不同部件即资源利用的不平衡性
  • 通过多道程序的并发执行（支持） 实现计算机系统资源利用效率的最大化
  • 引入进程概念（由特定的程序及相关联的进程控制块所组成）来描述并发执行程序的动态运行过程，解决由此引发的资源共享问题

进程及其与程序之间的区别与联系?

  • 程序的动态执行过程
  • 系统资源分配的独立单位
  • 进程标识符、进程控制块
  • 与程序之间的区别（动态/静态性、生命周期、是否支持并发、组成）

进程控制块中的内容？

  • 标识符
  • 调度信息、控制信息
  • 资源信息

为什么要引入线程？

  • 进程并发执行基础（资源拥有 + 调度分派）
  • 进程创建、切换和撤销等操作时空开销较大
  • 进程并发执行程度及进程间通信效率受限
  • 事务处理软件、数据库处理软件、窗口系统及操作系统自身对系统并发程度进一步提高的客观需求，而且有关需求呈现出多项任务处理同组数据（存储资源）的特征
  • 解决方案：（非处理器）资源拥有与（处理器）调度分派两类特性的分离

线程与进程间的区别与联系？

  • 轻型实体及共享进程资源
  • 独立调度和分派的基本单位
  • 创建、撤销、切换等系统开销
  • 地址空间共享及通信效率
  • 系统并发执行程度大大提高

UNIX/Linux 进程 #

UNIX 进程

  • 进程映像的概念
    • 处理器映像 + 内存映像 + 进程控制块 + 程序（用户程序 内核程序）
    • 数据段（静态/全局数据）+ 代码段 + 工作区（栈 + 堆）
  • proc 结构
  • user 结构
  • 共享代码段

proc 结构体数组

struct proc
{
	char  p_stat;		/*进程状态*/
	char  p_flag;		/*进程特征，含SLOAD标志位*/
	char  p_pri;		/*进程优先数*/
	char  p_uid;		/*用户标识符*/
	char  p_time;		/*驻留时间*/
	char  p_cpu;		/*占用CPU时间*/
	char  p_nice;		/*计算优先数时用，[-20,19]*/
	int   p_pid;		/*进程标识符*/
	int   p_ppid;		/*父进程标识符*/
	int   p_addr;		/*进程映像数据分部地址，由此可以找到user结构*/
	int   p_size;		/*进程映像数据分部大小*/
	int   p_wchan;		/*等待原因*/
	int   p_textp;		/*代码段所在的共享段表项text的地址*/
     char  p_sig;		/*软中断号*/
	int   p_ttyp;		/*控制终端tty结构的地址*/
}proc[NPROC];

UNIX 进程 user 结构体

struct user {
 int    u_rsav[2];	 	/*保留现场保护区指针r5和r6值*/
 int    u_fsav[2];	 	/*保存fp注册器*/	
 char u_segflg;	             /*用户/核心空间标志*/
 char u_error;		/*返回出错代码*/
 char u_uid;		/*有效用户标识符*/
 char u_gid;		/*有效组标识符*/
 char u_ruid;                    /*真实用户标识符*/
 char u_rgid;                    /*真实组标识符*/ 
 int    u_procp;		/*proc结构地址，与proc结构链接*/
 char *u_base;	             /*读写文件时的内存地址参数*/
 char u_count;	             /*读写文件时的传送字节数参数*/
 char u_offset[2];             /*文件读写位移参数*/	
 int    *u_cdir;		/*当前目录i节点地址*/
 char *u_dirp;		/*i节点当前指针*/
 char *u_dbuf[DIRSIZ]; 	/*当前路径名组件（文件名和路径名） */
 int   *u-pdir;                /*父目录*/
 int   u-uisa[16];           /*进程相对虚、实地址映射表*/
 int   u-uisd[16]; 
 int   u_ofile[NOFILE];   /*用户打开文件表，NOFILE默认为15*/
 int   u_arg[5];	         /*保存系统调用的参数*/
 int   u_tsize;	         /*代码段大小*/
 int   u_dsize;	         /*用户数据段大小*/
 int   u_ssize;	         /*用户栈大小*/
 int   u-sep;                  /*I和D分离标志 */
 int   u-qsav[2];           /*进程放弃CPU时的现场保护信息*/   
 int   u-ssav[2];
 int   u-signal[NSIG]; /*用于设置收到信号后的动作*/
 int   u_utime;	        /*用户态执行时间*/
 int   u_stime;	        /*核心态执行时间*/
 int   u_cutime;	        /*子进程用户态执行时间*/
 int   u_cstime;	        /*子进程核心态执行时间*/
 int   *u_ar0;	        /*当前中断保护区内r0的地址*/
 int   u-prof[4];         /*统计程序各部分的执行频率 */
 char  u-intflag；         /*来自系统内核栈的进程特征标志 */ 
} user;

 struct {
  int    u_ino;			
  char u_name[DIRSIZ];		
 } u_dent;	             /*当前目录项*/
字段 描述
u-prof[0] 统计表起始地址
u-prof[1] 统计表长度即代码分组数
u-prof[2] 被统计程序代码起始地址
u-prof[3] 比例尺大小即每个代码分组所含指令数的倒数

UNIX 共享段表

struct text
{
 int  x_daddr;		/*磁盘地址*/
 int  x_caddr;		/*内存地址*/
 int  x_size;		/*内存块数*/
 int  *x_iptr;		/*文件内存i节点地址*/
 char  x_count;		/*共享进程数*/
 char  x_ccount;		/*内存副本的共享进程数*/
} text[NTEXT];

UNIX 进程控制用数据结构

Linux 进程控制块所含信息

  • 进程执行状态
    • 运行/就绪态、挂起状态、阻塞状态、僵死状态
  • 调度信息
    • 优先级（普通进程、实时进程）、时间片
  • 标识符
    • 进程标识符、用户标识符、组标识符
  • 进程间通信相关信息
    • 链接信息
  • 父进程、兄弟进程、子进程
  • 时间和定时器
    • 进程创建时间、消耗处理器时间、定时器
  • 文件系统相关信息
    • 文件打开指针、当前目录指针、根目录指针
  • 地址空间
    • 虚拟地址空间
  • 处理器相关信息
    • 组成进程上下文的寄存器及栈信息

UNIX/Linux 进程状态演化 #

UNIX 进程表项之 p_stat 与 p_flag

  • p_stat
    • NULL 0 此 proc 结构为空
    • SSLEEP 1 高优先权睡眠状态、
    • SWAIT 2 低优先权睡眠状态
    • SRUN 3 运行或就绪态，仅当运行态时其 user 结构在内存
    • SIDL 4 进程创建时的过渡状态
    • SZOMB 5 进程终止前状态（僵死状态），等待善后处理
    • SSTOP 6 进程正被跟踪即暂停/挂起状态
  • p_flag (SLOAD = 01 表示在内存中时)
    • SSYS 02 常驻内存的系统进程（0#进程）标志
    • SLOCK 04 进程被锁，不能调出内存
    • SSWAP 010 交换标志
    • STRC 020 进程正被跟踪标志
    • SWTED 040 关于进程跟踪的另一标志

UNIX 进程状态转换：

Linux 进程状态转换：

UNIX/Linux 进程创建与执行 #

进程创建及相关函数

  • int fork( ); 创建子进程
    • 返回值=0，表明创建成功，返回到子进程继续执行
    • 返回值>0，表明创建成功，返回到父进程继续执行，其值为子进程的 PID 号
    • 返回值=-1，表明创建失败
    • ==在父进程中 fork 的返回值是子进程的 PID。在子进程中 fork 的返回值是 0==
  • int getpid( ); 获取本进程标识符
  • int getppid( ); 获取父进程标识符
  • int wait( ); 等待子进程结束
    • 成功则返回子进程标识符

线程通讯、wait和sleep 区别?sleep(0) vs wait(0)有什么区别_wait(null)与wait(0)区别-CSDN博客

int fork( ); 子进程创建步骤

  • （1）申请空闲 PCB，除子进程特有信息（如 p-pid）外，均复制父进程的相应信息（譬如文件打开表及资源）
  • （2）申请空闲内存区，复制父进程的进程映像数据分部，包括数据段、内核栈、用户栈和 user 结构体
  • （3）共享父进程的共享段表项 text
  • （4）从 fork 系统调用返回主调函数

fork() 调用及进程创建问题

  • 程序顺序逻辑结构而非分支判断或循环结构中多次调用 fork()，譬如 n 次，则整个程序运行过程所执行的进程数为 $2^n$
  • 当程序需要创建若干子进程，而不想创建孙子进程时，应当将 fork() 调用放入父进程的程序空间也即 fork() 调用返回值判断大于 0 成立时的条件分支中
  • fork() 调用的位置即所在程序段非常重要，直接关系到其所创建进程在整个进程家族中的逻辑地位

进程加载程序代码 exec()

  • fork() 创建的子进程虽然与其父进程拥有不同的进程映像，但其程序却未发生改变
  • exec() 系统调用可在当前进程上运行新程序，其主要功能是将指定的可执行文件加载到指定的进程映像中，并覆盖掉原有程序
    • exec 族系统调用共有六种函数
  • 子进程可以选择执行特定程序，但是不能使用 exec 调用父进程
  • 除非 exec 调用失败，否则对应进程将不会返回旧程序

Linux 线程与进程控制

  • Linux 独特的线程实现方案
    • 不严格区分进程与线程
    • 构成同一用户级进程的多个用户级线程将被映射到共享相同组标识符的内核级线程上，于是这些线程就可共享如文件、内存之类的资源，从而避免调度器在同组线程之间切换时进行上下文切换，也即无需进行上下文切换
  • 进程创建采用克隆方式 fork() => clone()

Linux 内核并发机制 #

并发控制的必要性和重要性 #

可能出现“与时间有关错误”的原因:

  • 与诸进程的执行速度有关；
  • 由于多个进程都共享了同一变量或者互相需要协调同步；
  • 对于变量的共享或者互相协作的进程没有进行有效的控制

操作系统内核功能自身需要

  • 各类资源管理的基本依据暨相关数据结构譬如可用内存空间大小等均为共享数据，在各进程进行资源申请（分配）和释放（回收）时会发生并发访问的情况

  • 操作系统必须提供有效可靠的并发控制机制，保证上述并发处理的正确协调 Linux 提供互斥、同步、通信机制

Linux 并发控制触发机制 #

早期不支持对称多处理器体系结构的 Linux

  • 中断服务程序是导致并发访问的因素
  • 只有发生中断或内核代码路径上显式要求重新调度和执行另一进程时，才会发生并发访问

支持对称多处理器体系结构的 Linux

  • 并发运行在不同处理器上的多个内核线程完全有可能在同一时刻并发访问共享数据，并发访问随时可能发生
  • 现代 Linux 内核已支持内核抢占，调度器可以抢占正在运行的进程而重新调度执行其他进程

内核中的并发源

  • 中断
    • 中断发生后，中断处理程序和被中断程序之间
    • 中断处理时通常会禁用所有中断或禁用当前级别以下的所有中断，但若时间太长可能造成事件错失，于是产生了上 - 下协同机制 top-half&bottom-half
  • 软中断请求（softirq）和小任务（tasklet）
    • 随时可能被调度，从而打断当前进程
    • invoke_softirq() 或 ksoftirqd() 触发执行软中断
  • 内核抢占
    • 调度器支持可抢占特性，将会导致进程与进程之间的并发
  • 多处理器并发执行
    • 多处理器上可以同时运行多个进程

单处理器系统内核中并发

  • 中断处理程序
    • 可以打断软中断、小任务和进程的执行
  • 软中断请求和小任务
    • 软中断请求间不会并发，但会打断进程的执行
  • 支持抢占的内核
    • 不同进程之间会产生并发
  • 不支持抢占的内核
    • 不同进程之间会否产生并发？
    • 会：主动放弃处理器情形也会触发重新调度

SMP 系统内核中的并发

  • 不同类型的中断处理程序之间可能并发
    • 不同类型的中断处理程序可被不同处理器执行
    • 同一类型的中断处理程序不会并发
  • 同一类型的软中断可能在不同处理器上并发
  • 同一类型的小任务是串行执行的
    • 不会在多个处理器上并发
  • 不同处理器上的进程会并发执行

并发访问潜在漏洞

  • 进程上下文操作某临界资源时发生中断，而恰巧某中断处理程序也访问了该资源
  • 进程上下文访问临界资源时发生抢占调度
  • 在自旋锁临界区中主动睡眠让出处理器
  • 两个处理器同时修改同一临界资源
  • 关键考虑什么呢？
    • 包括静态局部变量、全局变量、共享数据结构、缓存、链表、红黑树等所隐含的资源数据
    • 资源数据的访问路径

UNIX/Linux 并发同步机制 #

并发访问之同步必要性

  • 问题场景
    • 一个进程在操作某临界资源时发生中断而某中断处理程序恰巧也访问该临界资源
    • 进程在访问某临界资源时发生被抢占调度，而另一进程也恰巧访问该临界资源
  • 解决方案关键要领
    • 找出应被保护资源或数据（静态局部/全局变量、共享数据结构/缓存/链表/红黑树等）
    • 检查确认可能并发访问上面被保护资源或数据的代码段（也即临界区）

UNIX 并发同步机制

  • 管道
    • 环形缓冲，生产者 - 消费者模型，读写操作
  • 消息
    • 消息队列及消息的发生与接收
  • 共享存储器
    • 使用者进程自备互斥机制
  • 信号量
    • 进程间同步操作
  • 信号（用于通知另一进程发生了异步事件）

Linux 并发同步机制

  • 原子操作
    • 保证变量操作指令代码片段的“原子”般执行
  • 自旋锁
    • 忙 - 等待模式，分为基本自旋锁和读者 - 写者自旋锁
  • 信号量
    • 二元信号量、计数型信号量、读写型信号量
  • 内存屏障
    • 预防内存访问的越界 R- CU（read-copy-update）及等待队列

Linux- 原子操作 #

原子操作执行既不会被中断，也不会被干扰

  • 单处理器系统中，线程对原子操作的执行一旦启动将一直到完成，期间不会被中断
  • 多处理器系统中，被操作的变量会被上锁以防止其他线程的访问，直到对应操作完成

Linux 内核提供两类原子操作

  • 整数操作，针对整数变量
  • 位图操作，针对位图的某一位

实现 Linux 的任何体系结构，均须支持这些原子操作（汇编指令或内存总线上锁方式）

Linux 原子数据类型

//Linux-4.8.8/include/linux/types.h
typedef struct {
	int counter;
} atomic_t;

#ifdef CONFIG_64BIT
typedef struct {
	long counter;
} atomic64_t;
#endif

整数原子操作

#define __raw_cmpxchg(ptr, old, new, size, lock)  \
({				         \
  __typeof__(*(ptr)) __ret;		         \
  __typeof__(*(ptr)) __old = (old);	         \
  __typeof__(*(ptr)) __new = (new);	         \
  switch (size) {			         \
   case __X86_CASE_B:		         \
   { volatile u8 *__ptr = (volatile u8 *)(ptr);	         \
     asm volatile(lock "cmpxchgb %2,%1"	         \
	     : "=a" (__ret), "+m" (*__ptr)	         \
	     : "q" (__new), "0" (__old)	         \
	     : "memory");		         \
     break;				         \
   }				         \
   case __X86_CASE_W:  { ...... }	         \
   case __X86_CASE_L:   { ...... }	         \
   case __X86_CASE_Q:   { ...... }	         \
   default:	__cmpxchg_wrong_size();	         \
  }				         \
   __ret;				         \
})

位图原子操作

//Linux-4.8.8/include/asm-generic/bitops/atomic.h
static inline void set_bit(int nr, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
	unsigned long flags;

	_atomic_spin_lock_irqsave(p, flags);
	*p  |= mask;
	_atomic_spin_unlock_irqrestore(p, flags);
}
static inline void clear_bit(int nr, volatile unsigned long *addr)
static inline void change_bit(int nr, volatile unsigned long *addr)
static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
static inline int test_and_clear_bit(int nr, volatile unsigned long *addr)
static inline int test_and_change_bit(int nr, volatile unsigned long *addr)

Linux- 自旋锁 #

基本自旋锁

  • 朴素型 plain
    • static __always_inline void spin_lock(spinlock_t *lock)
    • 禁止内核抢占，preempt_disable();preempt_enable();
    • 在单处理机环境中可以使用特定的原子级汇编指令 swap 或 test_and_set 实现进程互斥；多 CPU 环境中可通过“锁总线”（bus locking）的形式保证 test_and_set 指令执行的原子性，因为 test_and_set 指令对内存的两次操作都需要经过总线

Linux 自旋锁类型

//Linux-4.8.8/include/linux/spinlock_types.h
typedef struct spinlock {
	union {
		struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
		struct {
			u8 __padding[LOCK_PADSIZE];
			struct lockdep_map dep_map;
		};
#endif
	};
} spinlock_t;

typedef struct raw_spinlock {
	arch_spinlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
	unsigned int break_lock;
#endif
#ifdef CONFIG_DEBUG_SPINLOCK
	unsigned int magic, owner_cpu;
	void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map dep_map;
#endif
} raw_spinlock_t;

#ifdef CONFIG_QUEUED_SPINLOCKS
#include <asm-generic/qspinlock_types.h>
#else
typedef struct arch_spinlock {
	union {
		__ticketpair_t head_tail;
		struct __raw_tickets {
			__ticket_t head, tail;
	          } tickets;
	};
} arch_spinlock_t;
  • 中断请求型 static __always_inline void spin_lock_irq(spinlock_t *lock)
  • 中断请求保护型 #define spin_lock_irqsave(lock, flags) …… / static __always_inline void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
    • 禁止内核抢占， 关闭中断，保存中断状态寄存器标志位
    • preempt_disable();
    • local_irq_save(flags);
  • 后半部分型 static __always_inline void spin_lock_bh(spinlock_t *lock)
    • 用来关闭/开放软中断
    • local_bh_disable()
    • local_bh_enable()

读者 - 写者自旋锁

  • 支持内核空间更大程度的并发
  • 每个读者 - 写者自旋锁由一个 24 位读者计数器和一个开关锁标志组成

队列自旋锁

自旋锁理解：就是一个 while 循环，在不需要 OS 进行进程和线程调度的情况下进行自旋等待 看完你就明白的锁系列之自旋锁 - 程序员cxuan - 博客园

Linux 读写自旋锁操作

/linux-4.8.8/include/linux/rwlock.h
#define rwlock_init(lock)   ......
#define read_lock(lock)   ......
#define read_unlock(lock)   ......
#define write_lock(lock)   ......
#define write_unlock(lock)   ......
#define read_lock_irq(lock)   ......
#define read_unlock_irq(lock)   ......
#define write_lock_irq(lock)   ......
#define write_unlock_irq(lock)   ......

Linux- 信号量 #

计数型信号量

//linux-4.8.8/include/linux/semaphore.h
struct semaphore {
 raw_spinlock_t	lock;
 unsigned int		count;
 struct list_head	wait_list;
};
void sema_init(struct semaphore *sem, int val);
void down(struct semaphore *sem);
void up(struct semaphore *sem);
int __must_check down_interruptible(struct semaphore *sem);
int __must_check down_killable(struct semaphore *sem);
int __must_check down_trylock(struct semaphore *sem);
int __must_check down_timeout(struct semaphore *sem, long jiffies);

互斥锁

struct mutex {
 atomic_t		count;
 spinlock_t		wait_lock;
 struct list_head	wait_list;
#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_MUTEX_SPIN_ON_OWNER)
 struct task_struct	*owner;
#endif
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
 struct optimistic_spin_queue osq;
#endif
#ifdef CONFIG_DEBUG_MUTEXES
 void			*magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
 struct lockdep_map	dep_map;
#endif
};

其中的 spinlock 代表了在互斥锁的实现中，通常会使用自旋锁来保护一些关键操作，以确保在多线程环境中的原子性，并不是直接代表互斥锁是由自旋锁实现的，二者是不同的并发同步机制。

读写型信号量

//linux-4.8.8/include/linux/rwsem.h
struct rw_semaphore {
 atomic_long_t count;
 struct list_head wait_list;
 raw_spinlock_t wait_lock;
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 struct optimistic_spin_queue osq;
 struct task_struct *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
 struct lockdep_map	dep_map;
#endif
};

Linux- 内存屏障 #

  • 预防内存读写访问的越界
    • #define mb() barrier() 或 dsb() 或 do { dsb(); arm_heavy_mb(); } while (0)
    • #define __smp_mb() dmb(ish)
  • 预防内存读访问的越界
    • #define rmb() dsb()
    • #define __smp_rmb() __smp_mb()
  • 预防内存写访问的越界
    • #define wmb() barrier() 或 dsb(st) 或 do { dsb(st); arm_heavy_mb(); } while (0)
    • #define __smp_wmb() dmb(ishst)

Linux-RCU 读时复制更新 #

已有其他机制存在的问题

  • 均使用了原子操作指令，多处理器争用共享变量会增大缓存一致性的复杂性并导致性能下降

[[MiniOB事务#^755b43|允许多个线程同时读，并运行一个线程同时修改链表]]

  • 读者线程几乎无同步开销
  • 写者线程负责同步协调并创建副本实施修改，且等所有读者线程完成后才会把旧数据销毁掉

重要应用场景

  • 有效提高链表中遍历读取数据的效率

Linux- 等待队列 #

本质上是双向链表

当运行进程需要获取某资源遭遇不可用情况时，可把该进程插入等待队列以等待对应资源的释放，这时进程进入睡眠状态

简单应用实现 #

互斥锁应用编程

void* thread_executive(void* zThreadName)
{
 int nRandom, nTemp1, nTemp2;
 int i;
 char *pThreadName = (char*)zThreadName;
 for (i=0; i<1000; i++)
 {
  nRandom = rand();
  pthread_mutex_lock(&mutex);
  nTemp1 = nAccount1 - nRandom;  nTemp2 = nAccount2 + nRandom;
  nAccount1 = nTemp1;  nAccount2 = nTemp2;
  pthread_mutex_unlock(&mutex);
  printf("[%s] Loop #%d: nAccount1 = %d, nAccount2 = %d\n", pThreadName, i, nTemp1, nTemp2);
 }
 return NULL;
}

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
pthread_mutex_t mutex;
int nAccount1=0, nAccount2=0;
int main(void)
{
 pthread_t thread1;
 pthread_t thread2;
 srand(time(NULL));
 pthread_mutex_init(&mutex, NULL);
 pthread_create(&thread1, NULL, thread_executive, "thread1");
 pthread_create(&thread2, NULL, thread_executive, "thread2");
 pthread_join(thread1, NULL); pthread_join(thread2, NULL);
 pthread_mutex_destroy(&mutex);
 return 0;
}

信号量应用编程

  • 生产者 - 消费者问题
    • 循环缓冲 buffer[N]
    • 输入输出指针 in=0; out=0;
  • 信号量设置及相关操作函数
    • 信号量 mutexP、mutexC、empty、full
    • int sem_init(sem_t *sem, intpshared, unsigned intvalue);
    • int sem_wait(sem_t *sem);
    • int sem_post(sem_t*sem);
    • int sem_destroy(sem_t*sem);
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>

#define N 5
typedef int ITEM;

ITEM buffer[N];

int in=0, out=0;

sem_t empty, full, mutexP, mutexC;

void* executive_producer(void* zThreadName)
{
 int nextP, i;
 char *pThreadName = (char*)zThreadName;
 for (i=0; i<30; i++)
 {
  nextP = rand();
  sem_wait(&empty);
  sem_wait(&mutexP);
  buffer[in] = nextP;
  printf("[%s] Loop #%d: PRODUCING %d => buffer[%d] \n", pThreadName, i, nextP, in);
  in = (in+1) % N;
  sem_post(&mutexP);
  sem_post(&full);
 }
 return NULL;
}

void* executive_consumer(void* zThreadName)
{
 int nextC, i;
 char *pThreadName = (char*)zThreadName;
 for (i=0; i<20; i++)
 {
  sem_wait(&full);
  sem_wait(&mutexC);
  nextC = buffer[out];
  printf("[%s] Loop #%d: CONSUMING nextC <= buffer[%d] = %d\n", pThreadName, i, out, nextC);
  out = (out+1) % N;
  sem_post(&mutexC);
  sem_post(&empty);
 }
 return NULL;
}

int main(void)
{
 #define nP 3
 #define nC 5
 int i;
 char threadProducerName[nP][10];   char threadConsumerName[nC][10];
 pthread_t thread_producer[3];   pthread_t thread_consumer[5];
 srand(time(NULL));
 sem_init(&mutexP, 0, 1);
 sem_init(&mutexC, 0, 1);
 sem_init(&empty, 0, N);
 sem_init(&full, 0, 0);
 for (i=0; i<nP; i++)
 {
  sprintf(threadProducerName[i], "producer%d", i);
  pthread_create(&thread_producer[i], NULL, executive_producer, threadProducerName[i]);
 }
  for (i=0; i<nC; i++)
 {
  sprintf(threadConsumerName[i], "consumer%d", i);
  pthread_create(&thread_consumer[i], NULL, executive_consumer, threadConsumerName[i]);
 }
 for (i=0; i<nP; i++)
  pthread_join(thread_producer[i], NULL);
 for (i=0; i<nC; i++)
  pthread_join(thread_consumer[i], NULL);

 sem_destroy(&mutexP);
 sem_destroy(&mutexC);
 sem_destroy(&empty);
 sem_destroy(&full);
 return 0;
}

Linux 父子进程间同步编程 #

父子进程间同步编程设计

父进程等待子进程

  • 父进程使用 wait() 等待子进程的终止
  • 子进程终止时执行 exit() 向父进程发终止信号

子进程等待父进程

  • 子进程使用 signal() 预置特定软中断信号的处理函数，并在该函数中编码设计影响自身运行逻辑流程的代码方案，然后在运行过程中接受/等待父进程利用 kill() 发出的软中断信号，进而触发软中断处理函数的执行和改变代码运行轨迹

wait() 与 exit() 用法

  • pid_t wait(int *status);
    • 用于暂停主调进程的执行以等待其子进程终止
    • 参数 status 用于存放子进程终止时的终止信号值
    • 返回值为终止子进程的进程标识符，无则返回 -1
  • pid_t waitpid(pid_t pid, int *status, int options);
    • 用于等待 pid 指定子进程的终止
  • void exit(int status);
    • 用于终止主调进程，status & 0377 结果发给父进程
  • 所需头文件
    • #include <sys/types.h>
    • #include <sys/wait.h>

软中断信号机制及用法

操作系统用来通知进程有事件发生，是最基本的进程间通信机制，其提供了一种简单的处理异步事件的方法

注意这种信号类似于中断总是在进程处于运行状态时才会去响应，故称之为软中断信号

进程在接收软中断信号之前必须先使用 signal() 进行预置，以便将其与某处理函数关联；当信号发出并被对应进程接收后，系统就中断该进程执行，转而执行与相应信号关联的函数，待函数执行完毕后再返回被中断进程继续执行

除了用户自定义信号 SIGUSR1 和 SIGUSR2 外，其它软中断信号都已经由操作系统预置了相应的处理函数；用户进程中如果对这些软中断信号进行预置，则会使有关信号与新的函数相关联；当相关软中断信号被接收时，被转去执行的将不再是操作系统预置的处理函数，而是用户对该软中断信号重新预置后的处理函数

同一个软中断信号可以通过多个 signal() 系统调用，分别与不同的处理函数进行关联；系统在响应该软中断信号时，执行的是当前/最近预置的处理函数，从而实现了同一软中断信号在不同的情况下可转向不同的处理函数去执行

signal() 与 kill() 用法

sighandler_t signal(int signum, sighandler_t handler);

  • #include <signal.h>
  • typedef void (*sighandler_t)(int);
  • 用于建立软中断信号与其处理函数之间的关联

int kill(pid_t pid, int sig);

  • #include <sys/types.h>
  • #include <signal.h>
  • 用于向 pid 指定进程或进程组发送 sig 指定的信号
  • pid>0 将信号发送给 pid 指定的进程；
  • pid=0 将信号发送给同组的所有进程；
  • pid=-1 将信号发送给进程用户标识符等于发送进程有效用户标识符的所有进程
#include <stdio.h>
#include <signal.h>
#include <stdlib.h>
int nStopLoop=0; //定义循环变量
void soft_interrupt_handler(int sig) //定义软中断处理函数
{
 nStopLoop = 1; //修改循环变量的值为1	
}
int main(void) {
 signal(SIGINT,soft_interrupt_handler);	//预置软中断信号对应处理函数-位置1
 //循环显示，等待键入Ctrl+C，获取该软中断信号后转软中断处理函数执行
 while (!nStopLoop)				
  printf("I'm running!\t");
 signal(SIGINT,soft_interrupt_handler);	//预置软中断信号对应处理函数-位置2
 printf("\n<======I stop running!======>\n");
 exit(0);
 return 0;
}
  • 第一种由于在循环前预置，所以可以被运行
  • 第二种在循环后预置，相当于预置自己的失败，所以直接被系统 ctrl c 接管

父子进程对话同步实例

#include <unistd.h>
#include <stdio.h>
#include <signal.h>
#include <stdlib.h>
#include <wait.h>
int nStopLoop=0; //定义循环变量
void soft_interrupt_handler(int sig) { nStopLoop = 1; }
int main(void) {
 int pid;
 signal(SIGUSR1, soft_interrupt_handler); while ((pid=fork())==-1);
 if (pid>0) {
  printf("[FJC=%d]: How are you?\n", getpid());  kill(pid, SIGUSR1);  wait(0);
  printf("[FJC=%d]: I'm fine too.\n", getpid());
 }
 else {
  while (!nStopLoop);
  printf("[ZJC=%d]: Fine, thanks. And you?\n", getpid());  exit(0);
 }
 return 0;
}

Linux 内存管理 #

操作系统内存管理

  • 硬件【内存条（物理地址空间）+ 内存管理部件】
  • 内存管理包括内存分配与回收、地址映射、内存保护、内存扩充四个方面

Linux 内存管理核心功能

  • 内存分配与回收、页表等内存管理结构及操作、缺页异常处理

Linux 内存管理探析技术路线

  • 从 Shell 命令看内存布局、从应用程序看进/线程内存管理模型、从内核源码看内存管理实现机制

Linux 内核镜像内存布局

(深入理解计算机系统) bss段，data段、text段、堆(heap)和栈(stack) - 跑马灯的忧伤 - 博客园

  • _bss_stop
    • 内核镜像 BSS 段的起始地址和结束地址，包含了初始化为 0 的所有静态全局变量
    • bss 段（bss segment）通常是指用来存放程序中未初始化的全局变量的一块内存区域。
    • bss 是英文 Block Started by Symbol 的简称。
    • bss 段属于静态内存分配。
  • _edata
    • 内核镜像数据段的起始地址和结束地址，包含了内核大部分已初始化的数据
    • 数据段（data segment）通常是指用来存放程序中已初始化的全局变量的一块内存区域。
    • 数据段属于静态内存分配。
  • __init_begin
    • 内核镜像初始化数据段的起始地址和结束地址，包含了大部分内核模块初始化数据
  • _etext or _text
    • 内核镜像代码段的起始地址和结束地址，包含了编译后的内核代码
    • 代码段（code segment/text segment）通常是指用来存放程序执行代码的一块内存区域。
    • 这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读 (某些架构也允许代码段为可写，即允许修改程序)。
    • 在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。

Linux 进程内存空间布局

  • NULL
    • 无效的节，也即没有关联的节
  • NOTE
    • 包含提示信息的节
  • RELA
    • 包含重定位表的节
  • PROGBITS
    • 包含程序所需数据或代码且格式与含义由程序决定
  • NOBITS
    • 不占用文件空间，仅提供地址偏移信息，用于存放那些未初始化的全局变量，譬如.bss 分段
  • INIT_ARRAY
    • 函数指针数组，数组各元素对应函数执行初始化工作，在主函数 main 之前执行
  • FINI_ARRAY
    • 函数指针数组，数组各元素对应函数执行善后扫尾工作，在主函数 main 之后执行
  • SYMTAB
    • 符号表，链接时会用到
  • STRTAB
    • 字符串表
    • .shstrtab
      • Section Header String Table

Linux 进程 -ELF 程序头

  • LOAD
    • 可加载的段
  • NOTE
    • 与加载的相关系统环境信息
  • TLS
    • Thread Local Storage

C 标准库常用内存管理函数

  • void *malloc(size_t size);
  • void free(void *ptr);
  • void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
  • int munmap(void *addr, size_t length);
  • int getpagesize(void);
  • int mprotect(void *addr, size_t len, int prot);
  • int mlock(const void *addr, size_t len);
  • int munlock(const void *addr, size_t len);
  • int madvise(void *addr, size_t length, int advice);

Linux 启动与内存空间布局 #

UNIX 进程存储管理 #

进程空间可划分为核心态和用户态两部分

UNIX 进程虚实地址映射机制

  • 两组内存管理寄存器：KISA 和 KISD 用于核心态，UISA 和 UISD 用于用户态；每组包含 8 对 16 位长的寄存器
  • 程序状态字寄存器 PSW 包含有指示机器执行状态的位
  • KISA 和 UISA 用于存放逻辑页在内存的首地址
  • KISD 和 UISD 用于存放相应页面的属性，关键位域包括：
    • 位 1~2 描述存取控制属性 ACF，譬如只读、可读写等；
    • 位 3 描述页扩展方向 ED，0/1 指示由低/高址向高/低址扩展；
    • 位 6 描述页面是否修改过 M
    • 位 8~14 描述页面的实际使用大小 PLF，指向虚页可用的最后一块内存字符块号，具体采用补码表示，便于越界检查
      • 若 ED＝0，表示页使用由低到高扩展，于是 PLF＝实际使用大小－1；
      • 若 ED=1，PLF＝页面大小－实际使用大小
      • 譬如，若 ED＝0 且已使用 32 块，则 PLF＝32－1=31；若 ED=1、页面大小为 128 个内存字符块且实际使用 100 块，则 PLF＝128－100=28。
假设页面大小为128个内存字符块，某进程的数据段使用了3个内存字符块，而用户栈使用了2个内存字符块，试分别给出它们的PLF值？

数据段由低址向高址扩展，ED=0，故而PLF=3-1=2

栈由高址向低址扩展，ED=1，故而PLF=128-2=126

UNIX 进程核心态虚实地址映射

  • 核心态下，0~5 及 7#页面映射关系固定，系统生成后就固定不变了，即不随运行进程变化；但 6#页面及 KISA6、KISD6 是不固定的，会随当前运行进程而变化，也即总是指向当前运行进程的 ppda 区
  • 地址映射过程如下：
    • (1) 搜索 proc 表，根据调度策略选中当前进程的 proc[n]
    • (2) 根据 proc[n].p-addr 找到 ppda
    • (3) 建立 ppda 和进程核心态空间第 6 页之间的映射关系，即将 ppda 首址赋给 KISA[6]

UNIX 进程用户态虚实地址映射

  • 假设某进程在用户态下访问的最大虚拟存储空间为 8 页，其中共享正文段占 2.5 页、数据段占 2.25 页、用户栈占 0.5 页。如果每页大小为 128 个内存字符块，则 0.5 页为 64 个字符块，0.25 页为 32 个字符块
  • 假设该进程正文段内存始址为 ta、数据段内存始址为 da，那么该进程 0~5#页面的内存始址分别为 ta、ta+128、ta+256、da、da+128、da+256；用户栈紧靠数据段的下方且由高向低扩展，于是其始址为 da+256+32+64=da+352

UNIX 进程被调度时地址映射

被调度进程 user 结构体内容加载到内存后，根据 u-uisa[] 的值相应地加上 x_caddr 或 p_addr 后赋给 UISA[]，而 UISD[] 和 u-uisd[] 的值相同

Linux 进程 - 线程空间探析 #

Linux 虚拟/物理地址空间映射

Linux 内存管理 #

页面 struct page

内存管理区 struct zone

页面的分配与释放

  • static inline struct page* alloc_pages(gfp_t gfp_mask, unsigned int order);
  • void __free_pages(struct page *page, unsigned int order);

内存碎片化解决方案——伙伴算法

小块内存分配机制

  • slob 分配
    • SLOB（Simple List Of Blocks）分配器，设计小而高效，采用了首次适应算法，存在内部碎片问题；设立小、中、大三个链表分别用来记录管理当前的空闲链表（small list：0~256 字节；medium list：256~1024 字节；large list：1024~Pagesize）；超过页面大小的空间申请直接通过伙伴系统进行分配，无需经过 SLOB 分配器
  • slab 分配
  • slub 分配
    • Slub 内存分配器的特点是简化设计理念，并保留 slab 分配器的核心思想（也即每个缓冲区由多个小的 slab 组成且每个 slab 包含固定数量的对象）；Slub 分配器简化了 kmem_cache、slab 等相关管理型数据结构，摒弃了 slab 分配器中众多的队列概念，针对多处理器、NUMA 系统进行优化，以提高性能和可扩展性并降低内存空间开销

虚拟内存管理之进程地址空间

内存描述符 struct mm_struct

内存分配与释放

  • malloc(); mmap();

缺页异常处理

  • do_page_fault();

页面淘汰机制

  • LRU 算法与页面缓存策略相结合

Linux 处理器及进程调度 #

Linux 处理器调度概要 #

处理器调度类型

  • 长程调度、中程调度、短程调度

处理器调度算法

  • 先来先服务调度算法、最短时间优先调度算法、时间片轮转调度算法、高响应比优先调度算法、多级反馈队列调度算法、公平型调度算法
  • 最早截止时间调度算法、最低松弛度优先调度算法

处理器调度评价指标

  • 用户角度、系统角度

Linux 内核基础设施

  • 进程控制块、进程状态转换
  • 线程及其与进程之间的控制操作关系

Linux 处理器调度算法

  • O(n) 调度算法 Linux2.4 内核及以前版本
  • O(1) 调度算法 Linux2.6 内核
  • CFS 调度算法 Linux2.6.23 内核

Linux 虚拟机进程调度

Linux 处理器调度算法 #

基于优先级的时间片轮转调度算法——O(n) 调度算法

  • 设立一个全局性的就绪队列链表 runqueue（无序）
  • 每个进程被赋予一个固定的时间片；当前运行进程的时间片使用完后，调度器会选择下一就绪进程运行；当所有进程的时间片都用完之后，才会对所有进程重新分配时间片
  • 从中选取下一最佳就绪进程的时间开销与就绪队列所含进程数有关，时间复杂度为 O(n)；当就绪队列中的进程数很多时，选择调度下一就绪进程的过程会变得很慢，从而导致系统整体性能下降

O(1) 调度算法

  • 每个处理器维护独立的就绪队列，减少了锁竞争
  • 拥有活跃型和过期型两类优先级就绪队列数组
  • 每个优先级就绪队列数组包含 MAX_PRIO 也即 140 个优先级队列，其中前 100 个对应实时进程、后 40 个对应普通进程。这样调度器在调度时，只需在活跃型优先级就绪队列数组中选择优先级最高且非空队列中的队首就绪进程调度运行即可

CFS 调度算法

  • 抛弃以往固定时间片和固定调度周期的做法，采用进程权重比值来量化和计算实际运行时间
  • 引入虚拟时钟概念，每个进程的虚拟时间是时间运行时间相对于 nice 值为 0 的权重的比例值
  • 进程按照各自不同速率比在物理时钟节拍内前进：
    • nice 值小的进程优先级高、权重大，且其虚拟时钟比真实时钟慢，但可获得较多的运行时间；
    • nice 值大的进程优先级低、权重小，且其虚拟时钟比真实时钟快，所获运行时间少
    • CFS 调度器总是选择虚拟时钟跑得慢的进程，就像一个多级变速箱：nice 值为 0 的进程是基准齿轮，其它各个进程在不同的变速比下相互追赶，从而达到公平、公正

Linux VServer 虚拟机机制

  • 提供了一种控制虚拟机使用处理器时间的方式
  • 其在 Linux 标准调度机制上面覆盖了一种令牌桶过滤器 TBF（Token Bucket Filter），以确定每个虚拟机应分配多少处理器执行时间（涵盖单处理器、多处理器、多核处理器）
  • 令牌输入速率（每时间段 T 可传入的令牌数 R）
  • 桶大小 S（达到该值，令牌输入无效）
  • 虚拟机上进程运行，则消耗桶中令牌
  • 最低阈值 M（触发重启和重新调度被停进程）

UNIX 进程调度 #

UNIX 进程调度功能框架

  • 确定调度时机
    • 抢占式系统出现高优先权可运行进程，立即让其运行
    • 非抢占式系统中即使出现高优先权可运行进程，也要等到调度时机（即当前运行进程自动放弃 CPU 或由核心态转入用户态）出现时，才让其运行
  • 执行调度算法（确定调度策略、计算优先数），从而选定某一进程运行
  • 完成调度的具体操作过程
    • 让原运行进程退出 CPU
    • 保护退出进程的运行现场
    • 让选中进程占用 CPU
    • 初始化或恢复选中进程的运行现场

进程占用 CPU 时间 p-cpu 统计

  • 每次时钟中断（20ms）使当前运行进程的 p-cpu 递增即 + 1
  • 每隔一秒（50 次时钟中断）依次检查各进程的 p-cpu
    • 如果 p-cpu ≤ 10，则 p-cpu = 0；
    • 如果 p-cpu > 10，则 p-cpu 的值减 10 后写回 p-cpu
  • p-cpu 与进程调度切换反馈过程

UNIX 进程调度策略

  • UNIX 采用基于动态优先数的进程调度策略

    • 0≤pri≤127，核心态进程优先数∈[0,49]、用户态进程优先数∈[50,127]

  • 核心态进程不可剥夺、用户态进程可剥夺

    • 例：进程 i 被阻塞时，将陷入睡眠状态，对应优先数 proc[i].p-pri∈[0,49]；其被唤醒时，该值小于用户态进程优先数，故可被优先执行
    • 合作进程唤醒或中断处理程序唤醒

  • 用户态进程优先数 p-pri 动态变化方式

    • 每秒重新计算一次：50 + ( p-cpu / a) + 2 * p-nice，其中 a = 2, 4, 8, 16

  • 基于动态优先数的进程调度

    • whichqs 以位图方式描述了多级优先级就绪进程队列状况（0 空/1 不空），并选择调度第一非空队列队首进程

UNIX 进程调度操作过程——由两组寄存器进行联合实现

当前运行进程 i => 非运行状态【保护现场】

  • 填写 p-wchan、u-rsav[2]
  • 修改 text 结构中共享正文段进程数
  • 记录用户空间页地址寄存器内容：UISA → u-uisa
  • 记录用户空间页描述符寄存器内容：UISD → u-uisd

所选进程 j 置换为运行状态【恢复现场】

  • 若映像不在内存：①如内存足够多，则直接调入；②否则根据淘汰策略换出某些内存页面并装入映像
  • KISA[6] → ppda proc[j].p-addr 写入 KISA[6]
  • 根据 p-textp 找到 text 结构，若 text 不在内存，同样涉及调入和淘汰页面的处理
  • 由 p-addr 或 KISA[6] 找到 user，并执行地址映射