Skyline对《编程之美》的笔记(3)

让多核CPU占用率曲线听你指挥——《编程之美》1.1学习笔记 Problem:

分析与解法： （1）通过观察任务管理器，它大约1s更新一次。当CPU使用率为0时，System Idle Process占用了CPU的空闲时间。 System Idle Process在CPU空闲的的时候，发出一个IDLE命令，使CPU挂起（暂时停止工作），可有效的降低CPU内核的温度，无法终止。在这个进程里出现的CPU占用数值并不是真正的占用而是体现的CPU的空闲率，也就说这个数值越大CPU的空闲率就越高，反之就是CPU的占用率越高。Linux中对应的进程为init,PID为1。 当系统中的进程或者在等待用户输入，或者在等待某些事件的发生（发出I/O请求等待I/O响应），或者主动进入休眠状态（比如Sleep()）。

书上的代码以单核CPU为前提，但对于多核CPU来说，同一个进程可能被CPU的任务分配器分配到不同的核心上执行，所以造成无法让任务管理器达到预想的效果。其实打开任务管理器，可以看到多个CPU使用记录。本人电脑CPU是Core i5 450M,双核4线程。在OS看来就如同有四个CPU工作一样。我的任务管理器中就有四个CPU使用记录。 所谓超线程技术就是利用特殊的硬件指令，把多线程处理器内部的两个逻辑内核模拟成两个物理芯片，从而使单个处理器就能“享用”线程级的并行计算的处理器技术。多线程技术可以在支持多线程的操作系统和软件上，有效的增强处理器在多任务、多线程处理上的处理能力。 可以使用SetProcessAffinityMask()函数可以使特定的处理器运行指定进程。 BOOL SetProcessAffinityMask(HANDLE hProcess, DWORD_PTR dwProcessAffinityMask); 第一个参数用来指定指定哪个进程，传入它的句柄。第二个进程用来指定哪个CPU核心来执行此进程。 DWORD_PTR,其实就是unsigned long*.Unsigned long type for pointer precision.Use when casting a pointer to a long type to perform pointer arithmetic.(Also commonly used for general 32-bit parameters that have been extended to 64 bits in 64-bit windows.) DWORD 其实就是unsigned long。Windows下常用来保存地址或存放指针。 比如这样调用函数： ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000001);可以指定当前执行的进程在第一个CPU上运行。对于双核CPU， ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000002);可以指定在第二个CPU上运行。 ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000003);可以允许在两个CPU上任意运行。 HANDLE GetCurrentProcess(void); 可以获得当前进程的句柄。注意，这个句柄为一个伪句柄。只能在我们的进程中才能代表当前进程的句柄，事实上这个函数目前只是简单的返回-1这个值。也就是说在我们的程序中-1便能表示本进程的句柄。 （2）那么对于绘制50%直线，程序代码为：

#include <Windows.h>  
#include<stdlib.h>  
#include<tchar.h>  
int _tmain(int argc,_TCHAR* argv[])  
{  
    int busyTime = 10;  
    int idleTime = busyTime*5;  
    __int64 startTime = 0;  
    ::SetThreadAffinityMask(::GetCurrentProcess(),0x00000001);  
    while(true)  
    {  
        startTime = GetTickCount();  
                //busy loop  
        while((GetTickCount() - startTime) <= busyTime);  
                //idle loop  
            Sleep(idleTime);  
    }  
    return 0;  
}

GetTickCount()可以得到系统从启动到运行到现在所经历时间的毫秒值。最多能统计到49.7天。我们利用它判断busy loop要持续多久。 其中idleTime为busyTime的五倍，可以修改其值使其更逼近50%。不同机子的情况不同。 __int64是VC++的64位扩展。范围为[-2^63,2^63)。当64位与32位混合运算时，32位整数会隐式转换成64位整数。输入输出它时使用cin、cout会造成错误。需要使用scanf("%I64d",&a);和printf("%I64d",a); 还有unsigned __int64，其范围为[0,2^64)。 对应g++中的64位扩展为long long和unsigned long long。范围与运算与上相仿。输入输出使用scanf("%lld",&a);和printf("%lld",a); int _tmain(int argc, _TCHAR* argv[])。 _tmain这个符号多见于VC++创建的控制台工程中，这个是为了保证移植unicode而加入的（一般_t、_T、T()这些东西都和unicode有关系）。定义在头文件tchar.h中。 （3）对于绘制正弦曲线：

#include <Windows.h>  
#include<stdlib.h>  
#include<math.h>  
#include<tchar.h>  
const double SPLIT = 0.01;  
const int COUNT = 200;  
const double PI = 3.14159265;  
const int INTERVAL = 300;  
int _tmain(int argc, _TCHAR* argv[] )  
{  
    DWORD busySpan[COUNT]; //array of busy times  
    DWORD idleSpan[COUNT]; //array of idle times  
    int half = INTERVAL/2;  
    double radian = 0.0;  
        //如何近似趋近一条正弦曲线？这样！  
    for(int i = 0; i < COUNT; ++i)  
    {  
        busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));  
        idleSpan[i] = INTERVAL - busySpan[i];  
        radian += SPLIT;  
    }  
    DWORD startTime = 0;  
    int j = 0;  
    ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000002);   
    while(true)  
    {  
        j = j % COUNT;  
        startTime = GetTickCount();  
        while((GetTickCount() - startTime) <= busySpan[j]);  
            Sleep(idleSpan[j]);  
        j++;  
    }  
    return 0;  
}

通过在一个周期2*PI中等分200份，将每一个间隔点的half + （sin( PI * radian) * half))的值存入busySpan[i]，将其补植存入idleSpan[i]。half是整个值域INTERVAL的一半。这样可以近似趋近一条正弦曲线。 运行效果为： （4)可以通过RDTSC指令获得当前CPU核心运行周期数。 在x86平台上定义函数：

inline __int64 GetCPUTickCount()  
{  
    __asm  
    {  
        rdtsc;  
    }  
}

在x64平台上定义： #define GetCPUTickCount() __rdtsc() 使用CallNtPowerInformation API得到CPU频率，从而将周期数转化为毫秒数，例如如下：

_PROCESSOR_POWER_INFORMATION info;  
CallNTPowerInformation(11,              //query processor power information  
    NULL,                               //no input buffer  
    0,                                  //input buffer size is zero  
    &info,                              //output buffer  
    sizeof(info)                        //outbuf size  
    );  
__int64 t_begin = GetCPUTickCount();  
//do something  
__int64 t_end = GetCPUTickCount();  
millisec = ((double)t_end - (double)t_begin)/(double)info.CurrentMhz;

RDTSC指令读取当前CPU的周期数，在多CPU系统中这个周期数在不同的CPU间基数不同，频率也不同。用从两个不同的CPU得到的周期数来计算会得出没有意义的值。所以需要用SetProcessAffinityMask避免进程迁移。另外，CPU的频率也会随系统供电及负荷情况有所调整。

引子问题： 中国象棋将帅问题：

分析与解法： 这个问题的解法并不复杂。 遍历A的所有位置 遍历B的所有位置 如果A的位置和B的位置在同一列 输出结果 否则 继续寻找 地图可以用0-8表示A或B可能的9个位置 0------1------2 3------4------5 6------7------8 关键问题在于只使用一个变量来表示A和B的位置。所以可以使用位运算来解决。一个无符号字符类型的长度是1字节，也就是8位，8位可以表示2^8=256个值，对于A、B的9个位置来说足够。可以用前4位来表示A的位置情况，后4位表示B的位置情况。而4位可以表示16个数也足够表示A、B的位置情况了。 通过位运算可以对A、B的位置进行读取和修改。 几种基本的位运算： （1）& 按位与运算 （2）| 按位或运算 "与"和"或"就不用说了吧 （3）^ 按位异或运算 相同为假，不同为真 （4）~ 按位取反 一元运算符 （5）<< 按位左移 如 0000 0111 << 2 = 0001 1100,将此数左移两位相当于将此数扩大两倍。 （6）>> 按位右移 如 0001 1000 >> 2 = 0000 0110,将此数右移两位相当于将此数缩小两倍。 令LMASK为1111 0000，另任意一个1字节的字符型变量与其做与运算，结果右移四位，便可得到此变量的高四位的值。 Example, 0110 1011 &1111 0000 = 0110 0000 >> 4 = 0000 0110 同理，令RMASK为0000 1111，即可得到它低四位的值。 Ex. 0110 1011 & 0000 1111 = 0000 1011 设置1字节字符型变量，比如对高四位进行设置，先将变量与RMASK相与，将要修改的变量左移四位后于前一结果进行“异或”或“或运算”。 Ex.将0110 1011高四位设置为1001. 0110 1011 & 0000 1111 = 0000 1011 0000 1001 << 4 = 1001 0000 ^ 1001 0000 = 1001 1011 同样的方法设置低四位的值。 代码：

#include<stdio.h>

#define HALF_BITS_LENGTH    4                                                                            //一半字节的长度
#define FULLMASK                 255                                                                        //即1111 1111
#define LMASK                      (FULLMASK << HALF_BITS_LENGTH)                     //即1111 0000
#define RMASK                      (FULLMASK >> HALF_BITS_LENGTH)                    //即0000 1111
#define RSET(b, n)                  (b = (LMASK & b) ^ n)                                          //设置低四位
#define LSET(b, n)                  (b = (RMASK & b) ^ (n << HALF_BITS_LENGTH)) //设置高四位
#define RGET(b)                     (RMASK & b)                                                        //得到低四位
#define LGET(b)                     ((LMASK & b) >> HALF_BITS_LENGTH)                //得到高四位
#define GRIDW                     3                                                                          //将帅活动范围尺寸
#define BYTE                         unsigned char

int main(void)
{
    BYTE b;     //只有一个变量
    for(LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))//从A的1位置一直找到9位置，注意自增的写法
        for(RSET(b, 1); RGET(b) <= GRIDW * GRIDW; RSET(b, (RGET(b) + 1)))//从B的1位置找到9位置
            if((LGET(b) % GRIDW) != (RGET(b) % GRIDW))   //如果不在同一列，则打印结果
                printf("A = %d, B = %d\n", LGET(b), RGET(b));
    return 0;
}

这是个关于如何利用位运算解决问题的一个简单的运用，可以看到位运算合理地利用一个变量解决象棋将帅问题。算法本身很简单，重点是位运算的应用。 <BOP>上还有两个更简洁的算法： 第一个：

#include<stdio.h>

#define BYTE unsigned char

int main(void)
{
    BYTE i = 81;
    while(i--)
    {
        if((i / 9) % 3 == (i % 9) % 3)
            continue;
        printf("A = %d, B = %d\n", i /9 + 1, i%9 + 1);
    }
    return 0;
}

可以把变量i想象成一个两位九进制的变量，而i在计算机中存储的值是i的十进制表示。则i/9的计算机处理结果，即结果直接去掉小数点后部分的结果即是此九进制数的第二位，而i%9即是此九进制数的个位。本程序用此九进制数的第二位保存A的位置，个位表示B的位置。最大值为88，即为十进制的80.程序从十进制的80，即九进制的88遍历到十进制的0，即九进制的0.将符合条件的位置全部输出。 第二个：

#include<stdio.h>


int main(void)
{
    struct
    {
        unsigned char a:4;
        unsigned char b:4;
    }i;


    for(i.a = 1; i.a <= 9; i.a++)
        for(i.b = 1; i.b <= 9; i.b++)
            if(i.a % 3 != i.b % 3)
                printf("A = %d, B = %d\n", i.a, i.b);
    return 0;
}

算法与上面的如出一辙。 其中unsigned char a:4表示结构体中a的位域只有4位，高位用作它用。只能在结构体里使用，建议尽量少用，会破坏程序的移植性。 当结构体中的元素的取值范围很小时，可以将几个字段按位合成一个字段来表示，起到节省内存空间的作用。 Ex:

#include<stdio.h>

int main(void)
{
    struct test
    {
        unsigned char a:4;
        unsigned char b:4;
    }i;
    i.a = 15;
    i.b = 10;
    printf("%d\n", sizeof(i));
}

将上面例子中的变量i的大小输出，结果为1字节。说明i.a和i.b各占4位。 结构体是C语言中的一种常用的自定义数据结构。 看下面的例子：

#include<stdio.h>

int main(void)
{
    struct test
    {
        int a;
        char b;
    }i;
    printf("%d\n",sizeof(i));
}

按理说结构体变量i的大小应该是sizeof(int)+sizeof(char)，即5，而输出显示的结果为8。再看一个例子：

#include<stdio.h>

int main(void)
{
    struct test
    {
        int a;
        char b,c;
    }i;
    printf("%d\n",sizeof(i));
}

应该是6对吧？结果还是8.这是为什么呢？ 这是因为在32位的操作系统上，操作系统组织数据是以32位(4个字节)作为一个标准，因此各种变量的size都一般都是4的倍数。而且结构体数据都是按照定义时所使用的顺序存放的，因此在第一个例子中尽管b变量只会占有一个字节，但是a + b = 5 > 4，因此第一个4个字节存放a，第二个4个字节用于存放b,这样实际上就浪费了3个字节。在第二个例子中第二个4个字节用来存放b和c。 所以，在结构体中要注意结构体中的变量定义的顺序，不同的顺序可能会造成占用空间的不同。这在嵌入式程序设计等系统资源比较少的情况下尤为重要。比如如下两种结构体：

#include<stdio.h>

struct m
{
    char a;
    int b;
    char c;
}x;
struct n
{
    char a;
    char c;
    int b;
}y;
int main(void)
{
    printf("m:%d\nn:%d\n", sizeof(x), sizeof(y));
    return 0;
}

对于结构体m来说，x变量的大小为12，而y变量的大小为8.编译器是按程序员在结构体中声明变量的顺序处理的。不当的顺序会造成空间的浪费。读者可以想到发生这样情况的原因的。所以建议声明结构体时，按照不同变量的类型，按占用空间的大小升序或降序声明会取得较好的空间占用。

本回将尝试在Linux环境下能否在系统监视器中画出一个正弦曲线。本人环境为Ubuntu 11.04. 基本思想还是和Windows下面的相同，更换系统调用，便可以实现功能的迁移。

#include <time.h>  
    #include <sys/time.h>  
    #include <unistd.h>  
    #include<stdlib.h>  
    #include<math.h>  
      
    #define DWORD unsigned long  
    #define UINT64 unsigned long long  
    const double SPLIT = 0.01;  
    const int COUNT = 200;  
    const double PI = 3.14159265;  
    const int INTERVAL = 300;  
      
    int main(int argc, char* argv[] )  
    {  
        struct timeval tms;  
        DWORD busySpan[COUNT];  
        DWORD idleSpan[COUNT];  
        int half = INTERVAL/2, i;  
        double radian = 0.0;  
        for(i = 0; i < COUNT; ++i)  
        {  
            busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));  
            idleSpan[i] = INTERVAL - busySpan[i];  
            radian += SPLIT;  
        }  
        clock_t startTime = 0;  
        int j = 0;  
        while(1)  
        {  
            j = j % COUNT;  
            timerclear(&tms);  
            gettimeofday(&tms,NULL);  
            UINT64 startTime = tms.tv_usec;  
            while(1)//clock返回该进程从启动到现在经历的毫秒数（千分之一秒）  
            {  
                timerclear(&tms);  
                gettimeofday(&tms,NULL);  
                UINT64 nowTime = tms.tv_usec;  
                if((nowTime - startTime)/1000 > busySpan[j])  
                    break;  
            }  
                if(usleep(idleSpan[j]*1000))  //精确到微秒（百万分之一秒）的函数  
                    exit(-1);  
            j++;  
        }  
        return 0;  
    }

gettimeofday()函数用来取得当前时间(微秒，百万分之一秒)。并通过参数传递给结构体timeval类型的tms。 int gettimeofday(struct timeval *tv, struct timezone *tz); tz用来获取时区信息。不做介绍。 结构体timeval的定义为： struct timeval { time_t tv_sec; //seconds suseconds_t tv_usec; //microseconds }; tz如果是NULL的话将不传递时区信息。tv提供秒为单位的和微妙为单位的从Epoch开始的计数。 结构体timeval的域为类型long的域。 此函数返回0，表示成功，-1表示失败。 Windows中，GetTickCount返回的是从系统启动到现在的毫秒。 int usleep(useconds_t usec); 定义在头文件unistd.h中。它使当前进程挂起至少usec微秒（百万分之一秒）.睡眠时间可能会被任意系统活动或进程切换开销或系统计时器的精确度而轻微延迟。成功时返回0，错误时返回-1. 或者使用clock()来得到系统时间也是可以的。它返回从进程启动到现在经历的时间，单位是毫秒（千分之一秒）。定义在头文件time.h下. clock_t clock(void); 相应代码如下。

#include <time.h>  
    #include <sys/time.h>  
    #include <unistd.h>  
    #include<stdlib.h>  
    #include<math.h>  
      
    #define DWORD unsigned long  
    #define UINT64 unsigned long long  
    const double SPLIT = 0.01;  
    const int COUNT = 200;  
    const double PI = 3.14159265;  
    const int INTERVAL = 300;  
      
    int main(int argc, char* argv[] )  
    {  
        struct timeval tms;  
        DWORD busySpan[COUNT];  
        DWORD idleSpan[COUNT];  
        int half = INTERVAL/2, i;  
        double radian = 0.0;  
        for(i = 0; i < COUNT; ++i)  
        {  
            busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));  
            idleSpan[i] = INTERVAL - busySpan[i];  
            radian += SPLIT;  
        }  
        clock_t startTime = 0;  
        int j = 0;  
        while(1)  
        {  
            j = j % COUNT;  
            timerclear(&tms);  
            gettimeofday(&tms,NULL);  
            clock_t startTime = clock();  
            while((clock()-startTime) <= busySpan[j])//clock返回该进程从启动到现在经历的毫秒数（千分之一秒）  
            ;  
            if(usleep(idleSpan[j]*1000))  //精确到微秒（百万分之一秒）的函数  
                    exit(-1);  
            j++;  
        }  
        return 0;  
    }

但对于多核CPU，如何限制进程在一个CPU上运行呢？ 如何察看某个进程在哪个CPU上运行： 在控制台中输入： #top -d 1 之后按下f.进入top Current Fields设置页面： 选中：j: P = Last used cpu (SMP) 则多了一项：P 显示此进程使用哪个CPU。 经过试验发现：同一个进程，在不同时刻，会使用不同CPU Core.这应该是Linux Kernel SMP处理的。 本程序通过这个方法查看，将会在多个CPU上运行。 想要让它在一个CPU上执行，可以这样做： 1.下载包schedtool. 在控制台中输入:sudo apt-get install schedtool，然后输入你的密码。 schedtool是Linux下用来查询或设置CPU状态的工具。通过不同的参数可以查看或设置不同的属性。 [-0|-N] [-1|-F] [-2|-R] [-3|-B] [-4|-I] [-5|-D] [-M policy] [-a affinity] [-p prio] [-n nice_level] [-e command [arg ...]] [-r] [-v] [-h] 我们这里要用到的是 -a和-e。其他可以参考这里： http://linux.die.net/man/8/schedtool -a用来设置进程在哪个CPU上运行。-a的参数为： 0x1 表示只运行在CPU0(00000001) 0x2 表示只运行在CPU1(00000010) 0x4表示紫云行在CPU2(00000100) 0x8表示只运行在CPU3(00001000) etc. 或者，多CPU运行可以这样表示， 0x7表示可以运行在CPU0,1,2 (00000111) 0x5表示可运行在CPU0，2 (00000101) 以此类推。 -e用来通过指定的参数来执行命令。后面的参数为控制台命令。 在Linux下，如何确认是多核或多CPU: #cat /proc/cpuinfo 如果有多个类似以下的项目，则为多核或多CPU: processor : 0 ...... processor : 1 在编译后，我们执行命令：sched -a 0x1 -e ./桌面/sin 可以通过上面介绍的方法查看进程sin是否在同一个CPU上运行。 然后就可以通过系统监视器查看运行结果啦！ 运行结果（橙色线）： 还有一段Python的代码，运行是与上面类似的，这个来自于网上^_^：

    #!/usr/bin/env python  


import itertools, math, time, sys  
      
    time_period = float(sys.argv[1]) if len(sys.argv) > 1 else 30   # seconds  
    time_slice  = float(sys.argv[2]) if len(sys.argv) > 2 else 0.04 # seconds  
      
    N = int(time_period / time_slice)  
    for i in itertools.cycle(range(N)):  
        busy_time = time_slice / 2 * (math.sin(2*math.pi*i/N) + 1)  
        t = time.clock() + busy_time  
        while t > time.clock():  
            pass  
        time.sleep(time_slice - busy_time);

在控制台下输入命令：sched -a 0x1 -e python ./桌面/sin_p.py(此处写你源文件的路径).即可！