RH442-6 Linux进程调度

RH442-6 Linux进程调度

Linux进程调度
一、Cache-主存存储结构
1.   Cache的优点：
l  Cache的读写速度几乎能够和CPU进行匹配，可以大大提供系统的存取速度。
l  Cache的容量相对主存较小，整个存储器系统的成本没有上升很多。
2.   结构
CPU 与主存之间的数据传输必须经过Cache控制器进行。Cache控制器将来自CPU 的数据读写请求，转向 Cache 存储器，如果数据在 Cache 中，则 CPU对Cache 进行读写操作，称为一次命中 。命中时，CPU从Cache中读(写)数据。由于Cache 速度与 CPU 速度相匹配，因此不需要插入等待状态，故 CPU 处于零等待状态，也就是说CPU 与 Cache 达到了同步，因此，有时称高速缓存为同步 Cache ；若数据不在 Cache 中，则 CPU对主存操作，称为 一次失败 。失败时， CPU 必须在其总线 周期中插入等待周期 T W 。

二、Cache的基本操作
1.   读操作
当 CPU 发出读操作命令时，要根据它产生的主存地址分两种情形：一种是需要的数据已在 Cache 存储器中，那么只需直接访问 Cache 存储器，从对应单元中读取信息到数据总线；另一种是所需要的数据尚未装入 Cache 存储器， CPU在从主存读取信息的同时，由 Cache 替换部件把该地址所在的那块存储内容从主存拷贝到 Cache 中。 Cache 存储器中保存的字块是主存相应字块的副本。
2.   写操作
当 CPU 发出写操作命令时，也要根据它产生的主存地址分两种情形：其一，命中时，不但要把新的内容写入 Cache 存储器中，必须同时写入主存，使主存和 Cache 内容同时修改，保证主存和副本内容一致，这种方法称写直达法或称通过式写 (Write-through ，简称通写法 ) 。其二，未命中时，许多微机系统只向主存写入信息，而不必同时把这个地址单元所在的主 存中的整块内容调入 Cache 存储器。
 
三、地址映像及其方法
主存与 Cache 之间的信息交换，是以数据块的形式来进行的，为了把信息从主存调入 Cache ，必须应用某种函数把主存块映象到 Cache 块，称作地址映象。当信息按这种映象关系装入 Cache 后，系统在执行程序时，应将主存地址变换为 Cache 地址，这个变换过程叫做地址变换（由于 Cache 的存储空间较 小，因此，Cache 中的一个存储块要与主存中的若干个存储块相对应，即若干个主存块将映象到同一个 Cache 块）。地址映象的方式通常有直接映象、全相联映象和组相联映象三 种 。
1.   直接映像
优点：实现简单，
缺点：不够灵活，当程序往返访问两个相互冲突的块中数据时Cache 的命中率急剧下降。

 
2.   全相联映像
优点：块冲突的概率低，Cache 的利用率高。
缺点： Cache 中块表查找的速度慢，由于 Cache 的速度要求高，因此全部比较和替换策略都要用硬件实现，控制复杂，实现起来也比较困难。

 
3.   组相联映像
组相联映象方式是全相联映象和直接映象的一种折衷方案。组相联映象方法在判断块命中以及替换算法上都要比全相联映象方法简单，块冲突的概率比直接映象方法的低，其命中率介于直接映象和全相联映象。

四、Cache信息查询
1.   Cache信息
[root@www ~]# getconf -a|grep -i cache
LEVEL1_ICACHE_SIZE                 32768     #一级cache：32KB
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  6291456   #二级cache：6MB
LEVEL2_CACHE_ASSOC                 24
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  0
LEVEL3_CACHE_ASSOC                 0
LEVEL3_CACHE_LINESIZE              0
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
#其他查看方法：
[root@www ~]# x86info –c
 
2.   查询Cache的命中率
[root@www~]#valgrind --tool=cachegrind --I1=32768,8,64 --D1=32768,8,64 --L2=2097152,8,64 cache2
==12949== Cachegrind, a cache and branch-prediction profiler
==12949== Copyright (C) 2002-2009, and GNU GPL'd, by Nicholas Nethercote et al.
==12949== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==12949== Command: cache2
==12949==
Starting
Finished
==12949==
==12949== I   refs:      6,188,124,129
==12949== I1  misses:              633
==12949== L2i misses:              629
==12949== I1  miss rate:          0.00%
==12949== L2i miss rate:          0.00%
==12949==
==12949== D   refs:      3,937,851,911  (3,375,260,605 rd   + 562,591,306 wr)
==12949== D1  misses:      562,500,831  (          647 rd   + 562,500,184 wr)
==12949== L2d misses:       35,162,671  (          608 rd   +  35,162,063 wr)
==12949== D1  miss rate:    14.2% (  0.0%     +   99.9%  )  #L1丢失率
==12949== L2d miss rate:   0.8% (   0.0%     +         6.2%  )
==12949==
==12949== L2 refs:         562,501,464  (        1,280 rd   + 562,500,184 wr)
==12949== L2 misses:        35,163,300  (        1,237 rd   +  35,162,063 wr)
==12949== L2 miss rate:            0.3% (  0.0%     +   6.2%)   #L2丢失率
 
#cache使用率分析：#valgrind --tool=cachegrind programm_name
# --I1、--D1、--L2：匹配cpu的cache
 
五、Linux进程调度
1.   Linux内核进程的三种调度方法
l  SCHED_OTHER：分时调度策略
l  SCHED_FIFO： 实时调度策略，先到先服务
l  SCHED_RR：  实时调度策略，时间片轮转
 
#实时进程将得到优先调用，实时进程根据实时优先级决定调度权值。
#分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。
 
2.   所有任务都采用SCHED_OTHER（分时调度策略）调度策略
l  创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。
l  将根据每个任务的nice值确定在cpu上的执行时间(counter)。
l  如果没有等待资源，则将该任务加入到就绪队列中。
l  调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。
l  此时调度程序重复上面计算过程，转到第4步。
l  当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。
 
3.   所有任务都采用FIFO调度（实时调度策略，先到先服务）策略
l  创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。
l  如果没有等待资源，则将该任务加入到就绪队列中。
l  调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。
l  调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。
l  如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。
 
4.   所有任务都采用SCHED_RR（实时调度策略，时间片轮转）调度策略时
l  创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。
l  如果没有等待资源，则将该任务加入到就绪队列中。
l  调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。
l  如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。
l  当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。
 
5.   既有SCHED_OTHER，又有SCHED_RR和SCHED_FIFO调度
l  RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。
l  当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。
l  RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性(优先级是一样的，为什么要让你一直运行?),如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行，保证了公平。
 
6.   SHCED_RR时间片轮转调度和SCHED_FIFO先进先出调度比较
l  不同点：
Ø  当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。  
Ø  SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。
Ø  如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。
l  相同点：
Ø  RR和FIFO都只用于实时任务。
Ø  创建时优先级大于0(1-99)。
Ø  按照可抢占优先级调度算法进行。
Ø  就绪态的实时任务立即抢占非实时任务。
 
六、进程调度设置
1.   查看进程的调度策略和优先级
[root@www ~]# chrt -p pid
[root@www ~]# chrt -p 29441
pid 29441's current scheduling policy: SCHED_OTHER
pid 29441's current scheduling priority: 0
#进程调度方法：SCHED_OTHER
#优先级：默认优先级0
 
[root@www ~]# ps axo pid,comm,rtprio,plicy
PID COMMAND         RTPRIO POL
    1 init                 - TS
    2 migration/0         99 FF
    3 ksoftirqd/0          - TS
    4 watchdog/0          99 FF
    5 migration/1         99 FF
    6 ksoftirqd/1          - TS
#静态进程调度优先级：1-99 SCHED_FIFO（SF实时调度策略，先到先服务） 和SCHED_RR（SR实时调度策略，时间轮询）
#动态进程调度优先级：100-139 SCHED_OTHER （ST分时调度策略)
 
2.   设置和调整进程调度及其优先级
l  SCHED_FIFO:  #chrt -f [1-99] /path/to/prog arguments
[root@www ~]# chrt -f 80 ping 192.168.32.221 &
[root@www ~]# chrt -p 13490
pid 13490's current scheduling policy: SCHED_FIFO
pid 13490's current scheduling priority: 80
 
l  SCHED_RR：   #chrt -r [1-99] /path/to/prog arguments
[root@www ~]# chrt -r 80 ping 192.168.32.221 &
[root@www ~]# chrt -p 13490
pid 13490's current scheduling policy: SCHED_RR
pid 13490's current scheduling priority: 80
 
l  SCHED_OTHER: #nice or renice
[root@www ~]# renice -10 -p 13464          
13464: old priority  0, new priority -10