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

麦哥哥

1. 
   
2. #include <unistd.h>
   
3. #include <stdio.h>
   
4. #include <pthread.h>
   
5. #include <string.h>
   
6. #include <errno.h>
   
7. #include <sys/types.h>
   
8. #include <sys/stat.h>
   
9. #include <fcntl.h>
   
10. #include <stdlib.h>
    
11. 
    
12. #define THREAD_NUM        (4)
    
13. #define        FILE_NUM        THREAD_NUM
    
14. 
    
15. struct _thread_pipe
    
16. {
    
17.         int        w_pipe;
    
18.         int r_pipe;
    
19. //        int file_fd;
    
20. }thread_pipe[THREAD_NUM];
    
21. 
    
22. struct _thread_data
    
23. {
    
24.         pthread_t        thid;
    
25.         int                        *filefds;
    
26.         void                 *data;
    
27.         int                        seq;
    
28. };
    
29. 
    
30. char *file_name[] = {"./A", "./B", "./C", "./D"};
    
31. 
    
32. void *thread_write(void *param)
    
33. {
    
34.         struct _thread_data *thdata = (struct _thread_data *)param;
    
35.         int                                        i = 0;
    
36.         char                                c = 0;
    
37.        
    
38.         for (i = 0; i <= thdata->seq; ++i)
    
39.         {
    
40.                 int                nlen = strlen((char *)thdata->data);
    
41.                 if (write(thdata->filefds[i], (char *)thdata->data, nlen) != nlen)
    
42.                 {
    
43.                         fprintf(stderr, "write error: %s\n", strerror(errno) );
    
44.                         pthread_exit( (void *)-1);
    
45.                 }
    
46.         }
    
47.        
    
48.         if (thdata->seq == (FILE_NUM-1) )  /* last thread write complete */
    
49.         {
    
50.                 c = 1;
    
51.                 write(thread_pipe[THREAD_NUM-1].w_pipe, &c, 1);
    
52.         }
    
53.        
    
54.         while (1)
    
55.         {
    
56.                 read(thread_pipe[thdata->seq].r_pipe, &c, 1);
    
57.                
    
58.                 for (i = 0; i < FILE_NUM; ++i)
    
59.                 {
    
60.                         size_t        nlen = strlen(thdata->data);
    
61.                         write(thdata->filefds[i], thdata->data, nlen);
    
62.                 }
    
63.                
    
64.                 c = ( ( (c+1)%4)? (c+1) : 1);
    
65.                 write(thread_pipe[thdata->seq].w_pipe, &c, 1);
    
66.         }
    
67.        
    
68.         pthread_exit(0);
    
69. }
    
70. 
    
71. int main(void)
    
72. {
    
73.         int                i = 0;
    
74.         int                pipe_fds[THREAD_NUM][2];
    
75.         struct _thread_data        thread_data[THREAD_NUM];
    
76.         char        *wdata[] = {"1", "2", "3", "4"};
    
77.         int                fds[FILE_NUM];
    
78.        
    
79.         /* create pipe */
    
80.         for (i = 0; i < THREAD_NUM; ++i)
    
81.         {
    
82.                 if (pipe(pipe_fds[i]) < 0)
    
83.                 {
    
84.                         fprintf(stderr, "pipe error: %s\n", strerror(errno));
    
85.                         exit(-1);
    
86.                 }
    
87.         }
    
88.        
    
89.         for (i = 0; i < THREAD_NUM; ++i)
    
90.         {
    
91.                 thread_pipe[i].w_pipe = pipe_fds[i][1];
    
92.                 thread_pipe[(i+1)%THREAD_NUM].r_pipe = pipe_fds[i][0];
    
93.         }
    
94.        
    
95.         for (i = 0; i < FILE_NUM; ++i)
    
96.         {
    
97.                 if ( (fds[i] = open(file_name[i], O_WRONLY | O_CREAT | O_TRUNC, S_IRWXU)) < 0)
    
98.                 {
    
99.                         fprintf(stderr, "open error: %s\n", strerror(errno));
    
100.                         exit(-1);
     
101.                 }
     
102.         }
     
103.        
     
104.         for (i = 0; i < THREAD_NUM; ++i)
     
105.         {
     
106.                 thread_data[i].data = wdata[i];
     
107.                 thread_data[i].seq = i;
     
108.                 thread_data[i].filefds = fds;
     
109.                 pthread_create(&(thread_data[i].thid), NULL, thread_write, &thread_data[i]);
     
110.         }
     
111.        
     
112.         /* wait for thread to terminate */
     
113.         for (i = 0; i < THREAD_NUM; ++i)
     
114.         {
     
115.                 pthread_join(thread_data[i].thid, NULL);
     
116.         }
     
117.        
     
118.         /* close all opened files or devices */
     
119.        
     
120.         return 0;
     
121. }
     
122. 
     

复制代码

独臂剑客

这道题如果用锁去做的话，还要保证锁的顺序，效率就更加不用说了。

为什么不想到用一个buf，四个线程只管输出自己的数值到buf的相应段位置，主线程不停从buf取值输出到文件呢？

shang2010

看一下，没懂

看来水平还不够

麦哥哥

回复 92# 独臂剑客
如何保证4个线程向buf输出的顺序呢，这是个问题吧？

独臂剑客

回复 94# 麦哥哥


    一块buf的话，不同线程处于buf不同位置段，或者4块buf都行，随便写个环形buf都OK.

halababy

我是个多线程新手，不过我跟92楼的想法一样，用4个BUFF，没个线程往固定的位置写，这是一个固定的循环嘛！这样不用用到锁也是对的，主线程可以设置一个定时器，每过一秒刷下缓存，这个时候需要加锁了，如果定时器太麻烦的话也可以在4个线程中间设置一个计数器啊！写多少次的适合就刷新一下，同样需要加锁！

bigxhome

看完题目后，第一个念头就是利用条件锁，于是就写了个试试！新手，多批评！
大体的思路是：每个文件都有一个条件锁，4个线程对每个文件取锁，当取到锁时，查看是不是该此线程写，如果不是的话就解锁，查看下一个文件；如果是的话就写内容到此文件，然后将findex的值赋成下一个该写的线程的值

1. #include <stdio.h>
   
2. #include <pthread.h>
   
3. #include <string.h>
   
4. #include <unistd.h>
   
5. 
   
6. #define NUM 4
   
7. #define FILE_NAME_LEN 8
   
8. typedef struct LockStruct
   
9. {
   
10.         pthread_mutex_t lock;
    
11.         int findex;
    
12. }LockStruct;
    
13. 
    
14. typedef struct MyStruct
    
15. {
    
16.         FILE *fp[NUM];
    
17.         LockStruct flock[NUM];
    
18. }MyStruct;
    
19. 
    
20. MyStruct g_par;
    
21. void* ThreadHandle(void*);
    
22. 
    
23. int main(int argc, char** argv)
    
24. {
    
25.         int i;
    
26. 
    
27. /*
    
28.         init g_par
    
29. */
    
30.         for(i = 0; i < NUM; i++)
    
31.         {
    
32.                 phtread_mutex_init(&g_par.flock[i].lock);
    
33.                 g_par.flock[i].findex = i;
    
34.         }
    
35. 
    
36. /*
    
37.         Open File
    
38. */
    
39.         const char filename[NUM][FILE_NAME_LEN] = {"A", "B", "C", "D"};
    
40.         for(i = 0; i < NUM; i++)
    
41.         {
    
42.                 g_par.fp[i] = fopen(filename[i], "w+");
    
43.                 if(g_par.fp[i] == NULL)
    
44.                 {
    
45.                         printf("Open file %s failed!\n", filename[i]);
    
46.                         exit(-1);
    
47.                 }
    
48.         }
    
49. 
    
50. /*
    
51.         create thread
    
52. */
    
53.         int ret;
    
54.         pthread_t pid[NUM];
    
55.         for(i = 0; i < NUM; i++)
    
56.         {
    
57.                 ret = pthread_create(&pid[i], NULL, ThreadHandle, (void*)&i);
    
58.                 if(ret != 0)
    
59.                 {
    
60.                         printf("create %d thread failed! ret = %d\n", i, ret);
    
61.                         exit(-1);
    
62.                 }
    
63.         }
    
64. 
    
65. /*
    
66.         sleep
    
67. */
    
68.         while(1)
    
69.         {
    
70.                 sleep(1);
    
71.         }
    
72.         return 0;
    
73. }
    
74. 
    
75. 
    
76. void* ThreadHandle(void* arg)
    
77. {
    
78.         int index = *(int*)arg;
    
79.         int i;
    
80.         while(1)
    
81.         {
    
82.                 for(i = 0 ; i < NUM; i++)//对4个文件循环查看
    
83.                 {
    
84. /* 取锁*/
    
85.                         pthread_mutex_lock(&g_par.flock[i].lock);       
    
86.                         if(g_par.flock[i].findex == index) //是不是该本线程写
    
87.                         {
    
88.                                 fprintf(g_par.fp[i], "%d", index+1);//是轮到本线程，写内容
    
89.                                 fflush(g_par.fp[i]);
    
90.                                 g_par.flock[i].findex == 3 ? g_par.flock[i].findex = 0 : g_par.flock[i].findex++; //将findex的值改成下个线程的值
    
91.                         }
    
92.                         pthread_mutex_unlock(&g_par.flock[i].lock);       
    
93.                 }
    
94.         }
    
95. }

复制代码

麦哥哥

回复  麦哥哥


    一块buf的话，不同线程处于buf不同位置段，或者4块buf都行，随便写个环形buf都OK.
独臂剑客 发表于 2011-06-04 08:28

恩。不失为一个更高效率的做法，可以减少锁的使用，而且减少了写文件次数，系统调用少了，效率提高不少。
PS：你Tencent的么？招人？

独臂剑客

回复 98# 麦哥哥


    TX的，现在急招QQ后台开发职位，具体参见：
    http://bbs.chinaunix.net/thread-2327967-1-1.html
   
    麦哥哥及各位cuer，最近有换工作打算的或者各位cuer有朋友、同事等要换工作的，麻烦帮推荐 一下，多谢！

   email到：vultureli@qq.com;wangshuai@vip.qq.com;randy@vip.qq.com;

    如果有想换工作的同学可以站内短信联系我，有相关问题可以站内信息，收到必定回复。

    有想换工作的同学Email啊或有相关同事，朋友想换工作的帮忙推荐 一下， 多谢！

lxyfirst

工作线程围绕文件状态处理，发一个无视CPU的实现，5秒生成的A，B，C，D每个文件均为4M左右。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <unistd.h>
   
4. #include <fcntl.h>
   
5. #include <sys/stat.h>
   
6. #include <sys/types.h>
   
7. #include <pthread.h>
   
8. #include <signal.h>
   
9. 
   
10. #define WORKER_COUNT (4)
    
11. 
    
12. class file_writer
    
13. {
    
14. public:
    
15. 
    
16.     int init(int worker_id)
    
17.     {
    
18.         snprintf(m_filename,sizeof(m_filename),"%c",'A' + worker_id) ;
    
19.         m_fd = open(m_filename,O_WRONLY|O_CREAT);
    
20.         if(m_fd < 0 ) return -1 ;
    
21.         m_worker_id = worker_id ;
    
22.         m_buf_pos = 0  ;
    
23.     }
    
24. 
    
25.     void fini()
    
26.     {
    
27.         if(m_fd >0)
    
28.         {
    
29.             ::write(m_fd,m_buf_data,m_buf_pos) ;
    
30.             close(m_fd) ;
    
31.             m_fd = -1 ;
    
32.         }
    
33. 
    
34.     }
    
35. 
    
36.     int write( int worker_id)
    
37.     {
    
38.         char v = '1' + (char)worker_id ;
    
39.         m_buf_data[m_buf_pos++] = v ;
    
40.         if(m_buf_pos == sizeof(m_buf_data) )
    
41.         {
    
42.             ::write(m_fd,m_buf_data,m_buf_pos) ;
    
43.             m_buf_pos = 0 ;
    
44.         }
    
45.         
    
46.         m_worker_id = (m_worker_id+1)%WORKER_COUNT ;
    
47. 
    
48.     }
    
49. 
    
50.     int get_worker_id()
    
51.     {
    
52.         return m_worker_id ;
    
53.     }
    
54.    
    
55. 
    
56.     file_writer():m_fd(-1) { } ;
    
57.     ~file_writer() { fini() ; } ;
    
58. 
    
59. private:
    
60.     char m_filename[64] ;
    
61.     int m_fd ;
    
62.     int m_worker_id ;
    
63.     char m_buf_data[4096] ;
    
64.     int m_buf_pos ;
    
65. 
    
66. } ;
    
67. 
    
68. typedef struct
    
69. {
    
70.     pthread_t tid ;
    
71.     int worker_id ;
    
72. 
    
73. } worker_info ;
    
74. 
    
75. 
    
76. static file_writer writers[WORKER_COUNT] ;
    
77. 
    
78. static volatile int running = 1 ;
    
79. 
    
80. void* worker_func(void* args)
    
81. {
    
82.     worker_info *worker = (worker_info*)args ;
    
83.     printf("worker %d started , tid:%ld\n",worker->worker_id,worker->tid);
    
84.     while(running)
    
85.     {
    
86.         file_writer *writer = NULL ;
    
87.         for(int i = 0 ; i < WORKER_COUNT ; ++i)
    
88.         {
    
89.             writer = writers + i ;
    
90.             if(writer->get_worker_id() == worker->worker_id )
    
91.             {
    
92.                 writer->write( worker->worker_id) ;
    
93.             }
    
94.         }
    
95. 
    
96.     }
    
97.     printf("worker %d stopped , tid:%ld\n",worker->worker_id,worker->tid);
    
98.     return NULL ;
    
99. }
    
100. 
     
101. int main(int argc,char** argv)
     
102. {
     
103.    
     
104.     worker_info workers[WORKER_COUNT] = {0} ;
     
105.     for(int i=0;i<WORKER_COUNT;++i)
     
106.     {
     
107.         writers[i].init(i) ;
     
108.         workers[i].worker_id = i ;
     
109.         pthread_create(&workers[i].tid,NULL,worker_func,workers+i) ;
     
110. 
     
111.     }
     
112.    
     
113.     sleep(5) ;
     
114.     running = 0 ;
     
115.     for(int i=0;i<WORKER_COUNT;++i)
     
116.     {
     
117.         pthread_join( workers[i].tid,NULL) ;
     
118.     }
     
119. 
     
120.     return 0 ;
     
121. }

复制代码