debugo

一道在线测试题：给一个二进制字符串str(即只包含0和1的字符)，找到其中连续最长0出现的位置。

#include <string.h>;
#include <stdio.h>;

int getLongestZeroPos(char *str, char **start, char **end)
{
  *start=str, *end=str;
  char *c_start=str, *c_end=str;

  while(*str!='�')
  {
    while((*str!='�') &amp;&amp; (*str == '0')) ++str;
    if (c_end!=str)
    {
      c_end=str;
      if ((c_end-c_start)&gt;(*end-*start)) 
      {
        *end = c_end;
        *start = c_start;
      }
    }
    while((*str!='�') &amp;&amp; (*str == '1')) c_end=c_start=++str;
  }

  if(*end == *start)
  {
    *start=NULL;
    *end=NULL;
    return 0;
  }

  *start++;
  return *end-*start;
}

int main(int argc, char* argv[])
{
  char str[100];
  char *start, *end;
  int len;

  scanf("%s", str);
  str[strlen(str)]='�';
  len = getLongestZeroPos(str, &amp;start, &amp;end);
  if(!len)
    printf("No zero in string %s", str);
  else printf("The string is %snLongest zero is from %d to %dn", str, start-str, end-str);
}

#include <string.h>;

#include <stdio.h>;

int getLongestZeroPos(char *str, char **start, char **end)

{

*start=str, *end=str;

char *c_start=str, *c_end=str;

while(*str!='')

{

while((*str!='') && (*str == '0')) ++str;

if (c_end!=str)

{

c_end=str;

if ((c_end-c_start)>(*end-*start))

{

*end = c_end;

*start = c_start;

}

while((*str!='') && (*str == '1')) c_end=c_start=++str;

}

if(*end == *start)

{

*start=NULL;

*end=NULL;

return 0;

}

*start++;

return *end-*start;

}

int main(int argc, char* argv[])

{

char str[100];

char *start, *end;

int len;

scanf("%s", str);

str[strlen(str)]='';

len = getLongestZeroPos(str, &start, &end);

if(!len)

printf("No zero in string %s", str);

else printf("The string is %snLongest zero is from %d to %dn", str, start-str, end-str);

}

1.线程实现

线程是在进程的基础上进一步的抽象，也就是说一个进程分为两个部分：线程集合和资源集合。线程是进程中的一个动态对象，它应该是一组独立的指令流，进程中的所有线程将共享进程里的资源。但是线程应该有自己的私有对象：比如程序计数器、堆栈和寄存器上下文。
线程分为三种类型：
(1).内核线程：
它的创建和撤消是由内核的内部需求来决定的，用来负责执行一个指定的函数，一个内核线程不需要和一个用户进程联系起来。它共享内核的正文段核全局数据，具有自己的内核堆栈。它能够单独的被调度并且使用标准的内核同步机制，可以被单独的分配到一个处理器上运行。内核线程的调度由于不需要经过态的转换并进行地址空间的重新映射，因此在内核线程间做上下文切换比在进程间做上下文切换快得多。
(2).轻量级进程：
轻量级进程是内核支持的用户线程，它在一个单独的进程中提供多线程控制。这些轻量级进程被单独的调度，可以在多个处理器上运行，每一个轻量级进程都被绑定在一个内核线程上，而且在它的生命周期这种绑定都是有效的。轻量级进程被独立调度并且共享地址空间和进程中的其它资源，但是每个LWP都应该有自己的程序计数器、寄存器集合、核心栈和用户栈。
(3).用户线程：
用户线程是通过线程库实现的。它们可以在没有内核参与下创建、释放和管理。线程库提供了同步和调度的方法。这样进程可以使用大量的线程而不消耗内核资源，而且省去大量的系统开销。用户线程的实现是可能的，因为用户线程的上下文可以在没有内核干预的情况下保存和恢复。每个用户线程都可以有自己的用户堆栈，一块用来保存用户级寄存器上下文以及如信号屏蔽等状态信息的内存区。库通过保存当前线程的堆栈和寄存器内容载入新调度线程的那些内容来实现用户线程之间的调度和上下文切换。
内核仍然负责进程的切换，因为只有内核具有修改内存管理寄存器的权力。用户线程不是真正的调度实体，内核对它们一无所知，而只是调度用户线程下的进程或者轻量级进程，这些进程再通过线程库函数来调度它们的线程。当一个进程被抢占时，它的所有用户线程都被抢占，当一个用户线程被阻塞时，它会阻塞下面的轻量级进程，如果进程只有一个轻量级进程，则它的所有用户线程都会被阻塞。
Linux线程是通过进程来实现。Linux kernel为进程创建提供一个clone()系统调用，clone的参数包括如 CLONE_VM, CLONE_FILES, CLONE_SIGHAND 等。通过clone()的参数，新创建的进程，也称为LWP(Lightweight process)与父进程共享内存空间，文件句柄，信号处理等，从而达到创建线程相同的目的。
在Linux 2.6之前，Linux kernel并没有真正的thread支持，一些thread library都是在clone()基础上的一些基于user space的封装，因此通常在信号处理、进程调度(每个进程需要一个额外的调度线程)及多线程之间同步共享资源等方面存在一定问题。Linux 2.6的线程库叫NPTL(Native POSIX Thread Library)。POSIX thread(pthread)是一个编程规范，通过此规范开发的多线程程序具有良好的跨平台特性。尽管是基于进程的实现，但新版的NPTL创建线程的效率非常高。一些测试显示，基于NPTL的内核创建10万个线程只需要2秒，而没有NPTL支持的内核则需要长达15分钟。
在Linux中，每一个线程都有一个task_struct。线程和进程可以使用同一调度其调度。内核角度上来将LWP和Process没有区别，有的仅仅是资源的共享。如果独享资源则是HWP，共享资源则是LWP。而在真正内核实现的

NPTL的实现是在kernel增加了futex(fast userspace mutex)支持用于处理线程之间的sleep与wake。futex是一种高效的对共享资源互斥访问的算法。kernel在里面起仲裁作用，但通常都由进程自行完成。NPTL是一个1×1的线程模型，即一个线程对于一个操作系统的调度进程，优点是非常简单。而其他一些操作系统比如Solaris则是MxN的，M对应创建的线程数，N对应操作系统可以运行的实体。(N2.Linux线程库pthread

(1). 测试宏
#ifdef _POSIX_THREADS
或者
sysconf(_SC_THREADS)
来检测是否支持宏。
(2). 线程标识pthread_t
pit_t是整个系统中唯一的。而线程pthread_t(struct)不同，只在它所属的进程环境有效。
判断两个线程ID是否相等：

#include <pthread.h>
int pthread_equal(pthread_t tid1, pthread_t tid2); //返回值若相等则返回非0值，不相等则返回0
pthread_t pthread_self(void) //获得线程自身pthread_t

#include <pthread.h>

int pthread_equal(pthread_t tid1, pthread_t tid2); //返回值若相等则返回非0值，不相等则返回0

pthread_t pthread_self(void) //获得线程自身pthread_t

(3).线程创建
程序启动时，它是以单进程的单个控制进程启动的。如果要增加新的线程，可以调用pthread_create来创建。

#include <pthread.h>
int pthread_create(
	pthread_t *restrict tidp, 		/*第一个参数为指向线程标识符的指针*/
	const pthread_attr_t *restrict attr,	/*第二个参数用来设置线程属性*/
	void *(*rtn)(void), 			/*第三个参数是线程运行函数的起始地址*/
	void *restrict arg			/*最后一个参数是运行函数的参数*/
);

#include <pthread.h>

int pthread_create(

pthread_t *restrict tidp, /*第一个参数为指向线程标识符的指针*/

const pthread_attr_t *restrict attr, /*第二个参数用来设置线程属性*/

void *(*rtn)(void), /*第三个参数是线程运行函数的起始地址*/

void *restrict arg /*最后一个参数是运行函数的参数*/

);

//若成功则返回0，否则返回错误编号。它不设置errno
C99中的新关键字restrict以及受限指针（restricted pointers）。受限指针作为一种编译器优化代码的方式，是由编译器厂商提供特定的实现.
restrict只可以用在指针身上。如果一个指针被restrict修饰，那么就在它（这个指针）和它所指向的对象之间建立了一种特殊的联系──只能用这个指针或者这个指针的表达式来访问这个对象的值.一个指针指向一个内存地址。同一块内存可以由多个指针来访问并在程序运行时修改它（这块内存）。restrict告诉编译器，如果一块由一个被restrict修饰的指针所指向的内存被修改了，那么没有其它的指针可以来访问这块内存。编译器可能会选择一种方式来优化代码中调用被restrict修饰的指针的部分，这可能导致错误发生。程序员有责任来确保正确地按照他们所设想的来使用被restrict修饰的指针，否则的话，可能会发生意想不到的结果。
如果一块特定的内存区没有被修改，那么它可以被多个restrict指针（被restrict修饰的指针）所指代（或者叫做引用或访问）。另外，restrict指针的赋值是有限制的，这一点在函数调用和嵌套块（nested block）之间是没有区别的。在包含restrict指针的块中，只能将外层的restrict指针的值赋给内层的restrict指针，在同层内不可以相互赋值，当然在外层不可能赋以内层的值。一个例外是，当一个声明restrict指针的代码快执行完后，这个restrict指针所指的内存就可以被其它的指针访问了（因为那个restrict是那个代码块的局部变量，当执行完那个代码块后，这个指针也就不复存在了）。
(4). 线程终止
如果进程中的任一线程调用了exit, __EXIT虎或_exit，那么整个进程就会终止。与之类似如果信号的默认动作是终止进程，那么信号发送到线程就会终止整个进程。
线程的退出方式:
(1).线程只从启动函数中返回，返回值是线程的退出码。
(2).线程可以被同一进程中其他线程取消。
(3).线程调用pthread_exit()。

void pthread_exit(void *rval_ptr);
rval_ptr是一个无类型指针，与传给启动函数的单个参数类似。进程中其他进程可以调用pthread_join函数访问到这个指针。如果线程从启动函数返回，rval_ptr将包含返回码。如果线程被取消，由rval_ptr指定的内存单元就置为PTHREAD_CANCELED。如果对线程的返回值不感兴趣，那么就可以把rval_ptr设置为NULL。在样调用pthread_join函数将等待指定的线程终止，但并不获取线程的终止状态。例如在线程启动函数中返回:return ((void *) 1)这样pthread_join的函数可以通过rval_ptr这个指针得到线程的退出状态。如果线程调用ptread_exit((void *2))，那么pthread_join依然可以得到退出状态2.这个指针可以是复杂的结构类型以便保存更多信息。

int pthread_join(pthread_t thread, void **rval_ptr);
/* 成功返回0，否则返回错误编号 */
调用pthread_join的线程将被阻塞，直到指定的线程(thread)调用pthread_exit，从启动函数或者被取消。另外，void *rval_ptr可以作为一个int直接返回。例如return (void *)1;或者pthread_exit((void *)1);那么从pthread_join获得该指针直接可以用(int)ptr来输出。
这个void *rval_ptr指向的内存地址不应该在栈上，其内容会被下面调用的函数覆盖。应该是在堆上(通过malloc来创建)或者在静态数据段(用静态，全局变量)。
int pthread_cancel(pthread_t tid);
/* 成功返回0，否则返回错误编号 */
行为相等于参数值等同于PTHREAD_CANCELED的pthread_exit函数。
注意：线程可以自行选择忽略取消或者控制取消方式。注意pthread_cancel并不等待线程终止，仅仅是提出请求。
线程可以自己安排退出时需要执行的函数，这与进程atexit函数安排退出时要执行的函数是类似的。这样的函数称为线程清理处理程序。线程可以建立多个线程处理函数，存放在栈中，执行顺序与他们注册的顺序相反。

void pthread_cleanup_push(void (*rtn)(void *), void *arg);
void pthread_cleanup_pop(int execute);

1 2	void pthread_cleanup_push(void (rtn)(void ), void *arg); void pthread_cleanup_pop(int execute);

pthread_cleanup_pop删除上一次注册的线程清理处理程序。如果execute非0，则执行这个程序。
关于参数的使用方法的一个例子:

void 
cleanup(void *arg) 
{ 
    printf("cleanup: %sn", (char *)arg); 
} 

void 
thr_fn1(void *arg) 
{ 
    /* ... */ 
    pthread_cleanup_push(cleanup, "first cleanup in Thread "); 
    pthread_cleanup_push(cleanup, "second cleanup in Thread ");  

    /* ... */ 
    pthread_cleanup_pop(0); 
    pthread_cleanup_pop(0); 
    return ((void *)1);/* 通过返回终止线程的话，清理处理程序就不会调用 */ 
    /* or pthread_exit((void *)2);   通过pthread_exit就会正常调用 */ 
} 

int 
main(void) 
{ 
    /* ... */ 
    err = pthread_create(&tid, NULL, thr_fn1, (void *)1); 
    if (err != 0) 
        /* print err and quit*/ 
    /* ... */ 
    err = pthread_join(tid1, &tret); 

    if (err != 0) 
        /* print err and quit*/ 
    /* ... */ 

    return 0; 
}

void

cleanup(void *arg)

{

printf("cleanup: %sn", (char *)arg);

}

void

thr_fn1(void *arg)

{

/* ... */

pthread_cleanup_push(cleanup, "first cleanup in Thread ");

pthread_cleanup_push(cleanup, "second cleanup in Thread ");

/* ... */

pthread_cleanup_pop(0);

return ((void *)1);/* 通过返回终止线程的话，清理处理程序就不会调用 */

/* or pthread_exit((void *)2); 通过pthread_exit就会正常调用 */

}

int

main(void)

{

/* ... */

err = pthread_create(&tid, NULL, thr_fn1, (void *)1);

if (err != 0)

/* print err and quit*/

/* ... */

err = pthread_join(tid1, &tret);

if (err != 0)

/* print err and quit*/

/* ... */

return 0;

}

参考：
APUE
ULK
fork vfork clone pthread_create http://blog.csdn.net/sandflee/article/details/5189312

Author Archives: debugo

找到二进制字符串中连续最长”0“出现位置

【APUE】守护进程

概念

创建守护进程

pthread线程和信号

pthread线程私有数据

pthread线程同步机制

pthread线程库简介

1.线程实现

近期文章

热评文章

文章归档

分类目录

友链

功能