یک پردازنده وجود دارد که کارهایی با مشخصات زیر برای پردازش به آن وارد می‌شوند. کارها به صورت تناوبی به پردازنده وارد می‌شوند؛ به این معنی که کار شماره‌ی $i$، مرتبا به صورت تناوبی با دوره‌ی تناوب $t_i$ وارد می‌شود یعنی در زمان‌های $2 \times t_i،t_i،0$ و … در ضمن هر کار باید در دوره‌ی تناوب مربوط به خود به پایان برسد به این معنی که اگر کار $i$ ام در زمان $k\times t_i$ به پردازنده وارد شده است باید حداکثر در زمان $(k+1)\times t_i$ پردازش آن، تمام شده باشد.

زمان پردازش کار $i$ ام، $s_i$ است به این معنی که هر نمونه از کار $i$ ام برای پردازش به اندازه‌ی $s_i$ از پردازنده زمان می‌برد که لزوما تمام این مدت نباید به صورت پیوسته باشد بلکه می‌توان پردازش کاری را هر چند بار که لازم باشد نیمه‌کاره رها کرد و سپس دوباره آن را ادامه داد.

در سیستم $n$ نوع کار وجود دارد که هرکدام با زوج $(s_i,t_i)$ ( $s_i$ ها و $t_i$ ها حقیقی هستند) مشخص می‌شوند. در زمان صفر از هر نوع کار یک نمونه به پردازنده وارد می‌شود و اولین دوره‌ی تناوب همه‌ی کارها شروع می‌شود. بعد از این در ابتدای هر دوره‌ی جدید تناوب هر کار باید پردازش نمونه‌ی قبلی همین کار که در ابتدای دوره‌ی تناوب قبلی وارد شده بود، پایان یافته باشد و در همین لحظه نمونه‌ی جدیدی از این کار به سیستم وارد می‌شود. این فرایند تا بینهایت ادامه پیدا می‌کند.

ثابت کنید شرط لازم و کافی برای این که بتوان این $n$ کار را زمانبندی کرد به نحوی که همه‌ی کارها به طور کامل در دروه‌ی تناوب خود انجام شوند این است که:

$$\sum_{i=1}^n \frac{s_i}{t_i} \leq 1$$

• سوال قبل