Archive for 十月, 2009

快速排序 - 分治策略

LINUX C & ARM & C51 | Posted by 老沙
10月 31 2009

看了书之后,自己写了一遍,留个印记
[ssj@main ~]$ cat my.c
#include <stdio.h>
int data[]={2,4,3,34,32,4,23,4,234,234,2,532,34,1,31,5,21,312,3,1523,12,3};
quick_sort(int data[],int low,int high)
{
int i,j,pivot;
if (low<high)
{
i=low;
j=high;
pivot=data[low];

while(i<j){
while(i<j&&data[j]>=pivot)j–;
if(i<j)data[i++]=data[j];
while(i<j&&data[i]<=pivot)i++;
if(i<j)data[j–]=data[i];
}
data[i]=pivot;
quick_sort(data,low,i-1);
quick_sort(data,i+1,high);

}

}
main()
{
int i;
for(i=0;i<=22;i++)
{printf("%d ",data[i]);}
printf("n");
quick_sort(data,0,22);
for(i=0;i<=22;i++){printf("%d ",data[i]);}
printf("n");

}

进程与线程的关系

LINUX C & ARM & C51 | Posted by 老沙
10月 31 2009

进程的两个特点:
资源所有权:进程是一个可拥有资源的独立单位;
调度/执行:进程同时又是一个可以独立调度和分派的基本单位;

引入线程的目的:
因为进程是一个资源拥有者,因而在进程的创建、撤消和切换中,系统必须为之付出较大的时空
开销。也因此,在系统中所设置的进程数目不宜过多,进程切换的频率也不宜过高,同时也限制了并
发程序的进一步提高。在操作系统中引入线程,是为了减少程序并发执行时所付出的时空开销,使操
作系统具有更好的并发性。

线程的实质:
线程是进程中的一个实体,是被系统独立调度和分派的基本单位,一个进程可有多个线程;
线程除运行必需的资源外,不拥有系统资源,但它可与同属一进程的其它线程共享进程所拥有的全部资源;
一个线程可创建和撤消另一线程;同一进程中的线程间可并发执行;
线程间相互制约;线程在运行中呈现间断性;
线程有就绪、阻塞、执行三种基本状态;

线程与进程的比较
引入线程的OS
调度:线程为调度和分派的基本单位。进程为拥有资源的基本单位。
并发性:进程间可并发执行,一个进程中的多个线程间也可并发执行。
拥有资源:进程是拥有资源的一个独立单位线程不拥有系统资源。
系统开销:线程切换的开销远小于进程切换的开销;有的系统线程切换、同步和通信都无须OS内核的干预

传统的OS
调度:拥有资源和独立调度、分派的基本单位都是进程。
并发性:进程间可并发执行。
拥有资源:进程是拥有资源的一个独立单位。
系统开销:进程切换的开销远大于线程切换的开销;进程切换涉及OS内核。

线程的功能特征
和进程一样,线程具有执行状态,且可以与另一个线程同步。
线程状态—-和进程一样,线程的主要状态有运行、就绪和阻塞。一般来说,挂起状态对线程
没有什么意义。与线程状态变化相关的有四种基本操作:
  产生(Spawn): 当产生一个新进程时,同时也为该进程产生一个线程,随后,进程中的线程可以
  在同一个进程中产生另一个线程,并为新线程提供指令指针和参数。
  阻塞(Block): 当线程需要等待一个事件时,它将自己阻塞,此时处理器转而执行另一个就绪线程。
  解除阻塞(Unlock): 当阻塞一个线程的事件发生时,该线程被转移到就绪队列中。
  结束(Finish): 当一个线程完成时,其寄存器上下文和栈都被释放。
  线程同步—-一个线程对资源任何的修改都会影响同一个进程中其他线程的环境。因此,需要对各种
  线程的活动进行同步。

线程的分类
线程可分以下两类:
内核支持线程—-线程的创建、撤消和切换都由内核实现。
用户级线程——线程的创建、撤消和切换都不利用系统调用来实现,与内核无关。

两类线程的比较:
内核支持线程
线程的调度与切换速度:与进程的调度与切换十分相似。
系统调用:调度以线程为单位。
线程执行时间:线程多的进程获得CPU时

用户级线程
线程的调度与切换速度:发生在一个应用进程的各线程间,无须OS内核的干预,规则远比进程调度和切换的规则简单。切换速度特别快。
系统调用:一个线程调度看作整个进程的行为。
线程执行时间:进程运行速度与其拥有线程的数量成反比。

C 优先级与结合性

LINUX C & ARM & C51 | Posted by 老沙
10月 31 2009

优先级:决定哪部分表达式先计算。
结合性:计算时是从左向右顺序,还是从右向左的顺序。

例1:
b=++a;

先看优先级:++ 优先级比 = 要高,先算++。
再看结合性:++ 的结合性是从右到左,这里就是它,直接算。
现在就剩下 = 号了,优先级就它一个了,但结合性还是 从右到左,那么现在把a 的值取出来赋值给 b 。
所以: 整个结果相当于
a = a + 1; b=a;

例2:
b=a++;

先看优先级,++ 虽然高,但是后置的(它的结合性是从左到右),这就意味着它返回左值。而返回值后就必须进行下面的计算
这里是 = ,运算全部完成后才能进行自身++运算,所以它最后算。我们这里先看 = ,再看结合性: 从右到左。故取 a 的值
赋值给 b ; 最后 a 的值加1 。
相当于: b=a; a = a + 1;

例3:
a+=b-=++c+4+e++;

这个够复杂吧,谁先? 单目运算符前缀 ++ 先算,然后是 + ,赋值运算最后。
然后看结合性。 -= += 都是从右到左,右边先算。故:
上例分解为:++c;b= b- e+c+4;a=a+b;e++

赋值运算符:结合性从右到左
先确定优先级,然后确定结合性。相同优先级的前提下,就要看结合性
结合性表示的是同级优先级,即同级运算符中的优先级。
优先级表示的是全局优先级,即不同运算符中的优先级。

对于自增自减表达式
前缀:先于表达式中其它部分的运算进行计算;
后缀:后于表达式中其它部分的运算进行计算。

++A ; 结合性,从右到左。 变量在右,返回右值。
//先看到 ++ 再看到 A ,返回 A 时 A 已经自增。

A++ ; 结合性,从左到右。 变量在左,返回左值。
//先看到 A,可以返回值,直接返回。A 本身再自增。

再来看看 B=A++; B=++A; 很容易就知道运算关系是怎么样的了,下面进行说明:

A++,执行后置运算,后计算A自增。先返回变量A的值参与表达式中其它部分的运算,整个表达式计算完成后,A才自增。
因其间返回的临时值参是一个常量,故该表达式不能写成:
A++ = 100;// 常量不能赋值

++A,执行前置运算,先计算A自增,然后返回A自增后的值。因为A自增操作已经完成,不必返回临时常量,直接返回A本身即可。
所以该表达式最终返回值是一个变量,故可以写成:
++A = 200; // 变量可以赋值

注意,理解它们, ++A, A++ ,要把它们当一个整体来看,即最小单位。在这里是没什么左右的,不要再分解它们。

自己总结的优先级
1. 括号操作符与关联和后置的自加自减(同级从左到右结合)
() isdigit('1')
[] array[4]
-> prt->age=34;
. *obj.age=34;
++ i++
— i–

2. 单字元的前置运算符(从右到左)
! if(!done)
~ flages=~flages;
++ ++i
— –i
+ int i=+1;
– int i=-1;
* int *p;
& p=&a;
sizeof sizeof(int);

3.数字运算符(乘除取模,高于加减 从左到右)

* i=2*4;
/ i=4/2;
% i=4%3;

+ i=2+4;
– i=4-2;

4.位移运算(从左到右)
>> int flages=flages<<2;
<<

5.比较大小(<,>高于==,!= 从左到右)
< if (i<2)
<=
>
>=

== if (i==2)
!=

6.位运算(&,^,|优先级从高到低,从左向右)
& flages=flages&42;
^
|

7.逻辑运算(从左到右)
&&
||

8.(右向左)
? : int i=(a>b)?a:b

9.赋值(从右向左)
=,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>=

10.
throw throw eclass("message");

11.逗号
, for (i=0,j=0;i<10;i++,j++)

ssh 配置 ssh_config sshd_config

LINUX | Posted by 老沙
10月 26 2009

ssh_config

# Host *  (只对能够匹配后面字串的计算机有效。“*”表示所有的计算机)
# ForwardAgent no  (设置连接是否经过验证代理(如果存在)转发给远程计算机)
# ForwardX11 no  (设置X11连接是否被自动重定向到安全的通道和显示集)
# RhostsRSAAuthentication no  (设置是否使用用RSA算法的基于rhosts的安全验证)
# RSAAuthentication yes  (设置是否使用RSA算法进行安全验证)
# PasswordAuthentication yes  (设置是否使用口令验证)
# HostbasedAuthentication no  (若设置为yes,则尝试着进行rhosts身份验证。对于安全要求更高的系统,请将其设置为no(默认值))
# GSSAPIAuthentication no  (ssh的会话直到DNS请求超时才会继续下去,建意no)
# GSSAPIDelegateCredentials no  (ssh的会话直到DNS请求超时才会继续下去,建意no)
# BatchMode no  (如果设为“yes”,passphrase/password(交互式输入口令)的提示将被禁止。
当不能交互式输入口令的时候,这个选项对脚本文件和批处理任务十分有用)
# CheckHostIP yes  (设置ssh是否查看连接到服务器的主机的IP地址以防止DNS欺骗。建议设置为“yes”)
# AddressFamily any  (设置允许的地址)
# ConnectTimeout 0  (连接超时)
# StrictHostKeyChecking ask  (如果设置成“yes”,ssh就不会自动把计算机的密匙加入“$HOME/.ssh)
# IdentityFile ~/.ssh/identity  (设置从哪个文件读取用户的RSA安全验证标识)
# IdentityFile ~/.ssh/id_rsa
# IdentityFile ~/.ssh/id_dsa
# Port 22  (设置连接到远程主机的端口)
# Protocol 2,1  (设置协议版本,建意用2)
# Cipher 3des  (设置加密用的密码)
# Ciphers aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc
# MACs hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-ripemd160
# EscapeChar ~  (设置escape字符)
# Tunnel no  (隧道模式)
# TunnelDevice any:any
# PermitLocalCommand no
# VisualHostKey no

=======================================================

sshd_config

#Port 22  (设置sshd监听的端口号)
#AddressFamily any
#ListenAddress 0.0.0.0  (设置sshd服务器绑定的IP地址)
#ListenAddress ::

Protocol 2  (设置协议版本)

# HostKey for protocol version 1
#HostKey /etc/ssh/ssh_host_key  (设置包含计算机私人密匙的文件)
# HostKeys for protocol version 2
#HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_dsa_key

# Lifetime and size of ephemeral version 1 server key
#KeyRegenerationInterval 1h  (KeyRegenerationInterval 3600)
#ServerKeyBits 1024  (定义服务器密匙的位数)

# Logging
# obsoletes QuietMode and FascistLogging
#SyslogFacility AUTH  (设置在记录来自sshd的消息的时候,是否给出“facility code”)
SyslogFacility AUTHPRIV
#LogLevel INFO  (设置记录sshd日志消息的层次。INFO是一个好的选择。查看sshd的man帮
助页,已获取更多的信息)

# Authentication:

#LoginGraceTime 2m  (设置如果用户不能成功登录,在切断连接之前服务器需要等待的时间)
#PermitRootLogin yes  (设置root能不能用ssh登录。这个选项一定不要设成“yes”)
#StrictModes yes (设置ssh在接收登录请求之前是否检查用户家目录和rhosts文件的权限和所
有权。这通常是必要的,因为新手经常会把自己的目录和文件设成任何人都有写权限)
#MaxAuthTries 6 (限制登陆密码输错次数)
#MaxSessions 10

#RSAAuthentication yes  (设置是否允许用rhosts或“/etc/hosts.equiv”加上RSA进行安全验证)
#PubkeyAuthentication yes
#AuthorizedKeysFile  .ssh/authorized_keys

# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
#RhostsRSAAuthentication no  (设置是否允许用rhosts或“/etc/hosts.equiv”加上RSA进行安全验证)
# similar for protocol version 2
#HostbasedAuthentication no
# Change to yes if you don't trust ~/.ssh/known_hosts for
# RhostsRSAAuthentication and HostbasedAuthentication
#IgnoreUserKnownHosts no (设置ssh daemon是否在进行RhostsRSAAuthentication安全验证
的时候忽略用户的“$HOME/.ssh/known_hosts)
# Don't read the user's ~/.rhosts and ~/.shosts files
#IgnoreRhosts yes (设置验证的时候是否使用“rhosts”和“shosts”文件)

# To disable tunneled clear text passwords, change to no here!
#PasswordAuthentication yes  (设置是否允许口令验证)
#PermitEmptyPasswords no  (设置是否允许用口令为空的帐号登录)
PasswordAuthentication yes

# Change to no to disable s/key passwords
#ChallengeResponseAuthentication yes
ChallengeResponseAuthentication no

# Kerberos options
#KerberosAuthentication no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes
#KerberosGetAFSToken no

# GSSAPI options
#GSSAPIAuthentication no
GSSAPIAuthentication yes
#GSSAPICleanupCredentials yes
GSSAPICleanupCredentials yes

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication. Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
#UsePAM no
UsePAM yes

# Accept locale-related environment variables
AcceptEnv LANG LC_CTYPE LC_NUMERIC LC_TIME LC_COLLATE LC_MONETARY LC_MESSAGES
AcceptEnv LC_PAPER LC_NAME LC_ADDRESS LC_TELEPHONE LC_MEASUREMENT
AcceptEnv LC_IDENTIFICATION LC_ALL LANGUAGE

#AllowAgentForwarding yes
#AllowTcpForwarding yes
#GatewayPorts no
#X11Forwarding no  (设置是否允许X11转发)
X11Forwarding yes
#X11DisplayOffset 10
#X11UseLocalhost yes
#PrintMotd yes  (设置sshd是否在用户登录的时候显示“/etc/motd”中的信息)
#PrintLastLog yes
#TCPKeepAlive yes
#UseLogin no
#UsePrivilegeSeparation yes
#PermitUserEnvironment no
#Compression delayed
#ClientAliveInterval 0
#ClientAliveCountMax 3
#ShowPatchLevel no
#UseDNS yes
#PidFile /var/run/sshd.pid
#MaxStartups 10 (同时登录的用户的个数)
#PermitTunnel no
#ChrootDirectory none (ChrootDirectory /home/%u改变登陆者的目录)

# no default banner path
#Banner none

# override default of no subsystems
Subsystem  sftp  /usr/libexec/openssh/sftp-server

# Example of overriding settings on a per-user basis
#Match User anoncvs
#  X11Forwarding no
#  AllowTcpForwarding no
#  ForceCommand cvs server

rpm 相关 依赖

LINUX | Posted by 老沙
10月 26 2009

查看一个rpm包的依赖
如果是本地的包,没有安装过的
rpm -qRp 包名

[root@mydisk ~]# rpm -qR /home/linux/tools/VMware-Workstation-6.5.2-156735.x86_64.rpm
package /home/linux/tools/VMware-Workstation-6.5.2-156735.x86_64.rpm is not installed
[root@mydisk ~]# rpm -qR /home/linux/tools/VMware-Workstation-6.5.3-185404.x86_64.bundle
package /home/linux/tools/VMware-Workstation-6.5.3-185404.x86_64.bundle is not installed
[root@mydisk ~]# rpm -qR /home/linux/tools/tftp-server-0.32-4.i386.rpm
package /home/linux/tools/tftp-server-0.32-4.i386.rpm is not installed
[root@mydisk ~]# rpm -qRp /home/linux/tools/tftp-server-0.32-4.i386.rpm
warning: /home/linux/tools/tftp-server-0.32-4.i386.rpm: Header V3 DSA signature: NOKEY, key ID db42a60e
/bin/sh
/bin/sh
config(tftp-server) = 0.32-4
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.2)
libc.so.6(GLIBC_2.3)
libnsl.so.1
libwrap.so.0
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
xinetd

如果是已安装过的用
rpm -qR 包名

[root@mydisk ~]# rpm -qR dhcp
/bin/sh
/bin/sh
/bin/sh
/bin/sh
chkconfig
chkconfig
config(dhcp) = 12:4.1.0p1-2.fc11
coreutils
initscripts
initscripts
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.2)
libc.so.6(GLIBC_2.3)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
libcrypto.so.8
liblber-2.4.so.2
libldap-2.4.so.2
policycoreutils
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(FileDigests) <= 4.6.0-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)

一个基木的小游戏

个人的心情空间 | Posted by 老沙
10月 24 2009

http://i3.sinaimg.cn/gm/downgames/littlegame/U1850P115T33D3906F646DT20090302115435.swf

tar 备份系统

LINUX | Posted by 老沙
10月 22 2009

linux 使用tar命令备份系统
参数说明:
-z进行压缩gzip格式
-j进行bzip2压缩
-c建立一个备份
-f指定设备文件
-v显示压缩过程
-p保留文件的权限
–exclude指定不备份的文件或文件夹

time tar -jcvf /home/mainf10.backup.bz2 –exclude /home –exclude /media –exclude /mydisk –exclude /tmp –exclude /mnt –exclude /proc –exclude /sys /

增量备份1:(u参数不支持压缩文件)
tar zcvf backup.tar.gz test
gunzip backup.tar.gz
tar uvf backup.tar test
gzip backup.tar

增量备份2:

1.首先创建完全备份:tar -zcvf -g ssj t1_full.tar.gz /var
待/var中的数据变化后
2.再做增量备份 : tar -zcvf -g ssj t1_1.tar.gz /var
3.还原
tar zxvf t1_full.tar.gz
tar zxvf t1_1.tar.gz

mdadm 软 raid 设置

LINUX | Posted by 老沙
10月 19 2009

mdadm参数(区分大小写)
-C 建立raid的 : 如 -C /dev/md[n]
-n 硬盘的个数
-l raid的级别
-x 热备盘个数
-D 显示raid信息
-s 扫描配置 /etc/mdadm.conf 或 proc/mdstut

例:(raid0)
1. 先将硬盘分区fdisk分区,分成一个区
2. mkfs.ext3 将硬盘格式化
3. mdadm -C /dev/md0 -l0 -n2 /dev/sda1 /dev/sdb1
4. mdadm -D -s > /etc/mdadm.conf    #生成配置

C 语言 优先级

LINUX C & ARM & C51 | Posted by 老沙
10月 17 2009

Operators Associativity
() [] -> . left to right
! ~ ++ — + – * (type) sizeof right to left
* / % left to right
+ – left to right
<< >> left to right
< <= > >= left to right
== != left to right
& left to right
^ left to right
| left to right
&& left to right
|| left to right
?: right to left
= += -= *= /= %= &= ^= |= <<= >>= right to left

C ++ 优先级列表
http://www.kumouse.com/C++%20operator_precedence.html

yum 加入RPM Fusion源 mplayer

LINUX | Posted by 老沙
10月 16 2009

yum 里没有闭源的和没有版权的软件,比如mplayer
加入他们的源
rpm -ivh http://download1.rpmfusion.org/free/fedora/rpmfusion-free-release-stable.noarch.rpm
rpm -ivh http://download1.rpmfusion.org/nonfree/fedora/rpmfusion-nonfree-release-stable.noarch.rpm

加入了软件源后安装mplayer
yum install mplayer mplayer-gui mencoder

1
/etc/mplayer/mplayer.conf找到fontconfig=yes一行改成fontconfig=no
2
然后启动mplayer,它依然说一个无法将sun.ttf字体应用于当前的错误,解决这个问题的办法很简单,就是在mplayer的首先项的font里面找个随便什么字体给它就行。如果找不到字体,在windows下的Fonts中复制一个过来simfang.ttf这个就行

然后打开什么都能看,网上说放不了rmvb,是因为没有mencoder这个包。播放开始还是有个小错,不过不影响用,就先这样吧