`
yingyingol
  • 浏览: 739346 次
文章分类
社区版块
存档分类
最新评论

临界区的互斥控制

 
阅读更多
一、前言
我正在研究线程的通讯,无奈有关这方面的资料实在太少,没办法我只好去啃MSDN,但是MSDN好像说得也不太清楚。所以那我就写了这么一个例子,以望对学习多线程编程起到引玉抛砖的作用。有个易懂的例子学起来总是容易很多。近来我正在复习那几个排序算法,于是就把这些算法写到了这里来作为线程的例子。同时也对几个通用的排序算法思想作了一些说明。
这个例子利用多线程使用不同的排序算法对数据进行排序,每一个线程使用不同的算法。主线程里使用快速排序QuickSort,其他四个算法分别建立四个子线程,在子线程中进行排序。因为每一个线程都要调用函数PrintResult把结果输出到显示器上,所以不同的线程就会争夺着向显示器输出,这样,不同线程的输出就会混合在一起,所以呢必须让线程一个接着一个输出。也就是必须对PrintResult进行互斥控
制。要进行互斥控制,则必须用到Event、Mutex、CrititicalSection、Semaphore等互斥控制量。这个例子可以使用Event、Mutex、CrititicalSection,你可以根据提示修改代码使用其中的一种互斥量进行测试。 我所写的例子没有使用MFC,用的都是SDK的WINAPI,如果使用MFC时有些许差别,但原理是一样的。而且MFC还把线程分成用户界面线程和工作者线程,实质上用户界面线程跟工作者线程的差别是,用户界面线程要继承的基类已经实现了消息循环,MFC帮你做了很多的消息处理和界面控制的工作。

一、WINAPI线程控制函数简介:有关详细说明请查看MSDN

1.1 线程建立函数



1.2 临界资源控制函数:

1)事件对象的创建
事件对象的作用是为线程传送一个公共的事件信号,使用CreateEvent函数创建:


2)互斥量的创建
互斥量的作用是保证每次只能有一个线程获得互斥量而得以继续执行,使用CreateMutex函数创建:
3)临界区信号的初始化
使用前必须先初始化


4)阻塞函数
如果等待的信号量不可用,那么线程就会挂起,直到信号可用线程才会被唤醒,该函数会自动修改信号,如Event,线程被唤醒之后
Event信号会变得无信号,Mutex、Semaphore等也会变。我们使用WaitForSingleObject函数等待信号,如果要等待多个信号可以使用WaitForMutipleObject函数。


二、实例讲解
下面我们结合本文的示例代码进行具体的讲解:

2.1 函数、变量的申明


下面使用了三种控制方法,你可以注释其中两种,使用其中一种。注意修改时要连带修改临界区PrintResult里的相应控制语句

要使用InterlockedIncrement(long* lpAddend)和InterlockedDecrement(long* lpAddend)进行加减操作*/
下面的结构是用于传送排序的数据给各个排序子线程
struct MySafeArray
{
    long* data;
    int iLength;
};
打印每一个线程的排序结果


排序函数


以上四个函数的声明必须乎合作为一个线程函数的必要条件才可以使用CreateThread建立一个线程。
(1)调用方法必须是__stdcall,即函数参数压栈顺序由右到左,而且由函数本身负责栈的恢复, C和C++默认是__cdecl, 所以要显式声明是__stdcall
(2)返回值必须是unsigned long
(3)参数必须是一个32位值,如一个指针值或long类型
(4)如果函数是类成员函数,必须声明为static函数,在CreateThread时函数指针有特殊的写法。如下(函数是类CThreadTest的成员函数中):


之所以要声明为static是由于该函数必须要独立于对象实例来使用,即使没有声明实例也可以使用。

2.2 具体实现代码


每一个线程都要使用下面这个函数进行输出,而且只有一个显示器,产生多个线程竞争对控制台的使用权。


三、排序思想与具体算法

3.1 冒泡排序思想(升序,降序同理,后面的算法一样都是升序):
从头到尾对数据进行两两比较进行交换,小的放前大的放后。这样一次下来,最大的元素就会被交换的最后,然后下一次循环就不用对最后一个元素进行比较交换了,所以呢每一次比较交换的次数都比上一次循环的次数少一,这样N次之后数据就变得升序排列了


3.2 选择排序思想:
每一次都从无序的数据中找出最小的元素,然后和前面已经有序的元素序列的后一个元素进行交换,这样整个源序列就会分成两部分,前面一部分是已经排好序的有序序列,后面一部分是无序的,用于选出最小的元素。 循环N次之后,前面的有序序列加长到跟源序列一样长,后面的无序部分长度变为0,排序就完成了。

3.3 堆排序思想:
堆:数据元素从1到N排列成一棵二叉树,而且这棵树的每一个子树的根都是该树中的元素的最小或最大的元素这样如果一个无序数据集合是一个堆那么,根元素就是最小或最大的元素 ,堆排序就是不断对剩下的数据建堆,把最小或最大的元素析透出来。
下面的算法,就是从最后一个元素开始,依据一个节点比父节点数值大的原则对所有元素进行调整,这样调整一次就形成一个堆,第一个元素就是最小的元素。然后再对剩下的无序数据再进行建堆,注意这时后面的无序数据元素的序数都要改变,如第一次建堆后,第二个元素就会变成堆的第一个元素。


3.4 插入排序思想:
把源数据序列看成两半,前面一半是有序的,后面一半是无序的,把无序的数据从头到尾逐个逐个的插入到前面的有序数据中,使得有序的数据的个数不断增大,同时无序的数据个数就越来越少,最后所有元素都会变得有序。


3.5 快速排序思想:
快速排序是分治思想的一种应用,它先选取一个支点,然后把小于支点的元素交换到支点的前边,把大于支点的元素交换到支点的右边。然后再对支点左边部分和右边部分进行同样的处理,这样若干次之后,数据就会变得有序。
下面的实现使用了递归
建立两个游标:iLow,iHigh;iLow指向序列的第一个元素,iHigh指向最后一个先选第一个元素作为支点,并把它的值存贮在一个辅助变量里。那么第一个位置就变为空并可以放置其他的元素。 这样从iHigh指向的元素开始向前移动游标iHigh查找比支点小的元素,如果找到,则把它放置到空置了的位置(现在是第一个位置)然后iHigh游标停止移动,这时iHigh指向的位置被空置,然后移动iLow游标寻找比支点大的元素放置到iHigh指向的空置的位置,如此往复直到iLow与iHigh相等。最后使用递归对左右两部分进行同样处理.

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics