使用信号量的冒泡排序算法
Bubble sort algorithm using Semaphores
我的任务是创建适当的信号量并相应地使用 signal 和 wait 命令以使排序正常工作。我得到了以下框架代码
Bubble.cpp
#include <iostream>
#include <sched.h>
#include <time.h>
#include <pthread.h>
#include "sem.h"
#define NUM_CELLS 32
using namespace std;
extern sim_semaphore create_sim_sem(int) ;
extern void wait_sem (sim_semaphore) ;
extern void signal_sem (sim_semaphore) ;
/* When debugging, we need to use this lock to get
intelligible printouts of what the various threads are
doing. Warning: Don't change how this is done.
If you insist on changing it, you need to have
thought a WHOLE lot about the consequences. */
pthread_mutex_t stdoutLock ;
/* Here declare whatever semaphores, flags, counters, and
so forth, that you want to use for synchronization. Variables
declared here will be visible to (shared by) all
the threads in the task. */
/* This is the array that will be filled and then sorted by
a group of child threads. */
int cell[NUM_CELLS] ;
/* These are global variable to represent threads created dynamically. */
pthread_t thr[NUM_CELLS] ;
/* This is included to facilitate adding random delays in the code -- as a
debugging aid. */
extern long random(void);
/* This can be changed to 1, but diagnostic output will probably
seem excessive. */
int checking = 0 ;
/* A data type - a struct with an int field to represent a thread ID. */
struct threadIdType
{
int id ;
};
/* ################################################## */
/* init */
/* ################################################## */
void init()
{
/* This code initializes special lock for screen output.
Just leave this alone. */
if ( 0!=pthread_mutex_init(&stdoutLock, NULL) )
{ cout << "MUTEX INITIALIZATION FAILURE!" << endl ;
exit(-1) ;}
/* Here insert the code you want to intialize semaphores, flags, counters,
and so forth. */
/* This initializes a random number generator */
srandom(time((time_t *) 0));
}
/* ################################################## */
/* child */
/* ################################################## */
void * child(void * idPtr)
{
int m_delay, j ;
/* This is just a change of data type for convenience.
Now 'me' is the number of the child. Children have
numbers from 1 to 31=NUM_CELLS-1. */
int me = ((threadIdType *) (idPtr))->id, temp ;
do
{
/* Put entry code below here. */
/* This next segment of code is 'critical' because TWO child threads
can access most of the cells. */
if (cell[me-1] > cell[me])
{
/* Start the swap of the cell values. */
temp = cell[me-1] ;
cell[me-1] = cell[me] ;
/* I inserted delay code here below to magnify the chances
that child threads will interfere with each other.
It's a "stress test" -- if the synchronization code
the student puts in the program is good, the delays
won't cause incorrect results. On the other hand,
if the student's code is flawed, the delay code below may
increase the likelihood that the program will output
incorrect results. Leave this here. */
m_delay = (int) random()%100 ;
for (j=0; j<m_delay; j++) sched_yield();
/* Finish up with the swap. */
cell[me] = temp ;
}
/* Put exit code below here. */
} while (true) ;
pthread_exit ((void *)0) ;
}
/* ################################################## */
/* mother */
/* ################################################## */
/* The mother spawns a given number of children and then waits
for them all to finish. */
void mother()
{
int i;
/* This is a pointer to a struct that contains an int
field - it is a convenient data type to use as the
parameter to the child function. */
threadIdType * idPtr ;
for (i = 1; i < NUM_CELLS ; i++)
{
/* Mother forks a child and detaches it - she will
not join it. In other words, she will not block,
waiting for it to exit. */
idPtr = new threadIdType ;
/* This records the current index as this child's ID */
idPtr->id = i ;
/* The call below is what actually creates the child
thread and passes a pointer to the struct 'idPtr' as
the parameter to the child function. */
if ( 0!=pthread_create(&thr[i], NULL, child, (void *) idPtr) )
{ cout << "THREAD CREATION FAILURE!" << endl ;
exit(-1) ; }
if (0!=pthread_detach(thr[i]))
{ cout << "THREAD DETACHMENT FAILURE!" << endl ;
exit(-1) ;}
}
bool sorted ;
int m_delay, j;
/* The code below can be used to check to see if the
list is sorted. However, you can't leave it just as it
is. When the mother checks the condition
cell[i-1] > cell[i]
she is accessing memory that she shares with
one or two of the child threads, and the child threads
could be writing that memory concurrently, so you need to
add entry and exit code that synchronizes the
mother with the children.
You can try to think of an algorithm different from the
one below, if you want. It's possible for
the child processes to figure out collectively
whether the list is sorted. */
do
{
/* You can insert random delays like the
one below where you want - to vary
timing. */
/*
m_delay = (int) random()%100 ;
for (j=0; j<m_delay; j++) sched_yield();
*/
/* MOTHER WALKS UP THE ARRAY, CHECKING */
sorted = true ;
/* You may need to add some entry code here. */
for (i=1; i<NUM_CELLS; i++)
{
/* You may need to add some entry code here. */
if (cell[i-1] > cell[i]) sorted = false ;
/* You may need to add some exit code here. */
}
/* You may need to add some exit code here. */
} while (!sorted) ;
/* This code prints the array - which should be sorted now. */
for (i=0; i<NUM_CELLS; i++) cout << cell[i] << endl ;
}
/* ################################################## */
/* main */
/* ################################################## */
int main()
{
/* This calls the function that performs initializations. */
init();
int idx ;
/* Read the (unsorted) input into the array */
for (idx=0; idx<NUM_CELLS; idx++) cin >> cell[idx] ;
/* Echo the (unsorted) input to the screen. */
for (idx=0; idx<NUM_CELLS; idx++) cout << cell[idx]
<< endl ;
cout << endl ;
/* Execute the mother() function, which creates the
child threads that sort the list. */
mother();
return 0 ;
}
我以前使用过一些信号量，但我对这个概念还是很陌生，可能需要更多指导。
我需要创建全局信号量变量，我以前做过类似的事情，例如：
sim_semaphore empty[i] ;
sim_semaphore full[i] ;
我可以再次使用相同的逻辑吗？意思是当一个单元格有一个值（也就是满的）并且正在被交换时，我会相应地使用 signal/wait 命令吗？我可以只使用两个不同的信号量来解决这个问题吗？
接下来我必须在 init() 中初始化它们，上次我这样做时我使用了 for 循环，示例：
for (index=0; index<numTrivets; index++) full[index] = create_sim_sem(0) ;
这是再次执行此操作的最有效方法吗？
最后，在它说我需要进入和退出代码的地方，我考虑通过初始化 boolean flag 并设置 flag = 1 进行第一次传递并返回 flag = 0 来使用 Peterson 的解决方案，当它完成了。但是，我开始相信这不是尝试解决此程序的 "most correct" 方法。我应该怎么做呢？
感谢所有花时间帮助我的人！如果您有任何问题或需要澄清，请随时问我，我会尽我所能帮助我解决这个问题。
我从这里的上一个程序中提取示例：
我参考了彼得森的解决方案，可以在这里找到：http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm
回答我的问题，解决方案比我想象的要简单。一开始我只需要一个信号量数组，
sim_semaphore semArray[NUM_CELLS] ;
然后按照我的问题进行初始化。
for (index=0; index<NUM_CELLS; index++) semArray[index] = create_sim_sem(1) ;
child 的工作仅由 signal 和 wait 组成，目标是能够一次交换所有数据，而不必一次等待一个.您可以通过让 child 在实际交换算法发生之前等待 i-1 和 i 并在算法之后在 i-1 和 i 上发出信号来做到这一点。
妈妈的工作基本上是沿着数据线走下去，仔细检查 child 是否完成了它的工作。您可以通过在已实现的 for-loop 之前和之后创建一个 for-loop 来完成此操作。之后，您需要做的就是 i 上的 wait 和 i 上的 signal 之后。这只是一种解决方案，还有更复杂的解决方案，但这可能是最简单的。
我的任务是创建适当的信号量并相应地使用 signal 和 wait 命令以使排序正常工作。我得到了以下框架代码
Bubble.cpp
#include <iostream>
#include <sched.h>
#include <time.h>
#include <pthread.h>
#include "sem.h"
#define NUM_CELLS 32
using namespace std;
extern sim_semaphore create_sim_sem(int) ;
extern void wait_sem (sim_semaphore) ;
extern void signal_sem (sim_semaphore) ;
/* When debugging, we need to use this lock to get
intelligible printouts of what the various threads are
doing. Warning: Don't change how this is done.
If you insist on changing it, you need to have
thought a WHOLE lot about the consequences. */
pthread_mutex_t stdoutLock ;
/* Here declare whatever semaphores, flags, counters, and
so forth, that you want to use for synchronization. Variables
declared here will be visible to (shared by) all
the threads in the task. */
/* This is the array that will be filled and then sorted by
a group of child threads. */
int cell[NUM_CELLS] ;
/* These are global variable to represent threads created dynamically. */
pthread_t thr[NUM_CELLS] ;
/* This is included to facilitate adding random delays in the code -- as a
debugging aid. */
extern long random(void);
/* This can be changed to 1, but diagnostic output will probably
seem excessive. */
int checking = 0 ;
/* A data type - a struct with an int field to represent a thread ID. */
struct threadIdType
{
int id ;
};
/* ################################################## */
/* init */
/* ################################################## */
void init()
{
/* This code initializes special lock for screen output.
Just leave this alone. */
if ( 0!=pthread_mutex_init(&stdoutLock, NULL) )
{ cout << "MUTEX INITIALIZATION FAILURE!" << endl ;
exit(-1) ;}
/* Here insert the code you want to intialize semaphores, flags, counters,
and so forth. */
/* This initializes a random number generator */
srandom(time((time_t *) 0));
}
/* ################################################## */
/* child */
/* ################################################## */
void * child(void * idPtr)
{
int m_delay, j ;
/* This is just a change of data type for convenience.
Now 'me' is the number of the child. Children have
numbers from 1 to 31=NUM_CELLS-1. */
int me = ((threadIdType *) (idPtr))->id, temp ;
do
{
/* Put entry code below here. */
/* This next segment of code is 'critical' because TWO child threads
can access most of the cells. */
if (cell[me-1] > cell[me])
{
/* Start the swap of the cell values. */
temp = cell[me-1] ;
cell[me-1] = cell[me] ;
/* I inserted delay code here below to magnify the chances
that child threads will interfere with each other.
It's a "stress test" -- if the synchronization code
the student puts in the program is good, the delays
won't cause incorrect results. On the other hand,
if the student's code is flawed, the delay code below may
increase the likelihood that the program will output
incorrect results. Leave this here. */
m_delay = (int) random()%100 ;
for (j=0; j<m_delay; j++) sched_yield();
/* Finish up with the swap. */
cell[me] = temp ;
}
/* Put exit code below here. */
} while (true) ;
pthread_exit ((void *)0) ;
}
/* ################################################## */
/* mother */
/* ################################################## */
/* The mother spawns a given number of children and then waits
for them all to finish. */
void mother()
{
int i;
/* This is a pointer to a struct that contains an int
field - it is a convenient data type to use as the
parameter to the child function. */
threadIdType * idPtr ;
for (i = 1; i < NUM_CELLS ; i++)
{
/* Mother forks a child and detaches it - she will
not join it. In other words, she will not block,
waiting for it to exit. */
idPtr = new threadIdType ;
/* This records the current index as this child's ID */
idPtr->id = i ;
/* The call below is what actually creates the child
thread and passes a pointer to the struct 'idPtr' as
the parameter to the child function. */
if ( 0!=pthread_create(&thr[i], NULL, child, (void *) idPtr) )
{ cout << "THREAD CREATION FAILURE!" << endl ;
exit(-1) ; }
if (0!=pthread_detach(thr[i]))
{ cout << "THREAD DETACHMENT FAILURE!" << endl ;
exit(-1) ;}
}
bool sorted ;
int m_delay, j;
/* The code below can be used to check to see if the
list is sorted. However, you can't leave it just as it
is. When the mother checks the condition
cell[i-1] > cell[i]
she is accessing memory that she shares with
one or two of the child threads, and the child threads
could be writing that memory concurrently, so you need to
add entry and exit code that synchronizes the
mother with the children.
You can try to think of an algorithm different from the
one below, if you want. It's possible for
the child processes to figure out collectively
whether the list is sorted. */
do
{
/* You can insert random delays like the
one below where you want - to vary
timing. */
/*
m_delay = (int) random()%100 ;
for (j=0; j<m_delay; j++) sched_yield();
*/
/* MOTHER WALKS UP THE ARRAY, CHECKING */
sorted = true ;
/* You may need to add some entry code here. */
for (i=1; i<NUM_CELLS; i++)
{
/* You may need to add some entry code here. */
if (cell[i-1] > cell[i]) sorted = false ;
/* You may need to add some exit code here. */
}
/* You may need to add some exit code here. */
} while (!sorted) ;
/* This code prints the array - which should be sorted now. */
for (i=0; i<NUM_CELLS; i++) cout << cell[i] << endl ;
}
/* ################################################## */
/* main */
/* ################################################## */
int main()
{
/* This calls the function that performs initializations. */
init();
int idx ;
/* Read the (unsorted) input into the array */
for (idx=0; idx<NUM_CELLS; idx++) cin >> cell[idx] ;
/* Echo the (unsorted) input to the screen. */
for (idx=0; idx<NUM_CELLS; idx++) cout << cell[idx]
<< endl ;
cout << endl ;
/* Execute the mother() function, which creates the
child threads that sort the list. */
mother();
return 0 ;
}
我以前使用过一些信号量，但我对这个概念还是很陌生，可能需要更多指导。
我需要创建全局信号量变量，我以前做过类似的事情，例如：
sim_semaphore empty[i] ;
sim_semaphore full[i] ;
我可以再次使用相同的逻辑吗？意思是当一个单元格有一个值（也就是满的）并且正在被交换时，我会相应地使用 signal/wait 命令吗？我可以只使用两个不同的信号量来解决这个问题吗？
接下来我必须在 init() 中初始化它们，上次我这样做时我使用了 for 循环，示例：
for (index=0; index<numTrivets; index++) full[index] = create_sim_sem(0) ;
这是再次执行此操作的最有效方法吗？
最后，在它说我需要进入和退出代码的地方，我考虑通过初始化 boolean flag 并设置 flag = 1 进行第一次传递并返回 flag = 0 来使用 Peterson 的解决方案，当它完成了。但是，我开始相信这不是尝试解决此程序的 "most correct" 方法。我应该怎么做呢？
感谢所有花时间帮助我的人！如果您有任何问题或需要澄清，请随时问我，我会尽我所能帮助我解决这个问题。
我从这里的上一个程序中提取示例：
我参考了彼得森的解决方案，可以在这里找到：http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm
回答我的问题，解决方案比我想象的要简单。一开始我只需要一个信号量数组，
sim_semaphore semArray[NUM_CELLS] ;
然后按照我的问题进行初始化。
for (index=0; index<NUM_CELLS; index++) semArray[index] = create_sim_sem(1) ;
child 的工作仅由 signal 和 wait 组成，目标是能够一次交换所有数据，而不必一次等待一个.您可以通过让 child 在实际交换算法发生之前等待 i-1 和 i 并在算法之后在 i-1 和 i 上发出信号来做到这一点。
妈妈的工作基本上是沿着数据线走下去，仔细检查 child 是否完成了它的工作。您可以通过在已实现的 for-loop 之前和之后创建一个 for-loop 来完成此操作。之后，您需要做的就是 i 上的 wait 和 i 上的 signal 之后。这只是一种解决方案，还有更复杂的解决方案，但这可能是最简单的。