При разблокировании уже разблокированного взаимного исключения действительно ли поведение не определено?

Так делать не обязательно. Попробуйте следующее:

    // This chunk of code makes dual locking semi-autonomous.
int c_lckd = 0, q_lckd = 0;
if (pthread_mutex_trylock(&crunch_mutex) == 0) c_lckd = 1;
if (pthread_mutex_trylock(&queue_mutex) == 0) q_lckd = 1;

if (c_lckd && q_lckd) {
  printf("cr = %d, max = %d, cnt = %d\n",
    crunching, max_crunching, queue_count(conn_queue));
  if (crunching < max_crunching && queue_count(conn_queue)) {
    pthread_t tid =
      pthread_create(
        &tid,
        NULL,
        crunch_conn,
        (void *)queue_dequeue(conn_queue)
      );
    crunching++;
  }

}

if (q_lckd) { QUEUE_UNLOCK; q_lckd = 0; }
if (c_lckd) { CRUNCH_UNLOCK; c_lckd = 0; }

Это немного проще, и вы не рискуете попытаться разблокировать разблокированный мьютекс.

В общем, для подобных вопросов документация является лучшим источником информации. Различные мьютексы могут вести себя по-разному, или на одном мьютексе могут быть параметры, которые заставляют его вести себя по-разному (например, в случае рекурсивного получения мьютекса в одном потоке).

Как заметил Глен, вы получите неопределенное поведение, если попытаетесь разблокировать разблокированный мьютекс - не пытайтесь. Отладка потоков достаточно сложна и без вызова неопределенного поведения.

Что еще более важно, стиль кодирования немного необычен - так как вы не собираетесь ничего делать, пока не получите обе блокировки, кодируйте соответственно:

if (pthread_mutex_trylock(&crunch_mutex) == 0)
{
    if (pthread_mutex_trylock(&queue_mutex) == 0)
    {
        printf("cr = %d, max = %d, cnt = %d\n",
               crunching, max_crunching, queue_count(conn_queue));
        if (crunching < max_crunching && queue_count(conn_queue))
        {
            pthread_t tid;
            int rc = pthread_create(&tid, NULL,
                               crunch_conn, (void *)queue_dequeue(conn_queue));
            if (rc != 0)
            {
                // Error recovery
                // Did you need what was returned by queue_dequeue()
                // to requeue it, perhaps?
            }
            else
            {
                crunching++;
                // Do something with tid here?
            }
        }
        QUEUE_UNLOCK;
    }
    CRUNCH_UNLOCK;
}

Это позволяет избежать ' я сделал это? переменные; также сразу становится ясно, что, пока макросы разблокировки делают то, что ожидается (и нет случайных исключений или setjmps), заблокированные мьютексы разблокируются. Это также позволяет избежать траты энергии на блокировку мьютекса очереди, когда мьютекс crunch недоступен - но это '