Asinxron İstisnalar#3560
Sizin vəzifəniz ACM (Asinxron Hesablama Maşını) adlı bir maşında əməliyyatları simulyasiya edərək, hər bir proqramın tamamlanması üçün nə qədər vaxt tələb olunduğunu müəyyənləşdirməkdir. Bu, yarış şəraiti və ya gözlənilməz iplik davranışlarını aşkar etməyə kömək edir.
ACM-də çoxlu emal vahidi mövcuddur və eyni anda bir çox iplik işlədə bilər. O, bütün iplikləri saxlayan, hər bir emal vahidinə bir iplik təyin edən və bütün semaforları idarə edən qlobal planlayıcı ilə işləyir. Hər bir ipliyin özünəməxsus iplik id-si var və hər bir iplik üç vəziyyətdən birindədir: İŞLƏYİR, HAZIR və GÖZLƏYİR. Qlobal planlayıcı HAZIR vəziyyətdə olan bütün iplikləri ehtiva edən bir iplik növbəsinə malikdir.
Proqram bir və ya daha çox kod blokundan ibarətdir. Hər bir kod bloku faktiki hesablama və iplik yaradılması daxil olmaqla ACM əməliyyatlarının siyahısına malikdir. Hər bir iplik yalnız verilmiş kod bloklarından birində əməliyyatları icra edir və digər ipliklərdən killThread siqnalı almadığı təqdirdə əməliyyatları blokun yuxarısından aşağıya doğru icra edir.
ACM simulyasiya proqramı 9 əməliyyatı simulyasiya edir. Burada onların hamısını təsvir edirəm. Zəhmət olmasa, [] ilə əhatə olunmuş sözün bəzi faktiki adı və ya dəyəri olmalıdır.
hesabla [saat]
Hesablama üçün [saat] saat sərf edin. Bu əməliyyat digər ipliklər və ya planlayıcı tərəfindən T saat sərf edildikdən sonra kəsildikdə və daha sonra bərpa edildikdə, [saat] - T saat sərf edir.
[iplik-dəyişən] <- forkR [kod bloku]
[kod bloku] üzərində işləyən yerli bir iplik yaradın və onun id-sini [iplik-dəyişən] iplik dəyişənində saxlayın. O, digər emal vahidində yaradılan hər hansı ipliklə eyni vaxtda işləyə bilər. Əgər [iplik-dəyişən] iplikdə əvvəllər istifadə olunubsa, onun əvvəlki dəyəri üst-üstə düşür və itirilir. (Bu o deməkdir ki, biz ipliyə istinad edə bilməyəcəyik, baxmayaraq ki, o, əbədi işləyə bilər.)
[iplik-dəyişən] <- forkI [kod bloku]
[kod bloku] üzərində işləyən virtual bir iplik yaradın və onun id-sini [iplik-dəyişən] iplik dəyişənində saxlayın. Virtual iplik bəzi OS resurslarını ana ipliklə paylaşır, buna görə də boş emal vahidləri olsa belə, onlar eyni vaxtda işləyə bilməzlər. Bu məhdudiyyət forkI-nin ana-uşaq əlaqəsi ilə birbaşa və ya dolayı yolla əlaqəli olan hər iki ipliyə tətbiq edilir. Əgər [iplik-dəyişən] iplikdə əvvəllər istifadə olunubsa, onun əvvəlki dəyəri üst-üstə düşür və itirilir.
ver
Cari ipliyi işləmə vəziyyətindən hazır vəziyyətə gətirin. İplik iplik növbəsinin sonuna keçir.
killThread [iplik-dəyişən]
[iplik-dəyişən] ipliyinə öldürmə siqnalı göndərin. [iplik-dəyişən] bu əməliyyatdan əvvəl eyni kod blokunda forkR və ya forkI əməliyyatlarında istifadə olunması təmin edilir. İplik öldürmə siqnalı aldıqda, dərhal kilidlə resurs tələblərini ləğv edir, blok vəziyyətindədirsə hazır vəziyyətə keçir və işləmə vəziyyətində olduqda əməliyyatını bitirir. Bu əməliyyat semafor dəyərlərini dəyişdirmir. Hədəf iplik artıq bitibsə, bu əməliyyat heç nə etmir.
kilid [semafor adı] [miqdar]
[semafor adı] üçün [miqdar] tələb edin. Əgər [semafor adı] dəyəri [miqdar]dan böyük və ya bərabərdirsə, sadəcə [miqdar]ı semafor dəyişənindən çıxarır. Əks halda, əməliyyat cari ipliyi dəyişən [miqdar]dan böyük və ya bərabər olana qədər bloklayır. Dəyişən [miqdar]dan böyük və ya bərabər olduqda, iplik HAZIR vəziyyətə keçir və dəyişəndən [miqdar] çıxıldıqdan sonra iplik növbəsinə keçir. Eyni semafor üçün bir neçə iplik tələb edirsə, semaforu ilk kilidləyən iplik həmişə birinci HAZIR olur. Beləliklə, digər ipliklər semafor dəyişəni tələblərinə cavab versə belə HAZIR olmayacaq. Bir neçə iplik HAZIR olarsa, semaforu daha əvvəl kilidləyən iplik növbəyə birinci keçir.
aç [semafor adı] [miqdar]
[semafor adı]na [miqdar] əlavə edin. Semaforların dəyərləri ilkin dəyərlərdən böyük ola bilər. İplik bu əməliyyatla heç vaxt bloklanmır.
döngü [döngü sayı]
Kod parçasını döngü və müvafiq növbəti əmrdən [döngü sayı] dəfə icra edin.
növbəti
Bu, eyni kod blokunda döngü əmrinə uyğundur. Döngü və növbəti arasında olan kod parçası icra edilməlidir.
son
Əməliyyatı bitirin. Bu əmr yalnız kod blokunun sonunda görünür və hər bir kod bloku sonunda bu əməliyyata malikdir.
Hər bir parametr ya ad, ya da rəqəm olmalıdır. Ad əlifba simvoludur (böyük-kiçik hərf həssasdır) və uzunluğu ən çox 200-dür. Burada bəzi izahlar var.
[iplik-dəyişən]
Bu bir addır. O, yalnız eyni iplikdəki id-yə istinad edir. Hər bir iplik öz dəyərinə malikdir, hətta eyni ada malik olsa belə.
[saat]
Bu, ən çox 1000 olan qeyri-mənfi tam ədəddir.
[semafor-adı]
Bu bir addır.
[miqdar]
Bu, ən çox 1000 olan qeyri-mənfi tam ədəddir.
[döngü sayı]
Bu, ən çox 1000 olan qeyri-mənfi tam ədəddir.
Əlavə olaraq, aşağıdakı məhdudiyyətləri qəbul edə bilərsiniz.
Simulyasiya boyunca bütün ipliklərin qiymətləndirdiyi sətirlərin ümumi sayı heç vaxt 100000-i keçmir.
Giriş faylının ölçüsü heç vaxt 100KB-i keçmir.
İpliklər CPU-lara təyin edilir
simulyasiya başladıqda. (İplik CPU 1-ə təyin edilir. Onun kod bloku girişin ilk kod blokudur.)
hazır vəziyyətdə olan və CPU-ya təyin edilə bilən bir neçə iplik olduqda. (İpliklər iplik növbəsi qaydasında təyin edilir. İplik təyin edilə bilən bir neçə CPU varsa, ən kiçik CPU seçilir.)
zaman addımı zaman diliminin çoxluğudur. (Əgər CPU işləmə vəziyyətində olan bir ipliyə malikdirsə, iplik CPU id-nin artan qaydasında hazır vəziyyətə keçir. Bundan sonra, ipliklər CPU id-nin artan qaydasında hər bir CPU-ya təyin edilir.)
Hər addımda simulyator dövrəvi preemsiya edir (zaman addımı zaman diliminin çoxluğudur), hər bir işləyən ipliyin əməliyyatlarını icra edir və zaman addımını artırır. Hesablama əməliyyatı icra edildikdə, iplik hesablama vaxtı alır. Hesablama vaxtı 0-dan böyük olan iplik heç bir əməliyyat edə bilmir. Hər addımdan sonra simulyator hər bir işləyən ipliyin müsbət hesablama vaxtını azaldır.
Eyni zaman addımında icra edilən əməliyyatlar CPU id-nin artan qaydasında icra edilir. Eyni zaman addımında, bir əməliyyatın CPU id-si artıq icra edilmiş əməliyyatların CPU id-lərindən böyük və ya bərabərdir.
Zaman addımı 0-dan başlayır.
Giriş bir neçə testdən ibarətdir.
Hər bir test iki tam ədəd olan bir sətirlə başlayır, boşluqla ayrılır. Onlar simulyasiyanın zaman addımlarının sayını və ACM-in bacardığı maksimum iplik sayını bildirir. Növbəti sətir mövcud CPU-ların sayını göstərən bir tam ədəd ehtiva edir. Sonrakı sətir planlayıcının zaman dilimini bildirən bir tam ədəd ehtiva edir.
Semaforların təsviri gəlir. O, hər bir semafor haqqında məlumatla, hər sətirdə bir olmaqla, bir semaforun adını və onun ilkin dəyərini göstərən bir əlifba simvolu (böyük-kiçik hərf həssasdır) və bir tam ədəd ilə başlayır.
Nəhayət, kod blokları verilir. Əvvəlcə kod bloklarının sayı gəlir, sonra hər bir kod bloku təsvir edilir. Hər bir kod blokunun təsvirinin ilk sətri blokun adı (böyük-kiçik hərf həssas əlifba simvolu) və iki nöqtə (:) ilə başlayır. Sonrakı sətirlər kod blokunun məzmununu təsvir edir. Kod bloku yuxarıda təsvir edilən əməliyyatların bir massividir və bir əməliyyat bir sətirdə yazılır. Hər bir kod bloku həmişə 'son' əməliyyatı ilə bitir.
Giriş boşluq simvolu ilə ayrılmış iki sıfırla bitir.
Məhdudiyyətlər
1 iplik növbəsi var.
n
-ci yaradılan ipliyin id-si n-dir.
CPU id-ləri 1-dən CPU-ların sayına qədərdir.
Zaman addımlarının sayı ən çox 1000-dir.
Maksimum iplik sayı ən çox 1000-dir.
CPU-ların sayı ən çox 100-dür.
Zaman dilimi ən çox 1000-dir.
Semaforların sayı ən çox 1000-dir.
Kod bloklarının sayı ən çox 1000-dir.
Hər bir test üçün, ilk sətirdə onun test nömrəsini çap edin.
Əgər yaşayan ipliklərin sayı ACM-in tutumunu aşarsa, tutumu aşmadan əvvəl bitən bütün ipliklərin məlumatlarını yazın və sonra "<>". Əks halda, simulyasiyanın sonunda bitməmiş bir və ya daha çox iplik varsa, bitən bütün ipliklərin məlumatlarını yazın və sonra "<>". Əks halda (yəni bütün ipliklər vaxtında bitdikdə), sadəcə bütün ipliklərin məlumatlarını yazın. Bütün sitatlar aydınlıq üçündür.
İpliklərin məlumatları iplik ID-sinin artan qaydasında, hər biri bir sətirdə yazılmalıdır. Tək bir ipliyin məlumatı iki tam ədədlə, iplik ID-si və bitmə vaxtı ilə, bir boşluq simvolu ilə ayrılmış şəkildə göstərilir.
Nümunə 1