进程管理

ps

查看当前进程瞬时快照

top

显示当前正在运行进程（动态更新）

• 按照使用内存大小排序，可以用于查找内存使用情况

pgrep

按名称、属性查找进程

pidof

根据进程名查找正在运行的进程进程号

kill

终止进程

killall

按名称终止进程

pkill

按名称、属性终止进程

timeout

在指定时间后仍然运行则终止进程

wait

等待指定进程

fuser

显示使用指定文件、socket的进程

pmap

报告进程的内存映射

lsof

列出打开的文件

chkconfig

为系统服务更新、查询运行级别信息

作业

&

放在命令之后，命令后台执行

1
2
3

$ ./pso > pso.file 2>&1 &
	# 将`pso`放在后台运行，把终端输出（包括标准错误）
		# 重定向的到文件中

nohup

不挂起job，即使shell退出

1
2
3
4

$ nohup ./pso > pso.file 2>&1 &
	# 不挂起任务，输出重定向到文件
$ nohup -p PID
	# 不挂起某个进程

jobs

列出活动的作业

-l：返回任务编号、进程号

bg

恢复在后台暂停工作的作业

1
2

$ bg %n
	# 将编号为`n`的任务转后台运行

fg

将程序、命令放在前台执行

1
2

$ fg %n
	# 将编号为`n`的任务转前台运行

setsid

在一个新的会话中运行程序

1
2
3
4

$ setsid ./test.sh &`
	# 新会话中非中断执行程序，此时当前shell退出不会终止job
$ (./test.sh &)
	# 同`setsid`，用`()`括起，进程在subshell中执行

`disown

1
2
3

$ disown -h %job_id
	# *放逐*已经在后台运行的job，
	# 则即使当前shell退出，job也不会结束

screen

创建断开模式的虚拟终端

1
2
3
4
5
6

$ screen -dmS screen_test
	# 创建断开（守护进程）模式的虚拟终端screen_test
$ screen -list
	# 列出虚拟终端
$ screen -r screen_test
	# 重新连接screen_test，此时执行的任何命令都能达到nohup

快捷键

• <c-z>：挂起当前任务
• <c-c>：结束当前任务

网络

ping

向被测试目的主机地址发送ICMP报文并收取回应报文

• -c：要求回应的次数
• -i：发送ICMP报文时间间隔
• -R：记录路由过程
• -s：数据包大小
• -t：存活数值（路由跳数限制）

ifconfig

显示、设置网络

• netmask：设置网卡子网掩码
• up：启动指定网卡
• down：关闭指定网络设备
• ip：指定网卡ip地址

netstat

显示与网络相关的状态信息：查看网络连接状态、接口配置信息、 检查路由表、取得统计信息

• -a：显示网络所有连接中的scoket
• -c：持续列出网络状态
• -i：显示网络界面信息表单
• -n：直接使用IP地址而不是主机名称
• -N：显示网络硬件外围设备号连接名称
• -s：显示网络工作信息统计表
• -t：显示TCP传输协议连接状况

route

查看、配置Linux系统上的路由信息

traceroute

跟踪UDP路由数据报

• -g：设置来源来路由网关
• -n：直接使用IP地址而不是主机名称
• -p：设置UDP传输协议的通信端口
• -s：设置本地主机送出数据包的IP地址
• -w：超时秒数（等待远程主机回报时间）

网络配置

HOST

/etc/hostname

设置主机名称，直接填写字符串即可

1

PC-NAME

/etc/hosts

ipd地址-主机名称映射

• 理论上说，这里主机名称应该是本机称呼，不要求其他主机 /etc/hostname与这里的主机名一致

1
2
3

127.0.0.1 localhost
xxx.xxx.xxx.xxx name
xxx.xxx.xxx.xxx domain.name

DNS Resolver

相关问题

• Temporary failure in name resolution
  • 问题：可能是DNS服务器配置缺失、错误
  • 场景：$ ping
  • 解决：设置nameserver配置DNS服务器地址

/etc/resolv.conf

域名解析器（resolver）（DNS客户机）配置文件

• 设置DNS服务器IP地址、DNS域名
• 包含主机域名搜索顺序

1
2
3
4

nameserver		114.114.114.114		# DNS服务器IP地址
domain			localhost			# 本地域名
search			search_list			# 域名搜索列表
sortlist							# 允许将得到域名结果进行排序

说明

• nameserver：可以有多行，每行一个ip地址，查询时按照 顺序依次查找
• domain：声明主机域名
  • 查询无域名主机时需要使用
  • 邮件系统需要使用
  • 未配置则使用主机名
• search：其参数指明域名查询顺序
  • 查询无域名主机时，将在其参数声明域中分别查找
  • domain、search不共存，同时存在时，后者覆盖前者
• sortlist：对得到的域名结果进行特定排序
  • 参数未网络/掩码对时，允许任意排列顺序

系统设置/etc/sysconfig

/etc/sysconfig/network[-scripts]

文件夹包含网卡配置文件

一般linux

• ifcfg-ethXX：linux默认ethernet网卡配置文件名称
• ifcfg-wlanXX：无线局域网网卡配置文件名称

CentOS7网卡名称

• 前两个字符

  • en：Enthernet以太网
  • wl：WLAN无线局域网
  • ww：WWAN无线广域网

• 第3个字符

  • o<index>：on-board device index number,
  • s<slot>：hotplug slot index number
  • x<MAC>：MAC address
  • p<bus>s<slot>：PCI geographical location/USB port number chain

• 命名优先级

  • 板载设备：固件、BIOS提供的索引号信息可读：eno1
  • 固件、BIOS提供的PCI-E热拔插索引号可读：ens33
  • 硬件接口物理位置：enp2s0
  • linux传统方案：eth0
  • 接口MAC地址：enxXXXXXXXXXXXXXXXXX，默认不使用， 除非用户指定使用

• 示例

  • enoXX：主板bios内置网卡
  • ensXX：主板bios内置PCI-E网卡
  • enpXXs0：PCI-E独立网卡

恢复传统命名方式

编辑grub文件，然后使用grub2-mkconfig重新生成 /boot/grub2/grub.cfg，这样系统就会根据传统linux网卡文件 命名方式查找配置文件

1
2
3

	# `/etc/sysconfig/grub`
GRUB_CMDLINE_LINUX="net.ifnames=0 biosdevname=0"
	# 为`GRUB_CMDLINE_LINUX`增加2个参数

CentOS7配置格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

DEVICE=ens33				# 网络连接名称（实际显示的网络名称）
NAME=ens33					# 网卡物理设备名称
TYPE = Ethernet				# 网卡类型：以太网
ONBOOT=yes					# 开机启动：是
DEFROUTE=yes				# 是否设置此网卡为默认路由：是
NM_CONTROLLED=yes			# 是否可由Network Manager托管：是

BOOTPROTO=dhcp				# 网卡引导协议
							# `none`：禁止DHCP
							# `static`：启用静态IP地址
							# `dhcp`：开启完整DHCP服务
IPADDR=xxx.xxx.xxx.xxx		# IP地址
IPV4_FAILURE_FATAL=no		# IPV4致命错误检测（失败禁用设备）：否
IPV6INIT=yes				# IPV6自动初始化：是
IPV6_AUTOCONF=yes			# IPV6自动配置：是
IPV6_DEFROUTE=yes			# IPV6是否可为默认路由：是
IPV6_FAILURE_FATAL=no		# IPV6致命错误检测（失败禁用设备）：否
IPV6_ADDR_GEN_MODE=stable-privacy
							# IPV6地地址生成模型：stable-privacy

DNS1=xxx.xxx.xxx.xxx		# DNS服务器地址1
DNS2=xxx.xxx.xxx.xxx		# DNS服务器地址2
PEERDNS=no					# 是否允许DHCP获得DNS覆盖本地DNS：否
GATEWAY=xxx.xxx.xxx.xxx		# 网关
PREFIX=24					# 子网掩码使用24位
NETMASK=255.255.255.0		# 子网掩码
							# 两个参数应该只需要使用一个即可
BROADCAST=	

HWADDR=xxxxxxxxxx			# 接口MAC地址
							# 配置文件都会被执行，`HWADDR`
							# 能匹配上硬件，配置才会生效，
							# 否则硬件使用默认配置
							# 若多个配置文件配置相同`HWADDR`
							# 则操作network服务时报错
UUID=xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
							# 通用唯一识别码：不能相同（注意虚拟机）

PROXY_METHOD=none			# 代理方式：无
BROWSER_ONLY=no				# 仅浏览器：否

USERCTL=no					# 是否允许非root用户控制此设备：否
MASTER=						# 主设备名称？
SLAVE=						# 从社会名称？
NETWORK=					# 网络地址

硬件

磁盘挂载

/etc/fstab

/etc/fstab：包含存储设备、文件系统信息，配置自动挂载 各种文件系统格式硬盘、分区、可移动设备、远程设备 （即mount参数存盘）

1

<fs> <mountpoint> <type> <opts> <dump> <pass>

• <fs>：挂载设备/分区名

  • /dev/sda：设备/分区名
  • UUID=xxxxx：使用设备UUID值表示设备
  • tmpfs：tmpfs分区，默认被设置为内存的一半（可在 <opts>中添加size=2G指定最大空间）

  • 所有设备/分区都有唯一UUID，由文件系统生成工具mkfs. 创建文件系统时生成

• <mountpoint>：挂载点，路径名（文件夹）

  • /
  • /boot

  • 路径名中包含可以空格使用\040（8进制）表示

• <type>：文件系统类型

  • ext2
  • ext3
  • reiserfs
  • xfs
  • jfs
  • iso9660
  • vfat
  • ntfs
  • swap
  • tmpfs：临时文件系统，驻留在交换分区、内存中
    • 提高文件访问速度，保证重启时自动清除这些文件
    • 常用tmpfs的目录：/tmp、/var/lock、/var/run
  • auto：由mount自动判断

• <opts>：文件系统参数

  • noatime：关闭atime特性

    • 不更新文件系统上inode访问记录，提高性能，否则 即使从缓冲读取也会产生磁盘写操作
    • 老特性可以放心关闭，能减少loadcycle
    • 包含nodiratime

  • nodiratime：不更新文件系统上目录inode访问记录

  • relatime：实时更新inode访问记录，只有记录中访问 时间早于当前访问才会被更新

    • 类似noatime，但不会打断其他程序探测，文件在 上次访问后是否需被修改（的进程）

  • auto：在启动、终端中输入$ mount -a时自动挂载

  • noauto：手动挂载

  • ro：挂载为自读权限

  • rw：挂载为读写权限

  • exec：设备/分区中文件可执行

  • noexec：文件不可以执行

  • sync：所有I/O将以同步方式进行

  • async：所有I/O将以异步方式进行

  • user：允许任何用户挂载设备，默认包含 noexec,nosuid,nodev（可被覆盖）

  • nouser：只允许root用户挂载

  • suid：允许set-user/group-id（固化权限）执行

    • set-user/group-id参见linux/shell/config_files

  • nosuid：不允许set-user/group-id权限位

  • dev：解释文件系统上的块特殊设备

  • nodev：不解析文件系统上块特殊设备

  • umask：设备/分区中文件/目录默认权限掩码

    • 权限掩码参见linux/kernel/file_system.md

  • dmask：设备/分区中目录默认权限掩码

  • fmask：设备/分区中普通文件默认权限掩码

  • nofail：设备不存在则直接忽略不报错

    • 常用于配置外部设备

  • defaults：默认配置，等价于 rw,suid,exec,auto,nouser,async

• <dump>：决定是否dump备份

  • 1：dump对此文件系统做备份
  • 0：dump忽略此文件系统

  • 大部分用户没有安装dump，应该置0

• <pass>：是否以fsck检查扇区，按数字递增依次检查（相同 则同时检查）

  • 0：不检验（如：swap分区、/proc文件系统）
  • 1：最先检验（一般根目录分区配置为1）
  • 2：在1之后检验（其他分区配置为2）

• /etc/fstab是启动时配置文件，实际文件系统挂载是记录到 /etc/mtab、/proc/mounts两个文件中

• 根目录/必须挂载，必须先于其他的挂载点挂载

文件系统配置

Ext 配置文件

• /etc/mke2fs.conf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[defaults]
	base_features = sparse_super,large_file,filetype,resize_inode,dir_index,ext_attr
	default_mntopts = acl,user_xattr
	enable_periodic_fsck = 0
	blocksize = 4096				# 块大小
	inode_size = 256				# Inode 大小
	inode_ratio = 16384				# 分配 Inode 号间隔

[fs_types]
	ext3 = {
		features = has_journal
	}
	ext4 = {
		features = has_journal,extent,huge_file,flex_bg,metadata_csum,64bit,dir_nlink,extra_isize
		inode_size = 256
	}

[options]
	fname_encoding = utf8

文件系统状态

du、df

• https://www.junmajinlong.com/linux/du_df

目录、文件操作

pwd

pwd：显示当前工作目录绝对路径

cd

cd：更改工作目录路径

• 缺省回到用户目录
• -：回到上个目录

ls

1

$ ls [params] expr

列出当前工作目录目录、文件信息

参数

• -a：列出所有文件，包括隐藏文件
• -l：文件详细信息
  • 详细信息格式、含义参见config_file
• -t：按最后修改时间排序
• -S：按文件大小排序
• -r：反向排序
• -h：显示文件大小时增加可读性
• -F：添加描述符到条目后
  • @：符号链接
  • *：文件
  • /：目录
• -i：显示索引节点

输出结果

• 文件权限：包括10个字符

  • 第1字符：文件类型
    • -；普通文件
    • d：目录
    • l：link，符号链接
    • s：socket
    • b：block，块设备
    • c：charactor，字符设备（流）
    • p：FIFO Pipe
  • 第2-4字符：owner，文件属主权限
  • 第5-7字符：group，同组用户权限
  • 第8-10字符：other，其他用户权限
    • 权限分别为r读、w写、x执行
    • 相应位置为-表示没有此权限
  • 执行位还可能是其他特殊字符
    • users：文件set-user-id、执行权限同时被置位
    • groups：文件set-group-id、执行权限同时被置位
    • userS：文件set-user-id被置位，执行权限未置位
    • groupS：文件set-group-id被置位，执行权限未置位
    • othert：文件sticky bit、执行权限均被置位
    • otherT：文件sticky bit被置位、执行权限未置位

  • 关于权限具体含义，参见linux/kernel/file_system
  • 权限设置，参见linux/shell/cmd_fds

• 文件数量

  • 一般文件：硬链接数目
  • 目录：目录中第一级子目录个数

• 文件属主名

• 文件属主默认用户组名

• 文件大小（Byte）

• 最后修改时间

• 文件名

dirs

显示目录列表

touch

创建空文件或更改文件时间

mkdir

创建目录

rmdir

删除空目录

cp

复制文件和目录

mv

移动、重命名文件、目录

rm

删除文件、目录

• 删除目录link时，注意末尾不要带/，否则被认为是目录， 此时rm -r <target>会删除源目录中文件

file

查询文件的文件类型

du

显示目录、文件磁盘占用量（文件系统数据库情况）

参数

• -a/--all：显示所有后代各文件、文件夹大小
  • 否则默认为显示所有后代文件夹大小
• -c/--total：额外显示总和
• -s/--summarize：仅显示总和
• --max-depth=[num]：显示文件夹的深度

• -S/--separate-dirs：文件夹大小不包括子文件夹大小

• -b/--bytes：以byte为单位

• -k/--kilobytes：以KB为单位
• -m/--megabytes：以MB为单位
• -h：human-readable，提升可读性

• -H/--si：同-h，但是单位换算以1000为进制

• -x/--one-file-system：以最初处理的文件系统为准，忽略 其他遇到的文件系统

• -L=/--dereference=：显示选项中指定的符号链接的源文件 大小
• -D/--dereference-args：显示指定符号链接的源文件大小
• -X=/--exclude-from=[file]：从文件中读取指定的目录、 文件
• --exclude=[dir/file]：掠过指定目录、文件
• -l/--count-links：重复计算hard-link

wc

统计文件行数、单词数、字节数、字符数

-    `-l, -w, -c`

tree

树状图逐级列出目录内容

cksum

显示文件CRC校验值、字节统计

mk5sum

显示、检查MD5（128bit）校验和

sum

为文件输出校验和及块计数

dirname

输出给出参数字符串中的目录名（不包括尾部/） ，如果参数中不带/输出.表示当前目录

basename

输出给出参数字符串中的文件、目录名

ln

创建链接文件

stat

显示文件、文件系统状态

文件、目录权限、属性

chown

更改文件、目录的用户所有者、组群所有者

chgrp

更改文件、目录所属组

umask

显示、设置文件、目录创建默认权限掩码

getfacl

显示文件、目录ACL

setfacl

设置文件、目录ACL

chacl

更改文件、目录ACL

lsattr

查看文件、目录属性

chattr

更改文件、目录属性

umask

查看/设置权限掩码，默认0000

1
2
3
4
5
6

$ umask
	# 数字形式返回当前权限掩码
$ umask -S
	# 符号形式返回当前权限掩码
$ umask 0003
	# 设置权限掩码为`0003`

• 权限掩码参见linux/kernel/permissions

chmod

关于文件、目录权限参见config_files###文件描述

• 普通用户只能修改user权限位
• root用户可以修改任意用户、任意文件权限

参数

• -R：对整个目录、子文件（目录）同时修改权限

操作

1
2

$ chmod [ugoa][+-=][rwxst] file
$ chmod xxxx file

• ugoa：分别表示user、group、other、all权限位
• +-=：表示增加、减少、设置权限

• rwxst：表示5不同的权限

  • S、T不是一种权限，只是一种特殊的状态
  • 设置状态时s时，是根据相应的x是否有确定s/S
  • 设置状态t同理

• xxxx：每个8进制数表示一组权限，对应二进制表示相应权限 是否置位

  • 第1个数字：set-user-id、set-group-id、sticky bit
  • 后面3个数字分别表示user、group、other权限
  • 第1个数字位0时可以省略（常见）

示例

1
2

$ chmod u+s file1
$ chmod 7777 file1

磁盘

df

文件系统信息

fdisk

查看系统分区

mkfs

格式化分区

fsck

检查修复文件系统

mount

查看已挂载的文件系统、挂载分区

umount

卸载指定设备

free

查看系统内存、虚拟内存占用

Ext 文件系统

Ext 文件系统结构

• dumpe2fs 命令可以获取 Ext 类文件系统信息
• https://www.junmajinlong.com/linux/ext_filesystem/

Index Node

Index Node/Inode 索引节点：记录文件的元信息

• 文件元信息

  • 文件大小
  • 访问权限
  • 创建时间
  • 修改时间
  • 数据块位置

• Inode 是文件的唯一标识，和文件一一对应

  • 存储在磁盘中，占用磁盘空间，大小为 126B 整数倍
  • 通常会把索引节点加载到内存中，加速文件的访问

• Inode 并未存储 Inode 号、文件名，而是存储在文件所在目录的数据块中

Inode 号

• Inode 号在同一文件系统内部唯一，可以、且被用于确定、定位 Inode

  • 创建文件系统时，每个块组中起始 Inode 号、Inode Table 起始地址确定
    • Inode 号按分配比率（间隔字节数）预分配
    • 若系统中大文件较多，Inode 分配比率应较大，避免 Inode Table 占用过大空间
  • 根据 Inode 号、Inode 结构大小计算偏移即可查确定

• Ext 预留部分 Inode 作特殊用途

  • 0：不存在，用于标识已删除文件
  • 1：虚拟文件系统，如：/proc、/sys
  • 2：根目录
  • 3：ACL 索引
  • 4：ACL 数据
  • 5：boot loader
  • 6：未删除的目录
  • 7：Reserved GDT
  • 8：日志
  • 11：首个非预留 Inode 号，通常是 lost+found 目录

• Inode 大小默认值在 /etc/mke2fs.conf 文件中指定
• ls -i 可查看文件 Inode 号
• find 可以使用 -inum 参数寻找指定 Inode 号文件

Inode 寻址

• Ext2/3 中 Inode 寻址混合直接查找、多级索引

• Inode 中包含 15 个指针 i_block[0..14]，分为 4 级

  • i_block[0..11]：直接寻址指针，直接指向数据块
  • i_block[12]：一级间接寻址指针，指向存储指针的块
  • i_block[13]：二级间接寻址指针
  • i_block[14]：三级间接寻址指针

• 根据文件大小选择不同的寻址方法

  • 文件小于 12block 时，直接用直接寻址指针
  • 文件较大时则利用更高级别的间接寻址指针，多级索引
  • Ext2/3 对超大文件存取效率低下，需要核对指针过多

  

Inode 内容

Hard Link

• 硬链接：指向 Inode（文件） 的 目录项

  • 此处文件、硬链接说明
    • 文件：Inode、相应数据块
    • 硬链接：目录文件中目录项
  • 硬链接是目录项
    • 同一个文件的多个硬链接应是仅文件名不同的目录项
    • Ext 文件系统中 Inode 号、文件名均在存储在目录项中即完美支持硬链接

• 硬链接创建、删除

  • 创建硬链接会增加文件的硬链接数
    • 不能跨分区创建硬链接：不同分区 Inode 号会重复
    • 不能手动对目录文件创建硬链接：防止路径混乱，文件系统已经为目录创建硬链接
      • .：当前目录硬链接
      • ..：上级目录硬链接
    • 目录的硬链接数 = 2 + 一级子目录数
      • 父目录中目录项
      • 自身 . 目录项
      • 子目录中 .. 目录项
  • 删除文件实质上就是删除硬链接，文件的硬链接数量归 0 时才被真正删除

  • ls -l 中第二行即为文件的硬链接数（包含文件自身）

• / 根目录是自引用的（唯一），即 .. 也指向自身

Symbolic Link

• 符号链接 / 软链接：通过文件名的链接文件的 文件
  • 符号链接是文件
    • 文件内容可认为是指向的目标路径，这也决定温文件大小
    • 符号链接文件本身也可以有多个硬链接、符号链接
  • 一般不占用数据块，Inode 记录即可描述完成
    • 只有符号链接指向的目标路径过长（大于 60B）时才会分配数据块
  • 符号链接权限不重要，取决于最终目标文件

• readlink 可以查看符号链接之

设备文件、FIFO、Socket

• 设备文件、FIFO、Socket
  • 没有大小，不占用数据块，在 Inode 记录中即可描述完成
    • 主设备号：标识设备类型
    • 次设备号：标识同种设备类型的不同编号

Block Group

Block Group 块组：逻辑上对块分组，提高查询效率

• 块组划分是文件系统创建的一部分

  • 一个磁盘分区包含多个块组
  • 块组是逻辑层面的划分，不会类似分区在磁盘上标记、划分

• 每个块组包含多个元数据区、数据区

  • 元数据区：存储 Bmap、Inode Table、Imap 等数据
  • 数据区：存储文件数据

• 块组特点

  • 块组大小（包含块数）= 块 bit 数，即单个 block （作为）Bmap 能标记的块数量
    • 此大小包含元数据区（也需要 Bmap 标记是否被占用）
  • 块组设置的 Inode 数量、Inode Table 由系统决定

分区级 Block

• 以下这些块不会出现在所有块组中，存储文件系统级别信息

Boot Block

• Boot Block / Boot Sector：存放有 boot loader 的块

  • 特点
    • 位于分区的首个块
    • 占用 1024B
    • 只有装有系统的主分区、逻辑分区才有 Boot Block
  • Boot Block 在不同分区时称为
    • 主分区装有操作系统时：Volume Boot Records
    • 逻辑分区装有操作系统时：Extended Boot Records

• MBR 会引导 VBR/EBR，开机启动时，首先加载 MBR 上 boot loader

  • 单操作系统时，直接定位到所在分区的 Boot Block，加载此处的 boot loader
  • 多操作系统时，加载 MBR 中 boot loader 后列出操作系统菜单，指向各分区的 boot block

  

  • 通过 MBR 管理启动菜单方式已经被 Grub 取代

Super Block

• Super Block：存储文件系统信息、属性元数据

  • 存储的信息包括
    • 块组的 block 数量、Inode 号数量
    • 文件系统本身的空闲 block 数量、Inode 数量
    • 文件系统本身的属性信息：时间戳、是否正常、自检时间
  • （首个）超级块的位置取决于块大小
    • 块大小为 1KB 时，引导块正好占用 1 个 block，则超级块号为 1
    • 块大小大于 1KB 时，超级块和引导块均位于 0 号块

• 超级块对文件系统至关重要

  • 超级块丢失和损坏必然导致文件系统损坏

  • Ext2 只在 0、1 和 3、5、7 的幂次块组中保存超级块信息

    • 但文件系统只使用首个块组的超级块信息获取文件系统属性，除非损坏或丢失

    • 有些旧式文件系统将超级块备份至每个块组

• df 命令读取文件系统的超级块，统计速度快

Group Descriptor Table

• GDT 块组描述符表：存储块组的信息、属性元数据

  • Ext 每个块组使用 32B 描述，被称为块组描述符，所有块组描述符组成 GBT
    • GDT 和超级块同时出现在某些块组中
    • 默认也只会读取 0 号块组的中 GDT

• Reserved GDT：保留作为 GDT 使用的块（扩容之后块组增加）

  • 和 GDT、超级块同时出现，同时修改

• GDT、Reserved GDT、超级块在某些块组同时出现，能提升维护效率

块组级 Block

Block Bitmap

Block Bitmap/Bmap 块位图：标记各块空闲状态

• Bmap 只优化写效率
  • 向磁盘写数据时才需要寻找空闲块，读数据时按照索引读取即可
  • Bamp 查询速度足够快，则向磁盘写数据效率极大取决于磁盘的随机读写效率

Inode Table

• Inode Table：物理上将多个 Inode 合并存储在块中
  • Inode 大小一般小于块大小，合并存储能节约存储空间

Inode Bitmap

Inode Bitmap/Imap 位图：标记各 Inode 号占用状态

Data Blocks

• Data Blocks：直接存储数据的块
  • 数据占用的块由文件对应 Inode 记录中块指针找到
  • 不同类型文件在数据块中存储的内容不同
    • 常规文件：存储文件数据
    • 目录：存储目录下文件、一级子目录
    • 符号链接：目标路径名较短则直接存储在 Inode 中，否则分配数据块保存

目录文件数据块

• 目录文件数据块存储多条目录项，每条目录项包含目录下
  • 文件 Inode 号
  • 目录项长度 rec_len
  • 文件名长度 name_len
  • 文件类型
    • 0：未知
    • 1：普通文件
    • 2：目录
    • 3：*character devicev
    • 4：block device
    • 5：命名管道
    • 6：socket
    • 7：符号链接
  • 文件名：文件名、一级子目录名、.、..

Directory Entry

Directory Entry/Dentry 目录项（缓存）：存放内存中的缩略版磁盘文件系统目录树结构

• Dentry 中需要记录

  • 文件名称
  • Inode 指针：与文件名建立映射关系
  • 与其他目录项的层级关联关系
    • 包括：父目录、子目录链表
    • 多个目录项通过指针关联起来就形成目录结构

• Dentry 是由内核维护，缓存在内存中

  • 内核会把读过的文件用 Dentry 缓存在内存中，提高文件系统效率

• Inode、Dentry 是一对多的关系

  • 即一个文件可以有多个别字
  • 硬链接实现就是多个 Dentry 中的 Inode 指向同一个文件

文件系统挂载

• Mount 挂载：将文件系统关联到路径

• 文件系统必须要挂载在一定路径下才能被使用

  • 文件系统体现在系统中即目录，即其文件系统的入口目录（根目录）
  • 而入口目录无名、无显式 Inode 号
    • Ext 中文件名、Inode 号存储在父目录中，入口目录是文件系统最底层目录，不存在父目录
    • 入口目录无名，所以挂载在任何目录下都是合理的
    • 入口目录被预留 Inode 号为 2，可直接寻址

• 挂载方式

  • / 根目录下挂载根文件系统，在系统启动之初即挂载
  • 其余文件系统则挂载在根文件系统的目录之下

挂载逻辑

• 挂载实现逻辑

  • 新建 Inode，将其寻址指针指向待挂载文件系统
  • 将挂载点目录 Inode 标记为不可用
  • 修改挂载点目录在其父目录目录项至新建 Inode
    • 挂载期间原目录会被遮蔽
    • 挂载点仍然是所在文件系统的文件，但是其数据不在

• 同步挂载信息

  • 挂载完成后，将挂载记录、相关信息写入 /proc/self/{mounts, mountstats, mountinfo}
  • 同步 /proc/self/mounts 同步至 /etc/mtab（若有必要）

文件操作

文件读取

• / 文件系统在系统启动时即挂载，此时已经读取超级块、GDT 等文件系统块

• 同文件系统内 / 开头绝对地址

  • 根据 GDT 确定各块组 Inode Table 块号
  • 在 Inode Table 中查找 / 目录文件 Inode
    • / Inode 号已知为预留 Inode 号 2，可直接在 Inode Table 中定位
  • 获取 / 数据块，并读取其中目录项
  • 在目录项中查找目标记录，获取文件 Inode 号
  • 如上重复，直到找到目标文件 Inode，根据 i_block 寻址指针读取数据块

• 相对地址

  • 按照所处目录的目录项获取 Inode 号，同绝对地址即可

• 跨文件系统地址

  • 类似同文件系统
  • 但挂载点目录会指向目标文件系统入口目录，再同绝对地址即可

文件删除

• 删除普通文件

  • 同读取找到文件 Inode、数据块
    • 将文件 Inode 硬链接数量减一
    • 若硬链接数量归 0，执行删除，否则不变
  • 将 Inode 中寻址指针删除
    • 此时即无法找到文件数据
  • 在 Imap 中标记文件 Inode 号为未使用
  • 删除文件所属目录的目录项
    • 实务中会将目录项 Inode 号标记为 0，避免产生空洞
    • 此时文件即不可见
  • 将 Bmap 中文件数据块块号标记为未使用
    • 此时即释放文件占用空间，若此时有其他进程持有数据块的指针，则文件系统不会立即释放该空间
    • Ext 系统中此步骤会导致删除大文件效率低

• 删除目录文件

  • 若目录非空，则尝试递归删除其中文件、子目录
  • 若目录为空，类似普通文件删除目录

文件移动、重命名

• 同目录文件重命名：修改文件所属目录的目录项中文件名

• 同文件系统下移动：增、删目录项

  • 文件移动不修改 Inode、Inode 号等

• 不同文件系统下移动：先复制、再删除

• 命名冲突时，覆盖会删除冲突文件，并修改相应目录项至新文件
• 因此，Ext 无法用同名子目录覆盖父目录，在尝试删除父目录时即失败

文件存储、复制

• 文件存储

  • 读取 GDT，寻找空闲块组
  • 根据块组 Imap 为文件分配未使用 Inode 号
  • 在 Inode Table 中完善 Inode 中文件元数据
  • 在所属目录中添加目录项
  • 将数据写入数据块
    • Ext2/3 中每次调用 block 分配器为数据分配 1 个数据块，直至写入完毕
    • Ext4 中允许一次分配多个数据块
  • 在 Inode Table 中更新 Inode 寻址指针

• 文件复制同文件存储

Ext2/3/4 迭代

• Ext 文件系统特点
  • 在创建时即划分好，方便使用时分配
    • 不支持动态划分、分配
    • 格式化超大磁盘时较慢

Ext3 日志功能

• Ext2 中只有两个区：元数据区、数据区

  • 从数据块中写入数据的中断中恢复检查一致性需要大量时间，甚至失败

• Ext3 增加日志区

  • 在向数据块中写入数据前会在日志区标记
  • 则根据日志区的标记即可判断操作完成情况，提高一致性确认效率

Ext4 段分配

• Ext2/3 中

  • Bmap 标记、分配块能提高效率，但扫描 Bmap 效率仍很低
  • 多级索引寻址效率低

• Ext4 中使用 extent 管理数据块

  • extent 尽可能包含物理上连续的块
  • Inode 中使用 4 个 extent 片段流替代多级索引指针
    • 每个 extent 片段流设定起始块号、块数量
    • extent 指向的块保存数据或索引指针
  • 支持调用一次 block 分配器分配多个块，并标记对应 Bmap

  

• Ext 删除数据

  • 会依次释放 Bmap 位、更新目录结构、释放 Inode 空间

Kernel

内核：提供硬件抽象层、磁盘及文件系统控制、多任务等功能的系统 软件

• 内核是操作系统的核心、基础，决定系统的性能、稳定性

  • 内核单独不是完整的操作系统

• 内核为应用程序提供对硬件访问

  • 应用程序对硬件访受限
    • 内核决定程序何时、对何种硬件操作多长时间
  • 内核提供硬件抽象的方法隐藏对硬件操作的复杂
    • 为应用程序和硬件提供简洁、统一的接口
    • 简化程序设计

内核功能

• 进程管理：实现了多个进程在CPU上的抽象

  • 负责创建、销毁进程，处理它们和外部输入、输出
  • 处理进程之间通讯
    • 信号
    • 管道
    • 通讯原语
  • 调度器控制进程如何共享CPU

• 内存管理：内存是主要资源，对其管理策略对性能影响非常重要

  • 为所有进程在有限资源上建立虚拟寻址空间
  • 内核不同部分与内存管理子系统通过函数调用交互，实现 malloc、free等功能

• 文件管理：Linux很大程度上基于文件系统概念，几乎任何东西 都可以视为是文件

  • 在非结构化硬件上建立了结构化文件系统
  • 支持多个文件系统，即物理介质上的不同数据组织方式

• 驱动管理

  • 除CPU、内存和极少的硬件实体外，基本设备控制操作都由 特定的、需寻址的设备相关代码（设备驱动）进行
  • 内核中必须嵌入系统中出现每个外设驱动

• 网络管理

  • 网络必须由系统管理
    • 大部分网络操作不是特定于某个进程：进入系统的报文 是异步事件
    • 系统在进程接手报文前收集、识别、分发，在程序和 网络接口间递送数据报文，根据程序的网络活动控制 程序执行
  • 路由、地址解析也在内核中实现

System Call

系统调用：操作系统提供的实现系统功能的子程序、访问硬件资源 的唯一入口

• 系统调用是用户空间进程访问内核、硬件设备的唯一手段

  • 用户空间进程不能直接访问内核、调用内核函数
  • 对计算机硬件资源的必须经过操作系统控制
    • 计算机系统硬件资源有限，多个进程都需要访问资源

• 系统调用与硬件体系结构紧密相关

  • 在用户空间进程和硬件设备之间添加中间层，是二者沟通的 桥梁
  • 是设备驱动程序中定义的函数最终被调用的一种方式

系统调用意义

• 用户程序通过系统调用使用硬件，简化开发、移植性

  • 分离了用户程序和内核的开发
    • 用户程序忽略API具体实现，仅借助其开发应用
    • 内核忽略API被调用，只需关心系统调用API实现
  • 为用户空间提供了统一硬件抽象接口，用户程序可以方便在 具有相同系统调用不同平台之间迁移

• 系统调用保证了系统稳定和安全

  • 内核可以基于权限和其他规则对需要进行的访问进行 裁决
  • 避免程序不正确的使用硬件设备、窃取其他进程资源、 危害系统安全

• 保证进程可以正常运行在虚拟寻址空间中

  • 程序可以随意访问硬件、内核而对此没有足够了解， 则难以实现多任务、虚拟内存
  • 无法实现良好的稳定性、安全性

通知内核

• 大部分情况下，程序通过API而不是直接调用系统调用
• POSIX标准是Unix世界最流行的API接口规范，其中API和系统 调用之间有直接关系，但也不是一一对应

系统调用表

系统调用表sys_call_table：其中元素是系统调用服务例程的 起始地址

1
2
3
4
5

// arch/x86/entry/syscall_64.c
asmlinkage const sys_call_ptr sys_call_table[__NR_syscall_max+1] ={
	[0 ... __NR_syscall_max] = &sys_ni_syscall,
#include <asm/syscalls_64.h>
};

• ...是GCCDesignated Initializers插件功能，此插件允许 无序初始化元素值

• sys_call_table是长为__NR_syscall_max+1的数组

• __NR_syscall_max是给定系统架构所允许的最大系统调用 数目

  1 2	// include/generated/asm-offsets.h #define __NR_syscall_max 547

  • 此数值必然和arch/x86/entry/syscalls/syscall_64.tbl 中最大系统调用数值相同

• sys_call_ptr是指向系统调用表指针类型

  1	typedef void (*sys_call_ptr_t)(void);

• sys_ni_syscall是返回错误的函数

  1 2 3

  asmlinkage long sys_ni_syscall(void){ return -ENOSYS; }

  • 未在<asm/syscalls_64.h>定义系统调用号将会对应此 响应函数，返回ENOSYS专属错误

• <asm/syscalls_64.h>由脚本 arch/x86/entry/syscalls/syscalltbl.sh从 arch/x86/entry/syscalls/syscall_64.tbl中生成

  1 2 3 4 5 6 7

  // <asm/syscalls_64.h> __SYS_COMMON(0, sys_read, sys_read) __SYS_COMMON(0, sys_write, sys_write) // <arch/x86/entry/syscall_64.c> #define __SYSCALL_COMMON(nr, sym, compat) __SYSCALL_64(nr, sym, compat) #define __SYSCALL_64(nr, sym, compat) [nr] = sym

系统调用号

1
2
3
4
5
6
7

/* fs/xattr.c */
#define __NR_setxattr 5
__SYSCALL(__NR_setxattr, sys_setxattr)
#define __NR_lsetxattr 6
__SYSYCALL(__NR_lsetxattr, sys_lsetattr)
#define __NR_fsetxattr 7
__SYSYCALL(__NR_fsetxattr, sys_fsetattr)

系统调用号_NR_XXX：系统调用唯一标识

• 系统调用号一旦分配不能有任何变更，否则编译好的程序会崩溃

  • 系统调用号定义在include/asm/unisted.h中

• 用户空间进程通过系统调用号指明需要执行的系统调用

  • 系统调用号就是系统调用在sys_call_table中的偏移
  • 根据系统调用号在sys_call_table中找到对应表项内容， 即可找到系统调用响应函数sys_NAME的入口地址

• 所有系统调用陷入内核的方式相同，所以必须把系统调用号一并 传给内核

  • X86机器上，系统调用号通过eax寄存器传递给内核
    • 陷入内核态，用户空间进程已经把系统调用对应系统 调用号放入eax中
    • 系统调用一旦运行，就可以从eax中得到数据

陷入指令

• 系统调用通过陷入指令进入内核态

  • 然后内核根据存储在寄存器中的系统调用号在系统调用表 中找到相应例程函数的入口地址
  • 根据入口地址调用例程函数

• 陷入指令是特殊指令，且依赖于机器架构，在X86机器中指令为 int 0x80

  • 不应直接使用陷入指令
  • 应实现系统调用库函数，以系统调用号为参数，执行陷入 指令陷入内核态，并执行系统调用例程函数，即 __syscall[N]系列宏

__syscall[N]

_syscall[N]：方便用户程序访问系统调用的一系列宏

1
2
3
4
5
6

// linux/include/asm/unistd.h
__syscall0(type, name)
__syscall1(type, name, type1, args1)
__syscall2(type, name, type1, arg1, type2, arg2)
// 0-6共7个宏
__syscall6(type, name, type1, arg1, type2, arg2, type3, arg3, type4, arg4, type5, arg5, type6, arg6)

1
2
3
4
5
6
7
8
9
10

#define _syscall2(type, name, type1, arg1, type2, arg2) \
type name(type1, arg1, type2, arg2) \
{ \
long _res; \
__asm__ volatile ("int $0x80" \
: "=a" (_res) \
: "0" (__NR##name), "b" ((long)(arg1)), "c" ((long)(arg2))); \
// some code
__syscall_return(type, __res)
}

• 7个宏分别可以适用于参数个数为0-6的系统调用 （超过6个参数的系统调用罕见）

• __syscall[N]宏根据系统调用名创建name同名函数，通过 该函数即可访问系统调用

• 大部分情况下用户程序都是通过库函数访问系统调用，调用 __syscall[N]系列宏通常由库函数完成
• Linux2.6.19内核之后弃用

syscall

syscall：通过系统调用号相应参数访问系统调用

1
2
3
4
5
6
7
8
9
10
11

int syscall(int number, ...);

#include <unistd.h>
#include <sys/syscall.h>
#include <sys/types.h>

int main(int argc, char *argv){
	pid_t tid;
	// `SYS_[NAME]`是系统调用号常量
	tid = syscall(SYS_getpid);
}

System Call Service Routine

系统调用服务例程/响应函数：系统调用的实际处理逻辑

• 一般以sys_开头，后跟系统调用名

  • fork()的响应函数是sys_fork()
  • exit()的响应函数是sys_exit()

• 系统调用可以看作是系统调用服务例程在内核中注册的 名，内核通过系统调用名寻找对应服务例程

  1 2 3 4

  // arch/x86/entry/syscalls/syscall_64.tbl 0 common read sys_read 1 common write sys_write 2 common open sys_open

参数传递

参数传递

• 除系统调用号外参数输入同样存放在寄存器中
  • X86机器上，ebx、ecx、edx、esi、edi按照顺序 存放前5个参数
  • 需要6个以上参数情况不多，此时应该用单独的寄存器存放 指向所有参数在用户空间地址的指针

参数验证

• 系统调用需要检查参数是否合法有效、正确

  • 文件IO相关系统调用需要检查文件描述符是否有效
  • 进程相关函数需要检查PID是否有效

• 用户指针检查，内核必须保证

  • 指针指向的内存区域属于用户空间：不能哄骗内核读取 内核空间数据
  • 指针指向的内存区域在进程地址空间：不能哄骗内核读取 其他进程数据
  • 进程不能绕过内存访问限制：内存读、写应被正确标记

访问系统调用

系统调用初始化

• 系统调用初始化就是对陷入指令的初始化，在X86机器上就是 初始化INT 0x80指令

• 系统启动时

  • 汇编子程序setup_idt()准备256项的idt表
  • 由start_kernel()、trap_init()调用的C宏定义 set_system_gate(0x80, &system_call)设置0x80号 软中断服务程序为system_call
  • system_call就是所有系统调用总入口

系统调用上下文

• 内核在执行系统调用时处于进程上下文

  • current指针指向当前任务，即引发系统调用的进程

• 在进程上下文中，内可以休眠、被抢占

  • 能够休眠：系统调用可以使用内核提供的绝大部分功能， 方便内核编程
  • 能被抢占：新进程可以使用相同的系统调用
    • 保证系统调用可重入

• 系统调用返回时，控制权依然在system_call()中，其会负责 切换到用户空间并让用户进程继续执行

系统调用返回值

errno错误码

• 系统调用将错误码放入名为errno的全局变量中

  • 为防止和正常返回值混淆，系统调用不直接返回错误码
  • errno值只在函数发生错误时设置，若函数不发生错误， errno值无定义，并不置为0
    • 0值通常表示成功
    • 负值表示系统调用失败
      • 错误值对应错误消息定义在error.h中
      • 可以通过perror()库函数翻译误码
  • 处理errno前最好将其存入其他变量中，因为在错误处理 过程中errno值可能会被改变

• 系统调用具有明确的操作

ret_from_sys_call

• 以ret_from_sys_call为入口的汇编程序段在Linux进程管理中 起到重要作用

  • 系统调用结束前、大部分中断服务返回前，都会跳转至此处 入口地址
  • 还处理中断嵌套、CPU调度、信号等

• 给用户空间进程的返回值同样通过寄存器传递

  • X86机器上，存放在eax寄存器中

Linux系统调用、派生函数

进程管理

进程控制

• fork：创建新进程
• clone：按照指定条件创建子进程
• execve：运行可执行文件
• exit：终止进程
• _exit：立即终止当前进程
• getdtablesize：进程能打开的最大文件数
• getpgid：获取指定进程组标识号
• setpgid：设置指定进程组标识号
• getpgrp：获取当前进程组标识号
• setpgrp：设置当前进程组标识号
• getpid：获取进程标识号
• getppid：获取父进程标识号
• getpriority：获取调度优先级
• setpriority：设置调度优先级
• modify_ldt：读写进程本地描述符
• nanosleep：使指定进程睡眠
• nice：改变分时进程的优先级
• pause：挂起进程，等待信号
• personality：设置进程运行域
• prctl：对进程进行特定操作
• ptrace：进程跟踪
• sched_get_priority_max：取得静态优先级上限
• sched_get_priority_min：取得静态优先级下限
• sched_getparam：取得进程调度参数
• sched_getscheduler：取得指定进程的调度策略
• sched_rr_get_interval：取得按RR算法实调度的实时进程 时间片
• sched_setparam：设置进程调度参数
• sched_setscheduler：设置进程调度策略和参数
• sched_yield：进程主动出让处理器，并添加到调度队列队尾
• vfork：创建执行新程序的子进程
• wait/wait3：等待子进程终止
• watipid/wait4：等待指定子进程终止
• capget：获取进程权限
• capset：设置进程权限
• getsid：获取会晤标识号
• setsid：设置会晤标识号

进程间通信

• ipc：进程间通信控制总控制调用

信号

• sigaction：设置对指定信号的处理方法
• sigprocmask：根据参数对信号集中的号执行阻塞、解除 阻塞等操作
• sigpending：为指定被阻塞信号设置队列
• sigsuspend：挂起进程等待特定信号
• signal
• kill：向进程、进程组发信号
• sigvec：为兼容BSD设置的信号处理函数，作用类似 sigaction
• ssetmask：ANSI C的信号处理函数，作用类似sigaction

消息

• msgctl：消息控制操作
• msgget：获取消息队列
• msgsnd：发消息
• msgrcv：取消息

管道

• pipe：创建管道

信号量

• semctl：信号量控制
• semget：获取一组信号量
• semop：信号量操作

内存管理

内存管理

• brk/sbrk：改变数据段空间分配
• mlock：内存页面加锁
• munlock：内存页面解锁
• mlockall：进程所有内存页面加锁
• munlockall：进程所有内存页面解锁
• mmap：映射虚拟内存页
• munmap：去除内存映射页
• mremap：重新映射虚拟内存地址
• msync：将映射内存中数据写回磁盘
• mprotect：设置内存映像保护
• getpagesize：获取页面大小
• sync：将内存缓冲区数据写回磁盘
• cacheflush：将指定缓冲区中内容写回磁盘

共享内存

• shmctl：控制共享内存
• shmget：获取共享内存
• shmat：连接共享内存
• shmdt：卸载共享内存

文件管理

文件读写

• tcntl：文件控制
• open：打开文件
• creat：创建新文件
• close ：关闭文件描述字
• read：读文件
• write：写文件
• readv：从文件读入数据到缓存区
• writev：将缓冲区数据写入文件
• pread：随机读文件
• pwrite：随机写文件
• lseek：移动文件指针
• _llseek：64位地址空间中移动文件指针
• dup：复制已打开的文件描述字
• dup2：按指定条件复制文件描述字
• flock：文件加/解锁
• poll：IO多路切换
• truncat/ftruncate：截断文件
• vumask：设置文件权限掩码
• fsync：将内存中文件数据写入磁盘

文件系统操作

• access：确定文件可存取性
• chdir/fchdir：改变当前工作目录
• chmod/fchmod：改变文件模式
• chown/fchown/lchown：改变文件属主、用户组
• chroot：改变根目录
• stat/lstat/fstat：获取文件状态信息
• statfs/fstatfs：获取文件系统信息
• ustat：读取文件系统信息
• mount：安装文件系统
• umount：卸载文件系统
• readdir：读取目录项
• getdents：读取目录项
• mkdir：创建目录
• mknod：创建索引节点
• rmdir：删除目录
• rename：文件改名
• link：创建链接
• symlink：创建符号链接
• unlink：删除链接
• readlink：读取符合链接值
• utime/utimes：改变文件的访问修改时间
• quotactl：控制磁盘配额

驱动管理

系统控制

• ioctl：IO总控制函数
• _sysctl：读写系统参数
• acct：启用或禁用进程记账
• getrlimit：获取系统资源上限
• setrlimit：设置系统资源上限
• getrusage：获取系统资源使用情况
• uselib：选择要使用的二进制库
• ioperm：设置端口IO权限
• iopl：改变进程IO权限级别
• outb：低级端口操作
• reboot：重启
• swapon：开启交换文件和设备
• swapoff：关闭交换文件和设备
• bdflush：控制bdflush守护进程
• sysfs：获取核心支持的文件系统类型
• sysinfo：获取系统信息
• adjtimex：调整系统时钟
• getitimer：获取计时器值
• setitimer：设置计时器值
• gettimeofday：获取时间、时区
• settimeofday：设置时间、时区
• stime：设置系统日期和时间
• time：获取系统时间
• times：获取进程运行时间
• uname：获取当前unix系统名称、版本、主机信息
• vhangup：挂起当前终端
• nfsservctl：控制NFS守护进程
• vm86：进入模拟8086模式
• create_module：创建可载入模块项
• delete_module：删除可载入模块项
• init_module：初始化模块
• query_module：查询模型信息

网络管理

网络管理

• getdomainname：获取域名
• setdomainname：设置域名
• gethostid：获取主机标识号
• sethostid：设置主机标识号
• gethostname：获取主机名称
• sethostname：设置主机名称

Socket控制

• socketcall：socket系统调用
• socket：建立socket
• bind：绑定socket到端口
• connect：连接远程主机
• accept：响应socket连接请求
• send/sendmsg：通过socket发送信息
• sendto：发送UDP信息
• recv/recvmsg：通过socket接收信息
• recvfrom：接收UDP信息
• listen：监听socket端口
• select：对多路同步IO进行轮询
• shutdown：关闭socket上连接
• getsockname：获取本地socket名称
• getpeername：获取通信对方socket名称
• getsockopt：获取端口设置
• setsockopt：设置端口参数
• sendfile：在文件端口间传输数据
• socketpair：创建一对已连接的无名socket

用户管理

• getuid：获取用户标识号
• setuid：设置用户标识号
• getgid：获取组标识号
• setgid：设置组标识号
• getegid：获取有效组标识号
• setegid：设置有效组标识号
• geteuid：获取有效用户标识号
• seteuid：设置有效用户标识号
• setregid：分别设置真实、有效的组标识号
• setreuid：分别设置真实、有效的用户标识号
• getresgid：分别获取真实、有效、保存过的组标识号
• setresgid：分别设置真实、有效、保存过的组标识号
• getresuid：分别获取真实、有效、保存过的用户标识号
• setresuid：分别设置真实、有效、保存过的用户标识号
• setfsgid：设置文件系统检查时使用的组标识号
• setfsuid：设置文件系统检查时使用的用户标识号
• getgroups：获取候补组标志清单
• setgroups：设置候补组标志清单

通知内核

• 一般系统调用都是通过软件中断向内核发请求，实现内核提供的 某些服务

  • 128号异常处理程序就是系统调用处理程序system_call()

• 用户空间进程不能直接执行内核代码，需要通过中断通知内核 需要执行系统调用，希望系统切换到内核态，让内核可以代表 应用程序执行系统调用

• 通知内核机制是靠软件中断实现，X86机器上软中断由int产生

  • 用户程序为系统调用设置参数，其中一个参数是系统调用 编号
  • 程序执行“系统调用”指令，该指令会导致异常
  • 保存程序状态
  • 处理器切换到内核态并跳转到新地址，并开始执行异常处理 程序，即系统调用处理程序
  • 将控制权返还给用户程序

• arch/i386/kernel/head.s

• init/main.c
• arhc/i386/kernel/traps.c
• include/asm/system.h

参数传递

• _syscalN()用于系统调用的格式转换和参数传递

  • 参数数量为N的系统调用由_syscallN()负责
  • N取值为0-5之间的整数

• 启动INT 0x80后，规定返回值送eax寄存器

  • 定义于include/asm/unistd.h，用于系统调用的格式转换 和参数传递

中断

• 软中断：

• 硬中断：外围设备完成用户请求后，会向CPU发出中断信号

  • CPU会暂停执行下条将要执行的指令，转而执行中断信号 对应处理程序，并将进程转入内核态

Interrupt

• 中断属性

  • 中断号：标识不同中断
  • 中断处理程序：不同中断有不同处理程序

• interrupt vector table：内核中维护，存储所有中断处理 程序地址

  • 中断号就是相应中断在中断向量表中偏移量

Linux进程、线程

进程发展

• Linux2.2内核

  • 进程通过系统调用fork()创建，新进程是原进程子进程
  • 不存在真正意义上的线程
  • 只默认允许4096个进程/线程同时运行

• Linux2.4内核

  • 运行系统运行中动态调整进程数上限，进程数仅受制于物理 内存大小，最大16000

• Linux2.6内核

  • 进程调度重新编写，引入slab分配器动态生成 task_struct
  • 最大进程数量提升至10亿
  • 线程框架重写
    • 引入tgid、线程组、线程各自的本地存储区
    • 得以支持NPTL线程库

线程/轻量级进程

• Linux未真正实现、区分线程，在内核层面是特殊进程，是 “真正的轻量级进程”

  • “线程”和“进程”共享
    • 相同调度策略，处于同一调度层次
    • 相同数据结构进程标识符，位于相同进程标识符空间
  • “线程”与“进程”的区别在于
    • 线程没有独立的存储空间

• 多线程即创建多个进程并分配相应的进程描述符 task_struct、指定其共享某些资源

  • 创建线程不会复制某些内存空间，较进程创建快
  • 在专门线程支持系统多线程中，系统会创建包含指向所有 线程的进程描述符，各线程再描述独占资源

• 尽管Linux支持轻量级进程，但不能说其支持核心级线程

  • 则不可能在Linux上实现完全意义上的POSIX线程机制
  • 所以Linux线程库只能尽可能实现POSIX绝大部分语义，尽量 逼近功能

• 线程在进程内共享某些资源

  • 打开的文件
  • 文件系统信息
  • 地址空间
  • 信号处理函数

• 这里讨论的线程都是内核线程，即内核可感知、调度线程，不 包括程序自建线程

内核守护线程

内核守护线程：内核为维护正常运行创建、仅工作在内核态线程

• 按作用可以分类

  • 周期性间隔运行，检测特定资源的使用，在用量超出或低于 阈值时采取行动
  • 启动后一直等待，直到系统调用请求执行某特定操作

• 执行以下任务

  • 周期性将dirty内存页与页来源块设备同步：bpflush线程
  • 将不频繁使用的内存写入交换区：kswapd线程
  • 管理延时动作：kthreadd线程接手内核守护线程创建
  • 实现文件系统的事务日志

• 内核守护线程只能工作在内核态

  • 没有用户空间，和内核共用一张内核页表
  • 只能使用大于PAGE_OFFSET部分的虚拟寻址空间，即进程 描述符中current->mm始终为空

  • 对4G主存的X86_32机器，只能使用最后1G，而普通pthreads 可以使用完整虚拟寻址空间

• 内核守护线程名往往为k开头、d结尾

特殊内核守护线程

• Linux内核启动的最后阶段，系统会创建两个内核线程

• init：运行文件系统上一系列init脚本，并启动shell 进程

  • 是所有用户进程的祖先，pid为1

• kthreadd：内核启动完成之后接手内核守护线程的创建

  • 内核正常工作时永不退出，是死循环，pid为2
  • 载入内核模块时即需要调用其创建新内核守护线程

进程状态

1
2
3
4
5
6
7
8

// <kernel/include/linux/sched.h>
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define __TASK_STOPPED 4
#define __TASK_TRACED 8
#define EXIT_ZOMBIE 16
#define TASK_DEAD 64

• 状态虽然有很多种，但总是TASK_RUNNING -> 非， 即使进程在TASK_INTERRUPTIBLE状态被kill，也需要先唤醒 进入TASK_RUNNING状态再响应kill信号进入TASK_DEAD

• TASK_RUNNING：可执行，正在执行或在运行队列中等待执行

  • 同一时刻可能有多个进程处于可执行态，位于运行队列中 等待进程调度器调度

• TASK_INTERRUPTIBLE：正在阻塞，等待某些条件达成

  • 条件达成后内核会把进程状态设置为运行
  • 此状态进程也会因为接收到信号而提前唤醒准备运行

  • 系统中大部分进程都此状态

• TASK_UNINTERRUPTILBE：不响应异步信号，即使接收到信号 也不会被唤醒或准备投入运行

  • 不可中断是指进程不响应异步信号，而不是指CPU不响应 中断
  • 内核某些处理流程是不可被打断的，如：内核和硬件设备 交互被打断会导致设备进入不可控状态，因此需要此状态

• __TASK_TRACED：被其他进程跟踪

  • 开发中进程停留在断点状态就是此状态，如：通过ptrace 对调试程序进行跟踪
  • 此状态进程只能等待调试进程通过ptrace系统调用执行 PTRACE_CONT、PTRACE_DETACH等操作才能恢复到 TASK_RUNNING状态

• __TASK_STOPPED：停止执行，没有也不能投入运行

  • 通常发生在接收到SIGSTOP、SIGSTP、SIGTTIN、 SIGTTOU等信号
  • 向此状态进程发送SIGCONT信号可以让其恢复到 TASK_RUNNING状态

• TASK_DEAD：退出状态，即将被销毁

• EXIT_ZOMBIE/TASK_ZOMBIE：进程已结束但task_struct未 注销

  • 进程退出过程中处于TASK_DEAD状态，进程占有的资源将 被回收，但父进程可能会关心进程的信息，所以 task_struct未被销毁

内核态、用户态

• 系统设计角度：为不同的操作赋予不同的执行等级，与系统相关 的特别关键的操作必须有最高特权程序来完成

  • 运行于用户态：进程可执行操作、可访问资源受到限制
  • 运行于内核态：进程可执行任何操作、使用资源无限制

• 内存使用角度（虚拟寻址空间，X86_32位系统，最大4GB主存）

  • 内核空间：最高的1G，所有进程共享
    • 包含系统堆栈：2页面，即8K内存，低地址中存放 task_struct值
    • 进程运行于内核空间时使用系统堆栈、处于内核态
  • 用户空间：剩余3G
    • 包含用户堆栈
    • 进程运行于用户空间时使用用户堆栈、处于用户态

  

• 内核态的逻辑

  • 进程功能和内核密切相关，进程需要进入内核态才能实现 功能
  • 应用程序在内核空间运行、内核运行于进程上下文、陷入 内核空间，这种交互方式是程序基本行为方式

• 用户态进入内核态的方式

  • 系统调用，如：printf函数中就是调用write函数
  • 软中断，如：系统发生异常
  • 硬件中断，通常是外部设备的中断

  

• 进程或者CPU在任何指定时间点上活动必然为

  • 运行于用户空间，执行用户进程
  • 运行于内核空间，处于进程上下文，代表某特定进程执行
  • 运行于内核空间，处于中断上下文，与任何进程无关，处理 特点中断

Linux进程数据结构

task_struct

1
2
3
4
5
6
7
8
9
10
11
12
13

// <kernel/include/linux/sched.h>
struct task_struct{
	volatile long state;	// -1：不可运行，0：可运行，>0：已中断
	int lock_depth;			// 锁深度
	unsigned int policy;	// 调度策略：FIFO，RR，CFS
	pid_t pid;				// 线程ID
	pid_t tgid;				// 线程组ID，2.6内核中引入
	struct task_struct *parent;	// 父进程
	struct list_head children;	// 子进程
	struct list_head sibling;	// 兄弟进程
	struct task_struct *group_leader;
	struct list_head thread_group;
}

• 内核使用任务队列（双向循环链表）维护进程（描述符）

• task_struct：进程描述符，包含进程的所有信息，包括

  • 进程状态
  • 打开的文件
  • 挂起信号
  • 父子进程

ID

• pid：字面意思为process id，但逻辑上为线程ID
• tgid：字面意思为thread group id，但逻辑上为 进程ID

1
2
3
4
5
6
7

// <kernel/timer.c>
asmlinkage long sys_getpid(void){
	return current->tgid;
}
asmlinakge long sys_gettid(void){
	return current->pid;
}

线程关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// <kernel/fork.c>
copy_process{
	// some code
	p->tgid = p->pid;

	// 创建线程时
	if (clone_flags & CLONE_THREAD)
		// 从父进程获取`tgid`，归属同一线程组
		p->tgid = current->tgid;

	// some code
	// 初始化`group_leader`、`thread_group`
	p->group_leader = p;
	INIT_LIST_HEAD(&p->thread_group);

	// some code

	// 创建线程时
	if (clone_flags & CLONE_THREAD){
		// `group_leader`设置为父进程`group_leader`
		// 即保证`group_leader`指向首个线程`task_struct`
		p->group_leader = current->group_leader;
		// 通过`thread_group`字段挂到首个线程的`thread_group`队列中
		list_add_tail_rcu(&p->thread_group, &p->group_leader->thread_group);

	// some code
	}

	if(likely(p->pid)){
		// some code
		// 仅首个线程才会通过`tasks`字段挂入`init_task`队列中
		if(thread_group_leader(p)){
			//...
			list_add_tail_rcu(&p->tasks, &init_task, tasks);
		}
	}
}

线程组退出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// <kernel/exit.c>
NORET_TYPE void do_group_exit(int exit_code){
	BUG_ON(exit_code & 0x80);

	// `current->signal`由线程组中所有线程共享
	// 若调用此方法线程`SIGNAL_GROUP_EXIT`标志已被设置，说明
		// 其他线程已经执行过此方法，已通知线程组中所有线程
		// 退出，则可以直接执行`do_exit`
	if(current->signal->flags & SIGNAL_GROUP_EXIT)
		exit_code = current->signal->group_exit_code;

	// 否则通知线程组中所有线程退出
	else if(!thread_gropu_empty(current)){
		struct signal_struct * const sig = current->signal;
		struct sighand_struct * const sighand = current->sighand;
		spin_lock_irq(&sighand->siglock);

		// another thread got here before we took the lock
		if(sig->flags & SIGNAL_GROUP_EXIT)
			exit_code = sig->group_exit_code;
		else{
			sig->group_exit_code = exit_code;
			zap_other_threads(current);
		}
		spin_unlock_irq(&sighand->sigloc);
	}

	do_exit(exit_code);
}

// <kernel/signal.c>
void zap_other_threads(struct task_struct *p){
	struct task_struct *t;

	// 设置`SIGNAL_GROUP_EXTI`标志
	p->signal->flags = SIGNAL_GROUP_EXIT;
	p->signal->group_stop_count = 0;

	if(thread_group_empty(p))
		return;

	for (t=next_thread(p); t != p; t=next_thread(t)){
		// don't bohter with already dead threads
		if (t->exit_state)
			continue;

		// 为每个线程设置`SIGKILL`信号
		sigaddset(&t->pending.signal, SIGKILL);
		signal_wake_up(t, 1);
	}
}

// <include/linux/sched.h>
static inline struct task_struct *next_thread(const struct task_struct *p){
	return list_entry(rcu_dereference(p->thread_group.next),
		struct task_struct, thread_group);
}

Slab分配器

• slab分配器把不同对象类型划分为不同高速缓存组，如： task_struct、inode分别存放

  • 高速缓存又会被划分为slab
  • slab由一个或多个物理上连续的页组成

• 申请数据结构时

  • 先从半满的slabs_partial中申请
  • 若没有半满，就从空的slabs_empty中申请，直至填满 所有
  • 最后申请新的空slab

• slab分配器策略优点

  • 减少频繁的内存申请和内存释放的内存碎片
  • 由于缓存，分配和释放迅速

thread_info

1
2
3
4
5
6
7
8
9
10

// <asm/thread_info.h>
struct thread_info{
	struct task_struct *task;
	struct exec_domain *exec_domain;
	usigned long flags;
	__u32 cpu;
	int preempt_count;
	mm_segment_t addr_limit;
	struct restart_block restart_block;
}

• 内核中对进程操作都需要获得进程描述符task_struct指针， 所以获取速度非常重要
  • 寄存器富余的体系会拿出专门的寄存器存放当前 task_struct的指针
  • 寄存器不富余的体系只能在栈尾创建thread_info结构， 通过计算间接查找

进程创建

• 继承于Unix，Linux进程创建使用两个函数分别完成，其他如Win 可能都是通过一个方法完成

• fork函数：拷贝当前进程创建子进程

  • 子进程、父进程区别仅在于PID、PPID和少量资源

• exec函数（族）：载入可执行文件至地址空间开始运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

SYSCALL_DEFINE0(fork){
	return do_fork(SIGCHLD, 0, 0, NULL, NULL);
}
SYSCALL_DEFINE0(vfork){
	return _do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD,
		0, 0, NULL, NULL, 0);
}
long do_fork(unsigned long clone_flags,
		unsigned long stack_start,
		unsigned long stack_size,
		int __user *parent_tidptr,
		int __user *child_tidptr){
	return _do_fork(clone_flags, stack_start, stack_size,
		parent_tidptr, child_tidptr, 0);
}
long _do_fork(unsigned long clone_flags,
		unsigned long stack_start,
		unsigned long stack_size,
		int __user *parent_tidptr,
		int __user *child_tidptr,
		unsigned long tls){
	// some code
	p = copy_process(clone_flags, stack_start, stack_size,
		child_tidptr, NULL, trace, tls);
	// some code
}

• fork、vfork最终都是通过调用_do_fork实现，仅传参 不一致

  • 首个参数为clone_flags，最终被copy_process用于 真正的拷贝执行

• 通过系统调用clone()创建线程

  • 同创建进程系统调用fork()、vfork()一样，最终调用 do_fork方法，但传递和进程创建时不同的flag，指明 需要共享的资源

    1	CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGNAND

fork

fork()：子进程是父进程的完整副本，复制了父进程的资源， 包括内存内容、task_struct

• 子进程拷贝父进程的数据段、代码段

  • 同一变量的虚拟地址相同（物理地址不同）

• 利用copy-on-write优化效率

  • 内核创建子进程时不复制父进程的地址空间，而是只读共享 父进程空间数据
  • 只有子进程需要写数据时才会拷贝到子进程

• 页表：存放给从逻辑页号到物理页帧/块号地址的映射

Unix傻瓜式进程创建

• 内核原样复制父进程整个地址空间，并分配给子进程，效率低

  • 为子进程页表分配页帧
  • 为子进程页分配页帧
  • 初始化子进程页表
  • 把父进程页复制到子进程相应页中

• 大部分情况下复制父进程页无意义

  • 子进程会载入新的程序开始运行
  • 丢弃所继承的地址空间

Copy-on-Write

copy-on-write思想简单：父进程、子进程共享页帧

• 共享页帧不能被修改，父进程、子进程试图写共享页帧时产生 page_fault异常中断

• CPU执行异常处理函数do_wp_page()解决此异常

  • 对导致异常中断的页帧取消共享操作
  • 为写进程复制新的物理页帧，使父、子进程各自拥有内容 相同的物理页帧
  • 原页帧仍然为写保护：其他进程试图写入时，内核检查进程 是否是页帧的唯一属主，如果是则将页帧标记为对此进程 可写

• 异常处理函数返回时，CPU重新执行导致异常的写入操作指令

• copy-on-write：多个呼叫者同时要求相同资源时，会共同 取得相同指针指向相同资源，直到某个呼叫者尝试修改资源时， 系统才给出private copy，避免被修改资源被直接察觉，此 过程对其他呼叫者transparent

vfork

vfork()：子进程直接共享父进程的虚拟地址空间、物理空间

• vfork被设计用以启动新程序

  • 内核不创建子进程的虚拟寻址空间结构
  • 进程创建后应立即执行exec族系统调用加载新程序，替换 当前进程

  • exec不创建新进程，仅用新程序替换当前进程正文、 数据、堆、栈

• 在子进程调用exec函数族、_exit()、exit()前，子进程 在父进程的地址空间中运行

  • 二者共享数据段，子进程可能破坏父进程数据结构、栈
  • 父进程地址空间被占用，因此内核会保证父进程被阻塞， 即vfork会保证子进程先运行

• 应确保一旦调用vfork后

  • 子进程不应使用return返回调用处，否则父进程又会 vfork子进程
  • 子进程不应依赖父进程进一步动作，否则会导致死锁
  • 子进程需避免改变全局数据
  • 若子进程改变了父进程数据结构就不能调用exit函数

clone

clone：可有选择地继承父进程资源

1

int clone(int (fn)(void), void * child_stack, int flags, void * args);

• clone通过众多参数有选择地创建进程

  • 创建LWP/线程
  • 创建兄弟进程
  • 类似vfork创建和父进程共享虚拟寻址空间

• 参数说明

  • fn：函数指针
  • child_stack：为子进程分配的系统堆栈空间
  • flags：描述需要从父进程继承的资源，如下
  • args：传给子进程的参数

Flags

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#define CSIGNAL		0x000000ff		// signal mask to be setn at exit
#define CLONE_VM	0x00000100		// set if VM shared between process
#define CLONE_FS	0x00000200		// set if fs info shared between processes
#define CLONE_FILES	0x00000400		// set if open files shared between processes
#define CLONE_SIGHAND	0x00000800	// set if signal handlers and blocked signals shared
#define CLONE_PTRACE	0x00002000	// set if we want to let tracing continue on the child too
#define CLONE_VFORK		0x00004000	// set if the parent wants the child to wake it up on mm_release
#define CLONE_PARENT	0x00008000	// set if we want to have the same parent as the cloner
#define CLONE_THREAD	0x00010000	// same thread group?
#define CLONE_NEWS		0x00020000	// new namespace group?
#define CLONE_SYSVSEM	0x00040000	// share system V SEM_UNDO semantics
#define CLONE_SETTLS	0x00080000	// create a new TLS for the child
#define CLONE_PARENT_SETTID		0x00100000	// set the TID in the parent
#define CLONE_CHILD_CLEARTID	0x00200000	// clear TID in the child
#define CLONE_DETEACHED			0x00400000	// unused
#define CLONE_UNTRACED			0x00800000	// set if the tracing process can't force `CLONE_PTRACE` on this clone
#define CLONE_CHILD_SETTID		0x01000000	// set the TID in the child
#define CLONE_STOPPED	0x02000000	// start in stopped state
#define CLONE_NEWUTS	0x04000000	// new utsname group
#define CLONE_NEWIPC	0x08000000	// new ipcs
#define CLONE_NEWUSER	0x10000000	// new user namespace
#define CLONE_NEWPID	0x20000000	// new pid namespace
#define CLONE_NEWNET	0x40000000	// new network namespace
#define CLONE_IO		0x80000000	// clone into context

线程库

• POSIX标准要求：线程不仅仅是共享资源即可，其需要被视为 整体
  • 查看进程列表时，一组task_struct需要被展示为列表中 一个节点
  • 发送给进程信号，将被一组task_struct共享，并被其中 任意一个线程处理
  • 发送给线程信号，将只被对应task_struct接收、处理
  • 进程被停止、继续时，一组task_struct状态发生改变
  • 进程收到致命信号SIGSEGV，一组task_struct全部退出

LinuxThread线程库

LinuxThread线程库：Linux2.6内核前，pthread线程库对应实现

• 特点
  • 采用1对1线程模型
  • 通过轻量级进程模拟线程
  • 线程调用由内核完成，其他线程操作同步、取消等由核外 线程库完成
  • 仅通过管理线程实现POSIX以上5点要求中最后一点

管理线程

管理线程：为每个进程构造、负责处理线程相关管理工作

• 管理线程是主线程的首个子线程

  • 进程首次调用pthread_create创建线程时会创建、启动 管理线程

• 管理线程负责创建、销毁除主线程外线程，成为LinuxThread 的性能瓶颈

  • 从pipe接收命令创建线程
  • 子线程退出时将收到SIGUSER1信号（clone时指定）， 若不是正常退出，则杀死所有子线程并自杀
  • 主循环中不断检查父进程ID，若为1说明原父线程退出并 被托管给init线程，则杀死所有子进程并自杀

• 通过LWP模拟线程存在的问题

  • LWP不共享进程ID
  • 某些缺省信号难以做到对所有线程有效，如：SIGSTOP、 SIGCONT无法将整个进程挂起
  • 线程最大数量收到系统总进程数限制
  • 管理线程是性能瓶颈，一旦死亡需要用户手动清理线程、 无人处理线程创建请求
  • 同步效率低，通过复杂的信号处理机制进行同步
  • 与POSIX兼容性差

Naive POSIX Thread Library

NPTL：Linux2.6内核重写线程框架的基础上引入的pthread线程库

• 本质上还是利用LWP实现线程的1对1线程模型，但结合新的线程 框架实现了POSIX的全部5点要求

  • 线程组tgid引入体现task_struct代表进程还是线程
  • task_struct维护两套signal_pending
    • 线程组共享signal_pending：存放kill发送信号， 任意线程可以处理其中信号
    • 线程独有signal_pending：存放pthread_kill发送 信号，只能由线程自身处理
  • 收到致命信号时，内核会将处理动作施加到线程组/进程中

• 但也存在一些问题

  • kill未展示的LWP会杀死整个进程

• RedHat开发，性能远高于LinuxThreads，需要内核支持

Next Generation Posix Threads for Linux

NGPT：基于GNU Portable Threads项目的实现多对多线程模型

• IBM开发，性能介于LinuxThread、NPTL间，2003年终止开发

Reproducing Kernel Hilbert Space

• Hilbert space：假设 $K(x,z)$ 是定义在 $\mathcal{X X}$ 上的对称函数，并且对任意 $x_1, x_2, \cdots, x_m \in \mathcal{X}$，$K(x,z)$ 关于其的 Gram* 矩阵半正定，则可以根据函数 $K(x,z)$ 构成一个希尔伯特空间

构造步骤

定义映射构成向量空间

• 定义映射

  $$\phi: x \rightarrow K(·, x)$$

• 根据此映射，对任意 $x_i \in \mathcal{X}, \alpha_i \in R, i = 1,2,\cdots,m$ 定义线性组合

  $$f(·) = \sum_{i=1}^m \alpha_i K(·, x_i)$$

• 由以上线性组合为元素的集合 $S$ 对加法、数乘运算是封闭的，所以 $S$ 构成一个向量空间

定义内积构成内积空间

• 在 $S$ 上定义运算 $ * $：对任意 $f,g \in S$

  $$\begin{align*} f(·) = \sum_{i=1}^m \alpha_i K(·, x_i) \\ g(·) = \sum_{j=1}^n \beta_j K(·, z_j) \end{align*}$$

  定义运算 $ * $

  $$f * g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \beta_j K(x_i, z_j)$$

• 为证明运算 $ * $ 是空间 $S$ 的内积

  • 需要证明：
    • $(cf) g = c(f g), c \in R$
    • $(f + g) h = f h + g * h, h \in S$
    • $f g = g f$
    • $f f \geq 0, f f = 0 \Leftrightarrow f = 0$
  • 其中前3条由 $S$ 元素定义、$K(x,z)$ 对称性容易得到
  • 由 $ * $ 运算规则可得 $$f * f = \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i, x_j)$$ 由 Gram 矩阵非负可知上式右端非负，即 $f * f \geq 0$

• 为证明 $f * f \Leftrightarrow f = 0$

  • 首先证明

    $$|f * g|^2 \leq (f * f)(g * g)$$

    • 设$f, g \in S$，则有$f + \lambda g \in S$，则有

      $$\begin{align*} (f + \lambda g) * (f + \lambda g) & \geq 0 \\ f*f + 2\lambda (f * g) + \lambda^2 (g*g) & \geq 0 \end{align*}$$

    • 则上述关于$\lambda$的判别式非负，即

      $$(f*g)^2 - (f*f)(g*g) \leq 0$$

  • $\forall x \in \mathcal{x}$，有

    $$K(·, x) * f = \sum_{i=1}^m \alpha_i K(x, x_i) = f(x)$$

    则有

    $$|f(x)|^2 = |K(·, x) * f|^2$$

  • 又

    $$|K(·, x) * f|^2 \leq (K(·, x) * K(·, x))(f * f) = K(x, x)(f*f)$$

    则有

    $$|f(x)|^2 \leq K(x, x) (f * f)$$

    即$f * f = 0$时，对任意$x$都有$|f(x)| = 0$

• 因为 $ * $ 为向量空间 $S$ 的内积，可以继续用 $ · $ 表示

  $$f·g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \alpha_j K(x_i,z_J)$$

完备化构成Hilbert空间

• 根据内积定义可以得到范数

  $$\|f\| = \sqrt {f · f}$$

  所以 $S$ 是一个赋范向量空间，根据泛函分析理论，对于不完备的赋范空间 $S$ ，一定可以使之完备化得到希尔伯特空间 $\mathcal{H}$

• 此希尔伯特空间 $\mathcal{H}$ ，称为 reproducing kernel Hilber Space ，因为核 $K$ 具有再生性

  $$\begin{align*} K(·, x) · f & = f(x) \\ K(·, x) · K(·, Z) & = K(x, z) \end{align*}$$

Positive Definite Kernel Function

• 设 $K: \mathcal{X X} \leftarrow R$ 是对称函数，则 $K(x,z)$ 为正定核函数的充要条件是 $\forall x_i \in \mathcal{X}, i=1,2,…,m$，$K(x,z)$ 对应的 Gram 矩阵 $K = [K(xi, x_j)]{mm} $ 是半正定矩阵

• 必要性

• 由于 $K(x,z)$ 是 $\mathcal{X X}$ 上的正定核，所以存在从 $\mathcal{X}$ 到 Hilbert* 空间 $\mathcal{H}$ 的映射，使得

  $$K(x,z) = \phi(x) \phi(z)$$

• 则对任意 $x_1, x_2, \cdots, x_m$，构造 $K(x,z)$ 关于其的 Gram 矩阵

  $$[K_{ij}]_{m*m} = [K(x_i, x_i)]_{m*m}$$

• 对任意 $c_1, c_2, \cdots, c_m \in R$，有

  $$\begin{align*} \sum_{i,j=1}^m c_i c_j K(x_i, x_j) & = \sum_{i,j=1}^m c_i c_j (\phi(x_i) \phi(x_j)) \\ & = (\sum_i c_i \phi(x_i))(\sum_j c_j \phi(x_j)) \\ & = \| \sum_i c_i \phi(x_i) \|^2 \geq 0 \end{align*}$$

  所以 $K(x,z)$ 关于 $x_1, x_2, \cdots, x_m$ 的 Gram 矩阵半正定

• 充分性

• 对给定的 $K(x,z)$，可以构造从 $\mathcal{x}$ 到某个希尔伯特空间的映射

  $$\phi: x \leftarrow K(·, x)$$

• 且有

  $$K(x,z) = \phi(x) · \phi(z)$$

  所以 $K(x,z)$ 是 $\mathcal{X * X}$ 上的核函数