Goal: Real-time abnormality detection in gait analysis is an open challenge. The existing state-of-the-art is limited by the fact that it does not take into account ’in-step’ anomaly detection. Timely detection of gait abnormalities during the mid-swing phase of the step (i.e., within 50ms detection time) is required to make informed gait correction. To meet this requirement and overcome state of the art limitations, we present real-time anomaly detection algorithms, a new dataset, and a framework to estimate performance of anomaly detection algorithms. Methods: We propose real-time in-step anomaly detection algorithms namely, i) real-time tslearn support vector machines anomaly detection (RTtsSVM-AD), ii) real-time one class support vector machines anomaly detection (RTOCSVMAD), and iii) signal shape tracking anomaly detection (SSTAD). For comparative assessment, twenty-two healthy volunteers realistically simulated eight different characteristic deviations in human gait of certain lower extremity disabilities. Motion patterns were recorded using an inertial motion unit (IMU) placed on the forefoot. F1 score, recall, precision, real-time factor (RTF), as well as ”earliness” measures are estimated and analyzed. The ”earliness” is a new metric which defines the time between the beginning of a step and the moment in time when the step is classified as abnormal. Results: The achieved results demonstrate that the proposed algorithms can detect gait abnormalities in real-time during the mid-swing phase of an ongoing step. The average accuracy and F1 score achieved by the three algorithms are: 91% and 81% for SST-AD; 74% and 54.9% for RTOCSVM-AD; and 64.5% and 49.2% for RTtsSVMAD, respectively. The best average earliness is achieved by the SST-AD algorithm at 0.4 second from the initial-swing phase start. Conclusion: Based on the results, SST-AD is the best suited algorithm for real-time gait anomaly detection and should be considered to be used in future embedded assistive devices.