一道面试题: 实现一个函数，对数组任两个元素实现交换，要求并发

gaoping561

有一个数组a[1000], 写一个函数实现其任两个数据交换，要求并发。
比如a[1] 和 a[99] 交换的同时 a[2] 和 a[3] 也能同时交换而不冲突，但a[1]和和其他数据就不能交换了。

1. void swap(int a[], int index1, int index2)
   
2. {
   
3. 
   
4. int tmp;
   
5. 
   
6. down_interruptible(&sem);
   
7. 
   
8. tmp = a[index1];
   
9. a[index1]=a[index2];
   
10. a[index2]=tmp;
    
11. 
    
12. up(&sem);
    
13. 
    
14. }

复制代码

这种实现显然是不行的，信号量锁住了整个数组，没有实现并发。问题是交换冲突的时候怎么处理？

求解答!

amarant

我感觉有多少个元素就要多少个锁...而且还要小心死锁

Godbach

LZ 实际的需求是什么呢

amarant

lz说了是面试题..

Godbach

晕。我还想呢，直接讨论内核里的实现

tempname2

为啥要发内核版......

gaoping561

回复 6# tempname2


    这里人多啊，而且并发讨论也是和内核有关的话题吧

tempname2

大哥你07注册,难道不知道C版一向比内核版人多吗?那里一样可以讨论并发......

kouu

这个貌似不需要用锁吧，直接用xchg()。
X86下可以直接使用xchgb/xchgw/xchgl指令原子性的实现交换。

longzhang

xchg必须有一个操作数是寄存器吧。
我的想法是使用以下结构。每一次锁的时候将a和b赋值。可以有几个锁，供不同的线程使用，每个线程只能申请一个锁。当申请锁的时候检查已经上锁的a,b是否是你想要操作的数。如果是的话，就等吧

struct{
  int a_vec;
  int b_vec
  sem
}