 |
Az S. 147. feladat (2020. november) |
S. 147. Ha egy számítógépes rendszerben egyszerre több program fut, akkor zárakat használnak a megosztott erőforrások biztonságos kezelése érdekében. Mielőtt egy program pl. közös memóriaterületet használna, megvizsgálja, hogy a hozzá tartozó zár nyitva van-e. Ha igen, akkor zárja azt, használja az erőforrást, majd ha már nincs rá szüksége, akkor a zárat kinyitja. Amíg a program használja az erőforrást és az ahhoz tartozó zár be van zárva, addig más program nem tudja az erőforrást használni, így várakoznia kell, amíg az erőforrás szabaddá nem válik és a zár újra nyitva nem lesz.
Van két programunk, melyek önmagukban determinisztikusak, azaz véges időn belül lefutnak és pontosan tudjuk, hogy az egyes utasításaikat milyen sorrendben hajtják végre. Mindkét program esetében ismerjük, hogy mely erőforrásokat és milyen sorrendben próbálják lefoglalni és elengedni, tehát azok zárjait milyen sorrendben nyitják és zárják.
Döntsük el, hogy kialakulhat-e holtpont, ha csak ez a két program fut a rendszerben. Holtpontnak nevezzük azt az állapotot, amikor a rendszerben futó összes program olyan erőforrásra vár, amelyet egy másik program már használ, ezért egyik program sem tud tovább futni. Készítsünk programot, amely \(\displaystyle T\) programpár esetében meghatározza, hogy kialakulhat-e holtpont.
Bemenet: az első sor tartalmazza a programpárok \(\displaystyle T\) számát. Minden programpárt három sor ír le. Az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle M\) számokat, melyek az első és a második program zár műveleteinek számát adja meg. A következő két sor az első és a második program erőforrás műveleteit írja le a programfutás szerinti sorrendben. Egy \(\displaystyle x>0\) szám azt jelenti, hogy a program a következő lépésében az \(\displaystyle x\)-edik erőforrást használná, míg egy \(\displaystyle x<0\) szám azt, hogy az \(\displaystyle x\)-edik erőforrást a program már nem használja tovább. Ha a program futása végére ér, akkor elengedi az összes lefoglalt erőforrást, tehát minden általa lezárt zár kinyílik. Ez nem feltétlenül jelenik meg a bemenetben.
Kimenet: \(\displaystyle T\) sort kell kiírni, amelyek mindegyike az ,,Igen'' vagy a ,,Nem'' szöveg aszerint, hogy kerülhet-e holtpontba a rendszer.
Példa:
| Bemenet (a / jel sortörést helyettesít) | Kimenet |
|---|---|
| 2 6 3 / 1 -1 2 3 -3 -2 / 1 3 2 4 5 / 1 2 -2 3 / 2 3 -2 -3 1 | Igen Nem |
Korlátok: \(\displaystyle 1\le T\le 10\), \(\displaystyle 1\le N, M\le 100\), \(\displaystyle 1\le x\le 10^6\). Időkorlát: 0,2 mp.
Beküldendő egy s147.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.
Javasolta: Erben Péter és Darabos Dániel
(10 pont)
A beküldési határidő 2020. december 15-én LEJÁRT.
A feladat megoldható dinamikus programozás segítségével. Minden \(\displaystyle (i,j)\) párra ki kell számolnunk, el lehet-e jutni abba az állapotba, amikor az első program az \(\displaystyle i.\), a második pedig a \(\displaystyle j.\) zárműveletet hajtotta végre utoljára. Az állapot akkor holtpont, ha az \(\displaystyle (i,j)\) állapotba el lehet jutni, de az \(\displaystyle (i,j+1)\) és \(\displaystyle (i+1,j)\) állapotok egyikébe sem. Mivel \(\displaystyle x<10^6\), a lefoglalt zárakat számon tarthatjuk egy megfelelően nagy logikai tömbben.
Ha DP táblát sorfolytonosan töltjük ki, ezt a logikai tömböt minden mezőnél egy helyen kell frissíteni és egy zár lefoglalásához is egy logikai érték frissítése szükséges. Ez tehát nem befolyásolja a futási idő nagyságrendjét.
Komplexitás: \(\displaystyle O(N*M)\)
Statisztika:
6 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Varga 256 Péter. 9 pontot kapott: Papp Marcell Miklós. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 2 versenyző.
A KöMaL 2020. novemberi informatika feladatai