題目說明

寫一程式,讓使用者決定 windows 工作管理員之 cpu 使用率。程式越精簡越好,電腦語言不限。如,可實現下列三種情況:

1. cpu 使用率固定在 50%
2. cpu 使用率為一直線
3. cpu 使用率狀態為一正弦曲線

[EdisonX 備註]

0. 此問題使用了大量之空回圈解決,部份 compiler 會自動將空回圈移除,故建議別開最佳化。若為 VC,建議用 debug mode 別用 release mode。
1. 這題目讓許多人感興趣,吾人也針對此題目補充了許多資料,總文之量約為原文之 2 部,看完後必可有不少收穫!

2. 據觀查結果,工作管理員約每秒更新一次
3. 作者該手邊之電腦配備為 CPU P4 2.4Ghz,單核,故多核 CPU 程式碼必定需要做修改
4. 若多核 CPU 不以多行緒方式執行,則使用率必須用寫檔紀錄方式進行;但此動作卻又會影響使用率。
5. 本書此章節使用之多行緒,不適合用 _beginthread / _beginthreadex 系列;
   因這系列函式無法將執行緒指定 CPU 執行,故以下提出相關之函式。

CreateThread :建立執行緒
SetThreadAffinityMask :將執行緒設定給指定 CPU 執行
ResumeThread :掛起執行緒
SuspendThread :繼續掛起之執行緒

用到 busy , idle 二個不同 loop,透過不同時間比例調節 cpu 使用率。


[解法一] 簡單解法

 若 CPU 使用率高的時候,sleep 少一點;CPU 使用率低的時候,sleep 多一點。其中 busy 可由空回圈;idle 以 Sleep 實現,重點便在於「如何控制二個 loop 時間」。所以程式碼看起來長這樣

for(;;){
    for(int i=0; i< ?? ; i++);
    Sleep( ???? );
}

 

上面那二處問號是我故意打的 (書上是寫 i<9600000, Sleep(10), 但這數字很沒意義)。首先,作者先以組語方式去拆寫 for(i=0; i<n; i++) 之程式碼,拆解如下

loop:
   mov dx i
   inc dx
   move i dx
   cmp i n
   jl loop

上述共 5 個指令,且作者手邊硬體為 CPU P4 2.4Ghz 單核,當時 CPU 每個時鐘週期可執行兩個以上程式碼,於是取平均值 2 個,就是讓 (2,400,000,000 * 2) / 5 = 960,000,000 (迴圈/秒)。換句話說,CPU 1 秒鐘執行這麼多回圈,再休息 1 秒鐘,這樣平均下來就有 50%。但這麼做會有個很嚴重的缺點,便是波形可能是鋸齒狀:先到峰值,再降到很低,因工作管理員約每秒更新一次。

於是,試著將 busy , idle 降下來,但保持比率不變之原則,就選擇了 for-loop 裡是 9,600,000 次;Sleep 為 10 ms,接下來便寫了這段程式碼

#include <windows.h>
int main()
{
    int i;
    for(;;){
        for(i=0; i<96000000; i++);
        Sleep(10);
    }
    return 0;
}

 

接著再依實際的結果去調用 for-loop 之計數次數與 Sleep 時間長短。 


[解法一實測與評論]  

0. 原理部份

吾人認為使用的原理如下所述

a. 計算 1 sec 會跑幾個 loop
b. 再休息 1 sec

這樣是 1 sec 滿載(100%); 1 sec 無載(近似0%);平均下來便是 (無載)/(滿載+無載),
比較正確的表示應為 (busy time) / (idle time+ busy time),但 idle+busy 盡量就小於 1 sec,
因工作管理員約 1 sec 更新一次。

1. asm 碼部份

吾人沒修過組合語言,所以籍由 DEV-C++ 內附之工具 (cc1.exe) 將 .c 轉成 .s(asm),
會特別再用 dev-c++ 協助轉,仍因吾人找不到 CL.exe 如何將 c source code 轉成 asm code。
考慮以下程式碼 (假設檔名為 C:\asm.c)

int main()
{
   int i;
   for(i=0; i!=9600000; ++i);
   // for(i=0; i!=9600000; i++); // 生成出來一樣
   return 0;
}

 

用 cmd.exe 切到 C:\Dev-Cpp\libexec\gcc\mingw32,指令下 cc1.exe C:\asm.c,
便於 C:\ 產生 asm.s,這裡只摘錄其回圈部份

L2:
 cmpl $9600000, -4(%ebp)
 je L3
 leal -4(%ebp), %eax
 incl (%eax)
 jmp L2
L3:
 movl $0, %eax
 leave
 ret

 

2. Sleep(10) 之部份

這部份作者之所以「至少」選擇 10,原因是「比較接近 windows 排程時間之間隔」,
這問題可引發很多討論,因其義應為 task timeslice,也就是在切換 task 時花費時間;
在 linux 上可以用 task_timeslice 此函式去取得,但在 windows 上怎麼去取得 ts?
這便是一個問題
(於是這問題後面有其它改善法),目前我試著去找的網頁,的確大多指向
ts = 15.625ms (感謝 Jacob Lee 指導:windows 99.99% 之 ts = 15.625 ms)。

若照作者意思,「若選擇太小,會造成執行緒頻繁被喚醒暫停,無形中又增加了核心時間不確定性」,
那是否就代表 Sleep 應「至少」要是 16 以上?吾人認為應為如此較為合理

3. 怎麼測 CPU 一個時脈週期可執行幾個指令?

這個的確為吾人所困惑之處,每個 CPU 所做之 pipeline 管數不盡相同,一個 clock 能執行幾個指令?
除了找技術文件之外,仍百思不得其解!實測就以書上說的「平均為 2 」下去實做看看。

4. 考慮 CPU 時脈率之實際程式碼

吾人手邊 CPU 為 AMD Athlon(tm)ⅡX2 245 processor 2.91Ghz,
若考慮加法、比較之 asm code 為 7 個指令,以作者計算之方式

(2,910,000,000 * 2) / 7 = 831,428,571.4,Sleep(1000)
--->  for loop:16,628,571  , Sleep(20)

會調用 Sleep(20),仍因 20 較接近且大於 ts (15.625)。
再考慮吾人為雙核非單核,使用 CreateThread 後,程式碼如下所示

#include <windows.h>
#include <stdlib.h>

const int IDLE = 20;
const int BUSY_COUNT = 16628571;

DWORD WINAPI LineThread(LPVOID Line)
{
    int i;
    while(1) {
       for (i=0; i!=BUSY_COUNT; ++i);
       Sleep(IDLE);
    }
}

int main()
{
    HANDLE hThread;
    DWORD dwThreadID;
    hThread = CreateThread(NULL, 0, LineThread,0,CREATE_SUSPENDED,&dwThreadID);
    SetThreadAffinityMask(hThread, 1); /* 第一顆 CPU */
    ResumeThread(hThread);
    SuspendThread(GetCurrentThread());
    return 0;
}

5. 缺點部份

(1) 如果數據都沒調過就真的是在 50% 上下,那只是僥倖而已,原因如下。

(2) 此程式只考慮「這個程式暫對 CPU 之影響」,而沒考慮到「對整個系統使用率」之影響,同時二個常數都要自己去調;調好後若再多開幾個應用程式那又不準了。

[解法一執行結果圖]

EdisonX-093.png  

這張圖結果吾人認為還算合理,我在程式中已設定此程式之執行緒由 CPU1 所執行,故只看 CPU 1 即可,而CPU 使用率的確是在 50% 上下 (算一下,中間線上下各 7 個隔子,應為 50% 左右);但如前述,這不是絕對,這應是僥倖。


[解法二] 使用 GetTickCount() 和 Sleep()

GetTickCount 可得到「系統啟動到現在」所經歷之毫秒數 (欲用 GetTickCount 可參考吾人另一篇文章),故可利用 GetTickCount() 判斷 busy loop 要回圈多久,程式碼如下所示

#include <windows.h>

int main()
{
    int busyTime=10;
    int idleTime=busyTime;
    __int64 startTime=0;

    while(1){
        /* 開始計時 */
       startTime = GetTickCount();
       /* loop 一直跑 10 ms */
       while( (GetTickCount() - startTime) <= busyTime); 
       /* 再休息 10 ms */
       Sleep(idleTime);
    }
    return 0;
}

 

但上述兩種解法都是在假設目前系統只有當前程式執行,實際上,作業系統中有很多程式會同時執行,若此刻其他 process 使用 10%  CPU,程式應只能使用 40% CPU,才能達到 50% 效果。於是作者便提出了另一工具 - Perfmon.exe 幫忙檢測。至於程式如何使用?這又是下一解法。


[解法二實測與評論]

 考慮多核、ts 後,程式碼如下所示

#include <windows.h>

const int busyTime=20;
const int idleTime=busyTime;

DWORD WINAPI LineThread(LPVOID Line)
{
    __int64 startTime;
    while(1) {       
       /* loop 裡跑 busyTime */
       startTime = GetTickCount();
       /* loop 裡跑 busyTime */
       while( (GetTickCount() - startTime) <= busyTime);
       /* 再休息 busyTime */
       Sleep(idleTime);
    }
}

int main()
{
    HANDLE hThread;
    DWORD dwThreadID;
    hThread = CreateThread(NULL, 0, LineThread,0,CREATE_SUSPENDED,&dwThreadID);
    SetThreadAffinityMask(hThread, 1); /* 第一顆 CPU */
    ResumeThread(hThread);
    SuspendThread(GetCurrentThread());
    SwitchToThread();
    return 0;
}

 

[解法二] 執行結果圖

EdisonX-094.png  

實際上約是在 65 % 左右做振盪,這結果並不讓人感到意外,因假設系統程式只有這個 process 在執行,忽略了其它之因素。


[解法三] 能動態調整之解法

 上述提到之 Perfmon 是從 Windows NT 開始便含在 Windows 管理工具組中之專業檢測工具之一,開啟方式為在 cmd.exe 下輸入 perfmon.exe 即可,大致會出現類似以下之圖

EdisonX-095.png   

也可寫程式來查詢 Perfmon 之值, Microsoft .Net Framework 提供 PerformanceCounter 此一物件,可方便得到各種效能資,含 CPU 使用率,C# 程式碼如下

static void MakeUsage(float level)
{
    PerformanceCounter p = new PerformanceCounter("Processor",
      "%Processor Time", "_Total");

   if(p==NULL) return;

   while(true)
   {
         if(p.NextValue() > level) System.Threading.Thread.Sleep(10);
   }
}

 


 

 [解法三實測與評論]

 上述提到利用 Microsoft .Net Framework PerformanceCounter 物件取得各種效能資料,其中便包括了 CPU 使用率,吾人對 .Net Framework 沒研究,且對 C# 也沒研究,故無法得知所謂的「CPU 使用率」是否有辦法取得「單一之 CPU 使用率」,抑或指的是綜合之 CPU 使用率。

目前吾人所知利用 API 取得 CPU 使用率,乃是利用 win32 undocument API 方式進行,目前只研究到「整體綜合之 CPU 使用率」,而非「單一 CPU 使用率」。故這部份看看參考便可,以下之 cpu.h 即為取得使用率之核心。

cpu.h

#include <windows.h>
#include <conio.h>
#include <stdio.h>

#define SystemBasicInformation 0
#define SystemPerformanceInformation 2
#define SystemTimeInformation 3

#define Li2Double(x)((double)((x).HighPart)* 4.294967296E9 +(double)((x).LowPart))

typedef   struct
{
    DWORD       dwUnknown1;
    ULONG       uKeMaximumIncrement;
    ULONG       uPageSize;
    ULONG       uMmNumberOfPhysicalPages;
    ULONG       uMmLowestPhysicalPage;
    ULONG       uMmHighestPhysicalPage;
    ULONG       uAllocationGranularity;
    PVOID       pLowestUserAddress;
    PVOID       pMmHighestUserAddress;
    ULONG       uKeActiveProcessors;
    BYTE         bKeNumberProcessors;
    BYTE         bUnknown2;
    WORD         wUnknown3;
}   SYSTEM_BASIC_INFORMATION;

typedef   struct
{
    LARGE_INTEGER       liIdleTime;
    DWORD                       dwSpare[76];
}   SYSTEM_PERFORMANCE_INFORMATION;

typedef   struct
{
    LARGE_INTEGER   liKeBootTime;
    LARGE_INTEGER   liKeSystemTime;
    LARGE_INTEGER   liExpTimeZoneBias;
    ULONG                   uCurrentTimeZoneId;
    DWORD                   dwReserved;
}   SYSTEM_TIME_INFORMATION;

typedef   LONG   (WINAPI   *PROCNTQSI)(UINT,PVOID,ULONG,PULONG);
PROCNTQSI   NtQuerySystemInformation;

SYSTEM_PERFORMANCE_INFORMATION SysPerfInfo;
SYSTEM_TIME_INFORMATION SysTimeInfo;
SYSTEM_BASIC_INFORMATION SysBaseInfo;
double dbIdleTime, dbSystemTime;
LONG status;
LARGE_INTEGER liOldIdleTime = {0,0}, liOldSystemTime = {0,0};

int CPURateInit()
{
    NtQuerySystemInformation = (PROCNTQSI)GetProcAddress(
       GetModuleHandle("ntdll"),
       "NtQuerySystemInformation"
       );

    if (!NtQuerySystemInformation) {
       printf("GetProcAddress fail.\n");
       return EXIT_FAILURE;
    }

    // get number of processor in the system
    status = NtQuerySystemInformation(SystemBasicInformation, &SysBaseInfo, sizeof(SysBaseInfo), NULL);
    if(status!=NO_ERROR) {
       printf("(NtQuerySystemInformation) get number of processor fail.\n");
       return EXIT_FAILURE;
    }
}

double GetCPURate()
{
    double x=0.0;
    // get new system time
    status = NtQuerySystemInformation(SystemTimeInformation, &SysTimeInfo, sizeof(SysTimeInfo), NULL);
    if(status!=NO_ERROR) {
       printf("NtQuerySystemInformation fail.\n");
       // return EXIT_FAILURE;
       return -1.0;
    }

    // get new CPU's idle time
    status = NtQuerySystemInformation(SystemPerformanceInformation,&SysPerfInfo,sizeof(SysPerfInfo),NULL);
    if(status!=NO_ERROR) {
       printf("NtQuerySystemInformation fail.\n");
       // return EXIT_FAILURE;
       return -1.0;
    }

    // if first call, skip it
    if(liOldIdleTime.QuadPart!=0){

       // current value = new value - old value
       dbIdleTime = Li2Double(SysPerfInfo.liIdleTime) - Li2Double(liOldIdleTime);
       dbSystemTime =  Li2Double(SysTimeInfo.liKeSystemTime) - Li2Double(liOldSystemTime);

       // current cpu idle = idle time / system time
       dbIdleTime = dbIdleTime / dbSystemTime;

       // usage % = 100 - current cpu idle * 100 / number of processors
       dbIdleTime = 100 - dbIdleTime*100 / SysBaseInfo.bKeNumberProcessors;
       x = dbIdleTime;

    }
    // store new cpu's idle and system time
    liOldIdleTime = SysPerfInfo.liIdleTime;
    liOldSystemTime = SysTimeInfo.liKeSystemTime;
    return x;
}

 

cpu_sample.c 

#include "cpu.h"

int main()
{
    CPURateInit();
    while(!kbhit()) {
       printf("\b\b\b\b\b\b\b\b%5.2lf %%", GetCPURate());
       Sleep(1000); // 每秒更新一次
    }
    return 0;
}

 

此部份便可利用 cpu.h 提供之 CPURateInit、GetCPURate,進行動態性之調整,若得到之 CPURate 大於 50%,則 Sleep 久一點;若取得之 CPURate 小於 50% ,則 Sleep 少一點 。


 [解法四]  正弦曲線

接著是正弦波問題,較屬於動態調整之方式,且數學較需畫圖理解,這部份若沒一點推導,可能看不大懂程式碼之用意。這裡便給三張圖說明變數與方式。


sin.PNG  

psin.PNG  

看完上述之圖,掌握幾個原則:

1. 假設全幅高度為 INTERVAL,則半幅高度 half = INTERVAL/2
2. COUNT 為樣本點的數目
3. radian 就是目前的 x 座標,而 SPLIT 為 x 座標的間隔,故 loop 裡面求樣本點之 x 值為
   for(i=0; i!=COUNT; ++i) radian += SPLIT;
4. 目前之 y 座標 = half + half*sin( PI*radian )
5. y 座標即為 busytime, 而 idletime = INVERVAL - busytime

掌握上述原則、考慮多核問題後,程式碼大致如下所示 (vc 使用者記得別用 release mode, 要用 debug mode)

#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>

#define COUNT 200

const double SPLIT = 0.01;
const double PI = 3.14159265;
const int INTERVAL = 300;

DWORD WINAPI Sin(LPVOID lParam)
{
    DWORD startTime=0;
    DWORD busySpan[COUNT];
    DWORD idleSpan[COUNT];
    int i=0, j=0, half = INTERVAL / 2;
    double radian = 0.0;
  
    // 計算 COUNT 個 busy, idle time
    for(i=0; i!=COUNT; ++i){
       busySpan[i] = (DWORD) (half + sin(PI*radian)*half);
       idleSpan[i] = INTERVAL - busySpan[i];
       radian += SPLIT;
    }

    // 進行 busy / idle 調整
    while(1){
       j=j%COUNT;
       startTime = GetTickCount();
       while((GetTickCount() - startTime) <= busySpan[j]);
       Sleep(idleSpan[j]);
       ++j;
    }
    return 0;
}

int main()
{
    DWORD dwThreadId;
    HANDLE hThread;
    CreateThread(NULL, 0, Sin, 0, CREATE_SUSPENDED, &dwThreadId);
    hThread = SetThreadAffinityMask(hThread, 1);
    ResumeThread(hThread);

    printf("press any key to exit...");
    while(!kbhit());    
    CloseHandle(hThread);
    return 0;
}

[解法四執行結果圖]

sol4.png  

這裡的截圖是截取第1顆 CPU 的圖 (因有將該執行緒設給第一顆 CPU 跑),由於第二顆 CPU 沒有再跑另一執行緒,便沒再截取。


 [解法五 - CreateThread]

這方法在書上沒提到,也不是我提出來的,是由 Jacob Lee 所提出,但我認為這方法效果還不錯,所以附上來當參考。這方法之結果並非指定某一 CPU 使用率維持在 50% ,而是使得「整體 CPU 使用率」維持在 50%。意指:若為單核心,用筆者使用之方法可維持在 50%;若為多核心,用筆者方式可指定某顆 CPU 維持在 50%;若為多核心,但要使整體效能維持在 50%,便可參考此方法。

Jacob Lee:

要維持在 50% 之直線

1. 假設為 n 核心數。
2. 若 n 為偶數,則開 x= n*0.5 之執行緒。
3. 若 n 為奇數(目前沒看過奇核心,如果有的話就這麼做),則開 x = (n-1)*0.5 + 1 之執行緒。
4. 執行緒內容如下

   while(1){
      for(int i=0; i!=x; ++i);
   }

綜合以上之說明,這裡也假定了 0.5 為可調部份,由圖形看不出來整體效能是否維持在 50%,故這裡調用 cpu.h 來達成紀錄之效果,程式碼大致如下

 

#include < windows.h >
#include < process.h >/* _beginthread, _endthread */
#include < stdio.h >
#include "cpu.h"

#define MULT 0.5 // 
#define PRE_SLEEP 2 // 初始待系統穩定時間
#define TIME_ELASPE 1000 // 取樣間隔
#define PT_CNT 60 // 60 個取樣點

/* 多行緒函式 */
void thread(void *x) 
{
    int target = *(int*)x ;
    int i=0;
    while(1) {
       for(i=0; i!=target; ++i) ;
    }
}

/* 取得 cpu 核心數 */
int GetCoreCnt()
{
    SYSTEM_INFO sysInfo = {0};
    GetSystemInfo(&sysInfo);
    return sysInfo.dwNumberOfProcessors;
}

/* log to file */
#define LOG(fp, num){fprintf(fp,"%d\n", num);}

int main()
{
    int N=0;
    int i=0;
    int core_cnt = GetCoreCnt();
    FILE *fp=fopen("log.txt", "w");

    printf("cpu core cnt: %d\n", core_cnt);
    CPURateInit();

    if(core_cnt==1) printf("can't test!!\n");
    else if(core_cnt& 0x01) N = (int) ((core_cnt-1) * MULT)+1;/* 奇核心 */
    else  N = (int)(core_cnt *  MULT); /* 偶核心 */

    for(i=0; i!=N; ++i) { _beginthread(thread, 0, (void*)(&N));}
    Sleep(PRE_SLEEP);
    for(i=0; i!=PT_CNT; ++i){
       LOG(fp, (int)GetCPURate());
       Sleep(TIME_ELASPE); // 取樣間隔 
    }
    fclose(fp);    
    printf("press enter to end..");
    getchar();
    return 0;
}

 將紀錄之結果繪出來後如下所示

 

sol5-2.png  


但這方式將有個缺點,若雙核心欲設在 75%,則 N = (int)(2* 0.75) = (int)(1.5) = 1,
實際上就只有開一個 thread 出來,這樣事實上是達到  50% 之效果,而非 75% 之效果。
故可控制之 rate 很粗略,但不可否認,這是解決原始問題之最方便之方法!

 [未完待續...]

解法已探討完畢,接下來的延伸問題也值得讓人研究,接下來的部份,

請參閱這篇

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()