Process variation is the dominating factor for performance degradation in modern IC chips. The conventional guard-band design methodology leads to significant performance penalty. This paper utilizes an emerging non-volatile resistive device, memristor, with timing violation detectors to dynamically achieve local recovery from timing violation during the runtime, eliminating the necessity of testing phase. It develops a systematic self-tuning mechanism that globally adjusts the clock skew scheduling to compensate the timing violation, and determines the tunability of the memristor-based self-tunable circuits. It also proposes an algorithmic memristor placement across the clock tree to balance the tradeoff between hardware cost and system tunability. Experimental results show that our approach can improve the yield from 90% to 98% with only 4% overhead in average.