C++博客-sin的博客

Linux自旋锁和互斥锁的实现

sin — Tue, 29 Oct 2013 14:40:00 GMT

自旋锁（spin lock）应用在多处理器环境中。如果内核控制路径发现自旋锁“开着”，就获取锁并继续自己的执行。相反，如果内核控制路径发现锁由运行在另一个CPU上的内核控制路径“锁着”，就在周围“旋转”，反复执行一条紧凑的循环指令，直到锁被释放。自旋锁的循环指令表示“忙等”。即使等待的内核控制路径无事可做（除了浪费时间），它也在CPU上保持运行。不过，自旋锁通常非常方便，因为很多内核资源只锁1毫秒的时间片段；所以说，等待自旋锁的释放不会消耗太多CPU的时间。

一般来说，由自旋锁所保护的每个临界区都是禁止内核抢占的。在单处理器系统上，这种锁本身并不起锁的作用，自旋锁技术仅仅是用来禁止或启用内核抢占。请注意，在自旋锁忙等期间，因为并没有进入临界区，所以内核抢占还是有效的，因此，等待自旋锁释放的进程有可能被更高优先级的所取代。这种设计是合理的，因为不能因为占用CPU太久而使系统死锁。

互斥锁（mutex lock）的实现，实际上就是一把锁维护了一个等待队列和一个引用计数器，当获取锁之前，先对引用计数器减1操作，如果为非负，则可以获取锁进入临界区。否则将该任务设为不可中断状态（uninterruptible），挂在该等待对列上。获取锁的任务从临界区退出后，计数器加1操作，唤醒（wake up）等待队列上的被挂起进程。

sin 2013-10-29 22:40 发表评论

C++对象模型

sin — Sat, 26 Oct 2013 15:39:00 GMT

摘要: 转自：http://blog.csdn.net/wxc1987821/article/details/5958325——谈VC++对象模型（美）简.格雷程化译译者前言一个C++程序员，想要进一步提升技术水平的话，应该多... 阅读全文

sin 2013-10-26 23:39 发表评论

虚析构函数问题：为什么要将基类的的析构函数设成虚的？

sin — Sat, 19 Oct 2013 13:36:00 GMT

转自：http://blog.csdn.net/pathuang68/article/details/4156308

某CSDN网友问：

class A
{
public:
   ~A()
   {
      cout < <"A::~A" < <endl;
   }
};

class B:public A
{
public:
   virtual ~B()
   {
      cout < <"B::~B" < <endl;
   }
};

class C:public B
{
public:
   ~C()
   {
      cout < <"C::~C" < <endl;
   }
};

int main()
{
   A *a=new A();
   B *b=new B();
   C *c=new C();
   A *d=new B();
   A *e=new C();
   B *f=new C();

   delete a;
   cout < <endl;
   delete b;
   cout < <endl;
   delete c;
   cout < <endl;
   delete d;
   cout < <endl;
   delete e;
   cout < <endl;
   delete f;
   cout < <endl;

   system("Pause");
}

这段程序运行时有错，当时考的时候题目直接说写出运行结果，我就稀里糊涂得写下来，回来编下发现有错，请教下错在哪，最好告诉我为什么？

玄机逸士回答：

1. 一般来说，如果一个类要被另外一个类继承，而且用其指针指向其子类对象时，如题目中的A* d = new B();(假定A是基类，B是从A继承而来的派生类)，那么其(A类)析构函数必须是虚的，否则在delete d时，B类的析构函数将不会被调用，因而会产生内存泄漏和异常；

2. 在构造一个类的对象时，先构造其基类子对象，即调用其基类的构造函数，然后调用本类的构造函数；销毁对象时，先调用本类的析构函数，然后再调用其基类的构造函数；

3. 题目给出的代码是可以编译的，但会出现运行时错误。错误出现在delete d;这一句。为讨论方便，我们不妨将A类和B类改写如下：

class A
{
public:
    int a;
    ~A()
    {
        cout << "A::~A" << endl;
    }
};

class B : public A
{
public:
    int b;
    virtual ~B()
    {
        cout << "B::~B" << endl;
    }
};

那么A* d = new B();这一句的左边所产生B的对象的内存结构如下：

而A对象的内存结构如下：

可见d只能找到a和A类的析构函数，而无法找到B对象的析构函数，所以当delete d;的时候，B对象所占用的内存就此被泄漏掉了，也从而产生了异常。

如果将A类的析构函数设为虚的，那么A类对象的内存结构将为：

B类对象的内存结构为：

此时通过A* d = new B();，A对象的内存结构中的vfptr，即虚函数表指针，就是B对象的vfptr(B对象的vfptr被bitwise copy，即浅拷贝到A对象的vfptr。如B是从A虚继承而来的，则需要加一个offset，情况要更复杂，见http://blog.csdn.net/pathuang68 /archive/2009/04/24/4105902.aspx)，因此，A对象的vfptr所指向的是B对象的虚函数表，而B的析构函数位于书函数表0的位置，因此，这样就可以通过A类对象的指针d，找到B类对象的析构函数，从而在delete d;时，可以销毁B对象，而不会产生内存泄漏和异常。

事实上，该题目只要将A中的析构函数设成虚的，B类中的析构函数前面的virtual关键字不管是否存在，其析构函数也一定是虚的，C类同此道理。因此，得到结论就是，只要能够保证继承关系中最高的基类的析构函数是虚的，那么就不会产生前面所谈及的问题。这就是为什么在想使用多态特性的时候，需要将基类的析构函数设成虚的真正原因。

sin 2013-10-19 21:36 发表评论

TCP窗口滑动机制

sin — Fri, 18 Oct 2013 13:54:00 GMT

滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的帧的序号，称为接收窗口。发送窗口和接收窗口的序号的上下界不一定要一样，甚至大小也可以不同。不同的滑动窗口协议窗口大小一般不同。发送方窗口内的序列号代表了那些已经被发送，但是还没有被确认的帧，或者是那些可以被发送的帧。下面举一个例子（假设发送窗口尺寸为2，接收窗口尺寸为1）：

①初始态，发送方没有帧发出，发送窗口前后沿相重合。接收方0号窗口打开，等待接收0号帧；
②发送方打开0号窗口，表示已发出0帧但尚确认返回信息。此时接收窗口状态不变；
③发送方打开0、1号窗口，表示0、1号帧均在等待确认之列。至此，发送方打开的窗口数已达规定限度，在未收到新的确认返回帧之前，发送方将暂停发送新的数据帧。接收窗口此时状态仍未变；
④接收方已收到0号帧，0号窗口关闭，1号窗口打开，表示准备接收1号帧。此时发送窗口状态不变；
⑤发送方收到接收方发来的0号帧确认返回信息，关闭0号窗口，表示从重发表中删除0号帧。此时接收窗口状态仍不变；
⑥发送方继续发送2号帧，2号窗口打开，表示2号帧也纳入待确认之列。至此，发送方打开的窗口又已达规定限度，在未收到新的确认返回帧之前，发送方将暂停发送新的数据帧，此时接收窗口状态仍不变；
⑦接收方已收到1号帧，1号窗口关闭，2号窗口打开，表示准备接收2号帧。此时发送窗口状态不变；
⑧发送方收到接收方发来的1号帧收毕的确认信息，关闭1号窗口，表示从重发表中删除1号帧。此时接收窗口状态仍不变。

sin 2013-10-18 21:54 发表评论

Linux内存管理之三页的分配和释放

sin — Sun, 29 Jul 2012 06:44:00 GMT

Linux对内存区内的页框的分配和释放，采用的算法是伙伴系统。

如上图，Linux分配页时，只能分配2^n个页。内核维护MAX_ORDER个链表，每个链表记录着连续的空闲页。第一个链表中的每一项为1个空闲页，第二个链表中的每一项为2个空闲页，第三个链表中的每一项为4个空闲页。。。，依次类推。分配页时，从对应的链表上摘除空闲页；释放页时，将对应的页归还到对应的链表。分配释放页的过程中，可能伴随着内存页的拆分和合并。比如要分配16个空闲页，但是对应的链表为空，这时如果32个空闲页对应的链表如果不为空，则从链表中摘除32个空闲页，并将其一分为二，其中16个页用于内存分配，剩余16个页则插入到16个页对应的链表中。

尽管页的分配算法是简单的，但是实际过程却非常复杂。这是因为分配页式必须考虑一下几点：
1 备用内存区。当从一个内存区无法得到内存时，系统会从同一内存节点的其它内存区或者从另一个内存节点中的内存区中获取内存。
2 页的换入和换出，在没有足够多的空闲页时，可能需要将页换出以获取空闲内存。
3 页的回收，对一些缓冲区的不再使用的页进行回收，以获取空闲页。
4 系统中必须保持一定“水位”的空闲页，以应付对内存的紧急分配。如果系统将页分配完，在急需内存时，再进行页的回收或换出，无疑是非常糟糕的设计。系统中必须保持一定量的内存页。
5 不同的分配策略。不同的分配策略可能采用的方法有区别。
总之，页的分配和释放需要考虑许多因素，尽量满足内存分配的同时，要保证系统的稳定性和健壮性。

sin 2012-07-29 14:44 发表评论

Linux内存管理之二内存节点和内存分区

sin — Sun, 29 Jul 2012 01:38:00 GMT

UMA和NUMA：
UMA(Uniform Memory Access)，即一致性内存访问。这种情况下，CPU访问内存的任何位置，代价都是一样的。
NUMA)(Non Uniform Memory Access)，即非一致性内存访问。这种情况下，CPU访问不同位置的内存，代价是不一样的。在多CPU情况下，对每个CPU来说有本地内存和远端内存，访问本地内存的代价比访问远端内存的代价小。确保CPU访问内存代价最小，是非常重要的一点。

Linux支持多种硬件体系结构，因此Linux必须采用通用的方法来描述内存，以方便对内存进行管理。为此，Linux有了内存节点、内存区、页框的概念，这些概念也是一目了然的。
内存节点：主要依据CPU访问代价的不同而划分。多CPU下环境下，本地内存和远端内存就是不同的节点。即使在单CPU环境下，访问所有内存的代价都是一样的，Linux内核依然存在内存节点的概念，只不过只有一个内存节点而已。内核以struct pg_data_t来描述内存分区。
内存分区：Linux对内存节点再进行划分，分为不同的分区。内核以struct zone来描述内存分区。通常一个节点分为DMA、Normal和High Memory内存区，具体下面再介绍。
页框：Linux采用页式内存管理，页是物理内存管理的基本单位，每个内存分区又由大量的页框组成。内核以struct page来描述页框。页框有很多属性，这些属性描述了这个页框的状态、用途等，例如是否被分配。

上图中的zone_mem_map是一个页框的数组，它记录了一个内存分区的所有页框的使用情况。

DMA内存区：即直接内存访问分区，通常为物理内存的起始16M。主要是供一些外设使用，外设和内存直接访问数据访问，而无需系统CPU的参与。
Normal内存区：从16M到896M内存区。
HighMemory内存区：896M以后的内存区。

为什么高端内存的边界是896M？这是因为，32位Linux虚拟内存空间为0-4G，其中0-3G用于用户态，3G-4G用于内核态。这意味着内核只有1G的虚拟地址空间，如果物理内存超过1G，内核就无法映射了。Linux采取的策略是，内核地址空间的前896M采用固定映射，映射方法是：虚拟地址-3G = 物理地址，只能映射到物理地址的前896M。也就是说内核虚拟地址空间的3G到3G+896M这部分，页表的映射是固定的，系统初始化时就建立起来。而虚拟地址空间的最后128M，也就是3G+896M到4G部分采用动态映射，也就是说页表映射的物理地址可变的。在系统运行过程中，通过更新页表，就可以映射到不同的物理地址，当然也包括高端物理内存。

这主要解决了两个问题：第一，这可以使内核地址空间映射到高端物理内存；第二，虚拟地址空间的3G+896M到4G部分，连续的虚拟地址空间可以映射到非连续的物理内存，只要通过更新页表就可以做到，这和用户态的虚拟内存映射采用了同样这种方法。这在没有大段连续的空闲物理地址时，是非常重要的。

备用内存区：
在一个内存区分配页时，如果这个内存区没有满足条件的内存页，则需要从其它内存区或从其它内存节点分配。Linux为每个内存区都建立了备用内存区列表，当前内存区没有满足条件的内存时，就从备用内存区分配。比如，系统中有4个内存节点A,B,C,D，每个内存节点又分为DMA、Normal、HighMemory内存区。对节点B来说，内存区分配列表可能是B(HighMemory)、B(Normal)、B(DMA)、

A(HighMemory)、A(Normal)、A(DMA)、

C(HighMemory)、C(Normal)、C(DMA)、

D(HighMemory)、D(Normal)、D(DMA)。
分配内存时，优先从本地内存节点分配，再从其它内存节点分配。对一个内存节点，优先从HighMemory分配，再从Normal或DMA分配。

sin 2012-07-29 09:38 发表评论

Linux内存管理之一分段与分页

sin — Thu, 19 Jul 2012 13:22:00 GMT

现代操作系统的内存管理机制有两种：段式管理和页式管理。

段式内存管理，就是将内存分成段，每个段的起始地址就是段基地址。地址映射的时候，由逻辑地址加上段基地址而得到物理地址。纯粹的段式内存管理的缺点很明显，就是灵活性和效率比较差。首先是段的长度是可变的，这给内存的换入换出带来诸多不便，如何选择一个段的长度是一个棘手的问题；其次进程在运行过程中，可能会扩充地址空间，这就要增加段，从而造成进程的地址空间由很多小段构成，在进程运行过程中，访问不同的段时，就需要频繁切换段基地址；再一点，段式内存管理如果有太多的小段，在释放段的时候，会造成外部碎片。

页式内存管理，内存分成固定长度的一个个页片。地址映射的时候，需要先建立页表，页表中的每一项都记录了这个页的基地址。通过页表，由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移一定长度就得到最后的物理地址，偏移的长度由逻辑地址的低位部分决定。一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。

严格说Linux采用段页式内存管理，也就是既分段，又分页。地址映射的时候，先确定对应的段，确定段基地址；段内分页，再找到对应的页表项，确定页基地址；再由逻辑地址低位确定的页偏移量，就能找到最终的物理地址。但是，实际上Linux采用的是页式内存管理。原因是Linux中的段基地址都是0，相当于所有的段都是相同的。这样做的原因是某些体系结构的硬件限制，比如Intel的i386。作为软件的操作系统，必须要符合硬件体系。虽然所有段基地址都是0，但是段的概念在Linux内核中是确实存在的。比如常见的内核代码段、内核数据段、用户态代码段、用户态数据段等。除了符合硬件要求外，段也是有实际意义的。

x86硬件分段单元：

逻辑地址分为两部分组成：段标识符和指定段内相对地址的偏移量。

段描述符：用来存放段起始地址，段大小，存储权限等。
段描述符表：存放段描述的表项。
段寄存器：存放段标识符。6个段寄存器称为cs(代码段寄存器)，ss(栈段寄存器)，ds(数据段寄存器)，es，fs 和gs。
段基地址寄存器：指向段描述符表地址。

Linux分段机制：
Linux对分段使用非常有限。作为一个跨硬件体系的操作系统，要支持多种硬件体系，而一些硬件体系结构式不支持分段的，Linux把所有段起始地址都设为0。
Linux采用4个段进行寻址，用户态代码段，用户态数据段，内核态代码段，内核态数据段。

x86分页单元：

x86采用两级页表。
第一级为页目录表，存储在一个4K字节的页中，每个表项包含了一个页表的物理地址。线性地址最高的10位(22-31)用来产生第一级表索引，由该索引得到的表项中的内容定位了二级表中的一个表的地址，即下级页表所在的内存块号。
第二级为页表，存储在一个4K字节页中，每个表项包含了一个页的物理地址。线性地址的中间10位(12-21)位进行索引，定位页表表项，获得页的物理地址。页物理地址的高20位与线性地址的低12位形成最后的物理地址。

分页机制由CR0寄存器中的PG位启用。如PG=1，启用分页机制，把线性地址转换为物理地址。如PG=0，禁用分页机制，直接段机制产生的线性地址当作物理地址使用。
页目录表的物理地址存放在CR3寄存器。每个进程有它自己的页全局目录和自己的页表集。当发生进程切换时，Linux把CR3控制寄存器的内容保存在前一个执行进程的描述符中，然后把下一个要执行进程的描述符的值装入CR3寄存器中。这确保了当新进程重新开始在CPU上执行时，分页单元指向一组正确的页表。

Linux分页机制：
作为一个通用的操作系统，Linux需要兼容各种硬件体系，包括不同位数的CPU。对64位的CPU来说，两级页表仍然太少，一个页表会太大，这会占用太多宝贵的物理内存。Linux采用了通用的四级页表。实际采用几级页表则具体受硬件的限制。

四种页表分别称为：页全局目录、页上级目录、页中间目录、页表。对于32位x86系统，两级页表已经足够了。Linux通过使“页上级目录”位和“页中间目录”位全为0，彻底取消了页上级目录和页中间目录字段。不过，页上级目录和页中间目录在指针序列中的位置被保留，以便同样的代码在32位系统和64位系统下都能使用。

sin 2012-07-19 21:22 发表评论

二叉树的非递归遍历

sin — Tue, 16 Mar 2010 01:57:00 GMT

这里的二叉树不是一般的二叉树，而是棵二叉查找树。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 128

struct node
{
    int        data;
    struct node*    lchild;
    struct node*    rchild;
};

struct bin_search_tree
{
    struct node*    root;
};

void    init_search_tree(struct bin_search_tree *tree);
void    clear_search_tree(struct bin_search_tree *tree);
void    insert_node(struct bin_search_tree *tree, int element);

void    pre_order(struct node *p);
void    in_order(struct node *p);
void    post_order(struct node *p);

void    visit(struct node *p);

int main()
{
    struct bin_search_tree tree;
    int i,arr[] = {40, 30, 50, 11, 27, 98, 74, 79, 9, 150, 37};

    init_search_tree(&tree);
    for (i=0; i<sizeof(arr)/sizeof(int); i++)
    {
        insert_node(&tree, arr[i]);
    }

    //前序遍历
    pre_order(tree.root);
    printf("\n");

    //中序遍历
    in_order(tree.root);
    printf("\n");

    //后续遍历
    post_order(tree.root);
    printf("\n");

    clear_search_tree(&tree);
    getchar();
    return 0;
}

/*
* 二叉树的初始化
*/
void init_search_tree(struct bin_search_tree *tree)
{
    tree->root = NULL;
}

/*
* 清除二叉树，用二叉树层次遍历
*/
void clear_search_tree(struct bin_search_tree *tree)
{
    int i,j;
    struct node *p,*queue[MAX_SIZE];

    i = j = 0;
    queue[0] = tree->root;

    while (i<=j)
    {
        for ( ; i<=j; i++ )
        {
            p = queue[i];

            if (p->lchild)
                queue[++j] = p->lchild;
            if (p->rchild)
                queue[++j] = p->rchild;
        }
    }

    for (i=0; i<=j; i++)
    {
        free(queue[i]);
    }

    tree->root = NULL;
}

/*
* 二叉树中插入节点element
*/
void insert_node(struct bin_search_tree *tree, int element)
{
    struct node    *p = tree->root;
    struct node *child, *newnode;

    newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = element;
    newnode->lchild = NULL;
    newnode->rchild = NULL;

    if (tree->root == NULL)
    {
        tree->root = newnode;
        return;
    }

    while (p)
    {
        if ( element < p->data )
        {
            child = p->lchild;
            if (NULL == child)
            {
                p->lchild = newnode;
                return;
            }
        }
        else
        {
            child = p->rchild;
            if (NULL == child)
            {
                p->rchild = newnode;
                return;
            }
        }

        p = child;
    }
}

/*
* 前序遍历，非递归
*/
void pre_order(struct node *p)
{
    int top = -1;
    struct node *stack[MAX_SIZE];

    if (p == NULL)
        return;

    stack[++top] = p;
    while (top>-1)
    {
        visit(p=stack[top--]);

        if (p->rchild)
            stack[++top] = p->rchild;
        if (p->lchild)
            stack[++top] = p->lchild;
    }
}

/*
* 中序遍历，非递归
*/
void in_order(struct node *p)
{
    int top = -1;
    struct node *stack[MAX_SIZE];

    while (top>-1 || p!=NULL)
    {
        while (p)
        {
            stack[++top] = p;
            p = p->lchild;
        }
        visit(p=stack[top--]);
        p = p->rchild;
    }
}

/*
* 后序遍历，非递归
*/
void post_order(struct node *p)
{
    int top = -1;
    int flag[MAX_SIZE];
    struct node *stack[MAX_SIZE];

    while (top>-1 || p!= NULL)
    {
        while (p)        //将p的所有左节点压入栈
        {
            stack[++top] = p;
            flag[top] = 0;
            p = p->lchild;
        }

        p = stack[top];    //弹出栈顶
        if (flag[top--]==0 && p->rchild)
        {
            stack[++top] = p;
            flag[top] = 1;
            p = p->rchild;
        }
        else
        {
            visit(p);
            p = NULL;    //将p置为NULL，防止进入while(p)循环
        }
    }
}

/*
* 访问一个节点
*/
void visit(struct node *p)
{
    printf("%d  ", p->data);
}

sin 2010-03-16 09:57 发表评论

WIN32多线程五线程同步机制Semaphore

sin — Sun, 14 Mar 2010 17:22:00 GMT

大学操作系统教材里讲的最多的估计就是信号量Semaphore了，具体就不再介绍了，通常用来处理多线程访问多个资源的情况。
实际上，如果创建一个信号量，并且它的最大计数是1，那么它就与Mutex等价。

下面是个生产者-消费者问题的Win32程序，运行时的截图如下:

代码如下:

/* 生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出；很多计算机问题都可以抽象为生产者-消费者问题。
* 有1个生产者生产商品放到环形buffer中供5个消费者消费；生产者每次最多生产5个商品，消费者每次消费1个。
* 要解决这个问题，我们必须确保:(1)并且当缓冲区中没有商品时，消费者不能消费，缓冲区满时，生产者也不能生产商品 (2)不同消费者  * 不能同时消费同一个商品；
*
* 解决(1)我们用一个生产者信号量表示生产者者资源，即空闲buffer数量；用一个消费者信号量表示消费者资源，即非空闲buffer数量。
* 解决(2)我们用一个互斥量Mutex，得到这个Mutex的消费者才能消费。
*/

#include <time.h>
#include <stdlib.h>
#include <Windows.h>

#define ASSERT(a) if (!(a)) \
    exit(EXIT_FAILURE)

#define MAX_PRODUCE_COUNT    5      //生产者每次最多生产数量
#define CONSUMER_COUNT        5     //消费者数量
#define BUFFER_SIZE        20       //缓冲区大小
#define SLEEP_TIME        600
#define WM_FORCE_PAINT        (WM_APP+10)

void    ProduceAndConsume();
void    EndProduceConsume();

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM) ;  //Win32窗口回调函数

DWORD    WINAPI    ProducerThread(LPVOID pVoid);   //生产者线程函数
DWORD    WINAPI    ConsumerThread(LPVOID pVoid);   //消费者线程函数

int        iProducerPointer;         //生产者指针，指向可以放商品的的位置
int        iConsumerPointer;         //消费者指针，指向可以消费商品的位置
HANDLE        hProducerSemaphore;    //生产者信号量，初始有20个资源
HANDLE        hConsumerSemaphore;    //消费者信号量，初始有0个资源
HANDLE        hConsumerMutex;        //生产者Mutex

HANDLE        hProducerThread;                     //生产者线程，不断生产商品
HANDLE        hConsumersThread[CONSUMER_COUNT];    //消费者线程，不断消费商品
HWND        hWnd;

int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
                    PSTR szCmdLine, int iCmdShow)
{
    static TCHAR szAppName[] = TEXT("生长者消费者") ;
    MSG        msg ;
    WNDCLASS    wndclass ;

    wndclass.style        = CS_HREDRAW | CS_VREDRAW ;
    wndclass.lpfnWndProc  = WndProc ;
    wndclass.cbClsExtra   = 0 ;
    wndclass.cbWndExtra   = 0 ;
    wndclass.hInstance    = hInstance ;
    wndclass.hIcon        = LoadIcon (NULL, IDI_APPLICATION) ;
    wndclass.hCursor      = LoadCursor (NULL, IDC_ARROW) ;
    wndclass.hbrBackground= (HBRUSH) GetStockObject (WHITE_BRUSH) ;
    wndclass.lpszMenuName = NULL ;
    wndclass.lpszClassName= szAppName ;

    if (!RegisterClass (&wndclass))
    {
        MessageBox (  NULL, TEXT ("This program requires Windows NT!"),
            szAppName, MB_ICONERROR) ;
        return 0 ;
    }

    hWnd = CreateWindow( szAppName,
        TEXT ("生长者消费者"),
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        NULL,
        NULL,
        hInstance,
        NULL) ;

    ShowWindow (hWnd, iCmdShow) ;
    UpdateWindow (hWnd) ;

    ProduceAndConsume();      //创建生产者消费者线程、信号量、Mutex，并运行

    while (GetMessage (&msg, NULL, 0, 0))
    {
        TranslateMessage (&msg) ;
        DispatchMessage (&msg) ;
    }

    EndProduceConsume();

    return (int)msg.wParam ;
}

LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    int        iTemp;
    int        iXStart,iYStart;
    HDC             hdc ;
    HBRUSH        hBrush;
    PAINTSTRUCT    ps ;
    RECT        rect;
    MSG        msg;

    switch (message)
    {
    case WM_CREATE:
        return 0 ;

    case WM_FORCE_PAINT:
        InvalidateRect(hWnd, NULL, TRUE);
        while (PeekMessage(&msg, hWnd, WM_FORCE_PAINT, WM_FORCE_PAINT, PM_REMOVE))
            ;
        return 0;

    case  WM_PAINT:
        hdc = BeginPaint (hwnd, &ps) ;

        GetClientRect(hWnd,&rect);
        iXStart = (rect.right-rect.left)/2-200;
        iYStart = (rect.bottom-rect.top)/2-10;
        hBrush = SelectObject(hdc, (HBRUSH)GetStockObject(GRAY_BRUSH));
        iTemp = iConsumerPointer;

        while (TRUE)
        {
            Rectangle(hdc, iXStart+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            if (++iTemp >= BUFFER_SIZE)
                iTemp = 0;
            if (iTemp == iProducerPointer)
                break;
        }

        SelectObject(hdc, hBrush);

        while (TRUE)
        {
            Rectangle(hdc, iXStart+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            if (++iTemp >= BUFFER_SIZE)
                iTemp = 0;
            if (iTemp == iConsumerPointer)
                break;
        }

        EndPaint (hwnd, &ps) ;
        return 0 ;

    case   WM_DESTROY:
        PostQuitMessage (0) ;
        return 0 ;
    }

    return DefWindowProc (hwnd, message, wParam, lParam) ;
}

DWORD WINAPI ProducerThread(LPVOID pVoid)
{
    int        i;
    int        iRandom;

    while (TRUE)
    {
        srand((unsigned)time(NULL));
        iRandom = rand()%MAX_PRODUCE_COUNT;
        if (iRandom == 0)
            iRandom++;

        //生产者申请iRandom个资源
        for (i=0; i<iRandom; i++)
            ASSERT( WAIT_OBJECT_0 == WaitForSingleObject(hProducerSemaphore, INFINITE) );

        //生产者生产iRandom个商品
        iProducerPointer = iProducerPointer+iRandom;
        if (iProducerPointer>=BUFFER_SIZE)
            iProducerPointer = iProducerPointer-BUFFER_SIZE;

        SendMessage(hWnd, WM_FORCE_PAINT, 0, 0);
        Sleep(SLEEP_TIME);

        //生产者生产了iRandom个商品，消费者有更多的商品消费了；所以为消费者释放iRandom个资源
        ASSERT(ReleaseSemaphore(hConsumerSemaphore, (long)iRandom, NULL));
    }

    return 0;
}

DWORD WINAPI ConsumerThread(LPVOID pVoid)
{
    while (TRUE)
    {
        //消费者申请到Semaphore和Mutex后，才能消费
        ASSERT( WAIT_OBJECT_0 == WaitForSingleObject(hConsumerSemaphore, INFINITE) );
        ASSERT( WAIT_OBJECT_0 == WaitForSingleObject(hConsumerMutex, INFINITE) );

        //消费者消费一个商品
        iConsumerPointer++;
        if (iConsumerPointer>=BUFFER_SIZE)
            iConsumerPointer = 0;

        SendMessage(hWnd, WM_FORCE_PAINT, 0, 0);
        Sleep(SLEEP_TIME/2);

        //消费者释放Mutex
        ASSERT(ReleaseMutex(hConsumerMutex));

        //消费者消费了一个商品，buffer中多了一个空闲位置，为生产者释放一个资源
        ASSERT(ReleaseSemaphore(hProducerSemaphore, (long)1, NULL));
    }

    return 0;
}

void ProduceAndConsume()
{
    int        i;
    DWORD    dwThreadID;

    iProducerPointer = 0;
    iConsumerPointer = 0;

    hProducerSemaphore = CreateSemaphore(NULL, BUFFER_SIZE, BUFFER_SIZE, NULL);      //创建生产者信号量，初始有20个资源
    hConsumerSemaphore = CreateSemaphore(NULL, 0, BUFFER_SIZE, NULL);                //创建消费者信号量，初始有0个资源
    hConsumerMutex       = CreateMutex(NULL, FALSE, NULL);                           //创建消费者Mutex

    hProducerThread       = CreateThread(NULL, 0, ProducerThread, NULL, 0, &dwThreadID);
    for (i=0; i<CONSUMER_COUNT; i++)
    {
        hConsumersThread[i] = CreateThread(NULL, 0, ConsumerThread, NULL, 0, &dwThreadID);
    }
}

void EndProduceConsume()
{
    int i;

    ASSERT(CloseHandle(hProducerSemaphore));
    ASSERT(CloseHandle(hConsumerSemaphore));
    ASSERT(CloseHandle(hConsumerMutex));
    ASSERT(CloseHandle(hProducerThread));
    for (i=0; i<CONSUMER_COUNT; i++)
    {
        ASSERT(CloseHandle(hConsumersThread[i]));
    }
}

sin 2010-03-15 01:22 发表评论

常用排序算法实现(C语言)

sin — Fri, 12 Mar 2010 14:02:00 GMT

摘要: 排序算法原理都不难，实现起来却没那么简单，特别是一些边界问题的处理。前些天把这些常有的排序算法实现了一遍，代码写的也不太好，很多i,j,k之类的变量，也很多循环嵌套，不过初步测试是正确的。 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> ... 阅读全文

sin 2010-03-12 22:02 发表评论