With the improvement of traffic electrification, the coupling between power and transportation systems becomes more and more intensified. In this paper, electrified railway is firstly introduced into power system to support frequency regulation under high penetration of renewable energy sources. A novel frequency regulation framework consisting of day-ahead capacity estimation, frequency control parameters dispatch, and real-time response is constructed for electrified railway to provide primary frequency control support. Motion equations of electric trains under regulation are developed in detail. To fulfill the frequency regulation requirement and ensure punctual arrival, a multi-train joint response strategy is proposed to coordinate different electric trains for primary frequency control. The frequency regulation capacity estimation problem and frequency control power dispatch problem are established based on the multi-train joint response strategy. A novel sequential cutting plane algorithm is developed to linearly relax the nonlinear capacity estimation problem and power dispatch problem with ordinary differential equation constraints and iteratively tighten the relaxation area to improve solution optimality with desirable efficiency. Comprehensive numerical studies verify the effectiveness of the proposed primary frequency control framework, indicating the high potential of electrified railway to support frequency regulation of modern power systems.