2006年11月20日

Nagios Addon

APAN:APAN, Advanced Performance Addon for Nagios is a tool for integrating Nagios with RRD-tool. The purpose is to make it easy to collect statistics from different service-checks in Nagios and to view it graphically via a web-interface.
url:http://www.nagiosexchange.org/Charts.42.0.html?&tx_netnagext_pi1[p_view]=116

Linux下软件RAID的实现

作为网络操作系统, 冗余磁盘阵列(Redundant Array of Inexpensive Disks,简称RAID)功能是必备的功能之一。从Linux 2.4内核开始,Linux就提供软件RAID,不必购买昂贵的硬件RAID控制器和附件(一般中、高挡服务器都提供这样的设备和热插拔硬盘),就能极大 地增强Linux磁盘的I/O性能和可靠性。同时,它还具有将多个较小的磁盘空间组合成一个较大磁盘空间的功能。这里的软件RAID不是指在单个物理硬盘 上实现RAID功能。为提高RAID的性能,最好还是使用多个硬盘,使用SCSI接口的硬盘效果会更好。

RAID作用及主要使用类型

RAID 将普通硬盘组成一个磁盘阵列,在主机写入数据时,RAID控制器把主机要写入的数据分解为多个数据块,然后并行写入磁盘阵列;主机读取数据时,RAID控 制器并行读取分散在磁盘阵列中各个硬盘上的数据,把它们重新组合后提供给主机。由于采用并行读写操作,从而提高了存储系统的存取程度。此外,RAID磁盘 阵列更主要的作用是,可以采用镜像、奇偶校验等措施来提高系统的容错能力,保证数据的可靠性。一般在安装Linux操作系统时可以根据需要进行RAID的 安装配置。

在使用Linux操作系统的过程中,也可以根据应用的需要,用手工方法进行RAID的配置。配置前提是必须已经安装 raidtools工具包。该包可以从http://people.redhat.com/mingo/raidtools处下载最新版 raidtools-1.00.3.tar.gz ,然后用root用户解压缩包然后输入以下命令:

# cd raidtools-1.00.3
# ./configure
# make
# make install

这样raidtools-1.00.3就安装好了,从而可以随时安装使用RAID。

在Linux 系统中,主要提供RAID 0、RAID 1、RAID 5三种级别的RAID方法。RAID 0又称为Stripe或Striping,中文译为集带工作方式。它是将要存取的数据以条带状形式尽量平均分配到多个硬盘上,读写时多个硬盘同时进行读 写,从而提高数据的读写速度。RAID 0另一目的是获得更大的“单个”磁盘容量。

RAID 1又称为Mirror或Mirroring,中文译为镜像方式。这种工作方式的出现完全是为了数据安全考虑的,它是把用户写入硬盘的数据百分之百地自动复 制到另外一个硬盘上或硬盘的不同地方(镜像)。当读取数据时,系统先从RAID 1的源盘读取数据,如果读取数据成功,则系统不去管备份盘上的数据;如果读取源盘数据失败,则系统自动转而读取备份盘上的数据,不会造成用户工作任务的中 断。由于对存储的数据进行百分之百的备份,在所有RAID级别中,RAID 1提供最高的数据安全保障。同样,由于数据的百分之百备份,备份数据占了总存储空间的一半,因而,Mirror的磁盘空间利用率低,存储成本高。

RAID 5是一种存储性能、数据安全和存储成本兼顾的存储解决方案,也是目前应用最广泛的RAID技术。各块独立硬盘进行条带化分割,相同的条带区进行奇偶校验 (异或运算),校验数据平均分布在每块硬盘上。以n块硬盘构建的RAID 5阵列可以有n-1块硬盘的容量,存储空间利用率非常高。RAID 5不对存储的数据进行备份,而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上,并且奇偶校验信息和相对应的数据分别存储于不同的磁盘 上。当RAID 5的任何一块硬盘上的数据丢失,均可以通过校验数据推算出来。RAID 5具有数据安全、读写速度快,空间利用率高等优点,应用非常广泛。其不足之处是如果1块硬盘出现故障以后,整个系统的性能将大大降低。RAID 5可以为系统提供数据安全保障,但保障程度要比Mirror低,而磁盘空间利用率要比Mirror高。RAID 5具有和RAID 0相近似的数据读取速度,只是多了一个奇偶校验信息,写入数据的速度比对单个磁盘进行写入操作稍慢。同时由于多个数据对应一个奇偶校验信息,RAID 5的磁盘空间利用率要比RAID 1高,存储成本相对较低。

RAID在Linux下的创建过程

在实际使用过程中,一般都是使用多个单独的磁盘建立RAID,当然也可以使用单个磁盘建立RAID,具体步骤类似。在此,我以使用单个磁盘建立RAID为例进行介绍。

1.以root用户登录

2.使用fdisk工具创建RAID分区

(1)fdisk /dev/hda,这里假定IDE1主接口上的硬盘有剩余空间。

(2)使用命令n创建多个大小相同的新分区,若建立RAID 0或RAID 1分区数至少要大于等于2, RAID 5分区数至少大于等于3。n—起始柱面(可直接按回车)—分区大小;重复以上过程到想创建的RAID分区数为止。结果如下所示:

disk /dev/hda: 240 heads, 63 sectors, 3876 cylinders
Units = cylinders of 15120 * 512 bytes

Device Boot Start End Blocks Id System
/dev/hda1 * 1 1221 9230728+ c Win95 FAT32 (LBA)
/dev/hda2 1222 1229 60480 83 Linux
/dev/hda3 1230 1906 5118120 83 Linux
/dev/hda4 1907 3876 14893200 f Win95 Ext’d (LBA)
/dev/hda5 1907 1960 408208+ 82 Linux swap
/dev/hda6 1961 2231 2048728+ b Win95 FAT32
/dev/hda7 2709 3386 5125648+ b Win95 FAT32
/dev/hda8 3387 3876 3704368+ 7 HPFS/NTFS
/dev/hda9 2232 2245 105808+ 83 Linux
/dev/hda10 2246 2259 105808+ 83 Linux
/dev/hda11 2260 2273 105808+ 83 Linux
/dev/hda12 2274 2287 105808+ 83 Linux

使用n命令创建4个Linux分区后,用命令p显示分区情况。这里/dev/hda9、/dev/hda10、/dev/hda11、/dev/hda12为创建的4个Linux分区。

(3)使用命令t改变分区类型为software raid类型。t—分区号—fd(分区类型);重复以上过程。修改分区类型后如下所示:

/dev/hda9 2232 2245 105808+ fd Linux raid autodetect
/dev/hda10 2246 2259 105808+ fd Linux raid autodetect
/dev/hda11 2260 2273 105808+ fd Linux raid autodetect
/dev/hda12 2274 2287 105808+ fd Linux raid autodetect

(4)使用命令w保存分区表。

3.重新启动使分区表生效

4.使用man raidtab查看配置文件结构

5.使用编辑命令将配置文件内容写入 /etc/raidtab

如下所示:

raiddev /dev/md0
raid-level 5
nr-raid-disks 3
nr-spare-disks 1
persistent-superblock 1
parity-algorithm left-symmetric
chunk-size 8

device /dev/hda9
raid-disk 0
device /dev/hda10
raid-disk 1
device /dev/hda11
raid-disk 2
device /dev/hda12
spare-disk 0

这 里创建RAID-5,使用3个RAID磁盘,1个备用磁盘。注意“chunk-size 8”一句不能少,指定RAID-5使用的块大小为8KB。RAID-5卷会以8KB的块写入其组成分区,即RAID卷的第一个8KB在hda9上,第二个 8KB在hda10上,依此类推。设备名可为md0或md1等。“spare-disk”磁盘主要起备用作用,一旦某一磁盘损坏可以立即顶上,这里也可以 不要。

6.使用mkraid /dev/md0创建RAID阵列

这里md表示创建的是RAID磁盘类型。结果如下所示:

[root@localhost root]# mkraid /dev/md0
handling MD device /dev/md0
analyzing super-block
disk 0: /dev/hda9, 105808kB, raid superblock at 105728kB
disk 1: /dev/hda10, 105808kB, raid superblock at 105728kB
disk 2: /dev/hda11, 105808kB, raid superblock at 105728kB
disk 3: /dev/hda12, 105808kB, raid superblock at 105728kB
md0: WARNING: hda10 appears to be on the same physical disk as hda9. True
protection against single-disk failure might be compromised.
md0: WARNING: hda11 appears to be on the same physical disk as hda10. True
protection against single-disk failure might be compromised.
md0: WARNING: hda12 appears to be on the same physical disk as hda11. True
protection against single-disk failure might be compromised.
md: md0: RAID array is not clean — starting background reconstruction
8regs : 2206.800 MB/sec
32regs : 1025.200 MB/sec
pII_mmx : 2658.400 MB/sec
p5_mmx : 2818.400 MB/sec
raid5: using function: p5_mmx (2818.400 MB/sec)
raid5: raid level 5 set md0 active with 3 out of 3 devices, algorithm 2

7.使用 lsraid -a /dev/md0 查看RAID分区状况

结果如下所示:

[root@localhost root]# lsraid -a /dev/md0
[dev 9, 0] /dev/md0 86391738.19BEDD09.8F02C37B.51584DBA online
[dev 3, 9] /dev/hda9 86391738.19BEDD09.8F02C37B.51584DBA good
[dev 3, 10] /dev/hda10 86391738.19BEDD09.8F02C37B.51584DBA good
[dev 3, 11] /dev/hda11 86391738.19BEDD09.8F02C37B.51584DBA good
[dev 3, 12] /dev/hda12 86391738.19BEDD09.8F02C37B.51584DBA spare

8.mkfs.ext3/dev/md0将RAID分区格式化为ext3格式

结果如下所示:

[root@localhost root]# mkfs.ext3 /dev/md0
mke2fs 1.27 (8-Mar-2002)
Filesystem label=
OS type: Linux
Block size=1024 (log=0)
Fragment size=1024 (log=0)
53040 inodes, 211456 blocks
10572 blocks (5.00%) reserved for the super user
First data block=1
26 block groups
8192 blocks per group, 8192 fragments per group
2040 inodes per group
Superblock backups stored on blocks:
8193, 24577, 40961, 57345, 73729, 204801

raid5: switching cache buffer size, 4096 –> 1024
Writing inode tables: done
Creating journal (4096 blocks): done
Writing superblocks and filesystem accounting information:
done

This filesystem will be automatically checked every 22 mounts or
180 days, whichever comes first. Use tune2fs -c or -i to override.

9.mount /dev/md0 /mnt/md0

这里应首先在mnt目录下创建md0子目录。

至此,所有创建工作完成,md0目录就成为具有RAID作用的一个目录。

检验RAID的效果

我们可以使用以下步骤检验RAID的效果。

1.dd if=/dev/zero of=/dev/hda9 bs=100000000 count=10

将RAID的第一个磁盘分区hda9全部置0;bs表示一次写多少位,count表示写多少次。这里一定要使写入的数据大于磁盘分区的容量,否则由于RAID的作用,数据会自动恢复原有值。如下所示:

[root@localhost root]
# dd if=/dev/zero of=/dev/hda9 bs=100000000 count=10
dd: writing `/dev/hda9′: No space left on device
2+0 records in
1+0 records out

2.用lsraid -a /dev/md0查看到/dev/hda9数据全为0

如下所示:

[root@localhost root]# lsraid -a /dev/md0
lsraid: Device "/dev/hda9" does not have a valid raid superblock
lsraid: Device "/dev/hda9" does not have a valid raid superblock
lsraid: Device "/dev/hda9" does not have a valid raid superblock
lsraid: Device "/dev/hda9" does not have a valid raid superblock
[dev 9, 0] /dev/md0 86391738.19BEDD09.8F02C37B.51584DBA online
[dev ?, ?] (unknown) 00000000.00000000.00000000.00000000 missing
[dev 3, 10] /dev/hda10 86391738.19BEDD09.8F02C37B.51584DBA good
[dev 3, 11] /dev/hda11 86391738.19BEDD09.8F02C37B.51584DBA good
[dev 3, 12] /dev/hda12 86391738.19BEDD09.8F02C37B.51584DBA spare

3.raidstop /dev/md0

4.raidstart /dev/md0

则/dev/hda9的数据恢复正常,说明RAID的数据校验功能已起作用。

在使用Linux的过程中,可以随时创建RAID来提高数据的可靠性和I/O性能,甚至可以将多个硬盘剩余的较小空间组合成一个较大空间。

2005年11月25日
农历8月16是偶的生日,HOHO,自己先庆祝下先。偶是农村来的,过的都是农历生日啦,公司每次都在公历的那天发生日礼物给我,其实不是我的生日啦。其实也没什么,我又不是什么大人物,哪天过生日还不是一样。哈哈。想想上大学的时候,偶们寝室的兄弟们把生日表排在门后面,到了差不多有兄弟生日的时候大家就开始兴奋了,要为兄弟过生日嘛,其实也就是找一出去吃喝买醉的借口。往往那个时候经常就会有人提议把生日提前过了吧,先吃先喝为上,而往往这也会得到大家的赞同。那时候真好,一大桌的兄弟,喝啊!毕业都散了,在北京就偶和廖批还有小古,过生日的时候也就冷冷清清的三个人喝上几杯,顶多也就多一两个无关紧要的人,还是好怀念大家一起在学校喝酒的日子。来,我敬大家一杯(常德话,这可是有典故的,HOHO)!
昨天又喝多了,现在头还痛得厉害!真是自己找罪受,喝的时候为什么就不这样想呢,一杯一杯的喝啊,好像自己是个酒桶喝少了会吃亏似的,唉!不过想想,这一个多月来周末都没有清醒过了,好像都是醉着过日子的,我昏厥!嗯,以后要少喝点酒了,小喝一点点就可以了。身体重要啊!
这么久的生活还是没有什么变化,仍然是上班下班,晚上看看书看看代码看看碟。只是有一点小小的变化。上次去图书城,看到了那本曾听说过很有名的《达.芬奇的密码》,于是就买了本回来。很久没有看纸版的书了,晚上洗完澡,关了电脑,躺在床上打开台灯静静的看会书也是一种享受。
公司看起来很不平静,上面好像斗争的非常厉害哦。靠,公司是越来越没前途了,唉。两年了,多少有点感情,现在我想该是走的时候了,何去何从呢。。。。。。
周未去和同事们一起玩球,赌晚餐,我们胜了。晚上又一起玩麻将,哈哈,我这个最不会玩的新手居然胜的最多,HOHO。不会是看我新手故意让我打的费的吧,哈哈。
今天看了李开复的一些文章,他说,做程序员的不要老是去学那些皮毛语言,要多看看操作系、数据结构、数据库这些东西,还说要多写写代码。嗯,有道理,语言这东西只要你有思想很快就可以学会的,我也是这样想的。HOHO。
这么久老是感觉时间安排的不好,一天到晚下来感觉都没个准,也不知道干了些什么东西,学习也没个计划,是要每天定好计划才行。
HOHO,看起来,我生活感悟还是太差,这么久才写一次都没写出什么东西来,就像写个流水帐似的,我想说,其实我的感悟也是很非富的,哈哈,只是表达不出来。以后多练练笔。
2005年11月24日
发贴心情

程序之美”-百度之星程序设计大赛 – 题目

第一题(共四题100分):连续正整数(10分)
   题目描述:
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
    15=1+2+3+4+5
    15=4+5+6
    15=7+8
    请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。
   输入数据:
一个正整数,以命令行参数的形式提供给程序。
   输出数据:

标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列,按各序
列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列,输出“NONE”。
    例如,对于15,其输出结果是:
    1 2 3 4 5
    4 5 6
    7 8
    对于16,其输出结果是:
    NONE

   评分标准:
程序输出结果是否正确。
   第二题(共四题100分):重叠区间大小(20分)
   题目描述:
请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。
    对一个正整数n,如果n在数据文件中某行的两个正整数(假设为A和B)之间,即A<=n<=B或A>=n>=B,则n属于该行;如果n同时属于行i和j,则i和j有重叠区间;重叠区间的大小是同时属于行i和j的整数个数。
    例如,行(10 20)和(12 25)的重叠区间为[12 20],其大小为9;行(20 10)和(12 18)的重叠区间为[10 12],其大小为3;行(20 10)和(20 30)的重叠区间大小为1。
   输入数据:

序读入已被命名为input.txt的输入数据文本文件,该文件的行数在1到1,000,000之间,每行有用一个空格分隔的2个正整数,这2个正整数的
大小次序随机,每个数都在1和2^32-1之间。(为便于调试,您可下载测试input.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出0。
   评分标准:
程序输出结果必须正确,内存使用必须不超过256MB,程序的执行时间越快越好。
   第三题(共四题100分):字符串替换(30分)
   题目描述:
请编写程序,根据指定的对应关系,把一个文本中的字符串替换成另外的字符串。
   输入数据:

序读入已被命名为text.txt和dict.txt的两个输入数据文本文件,text.txt为一个包含大量字符串(含中文)的文本,以
whitespace为分隔符;dict.txt为表示字符串(s1)与字符串(s2)的对应关系的另一个文本(含中文),大约在1万行左右,每行两个字
符串(即s1和s2),用一个\t或空格分隔。dict.txt中各行的s1没有排序,并有可能有重复,这时以最后出现的那次s1所对应的s2为准。
text.txt和dict.txt中的每个字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必须和dict.txt
中的某s1完全匹配才能被替换。(为便于调试,您可下载测试text.txt和dict.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印text.txt被dict.txt替换后了的整个文本。
   评分标准:
程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。
  第四题(共四题100分):低频词过滤(40分)
   题目描述:
请编写程序,从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数,则将这些单词都删除。
   输入数据:
程序读入已被命名为corpus.txt的一个大数据量的文本文件,该文件包含英文单词和中文单词,词与词之间以一个或多个whitespace分隔。(为便于调试,您可下载测试corpus.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印删除了corpus.txt中出现次数最少的单词之后的文本(词与词保持原来的顺序,仍以空格分隔)。
   评分标准:
程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。

Linux下的多线程编程


作者:姚继锋 2001-08-11 09:05:00 来自:http://www.china-pub.com

1 引言
 
 线程(thread)技术早在60年代就被提出,但真正应用多线程到操作系统中去,是在80年代中期,solaris是这方面的佼佼者。传统的Unix
也支持线程的概念,但是在一个进程(process)中只允许有一个线程,这样多线程就意味着多进程。现在,多线程技术已经被许多操作系统所支持,包括
Windows/NT,当然,也包括Linux。
  为什么有了进程的概念后,还要再引入线程呢?使用多线程到底有哪些好处?什么的系统应该选用多线程?我们首先必须回答这些问题。
 
 使用多线程的理由之一是和进程相比,它是一种非常"节俭"的多任务操作方式。我们知道,在Linux系统下,启动一个新的进程必须分配给它独立的地址空
间,建立众多的数据表来维护它的代码段、堆栈段和数据段,这是一种"昂贵"的多任务工作方式。而运行于一个进程中的多个线程,它们彼此之间使用相同的地址
空间,共享大部分数据,启动一个线程所花费的空间远远小于启动一个进程所花费的空间,而且,线程间彼此切换所需的时间也远远小于进程间切换所需要的时间。
据统计,总的说来桓鼋痰目笤际且桓鱿叱炭?0倍左右,当然,在具体的系统上,这个数据可能会有较大的区别。
  使用多线程的理由之二
是线程间方便的通信机制。对不同进程来说,它们具有独立的数据空间,要进行数据的传递只能通过通信的方式进行,这种方式不仅费时,而且很不方便。线程则不
然,由于同一进程下的线程之间共享数据空间,所以一个线程的数据可以直接为其它线程所用,这不仅快捷,而且方便。当然,数据的共享也带来其他一些问题,有
的变量不能同时被两个线程所修改,有的子程序中声明为static的数据更有可能给多线程程序带来灾难性的打击,这些正是编写多线程程序时最需要注意的地
方。
  除了以上所说的优点外,不和进程比较,多线程程序作为一种多任务、并发的工作方式,当然有以下的优点:
  1) 提高应用程序响应。这对图形界面的程序尤其有意义,当一个操作耗时很长时,整个系统都会等待这个操作,此时程序不会响应键盘、鼠标、菜单的操作,而使用多线程技术,将耗时长的操作(time consuming)置于一个新的线程,可以避免这种尴尬的情况。
  2) 使多CPU系统更加有效。操作系统会保证当线程数不大于CPU数目时,不同的线程运行于不同的CPU上。
  3) 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程,成为几个独立或半独立的运行部分,这样的程序会利于理解和修改。
  下面我们先来尝试编写一个简单的多线程程序。

2 简单的多线程编程
 
 Linux系统下的多线程遵循POSIX线程接口,称为pthread。编写Linux下的多线程程序,需要使用头文件pthread.h,连接时需要
使用库libpthread.a。顺便说一下,Linux下pthread的实现是通过系统调用clone()来实现的。clone()是Linux所特
有的系统调用,它的使用方式类似fork,关于clone()的详细情况,有兴趣的读者可以去查看有关文档说明。下面我们展示一个最简单的多线程程序
example1.c。

/* example.c*/
#include <stdio.h>
#include <pthread.h>
void thread(void)
{
int i;
for(i=0;i<3;i++)
printf("This is a pthread.\n");
}

int main(void)
{
pthread_t id;
int i,ret;
ret=pthread_create(&id,NULL,(void *) thread,NULL);
if(ret!=0){
printf ("Create pthread error!\n");
exit (1);
}
for(i=0;i<3;i++)
printf("This is the main process.\n");
pthread_join(id,NULL);
return (0);
}

我们编译此程序:
gcc example1.c -lpthread -o example1
运行example1,我们得到如下结果:
This is the main process.
This is a pthread.
This is the main process.
This is the main process.
This is a pthread.
This is a pthread.
再次运行,我们可能得到如下结果:
This is a pthread.
This is the main process.
This is a pthread.
This is the main process.
This is a pthread.
This is the main process.

  前后两次结果不一样,这是两个线程争夺CPU资源的结果。上面的示例中,我们使用到了两个函数,  pthread_create和pthread_join,并声明了一个pthread_t型的变量。
  pthread_t在头文件/usr/include/bits/pthreadtypes.h中定义:
  typedef unsigned long int pthread_t;
  它是一个线程的标识符。函数pthread_create用来创建一个线程,它的原型为:
  extern int pthread_create __P ((pthread_t *__thread, __const pthread_attr_t *__attr,
  void *(*__start_routine) (void *), void *__arg));
 
 第一个参数为指向线程标识符的指针,第二个参数用来设置线程属性,第三个参数是线程运行函数的起始地址,最后一个参数是运行函数的参数。这里,我们的函
数thread不需要参数,所以最后一个参数设为空指针。第二个参数我们也设为空指针,这样将生成默认属性的线程。对线程属性的设定和修改我们将在下一节
阐述。当创建线程成功时,函数返回0,若不为0则说明创建线程失败,常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程,例
如线程数目过多了;后者表示第二个参数代表的线程属性值非法。创建线程成功后,新创建的线程则运行参数三和参数四确定的函数,原来的线程则继续运行下一行
代码。
  函数pthread_join用来等待一个线程的结束。函数原型为:
  extern int pthread_join __P ((pthread_t __th, void **__thread_return));
 
 第一个参数为被等待的线程标识符,第二个参数为一个用户定义的指针,它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数,调用它的函数将
一直等待到被等待的线程结束为止,当函数返回时,被等待线程的资源被收回。一个线程的结束有两种途径,一种是象我们上面的例子一样,函数结束了,调用它的
线程也就结束了;另一种方式是通过函数pthread_exit来实现。它的函数原型为:
  extern void pthread_exit __P ((void *__retval)) __attribute__ ((__noreturn__));
 
 唯一的参数是函数的返回代码,只要pthread_join中的第二个参数thread_return不是NULL,这个值将被传递给
thread_return。最后要说明的是,一个线程不能被多个线程等待,否则第一个接收到信号的线程成功返回,其余调用pthread_join的线
程则返回错误代码ESRCH。
  在这一节里,我们编写了一个最简单的线程,并掌握了最常用的三个函数pthread_create,pthread_join和pthread_exit。下面,我们来了解线程的一些常用属性以及如何设置这些属性。

3 修改线程的属性
  在上一节的例子里,我们用pthread_create函数创建了一个线程,在这个线程中,我们使用了默认参数,即将该函数的第二个参数设为NULL。的确,对大多数程序来说,使用默认属性就够了,但我们还是有必要来了解一下线程的有关属性。
 
 属性结构为pthread_attr_t,它同样在头文件/usr/include/pthread.h中定义,喜欢追根问底的人可以自己去查看。属性
值不能直接设置,须使用相关函数进行操作,初始化的函数为pthread_attr_init,这个函数必须在pthread_create函数之前调
用。属性对象主要包括是否绑定、是否分离、堆栈地址、堆栈大小、优先级。默认的属性为非绑定、非分离、缺省1M的堆栈、与父进程同样级别的优先级。
 
 关于线程的绑定,牵涉到另外一个概念:轻进程(LWP:Light Weight
Process)。轻进程可以理解为内核线程,它位于用户层和系统层之间。系统对线程资源的分配、对线程的控制是通过轻进程来实现的,一个轻进程可以控制
一个或多个线程。默认状况下,启动多少轻进程、哪些轻进程来控制哪些线程是由系统来控制的,这种状况即称为非绑定的。绑定状况下,则顾名思义,即某个线程
固定的"绑"在一个轻进程之上。被绑定的线程具有较高的响应速度,这是因为CPU时间片的调度是面向轻进程的,绑定的线程可以保证在需要的时候它总有一个
轻进程可用。通过设置被绑定的轻进程的优先级和调度级可以使得绑定的线程满足诸如实时反应之类的要求。
  设置线程绑定状态的函数为
pthread_attr_setscope,它有两个参数,第一个是指向属性结构的指针,第二个是绑定类型,它有两个取值:
PTHREAD_SCOPE_SYSTEM(绑定的)和PTHREAD_SCOPE_PROCESS(非绑定的)。下面的代码即创建了一个绑定的线程。
#include <pthread.h>
pthread_attr_t attr;
pthread_t tid;

/*初始化属性值,均设为默认值*/
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

pthread_create(&tid, &attr, (void *) my_function, NULL);

 
 线程的分离状态决定一个线程以什么样的方式来终止自己。在上面的例子中,我们采用了线程的默认属性,即为非分离状态,这种情况下,原有的线程等待创建的
线程结束。只有当pthread_join()函数返回时,创建的线程才算终止,才能释放自己占用的系统资源。而分离线程不是这样子的,它没有被其他的线
程所等待,自己运行结束了,线程也就终止了,马上释放系统资源。程序员应该根据自己的需要,选择适当的分离状态。设置线程分离状态的函数为
pthread_attr_setdetachstate(pthread_attr_t *attr, int
detachstate)。第二个参数可选为PTHREAD_CREATE_DETACHED(分离线程)和 PTHREAD
_CREATE_JOINABLE(非分离线程)。这里要注意的一点是,如果设置一个线程为分离线程,而这个线程运行又非常快,它很可能在
pthread_create函数返回之前就终止了,它终止以后就可能将线程号和系统资源移交给其他的线程使用,这样调用pthread_create的
线程就得到了错误的线程号。要避免这种情况可以采取一定的同步措施,最简单的方法之一是可以在被创建的线程里调用
pthread_cond_timewait函数,让这个线程等待一会儿,留出足够的时间让函数pthread_create返回。设置一段等待时间,是
在多线程编程里常用的方法。但是注意不要使用诸如wait()之类的函数,它们是使整个进程睡眠,并不能解决线程同步的问题。
  另外一个可能常
用的属性是线程的优先级,它存放在结构sched_param中。用函数pthread_attr_getschedparam和函数
pthread_attr_setschedparam进行存放,一般说来,我们总是先取优先级,对取得的值修改后再存放回去。下面即是一段简单的例子。
#include <pthread.h>
#include <sched.h>
pthread_attr_t attr;
pthread_t tid;
sched_param param;
int newprio=20;

pthread_attr_init(&attr);
pthread_attr_getschedparam(&attr, &param);
param.sched_priority=newprio;
pthread_attr_setschedparam(&attr, &param);
pthread_create(&tid, &attr, (void *)myfunction, myarg);
  
4 线程的数据处理
 
 和进程相比,线程的最大优点之一是数据的共享性,各个进程共享父进程处沿袭的数据段,可以方便的获得、修改数据。但这也给多线程编程带来了许多问题。我
们必须当心有多个不同的进程访问相同的变量。许多函数是不可重入的,即同时不能运行一个函数的多个拷贝(除非使用不同的数据段)。在函数中声明的静态变量
常常带来问题,函数的返回值也会有问题。因为如果返回的是函数内部静态声明的空间的地址,则在一个线程调用该函数得到地址后使用该地址指向的数据时,别的
线程可能调用此函数并修改了这一段数据。在进程中共享的变量必须用关键字volatile来定义,这是为了防止编译器在优化时(如gcc中使用-OX参
数)改变它们的使用方式。为了保护变量,我们必须使用信号量、互斥等方法来保证我们对变量的正确使用。下面,我们就逐步介绍处理线程数据时的有关知识。

4.1 线程数据
 
 在单线程的程序里,有两种基本的数据:全局变量和局部变量。但在多线程程序里,还有第三种数据类型:线程数据(TSD:
Thread-Specific
Data)。它和全局变量很象,在线程内部,各个函数可以象使用全局变量一样调用它,但它对线程外部的其它线程是不可见的。这种数据的必要性是显而易见
的。例如我们常见的变量errno,它返回标准的出错信息。它显然不能是一个局部变量,几乎每个函数都应该可以调用它;但它又不能是一个全局变量,否则在
A线程里输出的很可能是B线程的出错信息。要实现诸如此类的变量,我们就必须使用线程数据。我们为每个线程数据创建一个键,它和这个键相关联,在各个线程
里,都使用这个键来指代线程数据,但在不同的线程里,这个键代表的数据是不同的,在同一个线程里,它代表同样的数据内容。
  和线程数据相关的函数主要有4个:创建一个键;为一个键指定线程数据;从一个键读取线程数据;删除键。
  创建键的函数原型为:
  extern int pthread_key_create __P ((pthread_key_t *__key,
  void (*__destr_function) (void *)));
 
 第一个参数为指向一个键值的指针,第二个参数指明了一个destructor函数,如果这个参数不为空,那么当每个线程结束时,系统将调用这个函数来释
放绑定在这个键上的内存块。这个函数常和函数pthread_once ((pthread_once_t*once_control, void
(*initroutine)
(void)))一起使用,为了让这个键只被创建一次。函数pthread_once声明一个初始化函数,第一次调用pthread_once时它执行这
个函数,以后的调用将被它忽略。

  在下面的例子中,我们创建一个键,并将它和某个数据相关联。我们要定义一个函数
createWindow,这个函数定义一个图形窗口(数据类型为Fl_Window
*,这是图形界面开发工具FLTK中的数据类型)。由于各个线程都会调用这个函数,所以我们使用线程数据。
/* 声明一个键*/
pthread_key_t myWinKey;
/* 函数 createWindow */
void createWindow ( void ) {
Fl_Window * win;
static pthread_once_t once= PTHREAD_ONCE_INIT;
/* 调用函数createMyKey,创建键*/
pthread_once ( & once, createMyKey) ;
/*win指向一个新建立的窗口*/
win=new Fl_Window( 0, 0, 100, 100, "MyWindow");
/* 对此窗口作一些可能的设置工作,如大小、位置、名称等*/
setWindow(win);
/* 将窗口指针值绑定在键myWinKey上*/
pthread_setpecific ( myWinKey, win);
}

/* 函数 createMyKey,创建一个键,并指定了destructor */
void createMyKey ( void ) {
pthread_keycreate(&myWinKey, freeWinKey);
}

/* 函数 freeWinKey,释放空间*/
void freeWinKey ( Fl_Window * win){
delete win;
}

 
 这样,在不同的线程中调用函数createMyWin,都可以得到在线程内部均可见的窗口变量,这个变量通过函数
pthread_getspecific得到。在上面的例子中,我们已经使用了函数pthread_setspecific来将线程数据和一个键绑定在一
起。这两个函数的原型如下:
  extern int pthread_setspecific __P ((pthread_key_t __key,__const void *__pointer));
  extern void *pthread_getspecific __P ((pthread_key_t __key));
 
 这两个函数的参数意义和使用方法是显而易见的。要注意的是,用pthread_setspecific为一个键指定新的线程数据时,必须自己释放原有的
线程数据以回收空间。这个过程函数pthread_key_delete用来删除一个键,这个键占用的内存将被释放,但同样要注意的是,它只释放键占用的
内存,并不释放该键关联的线程数据所占用的内存资源,而且它也不会触发函数pthread_key_create中定义的destructor函数。线程
数据的释放必须在释放键之前完成。

4.2 互斥锁
  互斥锁用来保证一段时间内只有一个线程在执行一段代码。必要性显而易见:假设各个线程向同一个文件顺序写入数据,最后得到的结果一定是灾难性的。
  我们先看下面一段代码。这是一个读/写程序,它们公用一个缓冲区,并且我们假定一个缓冲区只能保存一条信息。即缓冲区只有两个状态:有信息或没有信息。

void reader_function ( void );
void writer_function ( void );

char buffer;
int buffer_has_item=0;
pthread_mutex_t mutex;
struct timespec delay;
void main ( void ){
pthread_t reader;
/* 定义延迟时间*/
delay.tv_sec = 2;
delay.tv_nec = 0;
/* 用默认属性初始化一个互斥锁对象*/
pthread_mutex_init (&mutex,NULL);
pthread_create(&reader, pthread_attr_default, (void *)&reader_function), NULL);
writer_function( );
}

void writer_function (void){
while(1){
/* 锁定互斥锁*/
pthread_mutex_lock (&mutex);
if (buffer_has_item==0){
buffer=make_new_item( );
buffer_has_item=1;
}
/* 打开互斥锁*/
pthread_mutex_unlock(&mutex);
pthread_delay_np(&delay);
}
}

void reader_function(void){
while(1){
pthread_mutex_lock(&mutex);
if(buffer_has_item==1){
consume_item(buffer);
buffer_has_item=0;
}
pthread_mutex_unlock(&mutex);
pthread_delay_np(&delay);
}
}
 
 这里声明了互斥锁变量mutex,结构pthread_mutex_t为不公开的数据类型,其中包含一个系统分配的属性对象。函数
pthread_mutex_init用来生成一个互斥锁。NULL参数表明使用默认属性。如果需要声明特定属性的互斥锁,须调用函数
pthread_mutexattr_init。函数pthread_mutexattr_setpshared和函数
pthread_mutexattr_settype用来设置互斥锁属性。前一个函数设置属性pshared,它有两个取值,
PTHREAD_PROCESS_PRIVATE和PTHREAD_PROCESS_SHARED。前者用来不同进程中的线程同步,后者用于同步本进程的
不同线程。在上面的例子中,我们使用的是默认属性PTHREAD_PROCESS_
PRIVATE。后者用来设置互斥锁类型,可选的类型有PTHREAD_MUTEX_NORMAL、PTHREAD_MUTEX_ERRORCHECK、
PTHREAD_MUTEX_RECURSIVE和PTHREAD
_MUTEX_DEFAULT。它们分别定义了不同的上所、解锁机制,一般情况下,选用最后一个默认属性。
  
pthread_mutex_lock声明开始用互斥锁上锁,此后的代码直至调用pthread_mutex_unlock为止,均被上锁,即同一时间只
能被一个线程调用执行。当一个线程执行到pthread_mutex_lock处时,如果该锁此时被另一个线程使用,那此线程被阻塞,即程序将等待到另一
个线程释放此互斥锁。在上面的例子中,我们使用了pthread_delay_np函数,让线程睡眠一段时间,就是为了防止一个线程始终占据此函数。
 
 上面的例子非常简单,就不再介绍了,需要提出的是在使用互斥锁的过程中很有可能会出现死锁:两个线程试图同时占用两个资源,并按不同的次序锁定相应的互
斥锁,例如两个线程都需要锁定互斥锁1和互斥锁2,a线程先锁定互斥锁1,b线程先锁定互斥锁2,这时就出现了死锁。此时我们可以使用函数
pthread_mutex_trylock,它是函数pthread_mutex_lock的非阻塞版本,当它发现死锁不可避免时,它会返回相应的信
息,程序员可以针对死锁做出相应的处理。另外不同的互斥锁类型对死锁的处理不一样,但最主要的还是要程序员自己在程序设计注意这一点。

4.3 条件变量
 
 前一节中我们讲述了如何使用互斥锁来实现线程间数据的共享和通信,互斥锁一个明显的缺点是它只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和
等待另一个线程发送信号的方法弥补了互斥锁的不足,它常和互斥锁一起使用。使用时,条件变量被用来阻塞一个线程,当条件不满足时,线程往往解开相应的互斥
锁并等待条件发生变化。一旦其它的某个线程改变了条件变量,它将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。这些线程将重新锁定互斥锁并
重新测试条件是否满足。一般说来,条件变量被用来进行线承间的同步。
  条件变量的结构为pthread_cond_t,函数pthread_cond_init()被用来初始化一个条件变量。它的原型为:
  extern int pthread_cond_init __P ((pthread_cond_t *__cond,__const pthread_condattr_t *__cond_attr));
 
 其中cond是一个指向结构pthread_cond_t的指针,cond_attr是一个指向结构pthread_condattr_t的指针。结构
pthread_condattr_t是条件变量的属性结构,和互斥锁一样我们可以用它来设置条件变量是进程内可用还是进程间可用,默认值是
PTHREAD_
PROCESS_PRIVATE,即此条件变量被同一进程内的各个线程使用。注意初始化条件变量只有未被使用时才能重新初始化或被释放。释放一个条件变量
的函数为pthread_cond_ destroy(pthread_cond_t cond)。 
  函数pthread_cond_wait()使线程阻塞在一个条件变量上。它的函数原型为:
  extern int pthread_cond_wait __P ((pthread_cond_t *__cond,
  pthread_mutex_t *__mutex));
 
 线程解开mutex指向的锁并被条件变量cond阻塞。线程可以被函数pthread_cond_signal和函数
pthread_cond_broadcast唤醒,但是要注意的是,条件变量只是起阻塞和唤醒线程的作用,具体的判断条件还需用户给出,例如一个变量是
否为0等等,这一点我们从后面的例子中可以看到。线程被唤醒后,它将重新检查判断条件是否满足,如果还不满足,一般说来线程应该仍阻塞在这里,被等待被下
一次唤醒。这个过程一般用while语句实现。
  另一个用来阻塞线程的函数是pthread_cond_timedwait(),它的原型为:
  extern int pthread_cond_timedwait __P ((pthread_cond_t *__cond,
  pthread_mutex_t *__mutex, __const struct timespec *__abstime));
  它比函数pthread_cond_wait()多了一个时间参数,经历abstime段时间后,即使条件变量不满足,阻塞也被解除。
  函数pthread_cond_signal()的原型为:
  extern int pthread_cond_signal __P ((pthread_cond_t *__cond));
 
 它用来释放被阻塞在条件变量cond上的一个线程。多个线程阻塞在此条件变量上时,哪一个线程被唤醒是由线程的调度策略所决定的。要注意的是,必须用保
护条件变量的互斥锁来保护这个函数,否则条件满足信号又可能在测试条件和调用pthread_cond_wait函数之间被发出,从而造成无限制的等待。
下面是使用函数pthread_cond_wait()和函数pthread_cond_signal()的一个简单的例子。

pthread_mutex_t count_lock;
pthread_cond_t count_nonzero;
unsigned count;
decrement_count () {
pthread_mutex_lock (&count_lock);
while(count==0)
pthread_cond_wait( &count_nonzero, &count_lock);
count=count -1;
pthread_mutex_unlock (&count_lock);
}

increment_count(){
pthread_mutex_lock(&count_lock);
if(count==0)
pthread_cond_signal(&count_nonzero);
count=count+1;
pthread_mutex_unlock(&count_lock);
}
  count值为0
时,
decrement函数在pthread_cond_wait处被阻塞,并打开互斥锁count_lock。此时,当调用到函数
increment_count时,pthread_cond_signal()函数改变条件变量,告知decrement_count()停止阻塞。读
者可以试着让两个线程分别运行这两个函数,看看会出现什么样的结果。
  函数pthread_cond_broadcast(pthread_cond_t *cond)用来唤醒所有被阻塞在条件变量cond上的线程。这些线程被唤醒后将再次竞争相应的互斥锁,所以必须小心使用这个函数。

4.4 信号量
 
 信号量本质上是一个非负的整数计数器,它被用来控制对公共资源的访问。当公共资源增加时,调用函数sem_post()增加信号量。只有当信号量值大于
0时,才能使用公共资源,使用后,函数sem_wait()减少信号量。函数sem_trywait()和函数pthread_
mutex_trylock()起同样的作用,它是函数sem_wait()的非阻塞版本。下面我们逐个介绍和信号量有关的一些函数,它们都在头文件
/usr/include/semaphore.h中定义。
  信号量的数据类型为结构sem_t,它本质上是一个长整型的数。函数sem_init()用来初始化一个信号量。它的原型为:
  extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int __value));
  sem为指向信号量结构的一个指针;pshared不为0时此信号量在进程间共享,否则只能为当前进程的所有线程共享;value给出了信号量的初始值。
  函数sem_post( sem_t *sem )用来增加信号量的值。当有线程阻塞在这个信号量上时,调用这个函数会使其中的一个线程不在阻塞,选择机制同样是由线程的调度策略决定的。
 
 函数sem_wait( sem_t *sem
)被用来阻塞当前线程直到信号量sem的值大于0,解除阻塞后将sem的值减一,表明公共资源经使用后减少。函数sem_trywait (
sem_t *sem )是函数sem_wait()的非阻塞版本,它直接将信号量sem的值减一。
  函数sem_destroy(sem_t *sem)用来释放信号量sem。
  下面我们来看一个使用信号量的例子。在这个例子中,一共有4个线程,其中两个线程负责从文件读取数据到公共的缓冲区,另两个线程从缓冲区读取数据作不同的处理(加和乘运算)。
/* File sem.c */
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define MAXSTACK 100
int stack[MAXSTACK][2];
int size=0;
sem_t sem;
/* 从文件1.dat读取数据,每读一次,信号量加一*/
void ReadData1(void){
FILE *fp=fopen("1.dat","r");
while(!feof(fp)){
fscanf(fp,"%d %d",&stack[size][0],&stack[size][1]);
sem_post(&sem);
++size;
}
fclose(fp);
}
/*从文件2.dat读取数据*/
void ReadData2(void){
FILE *fp=fopen("2.dat","r");
while(!feof(fp)){
fscanf(fp,"%d %d",&stack[size][0],&stack[size][1]);
sem_post(&sem);
++size;
}
fclose(fp);
}
/*阻塞等待缓冲区有数据,读取数据后,释放空间,继续等待*/
void HandleData1(void){
while(1){
sem_wait(&sem);
printf("Plus:%d+%d=%d\n",stack[size][0],stack[size][1],
stack[size][0]+stack[size][1]);
–size;
}
}

void HandleData2(void){
while(1){
sem_wait(&sem);
printf("Multiply:%d*%d=%d\n",stack[size][0],stack[size][1],
stack[size][0]*stack[size][1]);
–size;
}
}
int main(void){
pthread_t t1,t2,t3,t4;
sem_init(&sem,0,0);
pthread_create(&t1,NULL,(void *)HandleData1,NULL);
pthread_create(&t2,NULL,(void *)HandleData2,NULL);
pthread_create(&t3,NULL,(void *)ReadData1,NULL);
pthread_create(&t4,NULL,(void *)ReadData2,NULL);
/* 防止程序过早退出,让它在此无限期等待*/
pthread_join(t1,NULL);
}

 
 在Linux下,我们用命令gcc -lpthread sem.c -o sem生成可执行文件sem。
我们事先编辑好数据文件1.dat和2.dat,假设它们的内容分别为1 2 3 4 5 6 7 8 9 10和 -1 -2 -3 -4 -5
-6 -7 -8 -9 -10 ,我们运行sem,得到如下的结果:
Multiply:-1*-2=2
Plus:-1+-2=-3
Multiply:9*10=90
Plus:-9+-10=-19
Multiply:-7*-8=56
Plus:-5+-6=-11
Multiply:-3*-4=12
Plus:9+10=19
Plus:7+8=15
Plus:5+6=11

  从中我们可以看出各个线程间的竞争关系。而数值并未按我们原先的顺序显示出来这是由于size这个数值被各个线程任意修改的缘故。这也往往是多线程编程要注意的问题。

5 小结
  多线程编程是一个很有意思也很有用的技术,使用多线程技术的网络蚂蚁是目前最常用的下载工具之一,使用多线程技术的grep比单线程的grep要快上几倍,类似的例子还有很多。希望大家能用多线程技术写出高效实用的好程序来。

2005年11月23日

 

Problem Statement

 

 

 

 

When editing a single line of text, there are four keys that can be used to move the cursor: end, home, left-arrow and right-arrow. As you would expect, left-arrow and right-arrow move the cursor one character left or one character right, unless the cursor is at the beginning of the line or the end of the line, respectively, in which case the keystrokes do nothing (the cursor does not wrap to the previous or next line). The home key moves the cursor to the beginning of the line, and the end key moves the cursor to the end of the line.

You will be given a int, N, representing the number of character in a line of text. The cursor is always between two adjacent characters, at the beginning of the line, or at the end of the line. It starts before the first character, at position 0. The position after the last character on the line is position N. You should simulate a series of keystrokes and return the final position of the cursor. You will be given a string where characters of the string represent the keystrokes made, in order. ‘L’ and ‘R’ represent left and right, while ‘H’ and ‘E’ represent home and end.

Definition

 

 

 

 

Class:

CursorPosition

Method:

getPosition

Parameters:

string, int

Returns:

int

Method signature:

int getPosition(string keystrokes, int N)

(be sure your method is public)

 

 

 

 

Constraints

-

keystrokes will be contain between 1 and 50 ‘L’, ‘R’, ‘H’, and ‘E’ characters, inclusive.

-

N will be between 1 and 100, inclusive.

Examples

0)

 

 

 

 

"ERLLL"

10

Returns: 7

First, we go to the end of the line at position 10. Then, the right-arrow does nothing because we are already at the end of the line. Finally, three left-arrows brings us to position 7.

1)

 

 

 

 

"EHHEEHLLLLRRRRRR"

2

Returns: 2

All the right-arrows at the end ensure that we end up at the end of the line.

2)

 

 

 

 

"ELLLELLRRRRLRLRLLLRLLLRLLLLRLLRRRL"

10

Returns: 3

3)

 

 

 

 

"RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL"

19

Returns: 12

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


我的答案:


#include <string>
#include <iostream>
using namespace std;
class CursorPosition
{
public:
    int getPosition(string keystrokes,int N);
};

int CursorPosition::getPosition(string keystrokes,int N)
{
    int pos = 0,i;
    int nCmd = keystrokes.size();
    int ELast = keystrokes.find_last_of(‘E’);
    ELast = ELast!=string::npos?ELast:0;
    int HLast = keystrokes.find_last_of(‘H’);
    HLast = ELast!=string::npos?HLast:0;
    pos = ELast>HLast?N:0;
   
    for(i= ELast>HLast?ELast:HLast;i<nCmd;i++)
    {
        switch(keystrokes[i])
        {
        case ‘L’:
            pos–;
            break;
        case ‘R’:
            pos++;
            break;
        }
        pos = pos>N?N:pos;
        pos = pos<0?0:pos;
       
    }
    return pos;
}

int main(int argc,char *argv[])
{
    CursorPosition cp;
    cout<<cp.getPosition("RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL",19)<<endl;
    return 0;
}

 

Problem Statement

 

 

 

 

A simple line drawing program uses a blank 20 x 20 pixel canvas and a directional cursor that starts at the upper left corner pointing straight down. The upper left corner of the canvas is at (0, 0) and the lower right corner is at (19, 19). You are given a String[], commands, each element of which contains one of two possible commands. A command of the form "FORWARD x" means that the cursor should move forward by x pixels. Each pixel on its path, including the start and end points, is painted black. The only other command is "LEFT", which means that the cursor should change its direction by 90 degrees counterclockwise. So, if the cursor is initially pointing straight down and it receives a single "LEFT" command, it will end up pointing straight to the right. Execute all the commands in order and return the resulting 20 x 20 pixel canvas as a String[] where character j of element i represents the pixel at (i, j). Black pixels should be represented as uppercase ‘X’ characters and blank pixels should be represented as ‘.’ characters.

Definition

 

 

 

 

Class:

DrawLines

Method:

execute

Parameters:

String[]

Returns:

String[]

Method signature:

String[] execute(String[] commands)

(be sure your method is public)

 

 

 

 

Notes

-

The cursor only paints the canvas if it moves (see example 1).

Constraints

-

commands will contain between 1 and 50 elements, inclusive.

-

Each element of commands will be formatted as either "LEFT" or "FORWARD x" (quotes for clarity only), where x is an integer between 1 and 19, inclusive, with no extra leading zeros.

-

When executing the commands in order, the cursor will never leave the 20 x 20 pixel canvas.

Examples

0)

 

 

 

 

{"FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19"}

Returns: {"XXXXXXXXXXXXXXXXXXXX",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"XXXXXXXXXXXXXXXXXXXX" }

This sequence of commands draws a 20 x 20 outline of a square. The cursor is initially at (0, 0) pointing straight down. It then travels to (0, 19) after the first FORWARD command, painting each pixel along its path with a ‘*’. It then rotates 90 degrees left, travels to (19, 19), rotates 90 degrees left, travels to (19, 0), rotates 90 degrees left, and finally travels back to (0, 0).

1)

 

 

 

 

{"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT"}

Returns: {"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"……………….." }

The cursor spins round and round, but never actually paints any pixels. The result is an empty canvas.

2)

 

 

 

 

{"FORWARD 1"}

Returns: {"X……………….",
"X……………….",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"……………….." }

Going forward by one pixel creates a line that is 2 pixels long because both the start and end points are painted.

3)

 

 

 

 

{"LEFT", "FORWARD 19", "LEFT", "LEFT", "LEFT",
"FORWARD 18", "LEFT", "LEFT", "LEFT", "FORWARD 17",
"LEFT", "LEFT", "LEFT", "FORWARD 16", "LEFT",
"LEFT", "LEFT", "FORWARD 15", "LEFT", "LEFT", "LEFT",
"FORWARD 14", "LEFT", "LEFT", "LEFT", "FORWARD 13",
"LEFT", "LEFT", "LEFT", "FORWARD 12", "LEFT", "LEFT",
"LEFT", "FORWARD 11", "LEFT", "LEFT", "LEFT", "FORWARD 10",
"LEFT", "LEFT", "LEFT", "FORWARD 9", "LEFT", "LEFT",
"LEFT", "FORWARD 8", "LEFT", "LEFT", "LEFT", "FORWARD 7"}

Returns: {"XXXXXXXXXXXXXXXXXXXX",
"……………….X",
"..XXXXXXXXXXXXXXXX.X",
"..X…………..X.X",
"..X.XXXXXXXXXXXX.X.X",
"..X.X……….X.X.X",
"..X.X.XXXXXXXX.X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.XXXXXXXXXX.X.X",
"..X.X…………X.X",
"..X.XXXXXXXXXXXXXX.X",
"..X…………….X",
"..XXXXXXXXXXXXXXXXXX",
"……………….." }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement

 

 

 

 

A square matrix is a grid of NxN numbers. For example, the following is a 3×3 matrix:

4 3 5
2 4 5
0 1 9

One way to represent a matrix of numbers, each of which is between 0 and 9 inclusive, is as a row-major string. To generate the string, simply concatenate all of the elements from the first row followed by the second row and so on, without any spaces. For example, the above matrix would be represented as "435245019".

You will be given a square matrix as a row-major string. Your task is to convert it into a vector <string>, where each element represents one row of the original matrix. Element i of the vector <string> represents row i of the matrix. You should not include any spaces in your return. Hence, for the above string, you would return {"435","245","019"}. If the input does not represent a square matrix because the number of characters is not a perfect square, return an empty vector <string>, {}.

Definition

 

 

 

 

Class:

MatrixTool

Method:

convert

Parameters:

string

Returns:

vector <string>

Method signature:

vector <string> convert(string s)

(be sure your method is public)

 

 

 

 

Constraints

-

s will contain between 1 and 50 digits, inclusive.

Examples

0)

 

 

 

 

"435245019"

Returns: {"435", "245", "019" }

The example above.

1)

 

 

 

 

"9"

Returns: {"9" }

2)

 

 

 

 

"0123456789"

Returns: { }

This input has 10 digits, and 10 is not a perfect square.

3)

 

 

 

 

"3357002966366183191503444273807479559869883303524"

Returns: {"3357002", "9663661", "8319150", "3444273", "8074795", "5986988", "3303524" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


我写的代码:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class MatrixTool
{
public:
    vector <string> convert(string s);
};

vector <string> MatrixTool::convert(string s)
{
    int n = s.size();
    int i=1,j=0,k=0;
    bool bMatrix = false;
    vector <string> vector_matrix;
    for(i;i<=n&&i<8;i++)
    {
        int temp = i*i;
        if( temp == n)
        {
            bMatrix = true;
            break;
        }
        else if( temp>n )
        {
            bMatrix = false;
            break;
        }
    }
    if(!bMatrix)
        return vector_matrix;
    vector_matrix.resize(i);
    for(j;j<i;j++)
        for(k = 0;k<i;k++)
            vector_matrix[j].push_back(s[i*j+k]);
   
    return vector_matrix;