Fast software pipelining for stream processing
Do the work in batches.  Have a separate buffer for each stream that stores the unprocessed items.  When you invoke $f$ for stream $S_i$, invoke 100 times on the 100 oldest items in the buffer for $S_{i-1}$, then remove those items from the buffer.  This basically increases the granularity of operations, and should reduce the overhead from synchronization by about 100x.  You can of course tune the number 100 to adjust throughput vs latency.