Managed hosting and enterprise wide resource consolidation trends are increasingly leading to sharing of storage resources across multiple classes, corresponding to different applications/customers, each with a different Quality of Service (QoS) requirement. To enable a storage system to meet diverse QoS requirements, we present two algorithms for dynamically allocating cache space among multiple classes of workloads. Our algorithms dynamically adapt the cache space allocated to each class depending upon the observed response time, the temporal locality of reference, and the arrival pattern for each class. Using trace driven simulations collected from large storage system installations, we experimentally demonstrate the following properties of CacheCOW. First, the CacheCOW algorithms enable a storage cache to meet the feasible QoS requirements that class-unaware cache management algorithms such as LRU do not. Second, if an offline, static partitioning of the cache can meet the QoS requirements, our algorithms also meet them and discover the allocations online. Third, the CacheCOW allocations achieve the same feasibility region as that of the offline static algorithms. Finally, the algorithms not only meet the QoS requirements, but also increase the throughput by achieving a higher hit rate whenever feasible.