POSIX Semaphores in Linux

[RyanV]

Hi,

I need to make a program that takes as input a series of customers for cashiers.
Each customer has an amount of time the system sleeps until they arrives.
Once they arrive each customer is forked into a separate process and then selects the cashier alice if n_alice (the number of customers queued up for alice) is less than or equal to cashier bob. If not they select cashier bob.
The cashiers are represented by semaphores.

So far my program appears to be forking properly, but seems to get hung up performing sem_wait(n_bob) and I am assuming the computer I am using (part of the cluster on campus) terminates the process once it does nothing for a while.

Here is my code:

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <stdio.h>
#include <semaphore.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <string>
#include <unistd.h>

using std::cout;
using std::vector;
using std::stringstream;
using std::ifstream;
using std::string;

struct customer
{
	int serialNumber;
	int timeToArrival;
	int executionTime;
};

void populateCustomerQueue(vector<customer*>&, char*);
int whoHasControl(vector<int>);

int main(int argc, char* argv[])
{
	//Ensure the proper number of input arguments were provided
	if(argc != 2)
	{
		cout << "Improper number of input arguments.\n";
		exit(1);
	}
	
	//Creates semaphores for: alice, bob, n_alice, n_bob
	sem_t* alice;
	char alice_name[] = "RV_alice";
	//unsigned int alice_initial_value;
	alice = sem_open(alice_name, O_CREAT);

	sem_t* n_alice;
	char n_alice_name[] = "RV_n_alice";
	//unsigned int n_alice_initial_value;
	n_alice = sem_open(n_alice_name, O_CREAT);
	
	sem_t* bob;
	char bob_name[] = "RV_bob";
	//unsigned int bob_initial_value;
	bob = sem_open(bob_name, O_CREAT);

	sem_t* n_bob;
	char n_bob_name[] = "RV_n_bob";
	//unsigned int n_bob_initial_value;
	n_bob = sem_open(n_bob_name, O_CREAT);

	//Creates shared int values for the queue size for Alice and Bob
	int n_alice_shmid;
	key_t n_alice_key;
	size_t n_alice_sizechar = sizeof(int);
	n_alice_shmid = shmget(n_alice_key, n_alice_sizechar, 0600 | IPC_CREAT);
	int* n_alice_shm = (int*) shmat(n_alice_shmid, 0, 0);
	*n_alice_shm = 0;

	cout << "n_alice>shm = " << *n_alice_shm << "\n";

	int n_bob_shmid;
	key_t n_bob_key;
	size_t n_bob_sizechar = sizeof(int);
	n_bob_shmid = shmget(n_bob_key, n_bob_sizechar, 0600 | IPC_CREAT);
	int* n_bob_shm = (int*) shmat(n_bob_shmid, 0, 0);
	*n_bob_shm = 0;
	cout << "n_bob_shm = " << *n_bob_shm << "\n";

	//Initialize and populate the vector containing the customer queue
	vector<int> accessArray;
	vector<customer*> customerQueue;
	populateCustomerQueue(customerQueue, argv[1]);

	//CHECK VALUES OF CUSTOMER QUEUE
	/*for(int i = 0; i < customerQueue.size(); i++)
	{
		cout << customerQueue[i]->serialNumber << " "
			 << customerQueue[i]->timeToArrival << " "
			 << customerQueue[i]->executionTime << "\n";
	}*/
	//FINISH CHECKING VALUES FOR CUSTOMER QUEUE

	pid_t pid;		//Initialize the pid variable

	//Iterate through the customer queue, sleeping in between customers until they arrive
	//then placing them into the appropriate queue. After each customer has been checked
	//out their process exits
	for(int i = 0; i < customerQueue.size(); i++)
	{
		cout << "Executing for loop, cycle " << i << "\n";
		if(customerQueue[i]->timeToArrival == 0)
		{
			cout << "Customer " << customerQueue[i]->serialNumber << " is being processed.\n";
			sleep(customerQueue[i]->executionTime);
			cout << "Done sleeping.\n";
			pid = fork();
			if(pid == 0)
			{
				cout << "Customer " << customerQueue[i]->serialNumber << " has been given a thread.\n";
				sem_wait(n_alice);
				cout << "Got alice.\n";
				sem_wait(n_bob);
				cout << "Got bob and alice.\n";
				if(*n_alice_shm >= *n_bob_shm)
				{
					*n_alice_shm++;
					sem_post(n_alice);
					sem_post(n_bob);
					cout << "Customer" << customerQueue[i]->serialNumber << " selected Alice.\n";
					sem_wait(alice);
					sleep(customerQueue[i]->executionTime);
					sem_post(alice);
					cout << "Customer " << customerQueue[i]->serialNumber << " leaves the supermarket.\n";	
					_exit(0);
				}
				else
				{
					*n_bob_shm++;
					sem_post(n_alice);
					sem_post(n_bob);
					cout << "Customer" << customerQueue[i]->serialNumber << " selected Bob.\n";
					sem_wait(bob);
					sleep(customerQueue[i]->executionTime);
					sem_post(bob);
					cout << "Customer " << customerQueue[i]->serialNumber << " leaves the supermarket.\n";
					_exit(0);
				}
			}
		}
		else
		{
			cout << "Customer " << customerQueue[i]->serialNumber << " is being processed.\n";
			sleep(customerQueue[i]->timeToArrival);
			pid = fork();
			if(pid == 0)
			{
				cout << "Customer " << customerQueue[i]->serialNumber << " has been given a thread.\n";
				sem_wait(n_alice);
				cout << "Got alice.\n";
				sem_wait(n_bob);
				cout << "Got bob and alice.\n";
				if(*n_alice_shm >= *n_bob_shm)
				{
					*n_alice_shm++;
					sem_post(n_alice);
					sem_post(n_bob);
					cout << "Customer" << customerQueue[i]->serialNumber << " selected Alice.\n";
					sem_wait(alice);
					sleep(customerQueue[i]->executionTime);
					sem_post(alice);
					cout << "Customer " << customerQueue[i]->serialNumber << " leaves the supermarket.\n";	
					_exit(0);
				}
				else
				{
					*n_bob_shm++;
					sem_post(n_alice);
					sem_post(n_bob);
					cout << "Customer" << customerQueue[i]->serialNumber << " selected Bob.\n";
					sem_wait(bob);
					sleep(customerQueue[i]->executionTime);
					sem_post(bob);
					cout << "Customer " << customerQueue[i]->serialNumber << " leaves the supermarket.\n";
					_exit(0);
				}
				sleep(customerQueue[i]->executionTime);
				_exit(0);
			}
		}
	}
}

int whoHasControl(vector<int> control)
{
	if(control.size() == 0) return 0;
	for(int i = 0; i < control.size(); i++)
	{
		if(control[i] == 1)
			return 1;
	}
	return 0;
}

void populateCustomerQueue(vector<customer*>& customerQueue, char* fileName)
{
	ifstream inputFile (fileName);
	string tempString;
	while(getline(inputFile, tempString))
	{
		stringstream ss;
		customer* tempCustomer = new customer;
		ss << tempString;
		int tempSerialNumber;
		int tempTimeToArrival;
		int tempExecutionTime;
		ss >> tempSerialNumber >> tempTimeToArrival >> tempExecutionTime;
		tempCustomer->serialNumber = tempSerialNumber;
		tempCustomer->timeToArrival = tempTimeToArrival;
		tempCustomer->executionTime = tempExecutionTime;
		customerQueue.push_back(tempCustomer);
		tempCustomer = NULL;
	}
}

running the following input file:

1 0 10
2 2 10
3 3 15
4 4 8
5 5 12

and here is my output:

n_alice>shm = 0
n_bob_shm = 0
Executing for loop, cycle 0
Customer 1 is being processed.
Done sleeping.
Customer 1 has been given a thread.
Got alice.
Executing for loop, cycle 1
Customer 2 is being processed.
Customer 2 has been given a thread.
Got alice.
Executing for loop, cycle 2
Customer 3 is being processed.
Customer 3 has been given a thread.
Got alice.
Executing for loop, cycle 3
Customer 4 is being processed.
Customer 4 has been given a thread.
Got alice.
Executing for loop, cycle 4
Customer 5 is being processed.
Customer 5 has been given a thread.
Got alice.

I'm not sure where I messed up and would appreciate some clarification. Thanks.

[Svnyster]

Here's a few problems I see that'll hopefully get you back on the right track.

1) You don't need the if statement at line 105. Just use sleep(customerQueue[i]->timeToArrival); outside of the fork, and it'll sleep if it needs to.

2) Get rid of line 108. You don't want the sleep for the executionTime to be performed outside of the fork.

3) It looks like you're going to need one pid for each process (5 in your example). You can create an array of pid_t and use customerQueue.size() to determine the appropriate size.

4) You are not decreasing *n_alice_shm and *n_bob_shm after a customer has been processed.

5) At line 118, you're checking if *n_alice_shm >= *n_bob_shm, which will always be true. I believe you meant to type if(*n_alice_shm <= *n_bob_shm)

[RyanV]

Cool, thanks!

I figured out why it got hung up waiting for n_bob, I forgot to unlink the semaphores after I used them. I don't fully understand why that caused the problem, but once I had my program start unlinking them, that part worked.

I'm a little confused on why you say I need a pid for each child process. The way I am looking at it, all I need pid for is to know whether or not I am in the child process. And since Linux copies-on-write, the pid that I get when I fork will be preserved for each child process.

I got my program to work without using an array of pids, but something interesting happened that I don't understand. It would only update the value of *n_alice_shm or *n_bob_shm if I did ++*n_alice_shm or ++*n_bob_shm. If I did *n_alice_shm++ it wouldn't update the value! Do you have any idea why that happened?

[Svnyster]

With the pids, I saw that your output was "Got alice." for each customer and thought that each fork was going to Alice, rather than selecting the lowest queue.

As for incrementing/decrementing the pointers, pointers have to be incremented and decremented in a specific way. Here's the different types of operators:

*p++   // same as *(p++): increment pointer, and dereference unincremented address
*++p   // same as *(++p): increment pointer, and dereference incremented address
++*p   // same as ++(*p): dereference pointer, and increment the value it points to
(*p)++ // dereference pointer, and post-increment the value it points to 

So in your case, ++*p would work, or you could use *p += *p