Deadlock akan terjadi, jika dan hanya jika grafik tunggu memiliki siklus di dalamnya.Untuk mendeteksi deadlock, sistem harus memiliki grafik tunggu dan menjalankan algoritma deteksi deadlock secara periodik. Hal yang harus diperhatikan adalah seberapa sering algoritma deteksi harus dipanggil. Hal ini tergantung dari dua faktor:

Bila deadlock terjadi maka algoritma deteksi harus sering dipanggil. Resource yang dialokasikan ke proses-proses yang mengalami deadlock tidak akan digunakan sampai kondisi deadlock diatasi. Bila deadlock tidak segera diatasi maka jumlah proses yang terlibat dalam deadlock akan semakin bertambah.

Salah satu ciri terjadinya deadlock adalah ketika beberapa proses mengajukan permohonan untuk resource, tetapi permohonan ini tidak dapat dipenuhi dengan segera. Sistem dapat saja memanggil algoritma deteksi setiap kali permohonan untuk resource tidak dapat diperoleh dengan segera. Namun,semakin sering algoritma deteksi dipanggil, maka waktu overhead yang dibutuhkan untuk komputasi menjadi semakin besar.

Jika semua sumber daya hanya memiliki satu instans, deadlock dapat dideteksi dengan mengubah graf alokasi sumber daya menjadi graf tunggu. Ada pun caranya sebagai berikut:

Gambar 24.10. Contoh Graf Alokasi Sumber Daya yang akan diubah menjadi graf tunggu

Gambar 24.11. Contoh Graf Tunggu

Untuk mendeteksi deadlock, sistem perlu membuat graf tunggu dan secara berkala memeriksa apakah ada perputaran atau tidak. Untuk mendeteksi adanya perputaran diperlukan operasi sebanyak n ², dimana n adalah jumlah simpul dalam graf alokasi sumber daya.