CRC1021 C++ 实现

CRC1021 C++ 实现

CRC算法是在通讯领域广泛采用的校验算法。原理我就不说了，这里说一下简单的程序实现。以下均采用CRC多项式为0x1021即：

g(x) = x16+x12+x5+x0;CRC的基本原理就不说了，那个搜一下就有了。

最基本的算法应该是按位计算了，这个方法可以适用于所有长度的数据校验，最为灵活，但由于是按位计算，其效率并不是最优，只适用于对速度不敏感的场合。基本的算法如下：

unsigned short do_crc_16(unsigned char *message, unsigned int len)

{

int i, j;

unsigned short crc_reg = 0;

unsigned short current;

for (i = 0; i < len; i++)

{

current = message[i] << 8;

for (j = 0; j < 8; j++)

{

if ((short)(crc_reg ^ current) < 0)

crc_reg = (crc_reg << 1) ^ 0x1021;

else

crc_reg <<= 1;

current <<= 1;

}

}

return crc_reg;

}

以是方法可以计算出任意长度数据的校验。但速度慢。下面介绍一种按字节计算的方法：按字节校验是每次计算8位数据，多是基于查表的算法，首先要准备一个表，一共256项。unsigned int crc_ta[256]={ /* CRC余式表*/

0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,

0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,

0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,

0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,

0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,

0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,

0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,

0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,

0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,

0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,

0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,

0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,

0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,

0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,

0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,

0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,

0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,

0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,

0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,

0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,

0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,

0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,

0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,

0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,

0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,

0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,

0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,

0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,

0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,

0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,

0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,

0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0

};

unsigned short do_crc_table(unsigned char *ptr,int len)

{

unsigned short int crc;

unsigned char da;

crc=0;

while(len--!=0)

{

da=(unsigned short)crc>>8; /* 以8位二进制数的形式暂存CRC的高8位*/

crc<<=8; /* 左移8位，相当于CRC的低8位乘以*/

crc^=crc_ta[da^*ptr]; /* 高8位和当前字节相加后再查表求CRC ，再加上以前的CRC */

ptr++;

}

return(crc);

}

以上算法实现了按字节进行计算校验值。在使用的时候，把计算出来的校验值放在最后两个字节里，将其发送出去，接收端对所有的数据进行相同的校验，如校验值为0我们则认为其数据没有出错。这个是按高位到低位的发送顺序时使用的校验方法。

在实际应用中，还有一种按低位到高位的发送方法，这样，就要进行反相的校验，但如果把数据反相，显然加大计算量，故可以使用相应的查表算法来进行计算。只是计算方法与表不太一样，其实现算法如下：

unsigned short crc16_ccitt_table[256] =

{

0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,

0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7, 0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e, 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876, 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd, 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5, 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c, 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974, 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb, 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3, 0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a, 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72, 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9, 0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1, 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738, 0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70, 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7, 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff, 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036, 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e, 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5, 0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd, 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134, 0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c, 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3, 0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb, 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232, 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a, 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1, 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9, 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330, 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78, };

unsigned short do_crc_table_1(unsigned char *pData,int nLength) {

unsigned short fcs = 0xffff; // 初始化

while(nLength>0)

{

fcs = (fcs >> 8) ^ crc16_ccitt_table[(fcs ^ *pData) & 0xff];

nLength--;

pData++;

}

return ~fcs; // 取反

}

检验的时候，只要用以下方法就可以

int IsCrc16Good(unsigned char* pData, int nLength)

{

unsigned short fcs = 0xffff; // 初始化

while(nLength>0)

{

fcs = (fcs >> 8) ^ crc16_ccitt_table[(fcs ^ *pData) & 0xff];

nLength--;

pData++;

}

// return (); // 0xf0b8是CRC-ITU的"Magic V alue"

if(fcs == 0xf0b8)

return 1;

else

return -1;

}

返回1则数据无误，否则数据错误。

其表的生成方法也比较简单，对于前一种查表方法，其生成表的算法可以由按位生成算法来计算得到，对0～255的字节进行CRC校验，得到的校验值分别做为表的相应项。

对于后一种查表方法，其码表可以由以下方法计算得到，

void crc16_ccitt()

{

unsigned char index = 0;

unsigned short to_xor;

int i;

printf("unsigned short crc16_ccitt_table[256] =\n{");

while (1)

{

if (!(index % 8))

printf("\n");

to_xor = index;

for (i = 0; i < 8; i++)

{

if (to_xor & 0x0001)

to_xor = (to_xor >>1) ^ 0x8408;

else

to_xor >>= 1;

}

printf("0x%04x", to_xor);

if (index == 255)

{

printf("\n");

break;

}

else

{

printf(", ");

index++;

}

}

printf("};");

//return 0;

}

这样，对CRC算法算是有一个新的认识了，至少是分清了对于同一个多项式，为什么会有不同的计算方法。弄清后，就会明白在什么场合用什么样的算法。

快速傅里叶变换(FFT)原理及源程序

创作编号： GB8878185555334563BT9125XW 创作者： 凤呜大王* 《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。全部计算分解为M 级，其中N M 2log =；在输入序列()i x 中是按码位倒序排列的，输出序列()k X 是按顺序排列；每级包含 2N 个蝶形单元，第i 级有i N 2 个群，每个群有12-i 个蝶形单元； 每个蝶形单元都包含乘r N W 和r N W -系数 的运算，每个蝶形单元数据的间隔为12-i ，i 为第i 级； 同一级中各个群的系数W 分布规律完全相同。 将输入序列()i x 按码位倒序排列时，用到的是倒序算法——雷德算法。 自然序排列的二进制数，其下面一个数总比上面的数大1，而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。 若已知某数的倒序数是J ，求下一个倒序数，应先判断J 的最高位是 否为0，与2 N k =进行比较即可得到结果。如果J k >，说明最高位为0， 应把其变成1，即2 N J +，这样就得到倒序数了。如果J k ≤，即J 的最高 位为1，将最高位化为0，即2N J -，再判断次高位；与4N k =进行比较， 若为0，将其变位1，即4 N J +，即得到倒序数，如果次高位为1，将其化 为0，再判断下一位……即从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。

注：因为0的倒序数为0，所以可从1开始进行求解。 二、程序设计框图 （1）倒序算法——雷德算法流程图 (2)FFT算法流程

JAVA线程池原理333

在什么情况下使用线程池？ 1.单个任务处理的时间比较短 2.将需处理的任务的数量大 使用线程池的好处: 1.减少在创建和销毁线程上所花的时间以及系统资源的开销 2.如不使用线程池，有可能造成系统创建大量线程而导致消耗完系统内存以及”过度切换”。 线程池工作原理：

线程池为线程生命周期开销问题和资源不足问题提供了解决方案。通过对多个任务重用线程，线程创建的开销被分摊到了多个任务上。其好处是，因为在请求到达时线程已经存在，所以无意中也消除了线程创建所带来的延迟。这样，就可以立即为请求服务，使应用程序响应更快。而且，通过适当地调整线程池中的线程数目，也就是当请求的数目超过某个阈值时，就强制其它任何新到的请求一直等待，直到获得一个线程来处理为止，从而可以防止资源不足。 线程池的替代方案 线程池远不是服务器应用程序内使用多线程的唯一方法。如同上面所提到的，有时，为每个新任务生成一个新线程是十分明智的。然而，如果任务创建过于频繁而任务的平均处理时间过短，那么为每个任务生成一个新线程将会导致性能问题。 另一个常见的线程模型是为某一类型的任务分配一个后台线程与任务队列。AWT 和 Swing 就使用这个模型，在这个模型中有一个 GUI 事件线程，导致用户界面发生变化的所有工作都必须在该线程中执行。然而，由于只有一个 AWT 线程，因此要在 AWT 线程中执行任务可能要花费相当长时间才能完成，这是不可取的。因此，Swing 应用程序经常需要额外的工作线程，用于运行时间很长的、同 UI 有关的任务。 每个任务对应一个线程方法和单个后台线程（single-background-thread）方法在某些情形下都工作得非常理想。每个任务一个线程方法在只有少量运行时间很长的任务时工作得十分好。而只要调度可预见性不是很重要，则单个后台线程方法就工作得十分好，如低优先级后台任务就是这种情况。然而，大多数服务器应用程序都是面向处理大量的短期任务或子任务，因此往往希望具有一种能够以低开销有效地处理这些任务的机制以及一些资源管理和定时可预见性的措施。线程池提供了这些优点。 工作队列 就线程池的实际实现方式而言，术语“线程池”有些使人误解，因为线程池“明显的”实现在大多数情形下并不一定产生我们希望的结果。术语“线程池”先于Java 平台出现，因此它可能是较少面向对象方法的产物。然而，该术语仍继续广泛应用着。 虽然我们可以轻易地实现一个线程池类，其中客户机类等待一个可用线程、将任务传递给该线程以便执行、然后在任务完成时将线程归还给池，但这种方法却存在几个潜在的负面影响。例如在池为空时，会发生什么呢？试图向池线程传递任务的调用者都会发现池为空，在调用者等待一个可用的池线程时，它的线程将阻塞。我们之所以要使用后台线程的原因之一常常是为了防止正在提交的线程被阻塞。完全堵住调用者，如在线程池的“明显的”实现的情况，可以杜绝我们试图解决的问题的发生。 我们通常想要的是同一组固定的工作线程相结合的工作队列，它使用 wait() 和

FFT相关原理及使用注意事项

FFT相关原理及使用注意事项 在信号分析与处理中，频谱分析是重要的工具。FFT（Fast Fourier Transform，快速傅立叶变换）可以将时域信号转换至频域，以获得信号的频率结构、幅度、相位等信息。该算法在理工科课程中都有介绍，众多的仪器或软件亦集成此功能。FFT实用且高效，相关原理与使用注意事项也值得好好学习。 一、何为FFT 对于模拟信号的频谱分析，首先得使用ADC（模拟数字转换器）进行采样，转换为有限序列，其非零值长度为N，经DFT（离散傅立叶变换）即可转化为频域。DFT变换式为： 在上式中，N点序列的DFT需要进行N2次复数乘法和次复数加法，运算量大。 FFT是DFT的快速算法，利用DFT运算中的对称性与周期性，将长序列DFT分解为短序列DFT 之和。最终运算量明显减少，使得FFT应用更加广泛。 FFT基于一个基本理论：任何连续的波形，都可以分解为不同频率的正弦波形的叠加。FFT将采样得到的原始信号，转化此信号所包含的正弦波信号的频率、幅度、相位，为信号分析提供一个创新视觉。 例如在日常生活中有使用到的AM（Amplitude Modulation，幅度调制）广播，其原理是将人的声音（频率约20Hz至20kHz，称为调制波）调制到500kHz～1500kHz正弦波上（称为载波）中，载波的幅度随调制波的幅度变化。声音经这样调制后，可以传播得更远。在AM的时域波形（波形电压随时间的变化曲线），载波与调制波特征不易体现，而在FFT后的幅频曲线中则一目了然。如下图为1000kHz载波、10kHz调制波的AM调制信号，时域信号经FFT后其频率能量出现在990kHz、1.01MHz频率处，符合理论计算。 图 1 调制波10kHz、载波1000kHz的AM时域与频域曲线 二、FFT相关知识 现实生活中的模拟信号，大多都是连续复杂的，其频谱分量十分丰富。正如在数学中常量π，其真实值是个无理数。当用3.14来替代π时，计算值与真实值就会有偏差。在使用FFT这个工具时，受限于采样时的频率Fs、采样点长度N、ADC的分辨率n bit等因素的制约，所得到的信息会有所缺失与混淆。 1.奈奎斯特区与波形混叠 FFT分析结果中，存在一个那奈奎斯特区的概念，其宽度为采样率的一半Fs/2，信号频

线程池的原理与实现详解

线程池的原理与实现详解 https://www.sodocs.net/doc/1615107278.html,/article/41375.htm2013下面利用C 语言来实现一个简单的线程池，为了使得这个线程池库使用起来更加方便，特在C实现中加入了一些OO的思想，与Objective-C不同，它仅仅是使用了struct来模拟了c++中的类，其实这种方式在linux内核中大量可见 一. 线程池的简介 通常我们使用多线程的方式是，需要时创建一个新的线程，在这个线程里执行特定的任务，然后在任务完成后退出。这在一般的应用里已经能够满足我们应用的需求，毕竟我们并不是什么时候都需要创建大量的线程，并在它们执行一个简单的任务后销毁。 但是在一些web、email、database等应用里，比如彩铃，我们的应用在任何时候都要准备应对数目巨大的连接请求，同时，这些请求所要完成的任务却又可能非常的简单，即只占用很少的处理时间。这时，我们的应用有可能处于不停的创建线程并销毁线程的状态。虽说比起进程的创建，线程的创建时间已经大大缩短，但是如果需要频繁的创建线程，并且每个线程所占用的处理时间又非常简短，则线程创建和销毁带给处理器的额外负担也是很可观的。 线程池的作用正是在这种情况下有效的降低频繁创建销毁

线程所带来的额外开销。一般来说，线程池都是采用预创建的技术，在应用启动之初便预先创建一定数目的线程。应用在运行的过程中，需要时可以从这些线程所组成的线程池里申请分配一个空闲的线程，来执行一定的任务，任务完成后，并不是将线程销毁，而是将它返还给线程池，由线程池自行管理。如果线程池中预先分配的线程已经全部分配完毕，但此时又有新的任务请求，则线程池会动态的创建新的线程去适应这个请求。当然，有可能，某些时段应用并不需要执行很多的任务，导致了线程池中的线程大多处于空闲的状态，为了节省系统资源，线程池就需要动态的销毁其中的一部分空闲线程。因此，线程池都需要一个管理者，按照一定的要求去动态的维护其中线程的数目。 基于上面的技术，线程池将频繁创建和销毁线程所带来的开销分摊到了每个具体执行的任务上，执行的次数越多，则分摊到每个任务上的开销就越小。 当然，如果线程创建销毁所带来的开销与线程执行任务的开销相比微不足道，可以忽略不计，则线程池并没有使用的必要。比如，FTP、Telnet等应用时。 二. 线程池的设计 下面利用C语言来实现一个简单的线程池，为了使得这个线程池库使用起来更加方便，特在C实现中加入了一些OO的思想，与Objective-C不同，它仅仅是使用了struct来模拟

实验八 快速傅立叶变换(FFT)实验

实验七 快速傅立叶变换（FFT ）实验 一 实验目的 1． 熟悉CCS 集成开发环境； 2． 了解FFT 的算法原理和基本性质； 3． 熟悉DSP 中cmd 文件的作用及对它的修改； 4． 学习用FFT 对连续信号和时域信号进行频谱分析的方法； 5． 利用DSPLIB 中现有的库函数； 6． 了解DSP 处理FFT 算法的特殊寻址方式； 7． 熟悉对FFT 的调试方法。 二 实验内容 本实验要求使用FFT 变换对一个时域信号进行频谱分析，同时进行IFFT 。这里用到时域信号可以是来源于信号发生器输入到CODEC 输入端，也可以是通过其他工具计算获取的数据表。本实验使用Matlab 语言实现对FFT 算法的仿真，然后将结果和DSP 分析的结果进行比较，其中原始数据也直接来自Matlab 。 三 实验原理 一个N 点序列][k x 的DFT ][m X ,以及IDFT 分别定义为： 1,,1,0,][][1 0-==∑-=N m W k x m X km N N k 1,,1,0,][1 ][1 -== --=∑ N k W m X N k x km N N m 如果利用上式直接计算DFT,对于每一个固定的m,需要计算N 次复数乘法，N-1次加法,对于N 个不同的m,共需计算N 的2次方复数乘法,N*(N-1)次复数加法.显然,随着N 的增加,运算量将急剧增加, 快速傅里叶算法有效提高计算速度（本例使用基2 FFT 快速算法）,利用FFT 算法只需(N/2)logN 次运算。 四 知识要点 . 1、 CMD 文件的功能及编写 2、 一种特殊的寻址方式：间接寻址 间接寻址是按照存放在某个辅助寄存器的16位地址寻址的。C54x 的8个辅助寄存器 （AR0—AR7）都可以用来寻址64K 字数据存储空间中的任何一个存储单元。 3、 TMS320C54x DSPLIB 中关于FFT 变换的一些函数的调用（SPRA480B.pdf ） 利用DSPLIB 库时，在主程序中要包含头文件：54xdsp.lib 4、 FFT 在CCS 集成开发环境下的相关头文件 #include //定义数据类型的头文件 #include //数学函数的头文件，如sqrt. #include //定义数据类型的头文件 #include // DSPLIB 库文件

操作系统精髓与设计原理课后答案

操作系统精髓与设计原理课后答案 第1章计算机系统概述 1.1列出并简要地定义计算机的四个主要组成部分。 主存储器，存储数据和程序；算术逻辑单元，能处理二进制数据；控制单元，解读存储器中的指令并且使他们得到执行；输入/输出设备，由控制单元管理。 1.2定义处理器寄存器的两种主要类别。 用户可见寄存器：优先使用这些寄存器，可以使机器语言或者汇编语言的程序员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪些变量应该分配给主存储器。一些高级语言，如C语言，允许程序言建议编译器把哪些变量保存在寄存器中。 控制和状态寄存器：用以控制处理器的操作，且主要被具有特权的操作系统例程使用，以控制程序的执行。 1.3一般而言，一条机器指令能指定的四种不同操作是什么？ 处理器－寄存器：数据可以从处理器传送到存储器，或者从存储器传送到处理器。 处理器－I/O：通过处理器和I/O模块间的数据传送，数据可以输出到外部设备，或者从外部设备输入数据。 数据处理：处理器可以执行很多关于数据的算术操作或逻辑操作。 控制：某些指令可以改变执行顺序。 1.4什么是中断？ 中断：其他模块（I/O，存储器）中断处理器正常处理过程的机制。 1.5多中断的处理方式是什么？ 处理多中断有两种方法。第一种方法是当正在处理一个中断时，禁止再发生中断。第二种方法是定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行。 1.6内存层次的各个元素间的特征是什么？ 存储器的三个重要特性是：价格，容量和访问时间。 1.7什么是高速缓冲存储器？ 高速缓冲存储器是比主存小而快的存储器，用以协调主存跟处理器，作为最近储存地址的缓冲区。1.8列出并简要地定义I/O操作的三种技术。 可编程I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令（用以执行这个指令）；在进一步的动作之前，处理器处于繁忙的等待中，直到该操作已经完成。 中断驱动I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令，并继续执行后续指令，直到后者完成，它将被I/O模块中断。如果它对于进程等待I/O的完成来说是不必要的，可能是由于后续指令处于相同的进程中。否则，此进程在中断之前将被挂起，其他工作将被执行。 直接存储访问：DMA模块控制主存与I/O模块间的数据交换。处理器向DMA模块发送一个传送数据块的请求，（处理器）只有当整个数据块传送完毕后才会被中断。 1.9空间局部性和临时局部性间的区别是什么？ 空间局部性是指最近被访问的元素的周围的元素在不久的将来可能会被访问。临时局部性（即时间局部性）是指最近被访问的元素在不久的将来可能会被再次访问。 1.10开发空间局部性和时间局部性的策略是什么？ 空间局部性的开发是利用更大的缓冲块并且在存储器控制逻辑中加入预处理机制。时间局部性的开发是利用在高速缓冲存储器中保留最近使用的指令及数据，并且定义缓冲存储的优先级。 第2章操作系统概述

java深入理解线程池

深入研究线程池 一.什么是线程池? 线程池就是以一个或多个线程[循环执行]多个应用逻辑的线程集合. 注意这里用了线程集合的概念是我生造的,目的是为了区分执行一批应用逻辑的多个线程和 线程组的区别.关于线程组的概念请参阅基础部分. 一般而言,线程池有以下几个部分: 1.完成主要任务的一个或多个线程. 2.用于调度管理的管理线程. 3.要求执行的任务队列. 那么如果一个线程循环执行一段代码是否是线程池? 如果极端而言,应该算,但实际上循环代码应该算上一个逻辑单元.我们说最最弱化的线程池 应该是循环执行多个逻辑单元.也就是有一批要执行的任务,这些任务被独立为多个不同的执行单元.比如: int x = 0; while(true){ x ++; } 这就不能说循环中执行多个逻辑单元,因为它只是简单地对循环外部的初始变量执行++操作. 而如果已经有一个队列 ArrayList al = new ArrayList(); for(int i=0;i<10000;i++){ al.add(new AClass()); } 然后在一个线程中执行: while(al.size() != 0){ AClass a = (AClass)al.remove(0); a.businessMethod(); } 我们说这个线程就是循环执行多个逻辑单元.可以说这个线程是弱化的线程池.我们习惯上把这些相对独立的逻辑单元称为任务. 二.为什么要创建线程池? 线程池属于对象池.所有对象池都具有一个非常重要的共性,就是为了最大程度复用对象.那么 线程池的最重要的特征也就是最大程度利用线程. 从编程模型模型上说讲,在处理多任务时,每个任务一个线程是非常好的模型.如果确实可以这么做我们将可以使用编程模型更清楚,更优化.但是在实际应用中,每个任务一个线程会使用系统限入"过度切换"和"过度开销"的泥潭. 打个比方,如果可能,生活中每个人一辆房车,上面有休息,娱乐,餐饮等生活措施.而且道路交道永远不堵车,那是多么美好的梦中王国啊.可是残酷的现实告诉我们,那是不可能的.不仅每个人一辆车需要无数多的社会资源,而且地球上所能容纳的车辆总数是有限制的. 首先,创建线程本身需要额外(相对于执行任务而必须的资源)的开销.

fft_原理详解

FFT算法 FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。虽然很多人都知道FFT是什么，可以用来做什么，怎么去做，但是却不知道FFT之后的结果是什意思、如何决定要使用多少点来做FFT。现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，这些我就不在此罗嗦了。 采样得到的数字信号，就可以做FFT变换了。N个采样点，经过FFT之后，就可以得到N个点的FFT结果。为了方便进行FFT运算，通常N取2的整数次方。 假设采样频率为Fs，信号频率F，采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢假设原始信号的峰值为A，那么FFT的结果的每个点（除了第一个点直流分量之外）的模值就是A的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个点表示直流分量（即0Hz），而最后一个点N的再下一个点（实际上这个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示采样频率Fs，这中间被N-1个点平均分成N等份，每个点的频率依次增加。例如某点n所表示的频率为：Fn=(n-1)*Fs/N。由上面的公式可以看出，Fn所能分辨到频率为为Fs/N，如果采样频率Fs为1024Hz，采样点数为1024点，则可以分辨到1Hz。1024Hz的采样率采样1024点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT，则结果可以分析到1Hz，如果采样2秒时间的信号并做FFT，则结果可以分析到。如果要提高频率分辨力，则必须增加采样点数，也即采样时间。频率分辨率和采样时间是倒数关系。 假设FFT之后某点n用复数a+bi表示，那么这个复数的模就是An=根号a*a+b*b，相位就是Pn=atan2(b,a)。根据以上的结果，就可以计算出n点（n≠1，且n<=N/2）对应的信号的表达式为：An/(N/2)*cos(2*pi*Fn*t+Pn)，即2*An/N*cos(2*pi*Fn*t+Pn)。对于n=1点的信号，是直流分量，幅度即为A1/N。由于FFT结果的对称性，通常我们只使用前半部分的结果，即小于采样频率一半的结果。好了，说了半天，看着公式也晕，下面圈圈以一个实际的信号来做说明。 假设我们有一个信号，它含有2V的直流分量，频率为50Hz、相位为-30度、幅度为3V的交流信号，以及一个频率为75Hz、相位为90度、幅度为的交流信号。用数学表达式就是如下： S=2+3*cos(2*pi*50*t-pi*30/180)+*cos(2*pi*75*t+pi*90/180) 式中cos参数为弧度，所以-30度和90度要分别换算成弧度。 我们以256Hz的采样率对这个信号进行采样，总共采样256点。按照我们上面的分析，Fn=(n-1)*Fs/N，我们可以知道，每

普元EOS工作流引擎设计原理

EOS工作流引擎工作原理 作者：Gocom注册用户dogreet（李国生） 1. 工作流基础知识 ……略 2. EOS工作流引擎工作原理 本文是我在工作之余写的一点我对EOS工作流的了解，我的理解不一定全是对的，可能会与引擎的真正的面目有出入。所以只能提供给大家一点参考。 2.1. EOS工作流引擎核心调度算法 EOS工作流最重要的组成部分是它的核心调度算法，在我们没有深入研究它的工作原理之前我们认为它的工作原理是在工作项，活动和流程实例对象上加了一些标志位来驱动流程的运转。认为其引擎完全是个由数据库来驱动流程的引擎（安徽二期的工作流平台好象就是以库表来驱动流程的运转），其实它是由事件来驱动流程运转的引擎，数据库只是把引擎运转前后的状态持久化。在我近来在工作之余对其引擎的工作原理进行跟踪才弄明白在EOS帮助文档上介绍的“事件驱动”的工作流引擎。 2.1.1. EOS工作流引擎的事件类型

以上的每个事件都是原子的不可分割的。其中一系列事件的集合通过EOS引擎事件调度机制实现我们平时在工作中经常遇到的如启动流程，结束工作项等等。（在事件类型类中EOS定义了29种事件，但在事件工厂类中EOS定义了26种类型。） 1.1.1. EOS工作流事件调度机制 EOS事件的调度服务是在工作流引擎初始化时通过服务工厂类加载到内存中（ServiceFactory.initEventService()）。用户可以通过服务工厂类（ServiceFactory）取得JVM的唯一事件服务实例进行事务调度。所有的事件程序入口都是事件类（EventService），这个类其实是个接口，其有两个实现类，一个是单线程的实现类SingleThreadEventService （在实现代码中其实不是单线程，而是单例的对象），一个是多线程的实现类MulThreadThreadSvc，（其实现方式不在这里详细说明，多线程的类后面又跟了一大堆的线程池实现代码），在事件服务类中有一个属性类是WFEventDisposer，这个类包含了事

快速傅里叶变换(FFT)原理及源程序

《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。全部计算分解为M 级，其中N M 2log =；在输入序列()i x 中是按码位倒序排列的，输出序列()k X 是按顺序排列；每级包含2N 个蝶形单元，第i 级有i N 2 个群，每个群有12-i 个蝶形单元； 每个蝶形单元都包含乘r N W 和r N W -系数的运算，每个蝶形 单元数据的间隔为12-i ，i 为第i 级； 同一级中各个群的系数W 分布规律完全相同。 将输入序列()i x 按码位倒序排列时，用到的是倒序算法——雷德算法。 自然序排列的二进制数，其下面一个数总比上面的数大1，而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。 若已知某数的倒序数是J ，求下一个倒序数，应先判断J 的最高位是否为0，与2 N k =进行比较即可得到结果。如果J k >，说明最高位为0，应把其变成1，即2 N J +，这样就得到倒序数了。如果J k ≤，即J 的最高位为1，将最高位化为0，即2N J -，再判断次高位；与4N k =进行比较，若为0，将其变位1，即4 N J +，即得到倒序数，如果次高位为1，将其化为0，再判断下一位……即从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。 注：因为0的倒序数为0，所以可从1开始进行求解。 二、程序设计框图 （1）倒序算法——雷德算法流程图

(2)FFT算法流程

FFT原理与实现

FFT原理与实现 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)一组N点组成的频率成分的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度只实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N截至的N个频率点的相对幅度。 N点DFT的计算量 根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子WN的特性 1. W的对称性 N W的周期性 2. N W的可约性 3. N

Tomcat线程池实现简介

Tomcat线程池实现简介 目前市场上常用的开源Java Web容器有Tomcat、Resin和Jetty。其中Resin从V3.0后需要购买才能用于商业目的，而其他两种则是纯开源的。可以分别从他们的网站上下载最新的二进制包和源代码。 作为Web容器，需要承受较高的访问量，能够同时响应不同用户的请求，能够在恶劣环境下保持较高的稳定性和健壮性。在HTTP服务器领域，Apache HTTPD的效率是最高的，也是最为稳定的，但它只能处理静态页面的请求，如果需要支持动态页面请求，则必须安装相应的插件，比如mod_perl可以处理Perl脚本，mod_python可以处理Python脚本。 上面介绍的三中Web容器，都是使用Java编写的HTTP服务器，当然他们都可以嵌到Apache 中使用，也可以独立使用。分析它们处理客户请求的方法有助于了解Java多线程和线程池的实现方法，为设计强大的多线程服务器打好基础。 Tomcat是使用最广的Java Web容器，功能强大，可扩展性强。最新版本的Tomcat（5.5.17）为了提高响应速度和效率，使用了Apache Portable Runtime（APR）作为最底层，使用了APR 中包含Socket、缓冲池等多种技术，性能也提高了。APR也是Apache HTTPD的最底层。可想而知，同属于ASF（Apache Software Foundation）中的成员，互补互用的情况还是很多的，虽然使用了不同的开发语言。 Tomcat 的线程池位于tomcat-util.jar文件中，包含了两种线程池方案。方案一：使用APR 的Pool技术，使用了JNI；方案二：使用Java实现的ThreadPool。这里介绍的是第二种。如果想了解APR的Pool技术，可以查看APR的源代码。 ThreadPool默认创建了5个线程，保存在一个200维的线程数组中，创建时就启动了这些线程，当然在没有请求时，它们都处理“等待”状态（其实就是一个while循环，不停的等待notify）。如果有请求时，空闲线程会被唤醒执行用户的请求。 具体的请求过程是：服务启动时，创建一个一维线程数组（maxThread＝200个），并创建空闲线程(minSpareThreads＝5个)随时等待用户请求。当有用户请求时，调用threadpool.runIt(ThreadPoolRunnable)方法，将一个需要执行的实例传给ThreadPool中。其中用户需要执行的实例必须实现ThreadPoolRunnable接口。ThreadPool 首先查找空闲的线程，如果有则用它运行要执行ThreadPoolRunnable；如果没有空闲线程并且没有超过maxThreads，就一次性创建minSpareThreads个空闲线程；如果已经超过了maxThreads了，就等待空闲线程了。总之，要找到空闲的线程，以便用它执行实例。找到后，将该线程从线程数组中移走。接着唤醒已经找到的空闲线程，用它运行执行实例（ThreadPoolRunnable）。运行完ThreadPoolRunnable后，就将该线程重新放到线程数组中，作为空闲线程供后续使用。 由此可以看出，Tomcat的线程池实现是比较简单的，ThreadPool.java也只有840行代码。用一个一维数组保存空闲的线程，每次以一个较小步伐（5个）创建空闲线程并放到线程池中。使用时从数组中移走空闲的线程，用完后，再“归还”给线程池。ThreadPool提供的仅仅是线程池的实现，而如何使用线程池也是有很大学问的。让我们看看Tomcat是如何使用ThreadPool的吧。 Tomcat有两种EndPoint，分别是AprEndpoint和PoolTcpEndpoint。前者自己实现了一套线

快速傅里叶变换原理及其应用(快速入门)

快速傅里叶变换的原理及其应用 摘要 快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换. 虽然傅里叶运算在各方面计算中有着重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。 关键词快速傅氏变换；快速算法；简化；广泛应用

Abstract Fast Fourier Transform (FFT), is a discrete fast Fourier transform algorithm, which is based on the Discrete Fourier Transform of odd and even, false, false, and other characteristics of the Discrete Fourier Transform algorithms improvements obtained. Its Fourier transform theory has not found a new, but in the computer system or the application of digital systems Discrete Fourier Transform can be said to be a big step into. Fourier transform theory and methods in the "mathematical equation" and "linear systems analysis" and "signal processing, simulation," and many other areas have a wide range of applications, as the computer can only handle a limited length of the sequence of discrete, so true On the computer's operation is a discrete Fourier transform. Fourier Although all aspects of computing in the calculation has an important role, but its calculation was too complicated, a lot of computing system for calculating the burden is too large for some Less power consumption, the slow speed of operation of its system at arm's length, however, have the fast Fourier transform, Fourier transform greatly simplifying the making, not in power at the expense of the conditions to increase the speed of computing systems, and enhance the system The comprehensive ability to improve the speed of operation, the Fast Fourier Transform in the production and life have a very important role in learning to master all have great significance. Key words Fast Fourier Transform; fast algorithm; simplified; widely used

线程池原理 C++实现

线程池原理及创建（C++实现） 时间:2010‐02‐25 14:40:43来源:网络 作者:未知 点击:2963次 本文给出了一个通用的线程池框架，该框架将与线程执行相关的任务进行了高层次的抽象，使之与具体的执行任务无关。另外该线程池具有动态伸缩性，它能根据执行任务的轻重自动调整线程池中线程的数量。文章的最后，我们给出一个 本文给出了一个通用的线程池框架，该框架将与线程执行相关的任务进行了高层次的抽象，使之与具体的执行任务无关。另外该线程池具有动态伸缩性，它能根据执行任务的轻重自动调整线程池中线程的数量。文章的最后，我们给出一个简单示例程序，通过该示例程序，我们会发现，通过该线程池框架执行多线程任务是多么的简单。 为什么需要线程池 目前的大多数网络服务器，包括Web服务器、Email服务器以及数据库服务器等都具有一个共同点，就是单位时间内必须处理数目巨大的连接请求，但处理时间却相对较短。 传统多线程方案中我们采用的服务器模型则是一旦接受到请求之后，即创建一个新的线程，由该线程执行任务。任务执行完毕后，线程退出，这就是是“即时创建，即时销毁”的策略。尽管与创建进程相比，创建线程的时间已经大大的缩短，但是如果提交给线程的任务是执行时间较短，而且执行次数极其频繁，那么服务器将处于不停的创建线程，销毁线程的状态。 我们将传统方案中的线程执行过程分为三个过程：T1、T2、T3。 T1：线程创建时间 T2：线程执行时间，包括线程的同步等时间 T3：线程销毁时间

那么我们可以看出，线程本身的开销所占的比例为(T1+T3) / (T1+T2+T3)。如果线程执行的时间很短的话，这比开销可能占到20%‐50%左右。如果任务执行时间很频繁的话，这笔开销将是不可忽略的。 除此之外，线程池能够减少创建的线程个数。通常线程池所允许的并发线程是有上界的，如果同时需要并发的线程数超过上界，那么一部分线程将会等待。而传统方案中，如果同时请求数目为2000，那么最坏情况下，系统可能需要产生2000个线程。尽管这不是一个很大的数目，但是也有部分机器可能达不到这种要求。 因此线程池的出现正是着眼于减少线程池本身带来的开销。线程池采用预创建的技术，在应用程序启动之后，将立即创建一定数量的线程(N1)，放入空闲队列中。这些线程都是处于阻塞（Suspended）状态，不消耗CPU，但占用较小的内存空间。当任务到来后，缓冲池选择一个空闲线程，把任务传入此线程中运行。当N1个线程都在处理任务后，缓冲池自动创建一定数量的新线程，用于处理更多的任务。在任务执行完毕后线程也不退出，而是继续保持在池中等待下一次的任务。当系统比较空闲时，大部分线程都一直处于暂停状态，线程池自动销毁一部分线程，回收系统资源。 基于这种预创建技术，线程池将线程创建和销毁本身所带来的开销分摊到了各个具体的任务上，执行次数越多，每个任务所分担到的线程本身开销则越小，不过我们另外可能需要考虑进去线程之间同步所带来的开销。 构建线程池框架 一般线程池都必须具备下面几个组成部分： 线程池管理器:用于创建并管理线程池 工作线程: 线程池中实际执行的线程

FFT算法原理

2010-10-07 21:10:09| 分类：数字信号处理 | 标签：fft dft |字号订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出DFT的计算公式： 其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)一组N点组成的频率成分的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT 计算得到的一组离散频率幅度只实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N截至的N个频率点的相对幅度。 N点DFT的计算量 根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子WN的特性 1.WN的对称性 2.WN的周期性 3.WN的可约性

IOCP 原理 代码

Windows I/O完成端口 2009-10-30 10:51 WINDOWS完成端口编程 1、基本概念 2、WINDOWS完成端口的特点 3、完成端口（Completion Ports ）相关数据结构和创建 4、完成端口线程的工作原理 5、Windows完成端口的实例代码 WINDOWS完成端口编程 摘要：开发网络程序从来都不是一件容易的事情，尽管只需要遵守很少的一些规则：创建socket，发起连接，接受连接，发送和接收数据，等等。真正的困难在于：让你的程序可以适应从单单一个连接到几千个连接乃至于上万个连接。利用Windows完成端口进行重叠I/O的技术，可以很方便地在Windows平台上开发出支持大量连接的网络服务程序。本文介绍在Windows平台上使用完成端口模型开发的基本原理，同时给出实际的例子。本文主要关注C/S结构的服务器端程序，因为一般来说，开发一个大容量、具有可扩展性的winsock程序就是指服务程序。 1、基本概念 设备---指windows操作系统上允许通信的任何东西，比如文件、目录、串行口、并行口、邮件槽、命名管道、无名管道、套接字、控制台、逻辑磁盘、物理磁盘等。绝大多数与设备打交道的函数都是CreateFile/ReadFile/WriteFile 等，所以我们不能看到**File函数就只想到文件设备。 与设备通信有两种方式，同步方式和异步方式：同步方式下，当调用ReadFile这类函数时，函数会等待系统执行完所要求的工作，然后才返回；异步方式下，ReadFile这类函数会直接返回，系统自己去完成对设备的操作，然后以某种方式通知完成操作。 重叠I/O----顾名思义，就是当你调用了某个函数（比如ReadFile）就立刻返回接着做自己的其他动作的时候，系统同时也在对I/0设备进行你所请求的操作，在这段时间内你的程序和系统的内部动作是重叠的，因此有更好的性能。所以，重叠I/O是在异步方式下使用I/O设备的。重叠I/O需要使用的一个非常重要的数据结构：OVERLAPPED。 2、WINDOWS完成端口的特点 Win32重叠I/O(Overlapped I/O)机制允许发起一个操作，并在操作完成之后接收信息。对于那种需要很长时间才能完成的操作来说，重叠IO机制尤其有用，因为发起重叠操作的线程在重叠请求发出后就可以自由地做别的事情了。在WinNT和Win2000上，提供的真正可扩展的I/O模型就是使用完成端口（Completion Port）的重叠I/O。完成端口---是一种WINDOWS内核对象。完成端口用于异步方式的重叠I/0情况下，当然重叠I/O不一定非得使用完成端口不可，同样设备内核对象、事件对象、告警I/0等也可使用。但是完成端口内部提

跟我学VS#语言编程技术——C#中的线程池Thread Pool技术及应用示例

1.1跟我学VS#语言编程技术——C#中的线程池Thread Pool技术及应用示例1.1.1C#中的线程池Thread Pool技术及应用示例 1、线程池Thread Pool技术概述 我们知道，大部分应用程序都是通过线程工作的，该线程等待一些引入的连接，一旦接收到一个连接，就会创建一个新的线程，并且要求这个线程服务于这个新的连接。 在此种工作方式下，当线程比较多的时候，系统的开销将会相当大。减少系统开销的一个方法就是使用一个线程池来处理，特别是关于在服务应用程序中使用线程的问题。 在服务器端的应用程序中几乎都采用了“线程池”技术，这主要是为了提高系统效率。因为如果服务器对应每一个请求就创建一个线程的话，在很短的一段时间内就会产生很多创建和销毁线程动作，导致服务器在创建和销毁线程上花费的时间和消耗的系统资源要比花在处理实际的用户请求的时间和资源更多。线程池就是为了尽量减少这种情况的发生。 2、线程池的工作原理 所谓线程池，就是在内存中等待工作的线程，系统会根据工作的情况，自动地创建并管理新的线程。其工作原理如下图所示：

3、ThreadPool类 在.NET中，通过System.Threading.ThreadPool类，每个进程都自动带有一个线程池，而且每个进程至多只能有一个线程池，可以在多个不同的行为间共享线程池。 上面我们已经知道了线程池主要用于服务引入的连接，但同时也还可以周期性地进行其它方面的服务，比如检查服务器上的磁盘空间，确保服务器高速运行，检查电子邮件以及服务客户连接等等。 其实，线程池可以使线程变得更容易，很明显还需要处理同步问题，但我们不需要真实地创建线程，.NET会帮助我们做这些。