One of the major challenges in Dynamic Spectrum Access (DSA) systems is to guarantee a required level of QoS to Secondary Users of the spectrum. In this paper, we propose efficient algorithms for deriving optimal policies for the sensing / transmitting trade-off in hardware constrained DSA. Unlike previous approaches which seek to maximize mean data rate for the secondary users, the proposed algorithms derive policies which minimize the probability of excessive queuing delays. Large Deviations (LD) asymptotics are used to approximate the probability of interest and policies maximizing the associated LD exponent proposed. Although Dynamic Programming is not able to identify the optimal policy in this case, much more efficient algorithms than exhaustive search are proposed. They are built on specific properties of the optimal policy which are described and proven in this paper.