Due to increasing shares of renewable energy sources, more frequency reserves are required to maintain power system stability. In this paper, we present a decentralized control scheme that allows a large aggregation of refrigerators to provide Primary Frequency Control (PFC) reserves to the grid based on local frequency measurements and without communication. The control is based on stochastic switching of refrigerators depending on the frequency deviation. We develop methods to account for typical lockout constraints of compressors and increased power consumption during the startup phase. In addition, we propose a procedure to dynamically reset the thermostat temperature limits in order to provide reliable PFC reserves, as well as a corrective temperature feedback loop to build robustness to biased frequency deviations. Furthermore, we introduce an additional randomization layer in the controller to account for thermostat resolution limitations, and finally, we modify the control design to account for refrigerator door openings. Extensive simulations with actual frequency signal data and with different aggregation sizes, load characteristics, and control parameters, demonstrate that the proposed controller outperforms a relevant state-of-the-art controller.