Parallel Proseslər

Paralel proseslərin təhlili zamanı sinxronizasiya tələb edən hallarda, hansı tapşırıqların paralel icra edilə biləcəyini bilmək çox vaxt vacibdir. m növündən olan n tapşırığını nəzərdən keçirin. İki növ tapşırığı müstəqil adlandıraq, əgər onlar paralel icra edilə bilərlərsə. Bir növ tapşırıqlar isə heç vaxt müstəqil deyil və ardıcıl icra olunmalıdır.

k prosessorda icra ediləcək tapşırıqların ardıcıllığını nəzərdən keçirin. Hər saniyə k qədər növbəti tapşırıq icra edilə bilər, əgər onların hər bir cütü paralel icra edilə bilərsə. Qeyd edək ki, tapşırıqları keçmək və ya gələcək icra üçün saxlamaq icazəli deyil. Məsələn, əgər A və B növündən olan tapşırıqlar müstəqildirsə, AABABBAB ardıcıllığı iki prosessorda beş saniyədə icra edilə bilər, bunu etmək üçün bir yol (A−), (AB), (AB), (B−), (AB).

Verilən tapşırıqlar ardıcıllığını iki prosessorda icra etməyin digər yolu (A−), (AB), (AB), (BA), (B−). İki yolun əsasən fərqli olduğunu deyirik, əgər elə bir saniyə varsa ki, icra edilən tapşırıqların dəstləri fərqlidir. Görmək olar ki, AABABBAB tapşırıqlar ardıcıllığını iki prosessorda minimal vaxtda icra etməyin iki əsasən fərqli yolu var. Həmçinin hər bir tapşırığın hansı prosessorda icra edildiyini nəzərə alsaq, verilən tapşırıqlar dəstini icra etməyin 64 yolu var (hər iki əsasən fərqli yolda hər saniyə tapşırıqları prosessorlar arasında dəyişə bilərik). Beləliklə, tapşırıqlar dəstini icra etməyin 64 dəqiq yolu olduğunu deyirik.

Müstəqil olan tapşırıq növləri, prosessorların sayı və tapşırıqların ardıcıllığı verildikdə, tapşırıqları icra etmək üçün tələb olunan minimal vaxtı, bunu etməyin əsasən fərqli yollarının sayını və icranın fərqli dəqiq yollarının sayını tapmalısınız.