实习一多进程线程实现快速排序课件.ppt

1、操作系统实习习题课张旦峰操作系统实验室2/41实习一：压力测试实习二、三：并发控制实习四：多进程（线程）快速排序实习五：快速文件系统3/41要求编写一组小程序测试你的Windows 2K/XP系统创建进程和线程的能力步骤压力测试压力测试：创建尽可能多的进程和线程，得到这个数目的极限，进程和线程启动后可以进入睡眠状态或者死循环，考虑这两种情况对结果的影响性能测试性能测试：测试系统创建单个进程和线程的平均速率以及速率变化情况，并且对不同的优先级进行测试，研究优先级对其影响4/41BOOL CreateProces(LPCTSTR lpApplicationName,LPTSTR lpCommand

2、Line,LPSECURITY_ATTRIBUTES lpProcessAttributes,LPSECURITY_ATTRIBUTES lpThreadAttributes,BOOL bInheritHandles,DWORD dwCreationFlags,LPVOID lpEnvironment,LPCTSTR lpCurrentDirectory,LPSTARTUPINFO lpStartupInfo,LPPROCESS_INFORMATION lpProcessInformation);5/41BOOL CreateThread(LPSECURITY_ATTRIBUTES lpThr

3、eadAttributes,SIZE_T dwStackSize,LPTHREAD_START_ROUTINE lpStartAddress,LPVOID lpParameter,DWORD dwCreationFlags,LPDWORD lpThreadId);6/41睡眠状态睡眠状态挂起操作在父进程通过将dwCreationFlags设置为CREATE_SUSPENDED选项实现死循环死循环父进程产生子进程后子进程立即执行，并且执行一个死循环程序 线程线程vs进程进程分别使用CreateProcess和CreateThread7/41CreateProcess(szAppName,szAp

4、pName,NULL,NULL,FALSE,0,NULL,NULL,&si,&pi)CreateProcess(szAppName,szAppName,NULL,NULL,FALSE,CREATE_SUSPENDED,NULL,NULL,&si,&pi)CreateThread(NULL,0,ThreadFunc,NULL,0,&dwThreadId)CreateThread(NULL,0,ThreadFunc,NULL,CREATE_SUSPENED,&dwThreadId)8/41进程子进程挂起：第一次：3607第二次：3607第三次：3610平均：3608（依赖于具体机器）死循环未知(非

5、常慢，8个小时1000多个进程)线程子线程挂起：第一次：2031第二次：2031第三次：2031平均：2031（操作系统限制）死循环同样非常慢（2031）9/41挂起vs死循环挂起创建速度相对要快，容易达到上限死循环死循环：每个子进程都持续占用cpu，cpu利用率持续为100%。创建的速度非常慢。很难达到上限进程vs线程对于挂起的情况，线程产生速度比进程快很多线程上限是固定的，受到每个进程能创建线程的上限限制。而进程数上限不确定，受限于系统性能对于死循环的情况类似，但是创建线程要比进程的情况要快10/41使用不同优先级测试创建进程、线程函数的dwCreationFlags参数指定优先级：REA

6、LTIME_PRIORITY：最高优先级 HIGH_PRIORITY_CLASS：高优先级。例如任务管理器 NORMAL_PRIORITY_CLASS：普通优先级，默认设置 IDLE_PRIORITY_CLASS：最低优先级，例如屏保11/41CreateProcess(szAppName,szAppName,NULL,NULL,FALSE,REALTIME_PRIORITY,NULL,NULL,&si,&pi)CreateProcess(szAppName,szAppName,NULL,NULL,FALSE,HIGH_PRIORITY_CLASS,NULL,NULL,&si,&pi)Crea

7、teProcess(szAppName,szAppName,NULL,NULL,FALSE,NORMAL_PRIORITY_CLASS,NULL,NULL,&si,&pi)CreateProcess(szAppName,szAppName,NULL,NULL,FALSE,IDLE_PRIORITY_CLASS,NULL,NULL,&si,&pi)CreateThread()12/4113/4114/41由于数据的随机性，以及系统状态的不稳定性，并不能看出不同优先级之间明显的差异随着创建进程、线程数目的增多，平均创建时间总体来说越来越长创建速度与系统负荷有关15/41在对进程创建进行计时的过程中

8、，有几种计时方法，哪种比较合理？Time(秒级)clock、timeGetTime、QueryPerformanceCounter（毫秒级）QueryPerformanceCounter精读最高，但开销可能会偏大，按应用场景而定在创建进程或线程的过程中系统需要做那些特殊处理（比如对调度和中断的处理），为什么？进程创建需要中断，是系统的调度单位。线程不需要16/41线程和进程的区别实验数据依赖于机器以及运行的环境，没有标准答案数据本身并不重要，重要的是获得数据，分析数据的能力（图表！）对比实验（关闭防火墙，关闭QQ，）17/41 互斥量操作HANDLE CreateMutex(LPSECURIT

9、Y_ATTRIBUTES lpMutexAttributes,BOOL bInitialOwner,LPCSTR lpName);HANDLE OpenMutex(DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName);BOOL ReleaseMutex(HANDLE hMutex);18/41 信号量操作BOOL CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,LONG lInitialCount,LONG lMaximumCount,LPCSTR lpName)

10、;HANDLE OpenSemaphore(DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName);BOOL ReleaseSemaphore(HANDLE hSemaphore,LONG lReleaseCount,LPLONG lpPreviousCount);19/41互斥量、信号量请求DWORD WaitForSingleObject(HANDLE hHandle,DWORD dwMilliseconds);DWORD WaitForMultipleObjects(DWORD nCount,const HANDLE*lpHand

11、les,BOOL bWaitAll,DWORD dwMilliseconds);20/41 临界区操作void InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection);void EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);void LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);21/41要求在Windows 2000/XP环境下，编程实现多生产者P-消费者C问题对某一P有需求的全

12、部C均访问过某缓冲区后、该P和其它的P才可以向这个缓冲区存放产品输入格式51 p 32 p 43 c 4 14 p 25 c 2.1 1 2 422/4123/41缓冲区的大小对实验结果有何影响？设置不同的大小，考察平均服务时间了解Win32 API中定义的IPC函数，说明比较说明涉及到的几种同步对象。你猜测哪一种操作速度比较快，证实你的想法，并给出一个合理的解释。Mutex，Semaphore，CriticalSection CriticalSection最快，因为其是目态下的对象，无需切换 临界区平均执行时间：0.24659ms 互斥量平均执行时间：2.398841ms 信号量平均执行时间

13、：2.3273ms 事件平均执行时间：3.43456ms24/41如果缓冲区是无限大的，那么输入、输出进程读、写缓冲区需要什么条件？生产者无需等待缓冲区，消费者无需释放缓冲区若使用进程间通信方式实现该问题，具体需要怎么做？使用消息传递（信箱）来解决这个问题（每个消费者和生产者都有一个）1.消费者对所有相关的生产者信箱发送一个空消息：send(producer,&m)并等待接受生产者返回的消息：receive(producer,&m)2.生产者生产一个数据 3.生产者接受所有相关消费者消息：receive(consumer,&m)4.生产者将item写入一个新的消息并发送回所有消费者：send(

14、consumer,&m)，回到2 5.消费者获得改消息后处理消息，回到125/41要求在Windows 2000/XP环境下，编程实现银行业务服务问题，用P、V操作实现柜台人员和顾客进程的程序问题描述银行业务服务问题：银行有n个柜员负责为顾客服务，顾客进入银行先取一个号码，然后等着叫号；当某个柜员空闲下来，就叫下一个号26/4127/41 柜员人数和顾客人数对结果分别有什么影响？同样柜员人数，不同客户人数；同样客户人数，不同柜员人数，对比测试 选择何种互斥方法实现本实习？原因为何？互斥量，信号量，临界区 如果用事件来实现同步操作，应该怎么做？事件：set和unset两种状态。两个赋值操作：Se

15、t和Reset客户：unset counter,set customer,waitfor counter 柜员：waitfor customer,set counter 该问题同多生产者-消费者问题的主要区别，从并发程度，题目内的制 约关系等方面考虑，并指出解决方法的不同 一对多和一对一的区别。前者需要当所有消费者均已消费完之后才能释放资源。后者没有这个需求28/41掌握windows下多线程并发控制熟悉基本概念（Mutex，PV操作等）的使用，掌握基本概念（死锁，饥饿）比较windows下各种同步对象的性能（实验！）发现新的互斥问题（互斥的输出控制）学习如何让主程序等待所有子线程结束（Wai

16、tForMultipleObjects）29/41要求在Windows 2000/XP环境下，编写一个多进程（线程）进行快速排序的程序，使用的是产生1，000，000个随机数的文件给出程序运行的系统资源配置，给出测试结果并对测试程序和结果做出说明30/41内存映射文件 由一个进程用CreateFile建立内存和文件的映射 CreateFileMapping创建内存映射文件 其他进程用OpenFileMapping打开打开之后用MapViewOfFile建立该文件到本进程地址空间的映射程序结束时请注意释放File和View31/41HANDLE CreateFile(LPCSTR lpFileN

17、ame,DWORD dwDesiredAccess,DWORD dwShareMode,LPSECURITY_ATTRIBUTES lpSecurityAttributes,DWORD dwCreationDisposition,DWORD dwFlagsAndAttributes,HANDLE hTemplateFile);HANDLE CreateFileMapping(HANDLE hFile,LPSECURITY_ATTRIBUTES lpFileMappingAttributes,DWORD flProtect,DWORD dwMaximumSizeHigh,DWORD dwMaxi

18、mumSizeLow,LPCSTR lpName);32/41LPVOID MapViewOfFile(HANDLE hFileMappingObject,DWORD dwDesiredAccess,DWORD dwFileOffsetHigh,DWORD dwFileOffsetLow,SIZE_T dwNumberOfBytesToMap);HANDLE OpenFileMapping(DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName);33/41快速排序代码（略，参考算法书）内存映射文件使用（只有使用多进程才需要！）主进程hF

19、ile=CreateFile(“dataFile.dat”,.,NULL,OPEN_EXISTING,.,NULL);hMapFile data=CreateFileMapping(hFile,NULL,PAGE_READWRITE,0,0,“data”);lpMapBase data=MapViewOfFile(hMapFile data,FILE_MAP_ALL_ACCESS,0,0,0);其他进程hMapFile data=OpenFileMapping(FILE_MAP_ALL_ACCESS,FALSE,“data”);lpMapBase data=MapViewOfFile(hMap

20、File data,FILE MAP ALL ACCESS,0,0,0);34/41用多进程实现和多线程实现体现了什么差异，产生的原因是什么？多线程明显快于多进程原因：创建开销，切换开销以及共享内存差别分割的均匀程度对进程(线程)数目和结果有什么影响？需要的进程线程数不同对数据分割的均匀程度对排序的时间有何影响 算法复杂度O(log n)到O(n2)对进程（线程）数目也有影响35/41分解到每个线程的排序算法应不应采用快速排序算法，为什么？数据量小，快速排序效率不一定高进程和线程在处理数据通信上有何差别，为什么会有这种差别？是否需要内存映射文件（差别在于线程之间共享地址空间，而进程不是）36/

21、41线程vs进程（是否共享地址空间）线程进程之间是否需要同步？基本算法的分析和实现37/41要求编写一个程序，测试采用三种访问模式随机访问大文件时的效率，三种模式使用类似的程序框架，只是产生文件对象时使用不同的模式。过程每一个测试环节非读即写，设读发生的概率为Q1随机选取文件位置p，读/写n字节的内容（注意遇到文件结尾的处理）若是读数据，调用函数f1对读入的数据作一系列操作或者调用f2做一些无关的操作，设f1调用的概率为Q2。f1和f2可以用循环来模拟，循环的次数可以是一个随机值，要在一个合理的范围之内重复以上三步，模拟随即文件读写访问38/41Windows 2K/XP的文件访问方式的文件访

22、问方式不使用文件缓冲不使用文件缓冲 普通的方式普通的方式使用文件缓冲使用文件缓冲 预读取。每次读取的块大小；缓冲区大小；替换方式预读取。每次读取的块大小；缓冲区大小；替换方式 写回。写回时机选择；一致性问题写回。写回时机选择；一致性问题异步模式异步模式 不再等待磁盘操作的完成不再等待磁盘操作的完成 使处理器和使处理器和I/O并发工作并发工作39/41HANDLE CreateFile(LPCSTR lpFileName,DWORD dwDesiredAccess,DWORD dwShareMode,LPSECURITY_ATTRIBUTES lpSecurityAttributes,DWORD

23、 dwCreationDisposition,DWORD dwFlagsAndAttributes,HANDLE hTemplateFile);40/41参考Windows内核实验教程中快速文件系统实习（P109）无缓冲CreateFile函数的dwFlagsAndAttributes标志位设置为FILE_FLAG_NO_BUFFERING文件缓冲 CreateFile函数的dwFlagsAndAttributes标志位设置为FILE_FLAG_SEQUENTIAL_SCAN异步传输CreateFile函数的dwFlagsAndAttributes标志位设置为FILE_FLAG_OVERLAPPED其他组合？41/41学习windows快速文件系统的使用熟悉文件缓冲，异步传输的概念详细的数据对比分析