多和程序设计技术

高级程序设计课程2013~2014年度第1学期论题：多核程序设计技术——通过软件提升性能院系：计算机学院学号：2111205002姓名：任课教师：成绩评定：完成日期：2013年12月28日五邑大学研究生考试1．多核体系结构随着桌面并行时代的来临，基于多核的并行计算机已进入千家万户。例如，很多人的笔记本就装有两个处理器芯片，台式计算机装有四个芯片。INTEL、AMD在多核技术方向的相继突破，更使得并行计算成为研究热点之一。虽然多核时代已经到来，目前的困境是，多核硬件技术已成熟，但并行处理核心算法等应用问题却尚未得到解决。中国科大研究人员所做的这项研究在网络数据包的有效分类算法，也即网络核心算法的研究方面获得进展。多核的普及是很重要的，因为以往仅仅提供高单线程性能。我们观察到，在一个大型变繁忙的内核数量多核心，这技术的应用是最理想的任何个人。每个单是往往无法把所有的方式多核其功率或温度信封由于电源电压或错误率的限制。多核技术已经是现代处理器发展的主流趋势,它的诞生给软件开发技术带来了新的挑战。如何编写出高效的并行程序使之充分地利用多核的资源,这一直是学术界和工艺界致力于解决的难题。多核程序的性能调试对于开发高效的并行程序来说,具有良好地辅助作用。它通过分析程序的行为并诊断其性能瓶颈,进而给性能优化提供有效的支持。由于并行程序的动态性和不确定性,传统的代码分析技术很难有效地检测其性能瓶颈。有的研究工作提出在软件层分析程序运行时行为,这通常会引入很大的运行时开销,并且获得数据精确度很低。硬件的实现虽然运行时开销低,然而其结构扩展引入的开销又会损伤程序的性能。CMP的低成本和广泛可用性，使得一般的软件开发人员能够进行各种级别的并行处理。并行处理不再是超级计算机或集群的专属领域。基本的开发工作站和入门级服务器现在都具有软件级和硬件级的并行处理能力。这意味着程序员和软件开发人员可以无需牺牲设计或性能，即可根据需要部署利用多处理和多线程的应用。然而，需要注意的是，并非每个软件应用都需要多处理或多线程。实际上，一些软件解决方案和计算机算法最好使用顺序编程技术来实现。在某些情况下，在软件中引入并行编程技术的开销会使软件性能降级。并行性和多处理是需要一定成本的。如果软件中顺序地解决问题需要的工作量少于创建额外线程和进程的开销，或者少于协调并发执行的任务之间通信的工作，则应选择顺序的方法。我们今天所使用的基本计算机体系结构是基于二十世纪四十年代数据学冯诺依曼提出的概念的。在他的体系结构中，数据和程序存储于计算机内存并被馈送给计算机的CPU。程序通过使用程序计数器执行，这就为CPU提供了内存当中下一个将执行的指令的地址。但是，这种方法是受限制的，因为它一次只允许执行单个指令。在多核处理器和拥有大量可用内存的时代，不再需要这种限制了。取而代之的是，多个指令通常可以更快地平行执行--所有指令都同时执行且只需一个步骤。多核体系结构，允许在任何指定的时间执行多个指令，这样可以极大地简化程序员的工作。2．多线程与多核编程多核、多处理器系统中的每颗处理器（每个核），同时间内可以执行各自不同的进程（或线程）。一颗单线程能力的处理器（一个核）只能执行一个进程，双核处理器就能够同时执行两个不同的进程（或线程），四核就可以同时不同的四个进程（或线程）。倘若是执行不支持多线程的程序，那么每颗处理器内的多线程功效就无从发挥。硬件条件已经具备，但作为人机交互的操作系统和应用软件需要研究它的并行化方法，最大限度挖掘系统的整体性能。2.1进程概念：进程是操作系统结构的基础；是一个正在执行的程序，是计算机中正在运行的程序实例，是可以分配给处理器并由处理器执行的一个实体；由单一顺序的执行显示，一个当前状态和一组相关的系统资源所描述的活动单元。进程为应用程序的运行实例，是应用程序的一次动态执行。我们可以简单地理解为：它是操作系统当前运行的执行程序。对应用程序来说，进程就像一个大容器。在应用程序被运行后，就相当于将应用程序装进容器里了，你可以往容器里加其他东西(如:应用程序在运行时所需的变量数据、需要引用的DLL文件等)，当应用程序被运行两次时，容器里的东西并不会被倒掉，系统会找一个新的进程容器来容纳它。2.2多线程的概念线程（thread）是进程上下文（context）中执行的代码序列，是进程中的一个实体，是被系统独立调度和分派的基本单位，又被称为轻量级进程（lightweightprocess）在支持多线程的系统中，进程成为资源分配和保护的实体，而线程是被调度执行的基本单元。线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。线程是程序中一个单一的顺序控制流程。在单个程序中同时运行多个线程完成不同的工作，称为多线程。线程的状态：就绪（ready）：线程等待可用的处理器。运行（running）：线程正在被执行。阻塞（blocked）：线程正在等待某个事件的发生（比如I/O的完成，试图加锁一个被上锁的互斥量）。终止（terminated）：线程从起始函数中返回或者调用pthread_exit。终止运行阻塞就绪调度条件满足等待资源切换被创建完成2.3进程与线程的关系程序在操作系统中作为进程方式存在、获取资源、运行。在一个进程内，线程可以创建其它线程。每个线程有各自的栈(stack)。一个进程内所有的线程共享代码段和数据段。进程对于在一个进程内的线程：一个线程对共享的系统资源进行修改，在这个进程内的其它线程也可以见到这种修改。进程内的多个线程可以对同一个内存单元进行读和写操作，所以必须要采取显式同步机制。在同一个进程的地址空间下，线程间的通信消耗更小。一个进程内的线程示例2.4线程的同步与互斥由于线程共享同一进程的内存空间，多个线程可能需要同时访问同一个数据。如果没有正确的保护措施，对共享数据的访问会造成数据的不一致和错误。全局变量是线程间通信最常用的手段，然而却容易造成访问冲突。常用的同步机制：互斥(mutualexclusion)条件同步(conditionsynchronization)线程的本地存储（threadlocalstorage,tls）互斥是指对于共享的操作系统资源（广义的资源，譬如全局变量），在各线程访问时的排它性。临界区（criticalsection）锁（lock）/互斥量（mutex）信号量（semaphore）同步是指线程间的一种制约关系，一个线程的执行依赖另一个线程的消息。当它没有得到消息时应等待，直到消息到达时被唤醒。事件（event）信号量（semaphore）如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。关于临界区的使用，有下列注意点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。每个共享资源使用一个CRITICAL_SECTION变量；不要长时间运行关键代码段，当一个关键代码段长时间运行时，其他线程就会进入等待状态，这会降低应用程序的运行性能；如果需要同时访问多个资源，则可能连续调用EnterCriticalSection；CriticalSection不是OS核心对象，如果进入临界区的线程挂了，将无法释放临界资源。这个缺点在Mutex中得到了弥补。锁（互斥量）跟临界区很相似，只有拥有锁（互斥对象）的线程才具有访问资源的权限。区别是：Mutex所花费的时间比CriticalSection多的多，但是Mutex是核心对象(Event、Semaphore也是)，可以跨进程使用，而且等待一个被锁住的Mutex可以设定TIMEOUT，不会像CriticalSection那样无法得知临界区域的情况，而一直死等。3．结束语因此要在多核体系结构的环境下，使软件充分发挥多核的效能，我们不能用开发单线程软件的思想来设计软件，而要根据多线程编程模型来设计软件，使开发出来的软件最大限度地利用CPU资源。参考文献：[1]英特尔软件学院教材编写组.多核多线程技术.上海:上海交通大学出版社，2011.1[2]UnderstandingHowOff-ChipMemoryBandwidthPartitioninginChipMultiprocessorsAffectsSystemPerformance.FangLiu,XiaoweiJiang,YanSolihin模拟十字路口交通控制程序1．程序说明使用java多线程模拟十字路口处通过红绿灯来控制汽车的通行。2．程序代码importjava.awt.*;importjava.util.Random;publicclassCarextendsThread{//汽车类：实际上是一个线程；roadsasroad;//数据成员：路类的对象asroad灯类的对象light_1、light_2；intx,y,a;Graphicsg;Lightlight_1;Lightlight_2;Randomrandom=newRandom(2005);//随机函数产生是否转弯的一个随机数；Car(Graphicsg,Lightlight1,Lightlight2,intx,inty,inta,roadsasroad){//CAR类的constructor;this.g=g;this.light_1=light1;this.light_2=light2;//传进灯的状态：红或是绿；this.x=x;//汽车的起驶位置的x值this.y=y;//汽车的起驶位置的y值this.a=a;//汽车的行驶方向this.asroad=asroad;//路类的对象asroad：用来解决小车碰撞问题；}publicvoidrun(){//线程的run函数；while(true){//汽车的起驶switch(a)//四个方向运行的画车函数；{case0:paint(g,0);break;//0为自西向东运行的车的实现；case1:paint(g,1);break;//1为自南向北运行的车的实现；case2:paint(g,2);break;//2为自东向西运行的车的实现；case3:paint(g,3);break;//3为自北向南运行的车的实现；default:;}}}voidpaint(Graphicsg,intb)//具体的画车函数；{switch(b){case0:{//车自西向东；if(x==60||x==280){if(Math.random()0.2)a=0;elsea=1;}///是否右转弯；while(x==60&&a==0&&light_1.i==true||x==280&&a==0&&light_1.i==true){//是否为红灯：Y则等N则直走；try//每隔0.3秒判断一次{this.sleep(300);}catch(InterruptedExceptione){}}if(asroad.s[x+25][180]==0){//前面是否有车；x=x+5;g.setColor(Color.RED);g.fillRect(x,180,20,15);if(x0)asroad.s[x][180]=1;if(x0)asroad.s[x-5][180]=0;g.clearRect(x-5,180,10,15);}while(a==1&&x=90&&x=0||x=280&&x=305&&a==1){//转弯时的完善；try{this.sleep(50);}catch(InterruptedExceptione){}for(intp=150;p=210;p++)if(asroad.s[90][p]==1){asroad.corner3=1;break;};for(intz=150;z=210;z++)if(asroad.s[280][z]==1){asroad.corner