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

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

2、pCommandLine,LPSECURITY_ATTRIBUTES lpProcessAttributes,LPSECURITY_ATTRIBUTES lpThreadAttributes,BOOL bInheritHandles,DWORD dwCreationFlags,LPVOID lpEnvironment,LPCTSTR lpCurrentDirectory,LPSTARTUPINFO lpStartupInfo,LPPROCESS_INFORMATION lpProcessInformation);4实习一：压力测试涉及函数BOOL CreateThread(LPSECURITY

3、_ATTRIBUTES lpThreadAttributes,SIZE_T dwStackSize,LPTHREAD_START_ROUTINE lpStartAddress,LPVOID lpParameter,DWORD dwCreationFlags,LPDWORD lpThreadId);5压力测试基本思路睡眠状态挂起操作在父进程通过将dwCreationFlags设置为CREATE_SUSPENDED选项实现死循环父进程产生子进程后子进程立即执行，并且执行一个死循环程序 线程vs进程分别使用CreateProcess和CreateThread6压力测试示例代码CreateProces

4、s(szAppName, szAppName, 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)7压力测试结果进程子进程挂起：第一次：3607第

5、二次：3607第三次：3610平均：3608（依赖于具体机器）死循环未知(非常慢，8个小时1000多个进程)线程子线程挂起：第一次：2031第二次：2031第三次：2031平均：2031（操作系统限制）死循环同样非常慢（2031）8压力测试结果分析挂起vs死循环挂起创建速度相对要快，容易达到上限死循环死循环：每个子进程都持续占用cpu，cpu利用率持续为100%。创建的速度非常慢。很难达到上限进程vs线程对于挂起的情况，线程产生速度比进程快很多线程上限是固定的，受到每个进程能创建线程的上限限制。而进程数上限不确定，受限于系统性能对于死循环的情况类似，但是创建线程要比进程的情况要快9性能测试基本

6、思路使用不同优先级测试创建进程、线程函数的dwCreationFlags参数指定优先级： REALTIME_PRIORITY：最高优先级 HIGH_PRIORITY_CLASS：高优先级。例如任务管理器 NORMAL_PRIORITY_CLASS：普通优先级，默认设置 IDLE_PRIORITY_CLASS：最低优先级，例如屏保10性能测试示例代码CreateProcess(szAppName,szAppName, NULL, NULL, FALSE,REALTIME_PRIORITY, NULL, NULL, &si, &pi)CreateProcess(szAppName,szAppNam

7、e, NULL, NULL, FALSE,HIGH_PRIORITY_CLASS, NULL, NULL, &si, &pi)CreateProcess(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()11性能测试结果12性能测试结果13性能测试结果分析由于数据的

8、随机性，以及系统状态的不稳定性，并不能看出不同优先级之间明显的差异随着创建进程、线程数目的增多，平均创建时间总体来说越来越长创建速度与系统负荷有关14性能测试问题在对进程创建进行计时的过程中，有几种计时方法，哪种比较合理？ Time(秒级) clock、timeGetTime、QueryPerformanceCounter（毫秒级） QueryPerformanceCounter精读最高，但开销可能会偏大，按应用场景而定在创建进程或线程的过程中系统需要做那些特殊处理（比如对调度和中断的处理），为什么？ 进程创建需要中断，是系统的调度单位。线程不需要15实习一：压力测试小结线程和进程的区别实验数

9、据依赖于机器以及运行的环境，没有标准答案数据本身并不重要，重要的是获得数据，分析数据的能力（图表！）对比实验（关闭防火墙，关闭QQ，）16实习二、三：并发控制涉及函数互斥量操作HANDLE CreateMutex (LPSECURITY_ATTRIBUTES lpMutexAttributes,BOOL bInitialOwner,LPCSTR lpName );HANDLE OpenMutex (DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName);BOOL ReleaseMutex (HANDLE hMutex);17实习二、三：

10、并发控制涉及函数信号量操作BOOL CreateSemaphore (LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,LONG lInitialCount,LONG lMaximumCount,LPCSTR lpName );HANDLE OpenSemaphore (DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName);BOOL ReleaseSemaphore (HANDLE hSemaphore,LONG lReleaseCount,LPLONG lpPreviousCount );18实

11、习二、三：并发控制涉及函数互斥量、信号量请求DWORD WaitForSingleObject (HANDLE hHandle,DWORD dwMilliseconds);DWORD WaitForMultipleObjects (DWORD nCount,const HANDLE* lpHandles,BOOL bWaitAll,DWORD dwMilliseconds);19实习二、三：并发控制涉及函数临界区操作void InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection);void EnterCriticalSec

12、tion(LPCRITICAL_SECTION lpCriticalSection);void LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);20多生产者消费者问题要求要求在Windows 2000/XP环境下，编程实现多生产者P-消费者C问题对某一P有需求的全部C均访问过某缓冲区后、该P和其它的P才可以向这个缓冲区存放产品输入格式51 p 32 p 43 c 4 14 p 25 c 2.1 1 2 421多生产者消费者问题实现22多生产者消费者问题问题缓冲区的大小对实验结果有何影响？设置不同的大小，考察平均服务时间了解W

13、in32 API中定义的IPC函数，说明比较说明涉及到的几种同步对象。你猜测哪一种操作速度比较快，证实你的想法，并给出一个合理的解释。 Mutex，Semaphore，CriticalSection CriticalSection最快，因为其是目态下的对象，无需切换临界区平均执行时间：0.24659ms互斥量平均执行时间：2.398841ms信号量平均执行时间：2.3273ms事件平均执行时间： 3.43456ms23多生产者消费者问题问题如果缓冲区是无限大的，那么输入、输出进程读、写缓冲区需要什么条件？ 生产者无需等待缓冲区，消费者无需释放缓冲区若使用进程间通信方式实现该问题，具体需要怎么做

14、？ 使用消息传递（信箱）来解决这个问题（每个消费者和生产者都有一个）1. 消费者对所有相关的生产者信箱发送一个空消息：send ( producer, &m) 并等待接受生产者返回的消息：receive ( producer, &m)2. 生产者生产一个数据 3. 生产者接受所有相关消费者消息 ：receive( consumer, &m) 4. 生产者将item写入一个新的消息并发送回所有消费者：send ( consumer, &m)，回到2 5. 消费者获得改消息后处理消息，回到124银行业务服务问题要求要求在Windows 2000/XP环境下，编程实现银行业务服务问题，用P、V操作实

15、现柜台人员和顾客进程的程序问题描述银行业务服务问题：银行有n个柜员负责为顾客服务，顾客进入银行先取一个号码，然后等着叫号；当某个柜员空闲下来，就叫下一个号25银行业务服务问题实现26银行业务服务问题问题柜员人数和顾客人数对结果分别有什么影响？ 同样柜员人数，不同客户人数；同样客户人数，不同柜员人数，对比测试选择何种互斥方法实现本实习？原因为何？ 互斥量，信号量 ，临界区如果用事件来实现同步操作，应该怎么做？ 事件：set和unset两种状态。两个赋值操作：Set和Reset客户： unset counter, set customer, waitfor counter 柜员：waitfor c

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

17、XP环境下，编写一个多进程（线程）进行快速排序的程序，使用的是产生1，000，000个随机数的文件给出程序运行的系统资源配置，给出测试结果并对测试程序和结果做出说明29实习四：多进程（线程）快速排序涉及函数内存映射文件 由一个进程用CreateFile建立内存和文件的映射 CreateFileMapping创建内存映射文件 其他进程用OpenFileMapping打开打开之后用MapViewOfFile建立该文件到本进程地址空间的映射程序结束时请注意释放File和View30实习四：多进程（线程）快速排序涉及函数HANDLE CreateFile (LPCSTR lpFileName,DWOR

18、D dwDesiredAccess,DWORD dwShareMode,LPSECURITY_ATTRIBUTES lpSecurityAttributes,DWORD dwCreationDisposition,DWORD dwFlagsAndAttributes,HANDLE hTemplateFile );HANDLE CreateFileMapping (HANDLE hFile,LPSECURITY_ATTRIBUTES lpFileMappingAttributes,DWORD flProtect,DWORD dwMaximumSizeHigh,DWORD dwMaximumSiz

19、eLow,LPCSTR lpName );31实习四：多进程（线程）快速排序涉及函数LPVOID MapViewOfFile (HANDLE hFileMappingObject,DWORD dwDesiredAccess,DWORD dwFileOffsetHigh,DWORD dwFileOffsetLow,SIZE_T dwNumberOfBytesToMap );HANDLE OpenFileMapping (DWORD dwDesiredAccess,BOOL bInheritHandle,LPCSTR lpName );32实习四：多进程（线程）快速排序实现快速排序代码（略，参考算

20、法书）内存映射文件使用（只有使用多进程才需要！）主进程hFile = 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_AC

21、CESS, FALSE,“data” );lpMapBase data = MapViewOfFile( hMapFile data,FILE MAP ALL ACCESS, 0, 0, 0 );33实习四：多进程（线程）快速排序问题用多进程实现和多线程实现体现了什么差异，产生的原因是什么？多线程明显快于多进程原因：创建开销，切换开销以及共享内存差别分割的均匀程度对进程(线程)数目和结果有什么影响？需要的进程线程数不同对数据分割的均匀程度对排序的时间有何影响 算法复杂度O(log n)到O(n2)对进程（线程）数目也有影响34实习四：多进程（线程）快速排序问题分解到每个线程的排序算法应不应采用快速排序算法，为什么？数据量小，快速排序效率不一定高进程和线程在处理数据通信上有何差别，为什么会有这种差别？是否需要内存映射文件（差别在于线程之间共享地址空间，而进程不是）35实习四：多进程（线程）快速排序小结线程vs进程（是否共享地址空间）线程进程之间是否需要同步？基本算法的分析和实现36实习五：快速文件系统要求要求编写一个程序，测试采用三种访问模式随机访问大文件时的效率，三种模式使用类似的程序框架，只是产生文件对象时使用不同的模式。过程每一个测试环节非读即写，设读发生的概率为Q1随机选取文件位置p，读/写n字节的内容（注意遇到文件结尾的处理）若是读数据，调用函数f