Skip to content

Lost wake-up in concurrency_breadth_first_search #550

@vil02

Description

@vil02

Describe the bug

I run the tests with the thread sanitizer. The test_bfs takes forever to finish, which indicates that there might be some problem in concurrency_breadth_first_search. When I set num_threads to 1, the problem does not occur.

This seems to be the problematic code:

next_level_cond.notify_all();
} else {
// not to wait if last worker reachs last statement before notify
// all or even further
std::unique_lock<std::mutex> next_level_lock(next_level_mutex);
next_level_cond.wait(next_level_lock, [&level, cur_level]() {

I think the problem is that the thread will not get notified by notify_all(), if it is not already in wait().
To Reproduce
Steps to reproduce the behavior:

  1. Replace

    CXXGraph/CMakeLists.txt

    Lines 26 to 35 in 376d91b

    if(SANITIZE)
    add_compile_options(
    -fsanitize=address
    -fsanitize=leak
    )
    add_link_options(
    -fsanitize=address
    -fsanitize=leak
    )
    endif(SANITIZE)

    with
	if(SANITIZE)
		add_compile_options(
			-fsanitize=thread
		)
		add_link_options(
			-fsanitize=thread
		)
	endif(SANITIZE)
  1. Run the build with -DSANITIZE=ON and run the tests (cf. you might need this).

Expected behavior
test_bfs takes reasonable amour of time.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions