GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 14

Question

Consider $4$ transactions $T_{1},T_{2},T_{3}$ and $T_{4}$ having $1,4,2$ and $3$ operations respectively. If $a$ is the total number of serial schedules and $b$ is the total number of concurrent schedules then the total number of non-serial schedules, $c = b – a = $ _______

Answer 1

If there are $n$ transactions then total no of serial schedule $= n!$

Here, $a = 4! = 24.$

If there are $n$ transactions each having $m_{1},m_{2},\dots,m_{n}$ operations. The number of concurrent schedules $ = \dfrac{(m_{1} + m_{2} + m_{3} + \dots + m_{n})!}{m_{1}!m_{2}!m_{3}!\dots m_{n}!}$

Here, $b = \dfrac{(1 + 2 + 3 + 4)!}{2!3!4!} = \dfrac{10!}{2 \cdot 6 \cdot 24} = 12600.$

Hence, $c = 12600 - 24 = 12576.$

Comments

Concurrency means there should be interleaving of schedules right? So why aren’t we taking b as 12600-24. How can serial schedules be considered concurrent, they are executing one after another like in isolation, where is the concurrency, please help

---

Do you see that definition anywhere? Anyway, it is defined in question to avoid any ambiguity.