A Disk Striping Model:
A Disk Striping Model Assume compressed videos stored on m disks with stripe units of size d – each round gets 1 stripe unit
Period P for a video: # rounds to get successive streams
q = max. number of videos serviced in a round / disk
If total memory=R
Optimal d given by:
If R=2GB, m=50, display rate=1.5Mbps
d=0.9Mb, q=20, round=600ms
Period for a video of 100 min = 1 min. round duration buffer/video is 2d tseek= avg. time to reach a track
Vertical Striping:
Vertical Striping A situation
4 supervideos V1 .. V4
V1, V2: 3 stripe units per disk
V3, V4: 2 stripe units per disk
2 stripe units/round/disk
Round 1..3: get data for V1 and V2 from disk 0
Round 4, 5: get data for V3 and V4 from disk 0
get data for V1 and V2 from disk 1
Round 6: get data for V1 and V2 from disk 1
get data for V3 and V4 from disk 1
4 streams from a disk!!!
A solution
Partition videos into sets that reduce the difference between the lengths of videos of any two sets as much as possible
Scheduling for Vertical Striping:
Scheduling for Vertical Striping The Problem:
Get w stripe units for every super video Vi at intervals of Pi from disk 0, when a maximum of q streams can be retrieved from a disk in one round
Schedule non-preemptible tasks T1…Tr with periods P1…Pr and computation time w on q processors
How complex is the problem?
What can be done?
Result 1: if n.w gcd(P1…Pn) then the tasks are schedulable on a single processor, where n=r/q
If tasks T1..T4 have periods 4,4,6,6 and w=1, they can be scheduled at 0,2,1,3 respectively – a stronger result is needed
Example:
Example Tasks T1..T4 have periods 4,4,6,6 and w=1
g=2
n=4, so n andgt; g
Make tasks T1…T4 with periods 2, 2, 3, 3
Initial subsets S1=T1, T2 S2=T3, T4
Next iteration:
From S1: {(T1, 0) (T2, 1)} From S2: {(T3, 0) (T4, 1)}
Step 5: {(T1, 0) (T2, 2) (T3, 1) (T4, 3)}