Chinaunix首页 | 论坛 | 博客
  • 博客访问: 530491
  • 博文数量: 18
  • 博客积分: 352
  • 博客等级: 二等列兵
  • 技术积分: 770
  • 用 户 组: 普通用户
  • 注册时间: 2011-09-15 15:44
文章分类

全部博文(18)

文章存档

2013年(4)

2012年(1)

2011年(13)

分类: LINUX

2011-09-18 23:18:55

今天用linux的list.h头文件实现了约瑟夫环。
笔者这里使用的办法比较老土。
基本思想:
    第一、本来是要用链表来实现的,但是内核态下,内存的分配;不是很了解。故这里使用了数组元素作为每一个链表的节点。也就是说,这个节点的个数是事先知道的。然后将其链接成一个双向循环链表。
    第二、约瑟夫环的实现原理,就是将n个人站成一个环,并假定从某个人开始编号为1,以后一次编号加一。编号结束之后,选择一个数字m作为跳出的条件,从第一个人开始数,当数到m的人边退出这个环,然后接着从下一个人重新开始数数,直到只剩一个人为止!

源代码如下:
  1.   1 #include <linux/module.h>
  2.   2 #include <linux/init.h>
  3.   3 #include <linux/kernel.h>
  4.   4 #include <linux/list.h>
  5.   5
  6.   6 struct Data{
  7.   7        int data;
  8.   8        struct list_head list;
  9.   9 };
  10.  10 static int __init start_init(void);
  11.  11 static void __exit end_exit(void);
  12.  12
  13.  13 static int __init start_init()
  14.  14 {
  15.  15        struct list_head *q;
  16.  16        struct Data *p;
  17.  17        struct Data data[7];
  18.  18        int i,count;
  19.  19
  20.  20        LIST_HEAD(head);
  21.  21
  22.  22        printk("Start Joesphus...\n");
  23.  23        for(i = 0 ; i < 7 ; i++){
  24.  24               p = &data[i];
  25.  25               p->data = i+1;
  26.  26               list_add_tail(&p->list,&head);
  27.  27  }
  28.  28
  29.  29        q = (&head)->next;
  30.  30        list_del(&head);
  31.  31        count = 1;
  32.  32        while(!list_empty(q)){
  33.  33        for(i = 0 ; i < 2 ; i++)
  34.  34                  q = q->next;
  35.  35        p = container_of(q,struct Data,list);
  36.  36        printk("%d-----%d\n",count,p->data);
  37.  37        count++;
  38.  38        q = q->next;
  39.  39        list_del(&p->list);
  40.  40 }
  41.  41        p = container_of(q,struct Data,list);
  42.  42        printk("%d-----%d\n",count,p->data);

  43.  43        list_del(&p->list);
  44.  44        printk("End Josephus...\n");
  45.  45
  46.  46        return 0;
  47.  47 }
  48.  48 static void __exit end_exit()
  49.  49 {
  50.  50        printk("Exit of this program...\n");
  51.  51 }
  52.  52 module_init(start_init);
  53.  53 module_exit(end_exit);


Makefile文件如下:
  1. 1 ifneq ($(KERNELRELEASE),)
  2.   2 mymodule-objs:= yuesefu.c
  3.   3 obj-m += yuesefu.o
  4.   4
  5.   5 else
  6.   6 PWD :=$(shell pwd)
  7.   7 KVER := $(shell uname -r)
  8.   8 KDIR :=/lib/modules/$(KVER)/build
  9.   9
  10.  10 all:
  11.  11 $(MAKE) -C $(KDIR) M=$(PWD)
  12.  12 clean:
  13.  13 rm -rf *.o *.mod.c *.ko *.symvers *order *.markers *-
  14.  14 endif

关于该Makefile文件的解释,请见笔者的上一篇博文。

执行命令:
  1. [#44#caopeng@laptop:~/kernel]$make
  2. make -C /lib/modules/2.6.32-33-generic/build M=/home/caopeng/kernel
  3. make[1]: 正在进入目录 `/usr/src/linux-headers-2.6.32-33-generic'
  4.   LD /home/caopeng/kernel/built-in.o
  5.   CC [M] /home/caopeng/kernel/yuesefu.o
  6.   Building modules, stage 2.
  7.   MODPOST 1 modules
  8.   CC /home/caopeng/kernel/yuesefu.mod.o
  9.   LD [M] /home/caopeng/kernel/yuesefu.ko
  10. make[1]:正在离开目录 `/usr/src/linux-headers-2.6.32-33-generic'
  11. [#45#caopeng@laptop:~/kernel]$sudo insmod yuesefu.ko
  12. [sudo] password for caopeng:
  13. [#46#caopeng@laptop:~/kernel]$sudo rmmod yuesefu.ko
  14. [#47#caopeng@laptop:~/kernel]$

执行结果可以在/var/log/messages查看到如下结果。

  • [
    #12#caopeng@laptop:~/kernel]$tail /var/log/messages
  • Sep 18 23:39:48 laptop kernel: [ 8676.733067] Start Joesphus...
  • Sep 18 23:39:48 laptop kernel: [ 8676.733069] 1-----3
  • Sep 18 23:39:48 laptop kernel: [ 8676.733071] 2-----6
  • Sep 18 23:39:48 laptop kernel: [ 8676.733072] 3-----2
  • Sep 18 23:39:48 laptop kernel: [ 8676.733073] 4-----7
  • Sep 18 23:39:48 laptop kernel: [ 8676.733075] 5-----5
  • Sep 18 23:39:48 laptop kernel: [ 8676.733076] 6-----1
  • Sep 18 23:39:48 laptop kernel: [ 8676.733077] 7-----4
  • Sep 18 23:39:48 laptop kernel: [ 8676.733078] End Josephus...
  • Sep 18 23:40:03 laptop kernel: [ 8691.687480] Exit of this program...
  • [#13#caopeng@laptop:~/kernel]$



  • 有关list.h的相关知识,请查阅笔者前几篇博文!!


    阅读(5627) | 评论(3) | 转发(1) |
    给主人留下些什么吧!~~

    qinjie68392015-07-28 11:36:40

    怎么不继续写了呢?

    曹朋Code2011-09-19 15:34:15

    sunjiangang-ok: 写得不错啊。.....
    班长过奖拉!!
    我要向您看其!!

    sunjiangang-ok2011-09-19 15:16:32

    写得不错啊。