Cyrus' Paperbox

Linux处理器及内存管理

学习笔记 操作系统 · 约 50 分钟阅读

Linux 进程/线程管理控制 #

进程与线程 #

为什么要引入进程？

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

进程控制块中的内容？

为什么要引入线程？

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

UNIX/Linux 进程 #

UNIX 进程

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

UNIX 进程状态转换：

Linux 进程状态转换：

UNIX/Linux 进程创建与执行 #

进程创建及相关函数

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

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

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

进程加载程序代码 exec()

Linux 线程与进程控制

Linux 内核并发机制 #

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

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

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

Linux 并发控制触发机制 #

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

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

内核中的并发源

单处理器系统内核中并发

SMP 系统内核中的并发

并发访问潜在漏洞

UNIX/Linux 并发同步机制 #

并发访问之同步必要性

UNIX 并发同步机制

Linux 并发同步机制

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- 自旋锁 #

基本自旋锁

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;

读者 - 写者自旋锁

队列自旋锁

自旋锁理解：就是一个 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- 内存屏障 #

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;
}

信号量应用编程

#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() 进行预置，以便将其与某处理函数关联；当信号发出并被对应进程接收后，系统就中断该进程执行，转而执行与相应信号关联的函数，待函数执行完毕后再返回被中断进程继续执行

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

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

signal() 与 kill() 用法

sighandler_t signal(int signum, sighandler_t handler);

int kill(pid_t pid, int sig);

#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;
}

父子进程对话同步实例

#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 内存管理探析技术路线

Linux 内核镜像内存布局

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

Linux 进程内存空间布局

Linux 进程 -ELF 程序头

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

Linux 启动与内存空间布局 #

UNIX 进程存储管理 #

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

UNIX 进程虚实地址映射机制

假设页面大小为128个内存字符块，某进程的数据段使用了3个内存字符块，而用户栈使用了2个内存字符块，试分别给出它们的PLF值？

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

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

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

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

UNIX 进程被调度时地址映射

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

Linux 进程 - 线程空间探析 #

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

Linux 内存管理 #

页面 struct page

内存管理区 struct zone

页面的分配与释放

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

小块内存分配机制

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

内存描述符 struct mm_struct

内存分配与释放

缺页异常处理

页面淘汰机制

Linux 处理器及进程调度 #

Linux 处理器调度概要 #

处理器调度类型

处理器调度算法

处理器调度评价指标

Linux 内核基础设施

Linux 处理器调度算法

Linux 虚拟机进程调度

Linux 处理器调度算法 #

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

O(1) 调度算法

CFS 调度算法

Linux VServer 虚拟机机制

UNIX 进程调度 #

UNIX 进程调度功能框架

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

UNIX 进程调度策略

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

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

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