stack/hopr

Using Windows Event Objects to Sync / Queue Parallel Tasks

Windows Event Objects is a wonderful mechanism provided to sync a lot of things happening in parallel. Particularly, in controlling a lot of things happening in parallel. Recently, I did just the same.

The scenario here is piece of code which downloads a lot of files. But, this piece of code can be deadly as it can downloads a lot of files. It has virtually no limit. You ask it to download 10 files, it will, you ask for 100, it sure will. This may be good for the client, but may choke the server to death. That’s not very good for the server. Hence, we need to limit the number of files being downloaded to some decent number.

One option, is to fire a certain number of downloads and keep waiting on them in a loop. As soon as one finishes, start the next one. Only downside: the loop. Looping continuously without sleeping can be painful for the processor. We can sleep for say, 100ms, between consecutive polls. But, this adds latency between the time that one file finishes and the next one begins. That is, there could be a maximum delay of 100ms between one file finishing and the next one starting. Latency is a waste of time.

Using event objects takes out the latency part from the above polling logic. We create events for each of the downloading files and then wait on those events. The thread waiting on an event is unblocked immediately after an event becomes signaled (an event can be signaled by a downloading thread). Thus, no latency.

The sample program, events.cpp is demonstrating such a strategy. The function “parallel_download” takes a list of files to be downloaded and and the file count. Here, we’re only simulating a download, as doing a real download is out of scope of this algorithm. The thread “download_file” downloads (simulates downloading) a file.

Pasting function “parallel_download” here. The code + comments explain the logic.

void parallel_download(int file_list[], int file_count)
{

	HANDLE event_handle_list[max_parallel_downloads];
	vector<file_data> file_data_list;
	DWORD dret;

	//create a list of files to be downloaded
	for(int i = 0; i < file_count; i++)
	{

		file_data_list.push_back(file_data(i, file_list[i]));
	}

	int download_started_count;

	bool less_than_max_files = max_parallel_downloads > file_count;
	int max_start_count = less_than_max_files ? file_count : max_parallel_downloads;		//in case file count < max parallel downloads

	//first, start download of max permissible no. of files

	for(download_started_count = 0; download_started_count < max_start_count; download_started_count++)
	{

		event_handle_list[download_started_count] = file_data_list[download_started_count].event_handle;
		_beginthread(download_file, 0, (void*)(&file_data_list[download_started_count]));
	}

	//wait for any one file to finish if not less than max no. of files permissible
	dret = WaitForMultipleObjects(max_start_count, event_handle_list, less_than_max_files, 300000);		

	if(!less_than_max_files)
	{

		bool last_wait;
		//one of the files has finished downloading, so start another one
		while(download_started_count + 1 < file_count)
		{

			download_started_count++;

			event_handle_list[dret - WAIT_OBJECT_0] = file_data_list[download_started_count].event_handle;

			_beginthread(download_file, 0, (void*)(&file_data_list[download_started_count]));

			last_wait = (download_started_count + 1) == file_count;		//if last wait, wait for all to finish, else wait for any one to finish

			dret = WaitForMultipleObjects(max_start_count, event_handle_list, last_wait, 300000);
		}
	}

	cout<<"\n all files finished\n";
}

Using the sample program

1. Three test functions are provided: test1(), test2() and test3(), call them one by one or all at once to see different sync conditions.

2. Set the const “max_parallel_downloads” to the number you want to limit the donwlodas to. (default = 5).

Note

1. The critical section variable is being used to sync output to stdout. It’s not part of the algorithm. without a critical section, the output may get all garbled in presence of multiple verbose threads.

I have to admit. The first version was put together hastily. With the feedback considered, here’s the second version. Again, the goal of simplicity and no dependency have been adhered to.

Thanks to Andrew, vlademar, Ben, schula and Desu for the quick comments.

Feedback goes like this:

1. No default copy constructor. So, the compiler will provide one and it allows the smart_ptr to be copied to another smart_ptr. It might make the pointer propagate out of scope / trigger multiple deallocations.
A. Facing a design dilemma here.

I have to forbid the assignments. So, I make the assignment operator and the copy constructor private.
Like this:

1. public:     smart_ptr(T* p):ptr(p) {}

2. private:     smart_ptr(smart_ptr& s):ptr(NULL) {}

It’s interesting to note that as long as both the above functions are public,

smart_ptr<myclass> s = new myclass;

calls the first function, which is NOT a copy constructor.

But, if i make the second function private, the compilation fails stating that the copy constructor is private.

Is there anyway, I can make copying a compile time offence and also maintain ability to do ” = new myclass”? Because, I think declaring a variable and initializing it on the same line is the fundamental right of a programmer. Nobody takes it away.

2. No assignment operator. the compiler will provide a default one. And then, same problem as above.
A. Assignment operator declared private.

3. No need to check if pointer in null before deleting it.
A. Extra check removed.

4. Use of “NULL” in place of “0″.
A. I would like to retain it for readability.

5. Why am I writing this class when we already have auto_ptr (STL) and scoped_ptr (boost)?
A. More than anything else, simplicity. Simple enough, for use in local allocations. Second, no dependency on any other library might make sense when you’re writing for embedded systems. Some libraries just may not be available there. Finally, education. Helps new folks learn what’s happening behind the scenes.

6. Const overloads for dereference and arrow operators is needed.
A. The dereference operator and the arrow operator are now aptly const.

7. Throw something derived from std::exception.
A. To keep things small (as in bullet 5), I’m skipping this. Although, I defined a constant “null_pointer_reference” for throwing and catching.

8. The dereferencing operator should throw somthing rather than returning NULL.
A. Yes, it compiles. Throws an exception now.

Code for smart_ptr class (v2) follows:

template<typename T>
class smart_ptr

{
public:
	T* operator->()	const {if(ptr) return ptr; throw null_pointer_reference;}

	T& operator*() const {if(ptr) return *ptr; throw null_pointer_reference;}

	smart_ptr():ptr(NULL) {}

	smart_ptr(T* p):ptr(p) {}

	~smart_ptr() {delete(ptr); ptr = NULL;}		

	smart_ptr& operator=(T* p) {delete(ptr); ptr = p; return *this;}

private:
	smart_ptr& operator=(const smart_ptr& s) {}

	//smart_ptr(smart_ptr& s):ptr(NULL) {}	
protected:
	T* ptr;
};

The complete program (with test cases) is here: smart.cpp.

It’s a really small smart pointer. 9 lines of code. Of course, I had to cut a few corners (newlines;) to make this happen. But, the readability is maintained.

It doesn’t do much other than being smart. Fit for trivial tasks, such as tracking and deleting local memory allocations, avoiding uninitialized references, etc. It’s so small, it cannot count references. But, it does deallocate when it goes out of scope.

Features:
1. Deallocation when the smart pointer goes out of scope.
2. Invalid reference check.
3. Not dependent on any library (including STL). Useful when you need a small binary footprint.

Restrictions:
1. No reference counting. So, avoid assigning one smart_ptr to another. (Enable test2 in the attached program to see the problem.)
2. Works only with “new” and not with “new []” or “malloc”. Needs further templatization for that to be handled. But, kills the simplicity of the current class.

Code follows:

template<typename T>
class smart_ptr
{
public:
   T* operator->() {if(ptr) return ptr; throw -1;}

   T& operator*() {if(ptr) return *ptr; return NULL;}

   smart_ptr() {ptr = NULL;}

   smart_ptr(T* p):ptr(p) {}

   ~smart_ptr() {if (ptr) delete(ptr); ptr = NULL;}

   smart_ptr& operator=(T* p) {if(ptr) delete(ptr); ptr = p; return *this;}

   bool operator==(const T& p1) {return (p1.ptr == ptr);}

   bool operator==(const int i) {return (i == (int)ptr);}

protected:
   T* ptr;
};

Command line for VC++ compiler to build this program:
1. Open Visual Studio command prompt
2. Compile and Link: >cl smart.cpp
3. Run: >smart.exe

Command line for g++ compiler to build this program:
1. Compile and Link: >g++ smart.cpp -o smart
2. Run: >./smart

For usage, see the complete program: smart.cpp