利用/proc精确计算Linux系统的CPU利用率

Linux 系统并未提供直接获取CPU 利用率的接口,一些应用程序通过访问/proc 文件系统中系统的状态统计从而计算得到CPU利用率。常用查看进程及其相关信息的top 命令和htop 命令即属于这一类。

本文简单介绍如何利用/proc/stat 文件计算CPU 利用率,这种经典方法在top 和htop 工具中也被采用,在StackOverflow 也有说明;接着,将上面经典方法获取的CPU 利用率和一种极端情况下的单核单任务的CPU占用率进行比较,单核单任务指的是,在隔离的单独CPU 和核心上只运行该程序(如果你对这有疑问,可以参考下core affinity 、core isolation 和non irqbalance)。

看下图htop 工具的截图:该系统有8个CPU核心,每个核心的CPU利用率位于图上方横向柱状图。8个核心中1-7都是被隔离的,1/3/4/5/6/7每个核心都分配了一个名称为grt_simple_conc_ispc 的线程,每个线程CPU 占用率(CPU%)位于图下方第5 列,可以看出CPU利用率(上方)和每个程序占CPU利用率(下方)结果是有差异的。

方法一

一种最直接计算程序占用CPU 使用率的计算方法是,采样N 次,如果有R 次该程序正在执行,则其占用CPU使用率为 R/N × 100%。

Linux 在/proc/{pid}/stat 文件中记录进程ID 为pid 的进程统计信息(按照类别分为几十个字段,详见 https://man7.org/linux/man-pages/man5/proc.5.html )。如果进程状态字符是R ,则表示进程正在运行(Running),如果状态字符是S ,则表示进程正在睡眠(Sleeping)。

将该方法作为CPU 利用率的前提是:该CPU 核心只运行该进程,尽量少地被中断。

计算CPU 利用率经典方法(方法二)

工具(如top 和htop)定时采样读取/proc/stat 文件内容,该文件记录了每个CPU核心所处不同状态的累计时间,再通过以下公式可计算得到指定核心CPU利用率:

previdle   = previdle + previowait
idle     = idle + iowait
prevnoidle  = prevuser + prevnice + prevsystem + previrq + prevsoftirq + prevsteal
noidle    = user + nice + system + irq + softirq + steal
prevtotal   = previdle + prevnonidle
total     = idle + nonidle
total_delta  = total - prevtotal
idle_delta  = idle - previdle
CPU_usage    = (total_delta - idle_delta)/total_delta

    以prev开头的变量是上一次采用数据,否则是当前采样数据,通过计算两次采样之间的CPU空闲时间(idle_delta)和总计时间(total_delta)得到CPU利用率,这是procs/top 工具默认使用的方法,也是最常见CPU利用率统计方法。

方法三

方法和约束情况类似于方法一,周期性读取/proc/{pid}/stat文件,获取进程用户态时间utime 和核态时间stime,按照如下公式计算CPU利用率

    CPU_usage = (utime+stime)/sample_interval

其中,utime和stime代表进程用户态时间和核态时间,sample_interval是采样间隔。

下面是负载由轻到高,三种方法得到的CPU 利用率:

Linux 内核文档PDF版(Linux kernel v5.8 documents pdf version)

accounting.pdf

doc-guide.pdf

ide.pdf

maintainer.pdf

process.pdf

timers.pdf

admin-guide.pdf

driver-api.pdf

iio.pdf

mhi.pdf

RCU.pdf

trace.pdf

arm64.pdf

fault-injection.pdf

infiniband.pdf

mips.pdf

riscv.pdf

translations.pdf

arm.pdf

fb.pdf

input.pdf

misc-devices.pdf

s390.pdf

usb.pdf

block.pdf

filesystems.pdf

isdn.pdf

netlabel.pdf

scheduler.pdf

userspace-api.pdf

bpf.pdf

firmware-guide.pdf

kbuild.pdf

networking.pdf

scsi.pdf

virt.pdf

cdrom.pdf

fpga.pdf

kernel-hacking.pdf

openrisc.pdf

security.pdf

vm.pdf

core-api.pdf

gpu.pdf

leds.pdf

parisc.pdf

sh.pdf

w1.pdf

cpu-freq.pdf

hid.pdf

PCI.pdf

sound.pdf

watchdog.pdf

crypto.pdf

hwmon.pdf

livepatch.pdf

pcmcia.pdf

sparc.pdf

x86.pdf

devicetree.pdf

i2c.pdf

locking.pdf

powerpc.pdf

spi.pdf

xtensa.pdf

dev-tools.pdf

ia64.pdf

m68k.pdf

power.pdf

target.pdf

你也可以在自己的Linux kernel 源码目录执行以下命令生成自己的pdf,但何必自己造轮子呢。

sudo apt-get install sphinxsearch
sudo apt-get install python-sphinx-rtd-theme
sudo apt-get install texlive-latex-recommended
sudo apt-get install texlive-base
sudo apt-get install graphviz
sudo apt-get install imagemagick
/usr/bin/virtualenv ~/sphinx_version
. ~/sphinx_version/bin/activate
pip install -r Documentation/sphinx/requirements.txt
make pdfdocs

安装RTAI5.2 基于Ubuntu18.04和4.14.111 内核

本文记录在我笔记本上安装最新版本RTAI(5.2)的过程和中间遇到的问题及解决方法,虽然不能覆盖所有问题,但希望能给后来者一些帮助。

安装的主要步骤:

1、安装操作系统和工具;

2、给内核打补丁并配置;

3、安装打补丁的内核与RTAI。

步骤一:安装操作系统和工具

1.1 安装操作系统

我选择的是Ubuntu18.04,因为这是带Linux 4.**.***内核的最新Ubuntu 版本(Ubuntu19.04 是以Linux5.**内核开始了)。而RTAI5.2 支持的最新内核版本即为4.14.111;

1.2 安装工具

这些工具是内核编译时需要的,下面命令可以保存为脚本执行

sudo apt install libncurses5-dev

sudo apt install libssl-dev

sudo apt install bison

sudo apt install flex

sudo apt install libssl-dev

sudo apt install libelf-dev

sudo apt install make gcc

sudo apt install patch

sudo apt install unzip

sudo apt install autoconf

注意:如果你使用的是不同的Linux 发布版(Redhat或openSUSE),有些包的名称是不同的,比如对于Redhat,libssl的安装包是libssl-devel。

注意:如果你采用的是Ubuntu16.04,那么可能因为包依赖的原因,你无法用apt install 命令安装libssl1.1,而这个包是在编译4.14.111 内核时必须的,所以建议你要么换更高版本OS,要么在Ubuntu 网站( https://packages.debian.org/stretch/amd64/libssl1.1/download )手动安装该包(sudo dpkg -i libssl1.1_1.1.0k-1~deb9u1_amd64.deb)。

1.3 安装已编译的Linux 内核4.14.111 (可选的)

该步骤是可选的,它会给系统安装上Linux4.14.111 的内核,从而获得一个默认的内核配置文件供后面使用,如果你是第一次安装RTAI,建议你执行该步骤。

在内核网站 https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/ 下载内核安装包:

cd ~/Downloads/

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111_4.14.111-0414111.201904052241_all.deb

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-image-unsigned-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb`

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-modules-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb

然后使用dpkg -i 命令安装

sudo dpkg -i *.deb   #执行该命令是可能会遇到错,再重新执行该命令可以解决;

sudo update-grub

sudo reboot

重启后可以在Grub (长按shift进入Grub)中看到安装后的内核有“Generic” 和“lowlatency” 两种。如果进入Grub 有困难,在Grub 配置文件(/etc/default/grub)中修改配置`GRUB_TIMEOUT_STYLE=hidden` 为`GRUB_TIMEOUT_STYLE=false`并更新Grub 菜单`sudo update-grub`。

步骤二:内核打补丁和编译

2.1 下载内核 (https://cdn.kernel.org/pub/linux/kernel/v4.x/)

内核的名称为 linux-4.1.111.tar.gz,为之后编译和安装方便,将源码解压到`/usr/src` 中,并创建一个软链接到该源码目录。

cd /usr/src

sudo tar xvf linux-4.1.111.tar.gz

sudo ln -sf linux-4.1.111 linux

然后,从`/boot` 中拷贝配置文件:

cd /usr/src/linux

sudo cp /boot/config-4.14.111-0414111-lowlatency .config

如果你已经有了一个配置文件(比如你安装过老版本RTAI,在其Linux 内核中拷贝其配置文件即可)uIf you already have a configuration file (e.g. in your old RTAI patched Linux system), just copy it to the source path(`/usr/src/linux`).

2.2 给内核打补丁(Ubuntu 的补丁和RTAI 的补丁)

Ubuntu 是Linux 的一个发行版本,并对Linux 内核代码做了少量修改,所以在编译内核前应该打上Ubuntu 的补丁(https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/)。

cd ~/Downloads/

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0001-base-packaging.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0004-adhoc-from-__future__-import-syncconfig.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0006-debian-changelog.patch

wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch

cd /usr/src/linux

sudo patch -p1 < ~/Downloads/0001-base-packaging.patch

sudo patch -p1 < ~/Downloads/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch

sudo patch -p1 < ~/Downloads/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch

sudo patch -p1 < ~/Downloads/0004-adhoc-from-__future__-import-syncconfig.patch

sudo patch -p1 < ~/Downloads/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch

sudo patch -p1 < ~/Downloads/0006-debian-changelog.patch

sudo patch -p1 < ~/Downloads/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch

下载RTAI5.2 并给内核打上相应的补丁 :

wget https://www.rtai.org/userfiles/downloads/RTAI/rtai-5.2.tar.bz2

sudo cp rtai-5.2.tar.bz2 /usr/src/

sudo tar xvf rtai-5.2.tar.bz2

sudo ln -sf rtai-5.2 rtai

cd /usr/src/linux

sudo patch -p1 < /usr/src/rtai/base/arch/x86/patches/hal-linux-4.14.111-x86-3.patch

同样方便起见,我们也为rtai 的源码创建了一个软链接。

注意:安装RTAI补丁和PREEMPT-RT补丁的过程是类似的,如果你想安装PREEMPT-RT补丁,它的地址在这里。下载xz或gz格式后的补丁,可以用xz工具解压发现,是一个个编了序号的补丁,通过下面命令逐个应用补丁

patch -p1 -i /path/to/004-patch.x.y.z

也可以通过下面命令应用所有补丁

xzcat /path/to/patch.xz | patch -p1

bzcat /path/to/patch.xz | patch -p1

2.3 配置内核

配置内核主要参考下面的资料:

如果你的配置文件是从其他老的内核里拷贝过来的,首先应执行:

cd /usr/src/linux

sudo make oldconfig

否则直接执行:

sudo make menuconfig

下面是配置项中应修改的部分:

[改为 -rtai] General setup -> Local Version

[改为 None] General setup -> Stack Protector buffer overflow detection

[Enable] Processor type and features -> Interrupt pipeline

[Disable] Power management and ACPI options -> CPU Frequency Scaling

[Disable] Power management and ACPI options -> ACPI Support -> Processor

[Disable] Power management and ACPI options -> CPU Idle -> CPU idle PM support

[Disable] Kernel hacking -> Compile-time checks and compiler options -> Compile the kernel with debug info

[Disable] Kernel hacking -> Tracers

[Disable] Device Drivers -> Microsoft Hyper-V guest support

[Disable] Device Drivers -> Staging drivers -> Data acquisition support (comedi)

在 README.CONF_RMRKS 文件中要求disable `AUDITSYSCALL`,但是我们在选项中没有找到这一项。一个可替代的方法是编辑 `/usr/src/linux/init/Kconfig`文件,找到`AUDITSYSCALL` 如下部分:

config AUDITSYSCALL

    def_bool y

    depends on AUDIT && HAVE_ARCH_AUDITSYSCALL

替换为:

config AUDITSYSCALL

    bool “Enable system-call auditing support”

    depends on AUDIT && HAVE_ARCH_AUDITSYSCALL

    default y if SECURITY_SELINUX

    help

      Enable low-overhead system-call auditing infrastructure that

      can be used independently or with another kernel subsystem,

      such as SELinux.

然后,你就可以在‘General Setup’选项下看到`ADUITSYSCALL`,取消即可。

如果你的主机是多CPU 或多核的,那么 `Processor type and features` 下的SMP 选项要使能(enabled),并且最大CPU 个数(`Maximum numbers of CPUs`)不应小于物理核心个数(即不考虑Hyperthreading)。因此,建议你在BIOS 中取消Hyperthreading。

步骤三:编译安装内核和RTAI

3.1 编译和安装Linux 内核

cd /usr/src/linux

sudo touch REPORTING-BUGS

sudo make -j3

sudo make modules

sudo make modules_install

sudo make install

sudo update-initramfs –c -k 4.14.111-rtai [注意修改这里的版本名称]

sudo update-grub [注意修改/etc/default/grub 启动项为自己的内核]

sudo reboot

从Linux 内核网站下载的4.14.111 版本的源码目录下没有`REPORTING-BUGS`这个文件,可能会导致你在编译的时候遇到`recipe for target ‘kernel_headers’ failed` 的错误,所以我们首先创建了这个文件。

如果一切顺利的的话,你重启后将在Grub 上看到你自己编译的内核选项:ubuntu18.04_4.14.111-rtai 。

3.2 安装RTAI5.2

RTAI 需要autotools 生成链接编译工具:

cd /usr/src/rtai

sudo autoconf

sudo ./configure

接着配置RTAI :

sudo cp ../linux/.config .rtai_config

sudo make menuconfig

将CPU 个数(`number of CPUs`)设置为实际的物理核心个数即可。

sudo make

sudo make install

如果在编译时遇到下面的错误:

make:execup: .//config.guess: Permission denied

make:execup: .//config.sub: Permission denied

手动修改权限后再编译:

chmod 764 ./config.guess

chmod 764 ./config.sub

RTAI 默认的安装路径是`/usr/realtime`,其中`modules`目录下是编译后的模块库, `testSuite` 目录下是RTAI 的测试程序,通过手动加载模块和运行测试程序可以验证RTAI是否安装成功。

cd /usr/realtime/modules

sudo insmod rtai_hal.ko

sudo insmod rtai_sched.ko

sudo insmod rtai_fifos.ko

sudo insmod rtai_sem.ko

sudo insmod rtai_shm.ko

sudo insmod rtai_rtdm.ko

一般来说,负责进程调度的 rtai_sched.ko 模块如果加载后无死机,则安装成功。

可能遇到的问题

最后罗列一些可能遇到的问题:

1 编译内核时, `implicit declaration of function ‘ipipe_root_**_syscalls’ did you mean ‘ipipe_handle_syscall’ ……` 错误

原因:在内核配置里,ipipeline 没有使能(Enable);

2 加载`sudo insmod rtai_hal.ko` 和`sudo insmod rtai_` 后,系统冻死,键盘和鼠标均无响应

可能原因:General setup -> Stack Protector buffer overflow detection 选项默认是`Strong`,应设置为`None`或 `Regular`,更多配置项参考 README.CONF_RMRKS 。

3 不能进入编译Linux内核后的系统,提示`Gave up waiting for root file system device. Common problems:  …… ALERT! UUID=8e478c20-25e4-49c0-…… does not exist. Drop to the shell`.

可能原因:系统无法识别存储设备,注意配置内核时关于存储的驱动(SATA/PATA)要使能,因为我是在U盘中安装的系统,因此U盘相关的驱动也得使能。

4  当准备加载 rtai_hal.ko 模块时,提示`ERROR: Could not insert module rtai_hal.ko: Operation not permitted`错误,系统日志Syslog(`/var/log/syslog`) 提示`RTAI[hal] RTAI configured with less than num online CPUs`。

可能原因:RTAI 配置的CPU 个数比实际CPU 核心数要多,切记不要算上超线程(Hyperthreading)。

以上错误远不能包含所有你在安装RTAI 时遇到的问题,但你还可以借助下面的工具来帮助你的调试。

一些有用的命令和工具

  • Dmesg

dmesg

  • Syslog  

sudo cat /var/logsys

  • Systemctl

   Systemctl -failed   # 查看哪些内核没有被正常加载

  • RTAI 官网和邮件列表

www.rtai.org

  • Dpkg

dpkg –list | grep linux-image

  • mkinitramfs

寻找最大容错的扁平XOR 码

参考:

[1] Finding the most fault-tolerant flat XOR-based erasure codes for storage systems [PDF]

[2] Determining fault tolerance of XOR-based erasure codes efficiently [PDF]

本文内容主要来源于上面两篇文章,主要讨论暴力搜寻方法具有最大容错能力(most fault-tolerant)的扁平(Flat)XOR 码。

XOR 码是通过异或运算(exclusive OR)进行数据编码、解码和重建的编码方法,其生成矩阵可以用1/0 二进制矩阵表示。

扁平码是一种每个节点只保存一个符号(数据块),即生成矩阵的每一行(列)对应一个节点。k 和m 分别表示原始数据块个数和校验块个数的话,扁平码的生成矩阵是一个(k+m)×k 大小的0/1 矩阵。常见的RS 码是扁平码,但不是XOR 码;CRS 码不是扁平码,是XOR 码。

暴力搜索通过遍历所有的解空间(所有可能的(k, m) 编码),通过计算每个解的性质,找到满足条件的编码。一个(k+m)×k 大小的0/1 矩阵有2^((m+k)×k) 种可能的二进制矩阵,如果将编码限制在系统码中,则有2^(m×k) 种可能的二进制矩阵。

[2] 中介绍了一种ME (Minimal Erasures)算法,是暴力搜索的关键,该算法通过找到最小失效列表(Minimal Erasure List)寻找某种编码的最大容错能力。ME 算法会用到几个术语:

汉明距离(Hamming distance):如果一个编码的汉明矩阵是d,那么它能容忍的最大失效节点少于d 个。

失效样式(Erasure pattern):一组失效(的数据块)使得有一个原始数据块无法被恢复。

失效列表(Erasure list):所有失效样式的集合。

失效矢量(Erasure vector):长度为m 的矢量,其中第i 个元素是失效列表中长度为i 的失效样式个数的总和。比如 < 0, 0, 3, 7, …> 表示有失效列表中有3 个长度为3 的失效样式,有7 个长度为4 的失效样式。失效矢量中第d 个值是第一个非零值(小于d 的失效均可恢复)。

最小失效(Minimal Erasure,ME)是一种特殊的失效样式,它的每个失效元素都是必须的,如果去掉其中之一,它就不再是失效样式。

最小失效列表(Minimal Erausre List,MEL)是一个编码的所有最小失效的集合。

最小失效矢量(Minimal Erasure Vector,MEV)是一个长度为m 的矢量,其第i 个元素是MEL 中长度为i 的ME 的个数。

ME 算法具体详见[2] ,其输入是编码的生成矩阵(或Tanner 图),输出为MEL 和MEV。下图给出了 m < 8 和 k < 8 的结果。

下图是m < 11 和 k < 21 所有扁平XOR 码的最大汉明距离。

下图是m < 11 和 k < 21 所有扁平XOR 码中具有最优容错的个数。

下图是下图是m < 11 和 k < 21 所有扁平XOR 码中能够达到最大汉明距离的个数。

[1] 还介绍了如何减少搜索的解空间等优化的方法,并指出搜索算法有部分是Python 写的,用C 能够进一步提高运算速度,并增加m 和k 的值。

遗传算法解决数学等式(续)

之前的文章(http://blog.foool.net/2017/08/用遗传算法解决简单的数学等式问题/) 中介绍了过如何使用遗传算法解决数学等式问题,即寻找满足等式

(a + 2b + 3c + 4d) – 30 = 0

的一组解。适应函数确定后,影响算法好坏的主要依赖于交叉概率(crossover ratio),变异概率(mutation ratio)、初始基因组大小(即用于交叉变异的基因个数)和基因初始阈值。基因初始阈值指的是基因的取值范围,比如等式中变量a/b/c/d 的取值范围,我在实验中限定变量为大小不超过100 的整数。下面给出本文的几个结论。

一、遗传算法也可以用于寻找唯一解

之前的文章 中寻找的是四元一次等式的一个解,这个解的个数是无穷的,遗传算法能够找到一个解,但每次找到的解也不相同。但如果要用遗传算法解一个包含四个等式的四元一次方程组(唯一解)也是可行的,只是时间话的需要更长。比如遗传算法解四元一次等式平均需294 次迭代,解四元一次方程组需11400 次迭代(所有参数同之前的文章)。本文使用的四元一次方程组为:

(a + 2b + 3c + 4d) – 30 = 0

(2a + 2b + 2c + 2d) – 24 = 0

(3a + 1b + 7c + 1d) – 60 = 0

(4a + 3b + 2c + 1d) – 30 = 0

二、增加初始基因组大小有可能加速算法速度

增加基因组中基因数量,那么每次迭代/循环中的基因数量更多,可能出现解的概率增大。在以四元一次等式为例的实验中,增加基因组大小的确显著减少了迭代的次数,即使考虑了增加基因数目而带来的增量计算,算法仍减少了程序的整体运行时间。

三、增加初始基因组大小也有可能不能加速算法速度

有点调皮了,这个结论是和第二点结论是相左的,如在其他参数相同情况下,随着基因组大小增大,遗传算法在解四元一次方程组需要迭代的次数增加。

四、对于特定问题,参数大小影响算法性能大

下图是在基因组大小为18 时, 遗传算法1000 次测试四元一次等式求解所需要迭代次数的热力图,横坐标是变异率,从5% 到43%,纵坐标是交叉率,从5% 到70% 。热力图颜色范围是0-300,最深颜色表示300 次或300次以上迭代(比如在交叉率是70%,变异率是43%,实际迭代次数是9268次)。

综上,1.借助于适应函数,交叉、变异过程,遗传算法给出了一个在较大解空间快速求解的途径,但具体设计交叉、变异过程需要考虑特定问题;2.选取合适的参数极大影响了遗传算法性能,一般可以通过相似问题(复杂度更低)的参数选择作为参考(但是这种参考也不一定可靠,比如上面例子中,四元一次方程中增大基因组个数可以减少迭代次数,但在四元方程组中增加基因组个数却增加了迭代次数)。

自循环字符串/周期性字符串的判别和概率

问题来源:需要判断一个长度为N 的0/1 二进制字符串是自循环的概率是多少?自循环指的是一个字符串循环移位s 位仍然可以得到其本身,s 小于字符串长度。比如,010010 是自循环的,为将这个字符串循环右移三个bits 字符串还是其本身。

通过自循环字符串特征很容易推导出:自循环字符串是周期性字符串,即字符串完全由若干个相同子串拼接得到,上面例子中重复的子串是 010。并且,自循环字符串移位得到其本身需要的最少步数s 和最小子串长度相同,也就是说,计算得到字符串最小重复子串也就得到了其自循环需要移位数s。

那么问题归结为如何找到一个周期性字符串的最小重复子串

算法:令周期性字符串为S,那么SS 是两个S 的拼接,从SS 第二个字符开始,利用字符串匹配寻找S,如果SS 从第c 个字符开始包含了S 字符串,则S 的最小周期子串长度为c。下面是两个例子:

例子一:S =  010010

SS = 010010010010

  1.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  2.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  3.  0 1 0 0 1 0 0 1 0 0 1 0  是S

结束,最小子串长度为3,即010 。

例子二:S =  abaaabaaabaa

SS = abaaabaaabaaabaaabaaabaa

  1.   a b a a a b a a a b a a a b a a a b a a a b a a
  2.   a b a a a b a a a b a a a b a a a b a a a b a a
  3.   a b a a a b a a a b a a a b a a a b a a a b a a
  4.   a b a a a b a a a b a a a b a a a b a a a b a a

结束,最小子串长度为4,即abaa 。

接着统计了下二进制字符长度(X轴)和周期性字符串个数/概率(Y轴)关系。

可见,自循环字符串个数和概率与其字符串长度有关,总的来说:

  1. 长度越长,包含的自循环的字符串个数越多,呈指数增加
  2. 长度越长,字符串可能是自循环的概率降低,呈指数下降
  3. 素数只有两个自循环字符串(全0,全1)
  4. 包含分解因子越多,越可能包含更多自循环字符串