新鲜出炉Google面试题一道(多线程)

anthony1983

原帖由 JohnBull 于 2007-10-30 11:17 发表


5楼的答案大概看了看，我相信没答到点子上。
既然是题目，当然有多种答案，满足需求就行，就像做项目不只有一种设计一样 教了这么多年书怎么不知道什么叫“发散思维呢”

根据我多年的教学经验，我揣测出题者的意图是考验学生是否会灵活利用mutex或信号量构造锁链。
所谓的锁链，我不明白是怎么实现，还请指教，另外信号量的效率我认为不会比OS调度锁的效率高多少


用锁链实现，代码要短一半以上，而且不需要出现“ ...

请计算好有效代码行数，看你用所谓的锁链+信号量能不能得到代码行数少一半的结果来。
所谓“第一次写”，懒得去归纳而已，所以才剥离出来放在前面。

没有和版主争辩的意思，记得有牛人说，与其在网上引经据典的和人争辩，不如亲自实践一下 不管答案如何，至少自己曾经做了，哪怕错了，也比所以为然强~！

[ 本帖最后由 anthony1983 于 2007-10-30 12:33 编辑 ]

baohuaihuai

原帖由 JohnBull 于 2007-10-30 11:17 发表


5楼的答案大概看了看，我相信没答到点子上。

根据我多年的教学经验，我揣测出题者的意图是考验学生是否会灵活利用mutex或信号量构造锁链。


用锁链实现，代码要短一半以上，而且不需要出现“ ...

版主说对了.出题者就是这个意思.

edccu

不管黑猫白猫抓住耗子就是好猫。抓不住耗子、拣死耗子、死拿耗子，争什么都是瞎争也。。。都是孬种猫的也也也。。。。。。。。。。。

[ 本帖最后由 edccu 于 2007-10-30 15:12 编辑 ]

anthony1983

更加另类的解法。
原理：建立线程间的通信管道，用管道的队列缓冲区作为同步用的队列，
      线程1写完后通知线程2，
      线程2写完后通知线程3，
      线程3写完后通知线程4，
      线程4写完后通知线程1

效率比用锁调度高很多，和用lseek差不多，但是比lseek更加合题意.
有人说用矩阵？ 好笑，若写的是abcd呢

#include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include <errno.h> #include <unistd.h> #include <stdio.h> #include <sys/types.h> #include <sys/socket.h> typedef struct file_node{         int             r_pipe;         int             w_pipe;         int             fd; }file_node; char *file[] = {"./a","./b","./c","./d"}; file_node  node_list[4]; void *thread_func(void *arg); int main() {         int     *num, i;         int     sockpair[2];         memset(node_list, 0, sizeof(node_list));         //打开文件，构建线程间管道         for (i=0; i<4; i++) {                 if (socketpair(AF_UNIX,SOCK_STREAM, 0, sockpair)) {                         printf("socketpair error !\n");                         exit(1);                 }                 node_list[i].w_pipe = sockpair[0];                 if (i != 3)                         node_list[i+1].r_pipe = sockpair[1];                 else                         node_list[0].r_pipe = sockpair[1];                 node_list[i].fd = open(file[i], O_CREAT | O_WRONLY| O_APPEND, S_IRUSR|S_IWUSR);                 if (node_list[i].fd < 0) {                         printf("open fd error , exit !\n");                         exit(1);                 }         }         //创建线程               for(i=0;i<4; i++) {                 num =(int*)malloc(sizeof(int));                 *num = i;                 pthread_create(NULL, NULL, thread_func, num);         }         pause(); } void *thread_func(void *arg) {         pthread_t          pid;         char               buf[100];         int                w_fd, num;         num = *(int*)arg;         free(arg);         pid = pthread_self();         pthread_detach(pid);         sprintf(buf, "%d", num+1);         w_fd = node_list[num].fd;         for (; ; )         {                         //写文件                 if (write(w_fd, (void*)buf, strlen(buf)) != strlen(buf)) {                         printf("write something to file error !\n");                         break;                 }                 //通知下一个线程写                       if (write(node_list[num].w_pipe, (void*)&w_fd, sizeof(int)) != sizeof(int)) {                         printf("write fd to pipe error !\n");                         break;                 }                 if (read(node_list[num].r_pipe, &w_fd, sizeof(int)) != sizeof(int)) {                         printf("read fd from pipe error !\n");                         break;                 }         }         pthread_exit(0); }

[ 本帖最后由 anthony1983 于 2007-10-31 08:38 编辑 ]

msj0520

我修改了一下楼主的，本人编程太菜，希望大家谅解，努力中。
我怎么发现我程序运行的效率比5楼的高啊，不明白。

#include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include <errno.h> #include <unistd.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct {         int fd;         pthread_mutex_t lock; }node; node node_list[5]; const char* file_name[] = {NULL, "./a", "./b", "./c", "./d"}; void *thread_fun(void* arg); int main() {         /*init node list*/         int i;         for(i = 0; i < 5; i++)         {                 if(pthread_mutex_init(&node_list[i].lock, NULL) == -1)                 {                         fprintf(stderr, "failed to initialize mutex lock:%s\n", strerror(errno));                         return -1;                 }                 if(i != 0)                 {                         if( pthread_mutex_lock(&node_list[i].lock) == -1)                         {                                 fprintf(stderr, "failed to lock mutex lock:%s\n", strerror(errno));                                 return -1;                         }                         node_list[i].fd = open(file_name[i], O_CREAT | O_WRONLY| O_APPEND, S_IRUSR|S_IWUSR);                 }         }         /*create thread*/         for(i = 1; i < 5; i++)         {                 pthread_t pid;                 int* num = (int *)malloc(sizeof(int));                 *num = i;                 pthread_create(&pid, NULL, thread_fun, num);         }         pause();         return 0; } void *thread_fun(void *arg) {         pthread_t pid;         int num = *(int *)arg;         char buf[100];         int current,last;         free(arg);         pid = pthread_self();         pthread_detach(pid);         sprintf(buf, "%d", num);         current = num;         while(1)         {                 if(current)write(node_list[current].fd, buf, strlen(buf));                 last = current--;                 if(current < 0)                         current = 4;                 if( pthread_mutex_lock(&node_list[current].lock) == 0 )                         pthread_mutex_unlock(&node_list[last].lock);         } }

[ 本帖最后由 msj0520 于 2007-10-30 20:05 编辑 ]

anthony1983

那个效率本来就不高，想了几秒钟就写出来的，后来也懒得去优化了。看看我刚想的那个解法吧 共同进步

[ 本帖最后由 anthony1983 于 2007-10-30 20:33 编辑 ]

msj0520

恩，看了74楼的，构思很巧妙！谁拿到句柄谁写！

anthony1983

原帖由 msj0520 于 2007-10-30 22:33 发表
恩，看了74楼的，构思很巧妙！谁拿到句柄谁写！

这道题应该还有更多的解法

xB1ue

一开始考虑错了，绕了点弯路，怎么都有问题，郁闷。晚上看着小说，福灵心至，分分钟写完，心情舒畅。

1. 
   
2. #include <stdio.h>
   
3. #include <pthread.h>
   
4. 
   
5. #define MAX_NAME    255
   
6. #define MAX_BUFF    4096
   
7. 
   
8. typedef struct _TH_FILE {
   
9.     char Name[MAX_NAME];
   
10.     pthread_mutex_t mutex;
    
11.     struct _TH_FILE * pNext;
    
12. } TH_FILE, * PTH_FILE;
    
13. 
    
14. TH_FILE thFiles[4] = { 0 };
    
15. 
    
16. typedef struct _TH_CONTS {
    
17.     char Conts[MAX_BUFF];
    
18. } TH_CONTS, * PTH_CONTS;
    
19. 
    
20. TH_CONTS thConts[4] = { 0 };
    
21. 
    
22. void * thWriter( void * pParas ) {
    
23.     unsigned int nIdx = (unsigned int)pParas;
    
24.     PTH_FILE pFile = &thFiles[nIdx], pTmp;
    
25.     const char * pConts = thConts[nIdx].Conts;
    
26.     FILE * fp = NULL;
    
27.    
    
28.     while( 1 ) {
    
29.         pthread_mutex_lock( &(pFile->mutex) );
    
30.         
    
31.         // For testing
    
32.         /*
    
33.         switch( nIdx ) {
    
34.             case 0:
    
35.                 usleep( 17 );
    
36.                 break;
    
37.             case 1:
    
38.                 usleep( 5 );
    
39.                 break;
    
40.             case 2:
    
41.                 usleep( 182 );
    
42.                 break;
    
43.             case 3:
    
44.                 usleep( 93 );
    
45.                 break;
    
46.         }
    
47.         */
    
48.         
    
49.         if( ( fp = fopen( pFile->Name, "ab+" ) ) != NULL ) {
    
50.             fwrite( pConts, sizeof( char ), strlen( pConts ), fp );
    
51.             fclose( fp );
    
52.         }
    
53.         
    
54.         pTmp = pFile;
    
55.         pFile = pFile->pNext;
    
56.         pthread_mutex_unlock( &(pTmp->mutex) );
    
57.     }
    
58.    
    
59.     return( NULL );
    
60. }
    
61. 
    
62. int main( void ) {
    
63.     pthread_attr_t thAttr = { 0 };
    
64.    
    
65.     strcpy( (char *)&(thFiles[0].Name), "/tmp/A" );
    
66.     strcpy( (char *)&(thFiles[1].Name), "/tmp/B" );
    
67.     strcpy( (char *)&(thFiles[2].Name), "/tmp/C" );
    
68.     strcpy( (char *)&(thFiles[3].Name), "/tmp/D" );
    
69. 
    
70.     /*
    
71.      * "1": ADCBA...
    
72.      * "2": BADCB...
    
73.      * "3": CBADC...
    
74.      * "4": DCBAD...
    
75.     */
    
76.     thFiles[0].pNext = &thFiles[3]; // 写"1 "，线程写完A后写D
    
77.     thFiles[1].pNext = &thFiles[0]; // 写"2 "，线程写完B后写A
    
78.     thFiles[2].pNext = &thFiles[1]; // 写"3 "，线程写完C后写B
    
79.     thFiles[3].pNext = &thFiles[2]; // 写"4 "，线程写完D后写C
    
80. 
    
81.     pthread_mutex_init( &(thFiles[0].mutex), NULL );
    
82.     pthread_mutex_init( &(thFiles[1].mutex), NULL );
    
83.     pthread_mutex_init( &(thFiles[2].mutex), NULL );
    
84.     pthread_mutex_init( &(thFiles[3].mutex), NULL );
    
85. 
    
86.     memcpy( &(thConts[0].Conts), "1 ", strlen( "1 " ) );
    
87.     memcpy( &(thConts[1].Conts), "2 ", strlen( "2 " ) );
    
88.     memcpy( &(thConts[2].Conts), "3 ", strlen( "3 " ) );
    
89.     memcpy( &(thConts[3].Conts), "4 ", strlen( "4 " ) );
    
90. 
    
91.     pthread_attr_init( &thAttr );
    
92.     pthread_attr_setdetachstate( &thAttr, PTHREAD_CREATE_DETACHED );
    
93.    
    
94.     pthread_t tid = 0;
    
95.     pthread_create( &tid, &thAttr, thWriter, (void *)(0) );
    
96.     pthread_create( &tid, &thAttr, thWriter, (void *)(1) );
    
97.     pthread_create( &tid, &thAttr, thWriter, (void *)(2) );
    
98.     pthread_create( &tid, &thAttr, thWriter, (void *)(3) );
    
99. 
    
100.     pthread_attr_destroy( &thAttr );
     
101.    
     
102.     while( 1 ) {
     
103.         sleep( 10000 );
     
104.     }
     
105.         
     
106.     return( 0 );   
     
107. }
     
108. 
     

复制代码

anthony1983

原帖由 xB1ue 于 2007-11-1 00:26 发表
一开始考虑错了，绕了点弯路，怎么都有问题，郁闷。晚上看着小说，福灵心至，分分钟写完，心情舒畅。


#include
#include

#define MAX_NAME    255
#define MAX_BUFF    4096

typedef struct _TH ...

锁链是这样子滴呀。学习了~