排列算法

留下评论

#include <iostream>
using namespace std;

#define N 5
#define M 2
int data[] = {1, 2, 3, 4, 5};
int len = N;
int count = 0;

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void permutation(int* arr, int n, int m)
{
    int i;
    if (m == 0)
    {
        ++count;
        for (i = 0; i < M; ++i)
        {
            cout << data[i] << " ";
        }
        cout << endl;
        return;
    }
    for (i = 0; i < n; ++i)
    {
        swap(arr[i], arr[0]);
        permutation(arr + 1, n – 1, m – 1);
        swap(arr[i], arr[0]);
    }
}

Advertisements

组合算法

留下评论

#include <iostream>
using namespace std;

#define LEN 100

int solv[LEN] = {0};
int count = 0;

void comb2( int n,int r, int current)
{
    if (r == 0)
    {
        ++count;
        for (int i = 1; i <= 10; ++i)
        {
            cout << solv[i] << " ";
        }
        cout << endl;
    }
    else
    {
        for ( int j = n; j >= 1; –j)
        {
            solv[current] = j;
            comb2( j-1, r-1, current + 1);
        }
    }
}

重温”找零钱”程序

留下评论

// PP1.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#define LEN 5

void fun(int &sum, int factors[], int solv[], int n)

{

if (sum == 0)

{

for (int j = 0; j < LEN; ++j)

{

std::cout << solv[j] << " ";

}

std::cout << std::endl;

return;

}

if (n < 0)

{

return;

}

if (sum < factors[n])

{

fun(sum, factors, solv, –n);

}

else

{

int k = sum / factors[n];

for (int i = k; i >= 0; –i)

{

solv[n] = i;

int temp = (sum – (solv[n] * factors[n]));

fun(temp, factors, solv, n – 1);

sum = temp + solv[n] * factors[n];

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int f[LEN] = {5, 6, 7, 8, 9};

int s[LEN] = {0};

int sum = 8;

fun(sum, f, s, 4);

return 0;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

下面是改进版,尾递归

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


#include <iostream>
using namespace std;

#define LEN 5

int index[LEN] = {0};

void GetChange(int sum, int cents[], int index[], int current)
{
    if (sum == 0)
    {
        for (int i = 0; i < LEN; ++i)
        {
            cout << index[i] << " ";
        }
        cout << endl;
        return;
    }
    if (current < 0)
    {
        return;
    }
    if (sum < cents[current])
    {
        GetChange(sum, cents, index, current – 1);
    }
    else
    {
        int k = sum / cents[current];
        for (int i = k; i >= 0; –i)
        {
            index[current] = i;
            int temp = sum – cents[current] * i;
            GetChange(temp, cents, index, current – 1);
        }
    }
}

int main()
{
    int cents[LEN] = {1, 2, 5, 10, 20};
    int sum = 15;
    GetChange(sum, cents, index, LEN – 1);
    return 0;
}

中断与异常的区别

留下评论

中断是一个异步事件(但是在同一时刻只能触发一个中断),它与处理器当前正在执行的内容无关;
中断大部分是由I/O设备,系统时钟以及计时器等触发;
中断可以被启用或者关闭。

异常是由特定指令的执行所触发的同步事件。并且他们一般都是可重现的,如果输入以及执行
环境不变的话。

一些常见system trap的处理
 

Hal.dll小常识

留下评论

为了适应不同的计算机硬件架构,Windows安装程序包括了多个Hal.dll文件,但是,在系统安装过程中,只会有一个
版本的Hal.dll被拷贝到本地磁盘中。

HAL File Name Systems Supported
Hal.dll Standard PCs
Halacpi.dll Advanced Configuration and Power Interface(ACPI) PCs
Halapic.dll Advanced Programmable Interrupt Controller (APIC) PCs
Halaacpi.dll APIC ACPI PCs
Halmps.dll Multiprocessor PCs
Halmacpi.dll Multiprocessor ACPI PCs
Halborg.dll Sillicon Graphics Workstation (Windows 2000 only; platform no longer marketed)
Halsp.dll Compaq SystemPro(Windows XP only)

Windows 核心DLL列举

留下评论

Ntoskrnl.exe : Executive and kernel
Ntkrnlpa.exe(32-bit only) : Executive and kernel with support for Physical Address Extension(PAE),
                                          which allows addressing of up to 64 GB of physical memory
Hal.dll : Hardware abstraction layer

Win32k.sys : Kernel-mode part of the Windows subsystem
Ntdll.dll : Internal support functions and system service dispatch stubs to executive functions
Kernel32.dll, Advapi32.dll, User32.dll, Gdi32.dll : Core Windows subsystem DLLs

Ntdll.dll并不在内核模态运行,而是在用户模态下运行。它负责处理应用程序向操作系统内核态服务请求响应,
并把控制权转向内核态执行。另外,对于一些不需要转向内核态的请求,它也可以直接处理掉了,从而避免
模态切换的开销。

Windows子系统

  1. csrss.exe: Client/Server Run-time Subsystem,是Windows子系统的进程名。它提供如下支持:
  • 命令行模式
  • 线程/进程创建与删除
  • 16-位虚拟DOS进程
  • 其它一些零散的函数,例如GetTempFile,DefineDosDevice,ExitWindowEx和几个自然语言支持功能集。
  1. 内核态设备驱动(Win32k.sys)支持:
  • 窗口管理器,包括窗口显示,屏幕输出,收集键盘,鼠标等输入设备的信号以及在应用程序间传递消息
  • 图形设备接口(GDI),提供图形输出设备的功能集,包括绘制线条,文字,图像以及图形编辑操作等
  1. 子系统DLL(常见的Kernel32.dll, Advapi32.dll, User32.dll, Gdi32.dll)也就是常说的Windows API
  1. 图形设备驱动包括硬件依赖的图形显示驱动,打印机驱动和视频驱动。

理解图像和视频驱动架构:阅读Windows DDK中 Design Guide – Graphics Drivers

csrss.exe运行于内核态,这样有利于提升系统性能。但是具体原因还不清楚。
有人认为把窗口管理器和GDI移到内核态下运行不利于Windows的抢占式多任务能力。
他们认为如果这些进程如果运行在内核态的话,其它的线程将获得更少的机会去抢占
CPU。这种观点建立在对Windows架构不理解的基础之上。诚然,在许多其他名义上
抢占式调度的操作系统中,内核态的CPU占用不能被操作系统的调度程序来抢占,或者
只能在内核可重入的某几个限制点上。然后在Windows中,不管线程运行于何种态,它们
都一样必须接受抢占与调度。这种设计有利于提升系统性能如果运行于SMP硬件之上。

Windows九大精通门类

留下评论

1》WinDbg (digging into OS internal)
2》Registry (OS database)
3》Security
4》Object and Handle
5》Terminal Services and Multiple Sessions
6》Performance Counter(Kernel mode vs. User mode resource consumption)
7》Virtual Memory
8》Process, Threads and Jobs
9》Native system service, Windows API and Kernel support functions

Older Entries