text:
# American Institute of Mathematical Sciences

• Previous Article
On the detection of several obstacles in 2D Stokes flow: Topological sensitivity and combination with shape derivatives
• IPI Home
• This Issue
• Next Article
Restoration of manifold-valued images by half-quadratic minimization
May  2016, 10(2): 305-325. doi: 10.3934/ipi.2016002

## Forward and backward filtering based on backward stochastic differential equations

 1 Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Received  March 2013 Revised  January 2015 Published  May 2016

In this paper we explore the problem of reconstruction of blurred and noisy images. The idea presented here provides a new methodology based on advanced tools of stochastic analysis which can be successfully used to solve the inverse problem. In order to solve this problem we use backward stochastic differential equations. The reconstructed image is characterized by smoothing noisy pixels and at the same time enhancing and sharpening edges. Our experiments show that the new approach gives very good results and compares favourably with deterministic partial differential equation methods.
Citation: Dariusz Borkowski. Forward and backward filtering based on backward stochastic differential equations. Inverse Problems and Imaging, 2016, 10 (2) : 305-325. doi: 10.3934/ipi.2016002
##### References:
 [1] M. Aharon, M. Elad and A. Bruckstein, K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., 54 (2006), 4311-4322. doi: 10.1109/TSP.2006.881199. [2] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing, Applied Mathematical Sciences, 147, Springer, New York, 2006. doi: 10.1007/978-0-387-44588-5. [3] D. Borkowski, Chromaticity denoising using solution to the Skorokhod problem, in Image Processing Based on Partial Differential Equations, Mathematics and Visualization, 2007, 149-161. doi: 10.1007/978-3-540-33267-1_9. [4] D. Borkowski, Smoothing, enhancing filters in terms of backward stochastic differential equations, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 6374 (2010), 233-240. doi: 10.1007/978-3-642-15910-7_26. [5] D. Borkowski, Euler's approximations to image reconstruction, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 7594 (2012), 30-37. doi: 10.1007/978-3-642-33564-8_4. [6] D. Borkowski and K. Jańczak-Borkowska, Application of backward stochastic differential equations to reconstruction of vector-valued images, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 7594 (2012), 38-47. doi: 10.1007/978-3-642-33564-8_5. [7] A. Buades, B. Coll and J. M. Morel, A non local algorithm for image denoising, in Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2 (2005), 60-65. doi: 10.1109/CVPR.2005.38. [8] A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Model. Simul., 4 (2005), 490-530. doi: 10.1137/040616024. [9] A. Buades, B. Coll and J. M. Morel, Non-local means denoising, Image Processing On Line, 1 (2011). doi: 10.5201/ipol.2011.bcm_nlm. [10] F. Catte, P. L. Lions, J. M. Morel and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J. Numer. Anal., 29 (1992), 182-193. doi: 10.1137/0729012. [11] T. F. Chan and J. J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, SIAM, 2005. doi: 10.1137/1.9780898717877. [12] K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans. Image Process., 16 (2007), 2080-2095. doi: 10.1109/TIP.2007.901238. [13] A. Danielyan, V. Katkovnik and K. Egiazarian, Bm3d frames and variational image deblurring, IEEE Trans. Image Process., 21 (2012), 1715-1728. doi: 10.1109/TIP.2011.2176954. [14] D. L. Donoho and I. M. Johnstone, Ideal spatial adaptation via wavelet shrinkage, Biometrika, 81 (1994), 425-455. doi: 10.1093/biomet/81.3.425. [15] D. Duffie and L. Epstein, Asset pricing with stochastic differential utility, Review of Financial Studies, 5 (1992), 411-436. doi: 10.1093/rfs/5.3.411. [16] D. Duffie and L. Epstein, Stochastic differential utility, Econometrica, 60 (1992), 353-394. doi: 10.2307/2951600. [17] A. Efros and T. Leung, Texture synthesis by non parametric sampling, in Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, 2 (1999), 1033-1038. doi: 10.1109/ICCV.1999.790383. [18] D. Fang, Z. Nanning and X. Jianru, Image smoothing and sharpening based on nonlinear diffusion equation, Signal Process., 88 (2008), 2850-2855. doi: 10.1016/j.sigpro.2008.05.008. [19] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6 (1984), 721-741. doi: 10.1109/TPAMI.1984.4767596. [20] P. Getreuer, Rudin-Osher-Fatemi total variation denoising using split Bregman, Image Processing On Line, 2 (2012), 74-95. doi: 10.5201/ipol.2012.g-tvd. [21] G. Gilboa, N. Sochen and Y. Y. Zeevi, Forward-and-backward diffusion processes for adaptive image enhancement and denoising, IEEE Trans. Image Process., 11 (2002), 689-703. doi: 10.1109/TIP.2002.800883. [22] T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343. doi: 10.1137/080725891. [23] S. Hamadene and J. P. Lepeltie, Zero-sum stochastic differential games and backward equations, Syst. Control Lett., 24 (1995), 259-263. doi: 10.1016/0167-6911(94)00011-J. [24] N. El Karoui, S. Peng ang M. C. Quenez, Backward stochastic differential equations in finance, Math. Finance, 7 (1997), 1-71. doi: 10.1111/1467-9965.00022. [25] V. Katkovnik, A. Danielyan and K. Egiazarian, Decoupled inverse and denoising for image deblurring: variational BM3D-frame technique, in Image Processing (ICIP), 2011 18th IEEE International Conference on, 2011, 3453-3456. doi: 10.1109/ICIP.2011.6116455. [26] M. Lebrun, A. Buades and J. M. Morel, Implementation of the non-local Bayes image denoising, Image Processing On Line, 3 (2013), 1-42. doi: 10.5201/ipol.2013.16. [27] J. Ma, P. Protter, J. San Martín and S. Torres, Numerical method for backward stochastic differential equations, Ann. Appl. Probab., 12 (2002), 302-316. doi: 10.1214/aoap/1015961165. [28] J. Mairal, M. Elad and G. Sapiro, Sparse representation for color image restoration, IEEE Trans. Image Process., 17 (2008), 53-69. doi: 10.1109/TIP.2007.911828. [29] É. Pardoux and S. G. Peng, Adapted solution of a backward stochastic differential equation, Systems Control Lett. 14 (1990), 55-61. doi: 10.1016/0167-6911(90)90082-6. [30] É. Pardoux, Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic PDEs of second order, in: Stochastic Analysis and Related Topics VI, Progr. Probab. 42 (1998), 79-127. doi: 10.1007/978-1-4612-2022-0_2. [31] É. Pardoux and S. G. Peng, Backward stochastic differential equations and quasilinear parabolic partial differential equations, Lecture Notes in Control and Inform. Sci., 176 (1992), 200-217. doi: 10.1007/BFb0007334. [32] P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), 629-639. doi: 10.1109/34.56205. [33] R. Pettersson, Approximations for stochastic differential equations with reflecting convex boundaries, Stochastic Process. Appl., 59 (1995), 295-308. doi: 10.1016/0304-4149(95)00040-E. [34] W. H. Richardson, Bayesian-based iterative method of image restoration, J. Opt. Soc. Am., 62 (1972), 55-59. doi: 10.1364/JOSA.62.000055. [35] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [36] B. Smolka and K. N. Plataniotis, On the coupled forward and backward anisotropic diffusion scheme for color image enhancement, in Image and Video Retrieval, Lect. Notes Comput. Sci., 2383 (2002), 70-80. doi: 10.1007/3-540-45479-9_8. [37] L. Słomiński, Euler's approximations of solutions of SDEs with reflecting boundary, Stochastic Process. Appl., 94 (2001), 317-337. doi: 10.1016/S0304-4149(01)00087-4. [38] H. Tanaka, Stochastic differential equations with reflecting boundary condition in convex regions, Hiroshima Math. J., 9 (1979), 163-177. Available from: http://projecteuclid.org/euclid.hmj/1206135203. [39] J. Weickert, Theoretical foundations of anisotropic diffusion in image processing, in Theoretical Foundations of Computer Vision, Computing Supplement, 11 (1996), 221-236. doi: 10.1007/978-3-7091-6586-7_13. [40] J. Weickert, Coherence-enhancing diffusion filtering, Int. J. Comput. Vision, 31 (1999), 111-127. doi: 10.1023/A:1008009714131. [41] M. Welk, G. Gilboa and J. Weickert, Theoretical foundations for discrete forward-and-backward diffusion filtering, in Scale Space and Variational Methods in Computer Vision, Lect. Notes Comput. Sci., 5567 (2009), 527-538. doi: 10.1007/978-3-642-02256-2_44. [42] L. P. Yaroslavsky, Local adaptive image restoration and enhancement with the use of DFT and DCT in a running window, in Wavelet Applications in Signal and Image Processing IV, 2 (October 23, 1996), Proc. SPIE, 2825 (1996), 2-13. doi: 10.1117/12.255218. [43] L. P. Yaroslavsky, K. O. Egiazarian and J. T. Astola, Transform domain image restoration methods: review, comparison, and interpretation, in Nonlinear Image Processing and Pattern Analysis XII, 155 (May 8, 2001), Proc. SPIE, 4304 (2001), 155-169. doi: 10.1117/12.424970.

show all references

##### References:
 [1] M. Aharon, M. Elad and A. Bruckstein, K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., 54 (2006), 4311-4322. doi: 10.1109/TSP.2006.881199. [2] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing, Applied Mathematical Sciences, 147, Springer, New York, 2006. doi: 10.1007/978-0-387-44588-5. [3] D. Borkowski, Chromaticity denoising using solution to the Skorokhod problem, in Image Processing Based on Partial Differential Equations, Mathematics and Visualization, 2007, 149-161. doi: 10.1007/978-3-540-33267-1_9. [4] D. Borkowski, Smoothing, enhancing filters in terms of backward stochastic differential equations, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 6374 (2010), 233-240. doi: 10.1007/978-3-642-15910-7_26. [5] D. Borkowski, Euler's approximations to image reconstruction, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 7594 (2012), 30-37. doi: 10.1007/978-3-642-33564-8_4. [6] D. Borkowski and K. Jańczak-Borkowska, Application of backward stochastic differential equations to reconstruction of vector-valued images, in Computer Vision and Graphics, Lect. Notes Comput. Sci., 7594 (2012), 38-47. doi: 10.1007/978-3-642-33564-8_5. [7] A. Buades, B. Coll and J. M. Morel, A non local algorithm for image denoising, in Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2 (2005), 60-65. doi: 10.1109/CVPR.2005.38. [8] A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Model. Simul., 4 (2005), 490-530. doi: 10.1137/040616024. [9] A. Buades, B. Coll and J. M. Morel, Non-local means denoising, Image Processing On Line, 1 (2011). doi: 10.5201/ipol.2011.bcm_nlm. [10] F. Catte, P. L. Lions, J. M. Morel and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J. Numer. Anal., 29 (1992), 182-193. doi: 10.1137/0729012. [11] T. F. Chan and J. J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, SIAM, 2005. doi: 10.1137/1.9780898717877. [12] K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans. Image Process., 16 (2007), 2080-2095. doi: 10.1109/TIP.2007.901238. [13] A. Danielyan, V. Katkovnik and K. Egiazarian, Bm3d frames and variational image deblurring, IEEE Trans. Image Process., 21 (2012), 1715-1728. doi: 10.1109/TIP.2011.2176954. [14] D. L. Donoho and I. M. Johnstone, Ideal spatial adaptation via wavelet shrinkage, Biometrika, 81 (1994), 425-455. doi: 10.1093/biomet/81.3.425. [15] D. Duffie and L. Epstein, Asset pricing with stochastic differential utility, Review of Financial Studies, 5 (1992), 411-436. doi: 10.1093/rfs/5.3.411. [16] D. Duffie and L. Epstein, Stochastic differential utility, Econometrica, 60 (1992), 353-394. doi: 10.2307/2951600. [17] A. Efros and T. Leung, Texture synthesis by non parametric sampling, in Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, 2 (1999), 1033-1038. doi: 10.1109/ICCV.1999.790383. [18] D. Fang, Z. Nanning and X. Jianru, Image smoothing and sharpening based on nonlinear diffusion equation, Signal Process., 88 (2008), 2850-2855. doi: 10.1016/j.sigpro.2008.05.008. [19] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6 (1984), 721-741. doi: 10.1109/TPAMI.1984.4767596. [20] P. Getreuer, Rudin-Osher-Fatemi total variation denoising using split Bregman, Image Processing On Line, 2 (2012), 74-95. doi: 10.5201/ipol.2012.g-tvd. [21] G. Gilboa, N. Sochen and Y. Y. Zeevi, Forward-and-backward diffusion processes for adaptive image enhancement and denoising, IEEE Trans. Image Process., 11 (2002), 689-703. doi: 10.1109/TIP.2002.800883. [22] T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343. doi: 10.1137/080725891. [23] S. Hamadene and J. P. Lepeltie, Zero-sum stochastic differential games and backward equations, Syst. Control Lett., 24 (1995), 259-263. doi: 10.1016/0167-6911(94)00011-J. [24] N. El Karoui, S. Peng ang M. C. Quenez, Backward stochastic differential equations in finance, Math. Finance, 7 (1997), 1-71. doi: 10.1111/1467-9965.00022. [25] V. Katkovnik, A. Danielyan and K. Egiazarian, Decoupled inverse and denoising for image deblurring: variational BM3D-frame technique, in Image Processing (ICIP), 2011 18th IEEE International Conference on, 2011, 3453-3456. doi: 10.1109/ICIP.2011.6116455. [26] M. Lebrun, A. Buades and J. M. Morel, Implementation of the non-local Bayes image denoising, Image Processing On Line, 3 (2013), 1-42. doi: 10.5201/ipol.2013.16. [27] J. Ma, P. Protter, J. San Martín and S. Torres, Numerical method for backward stochastic differential equations, Ann. Appl. Probab., 12 (2002), 302-316. doi: 10.1214/aoap/1015961165. [28] J. Mairal, M. Elad and G. Sapiro, Sparse representation for color image restoration, IEEE Trans. Image Process., 17 (2008), 53-69. doi: 10.1109/TIP.2007.911828. [29] É. Pardoux and S. G. Peng, Adapted solution of a backward stochastic differential equation, Systems Control Lett. 14 (1990), 55-61. doi: 10.1016/0167-6911(90)90082-6. [30] É. Pardoux, Backward stochastic differential equations and viscosity solutions of systems of semilinear parabolic and elliptic PDEs of second order, in: Stochastic Analysis and Related Topics VI, Progr. Probab. 42 (1998), 79-127. doi: 10.1007/978-1-4612-2022-0_2. [31] É. Pardoux and S. G. Peng, Backward stochastic differential equations and quasilinear parabolic partial differential equations, Lecture Notes in Control and Inform. Sci., 176 (1992), 200-217. doi: 10.1007/BFb0007334. [32] P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), 629-639. doi: 10.1109/34.56205. [33] R. Pettersson, Approximations for stochastic differential equations with reflecting convex boundaries, Stochastic Process. Appl., 59 (1995), 295-308. doi: 10.1016/0304-4149(95)00040-E. [34] W. H. Richardson, Bayesian-based iterative method of image restoration, J. Opt. Soc. Am., 62 (1972), 55-59. doi: 10.1364/JOSA.62.000055. [35] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [36] B. Smolka and K. N. Plataniotis, On the coupled forward and backward anisotropic diffusion scheme for color image enhancement, in Image and Video Retrieval, Lect. Notes Comput. Sci., 2383 (2002), 70-80. doi: 10.1007/3-540-45479-9_8. [37] L. Słomiński, Euler's approximations of solutions of SDEs with reflecting boundary, Stochastic Process. Appl., 94 (2001), 317-337. doi: 10.1016/S0304-4149(01)00087-4. [38] H. Tanaka, Stochastic differential equations with reflecting boundary condition in convex regions, Hiroshima Math. J., 9 (1979), 163-177. Available from: http://projecteuclid.org/euclid.hmj/1206135203. [39] J. Weickert, Theoretical foundations of anisotropic diffusion in image processing, in Theoretical Foundations of Computer Vision, Computing Supplement, 11 (1996), 221-236. doi: 10.1007/978-3-7091-6586-7_13. [40] J. Weickert, Coherence-enhancing diffusion filtering, Int. J. Comput. Vision, 31 (1999), 111-127. doi: 10.1023/A:1008009714131. [41] M. Welk, G. Gilboa and J. Weickert, Theoretical foundations for discrete forward-and-backward diffusion filtering, in Scale Space and Variational Methods in Computer Vision, Lect. Notes Comput. Sci., 5567 (2009), 527-538. doi: 10.1007/978-3-642-02256-2_44. [42] L. P. Yaroslavsky, Local adaptive image restoration and enhancement with the use of DFT and DCT in a running window, in Wavelet Applications in Signal and Image Processing IV, 2 (October 23, 1996), Proc. SPIE, 2825 (1996), 2-13. doi: 10.1117/12.255218. [43] L. P. Yaroslavsky, K. O. Egiazarian and J. T. Astola, Transform domain image restoration methods: review, comparison, and interpretation, in Nonlinear Image Processing and Pattern Analysis XII, 155 (May 8, 2001), Proc. SPIE, 4304 (2001), 155-169. doi: 10.1117/12.424970.
 [1] Vladimir Kazakov. Sampling - reconstruction procedure with jitter of markov continuous processes formed by stochastic differential equations of the first order. Conference Publications, 2009, 2009 (Special) : 433-441. doi: 10.3934/proc.2009.2009.433 [2] Lacramioara Grecu, Constantin Popa. Constrained SART algorithm for inverse problems in image reconstruction. Inverse Problems and Imaging, 2013, 7 (1) : 199-216. doi: 10.3934/ipi.2013.7.199 [3] Jasmina Djordjević, Svetlana Janković. Reflected backward stochastic differential equations with perturbations. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 1833-1848. doi: 10.3934/dcds.2018075 [4] Jan A. Van Casteren. On backward stochastic differential equations in infinite dimensions. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 803-824. doi: 10.3934/dcdss.2013.6.803 [5] Joscha Diehl, Jianfeng Zhang. Backward stochastic differential equations with Young drift. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 5-. doi: 10.1186/s41546-017-0016-5 [6] Xin Chen, Ana Bela Cruzeiro. Stochastic geodesics and forward-backward stochastic differential equations on Lie groups. Conference Publications, 2013, 2013 (special) : 115-121. doi: 10.3934/proc.2013.2013.115 [7] Ying Hu, Shanjian Tang. Switching game of backward stochastic differential equations and associated system of obliquely reflected backward stochastic differential equations. Discrete and Continuous Dynamical Systems, 2015, 35 (11) : 5447-5465. doi: 10.3934/dcds.2015.35.5447 [8] Weihong Guo, Jing Qin. A geometry guided image denoising scheme. Inverse Problems and Imaging, 2013, 7 (2) : 499-521. doi: 10.3934/ipi.2013.7.499 [9] Qi Zhang, Huaizhong Zhao. Backward doubly stochastic differential equations with polynomial growth coefficients. Discrete and Continuous Dynamical Systems, 2015, 35 (11) : 5285-5315. doi: 10.3934/dcds.2015.35.5285 [10] Yufeng Shi, Qingfeng Zhu. A Kneser-type theorem for backward doubly stochastic differential equations. Discrete and Continuous Dynamical Systems - B, 2010, 14 (4) : 1565-1579. doi: 10.3934/dcdsb.2010.14.1565 [11] Yanqing Wang. A semidiscrete Galerkin scheme for backward stochastic parabolic differential equations. Mathematical Control and Related Fields, 2016, 6 (3) : 489-515. doi: 10.3934/mcrf.2016013 [12] Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete and Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905 [13] Weidong Zhao, Yang Li, Guannan Zhang. A generalized $\theta$-scheme for solving backward stochastic differential equations. Discrete and Continuous Dynamical Systems - B, 2012, 17 (5) : 1585-1603. doi: 10.3934/dcdsb.2012.17.1585 [14] Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control and Related Fields, 2021, 11 (4) : 797-828. doi: 10.3934/mcrf.2020047 [15] Jiongmin Yong. Forward-backward stochastic differential equations: Initiation, development and beyond. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022011 [16] Yinggu Chen, Said HamadÈne, Tingshu Mu. Mean-field doubly reflected backward stochastic differential equations. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022012 [17] Martin Hutzenthaler, Thomas Kruse, Tuan Anh Nguyen. On the speed of convergence of Picard iterations of backward stochastic differential equations. Probability, Uncertainty and Quantitative Risk, 2022, 7 (2) : 133-150. doi: 10.3934/puqr.2022009 [18] Renzhi Qiu, Shanjian Tang. The Cauchy problem of Backward Stochastic Super-Parabolic Equations with Quadratic Growth. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 3-. doi: 10.1186/s41546-019-0037-3 [19] Ishak Alia. Time-inconsistent stochastic optimal control problems: a backward stochastic partial differential equations approach. Mathematical Control and Related Fields, 2020, 10 (4) : 785-826. doi: 10.3934/mcrf.2020020 [20] Ying Liu, Yabing Sun, Weidong Zhao. Explicit multistep stochastic characteristic approximation methods for forward backward stochastic differential equations. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 773-795. doi: 10.3934/dcdss.2021044

2021 Impact Factor: 1.483


text:
[Opinion] The Hypocrisy of the NCAA's Amateurism Model

Wednesday, Mar 4, 2020

Photo credit: AP Images.

As the confetti rained down on the victorious LSU Tigers football team, proud alumnus Odell Beckham Jr., now a wide receiver for the Cleveland Browns, handed out wads of cash to the beaming players. The players will have to give that money back, but their coach, university, and sponsors will pocket millions because of their victory. This was but the most recent example of the injustice of the NCAA’s insistence on amateurism, which claims the purity of having no money in the game while at the same time constructing a multibillion-dollar industry around college athletics. This massive business is built on the backs of athletes, the majority of whom are black, while the profits go to mostly white power brokers.

The racial dynamics of college athletics frame the injustice of the amateurism model. A 2017 study found that the majority of the athletes who play the highest revenue-generating sports, FBS-level football and men’s basketball, were black. Meanwhile, white people held 84 percent of college basketball and 91 percent of football coaching positions, while over 86 percent of football conference commissioners were white. Similar disparities exist higher up the chain, with athletic directors, conference commissioners, and university presidents.

This stark divide, between the majority-black athletes creating vast revenue for mostly white beneficiaries, lays bare the inequality of the NCAA’s policies. Despite their scholarships and small stipends, athletes often struggle to live comfortably at school. During the University of Connecticut's championship run in the men’s basketball tournament in 2014, Shabazz Napier told reporters “sometimes there's hungry nights where I’m not able to eat but I still have to play up to my capabilities.” Napier presents just one example of student-athletes struggling to fulfill all of the expectations that the collegiate athletics machine puts on their shoulders without providing the resources to fulfill them.

With fifty hours a week dedicated to their sports, athletes are often not able to get a campus job to cover expenses. They are provided a stipend, but often it is not sufficient, as Napier attests. The same issue exists in college football. At Clemson, for example, football players are given a stipend, $388 a month in 2017 for example, to meet the costs of attendance not covered in the scholarship. Many players, after using some for their expenses, send the money home to help their families. In 2017, Clemson linebacker Dorian O’Daniel said “it’s not enough. I know beggars can’t be choosers, but it’s still not enough.” Clemson's$55 million football facility. Photo credit: HOK

While athletes stretch to get by, their coaches and schools are flooded with upwards of hundreds of millions of dollars. In that same year, 2017, Clemson unveiled a new $55-million football complex, complete with an indoor slide, bowling alley, basketball court, putting green, mini-golf course, wiffle ball field, fire pit, lockers designed to look like thrones, multiple swimming pools, and many more amenities. Clemson’s head coach Dabo Swinney signed a 10 year,$92 million contract last year, with hundreds of thousands of dollars in bonuses for success in the playoffs. He gets rewarded for the work he does, while many of his players will not be.

Clemson's football complex features 1.5 acres of outdoor leisure space. Photo credit: HOK

Some have compared the amateurism model to slavery, wherein laborers, mostly black, create profits for their superiors, mostly white, that they will never see a piece of. For example, Kylia Carter, mother of then-UNC basketball player Wendell Carter Jr., explained that the NCAA model is “a system like the only system I have ever seen, where the laborers are the only people that are not being compensated for the work they do, while those in charge receive mighty compensation. The only two systems that I’ve known that to be in place is slavery, and the prison system. And now I see the NCAA as a system that is identical for that.”

Taylor Branch, a historian who studied the history of the NCAA’s exploitation of athletes, wrote that the NCAA’s clinging to amateurism “echoes masters who once claimed that heavenly salvation would outweigh earthly injustice to slaves. In the era when our college sports first arose, colonial powers were turning the whole world upside down to define their own interests as all-inclusive and benevolent. Just so, the NCAA calls it heinous exploitation to pay college athletes a fair portion of what they earn.” Walter Byers, who built up the commercial enterprise that is the modern NCAA, came to regret the injustice of the system he constructed. He wrote in his memoir that the NCAA’s treatment of athletes is “the plantation mentality resurrected and blessed by today’s campus executives.”

The myriad ways in which the NCAA takes advantage of student-athletes all compound this unequal framework, as each element of exploitation disproportionately disadvantages black athletes while enriching white beneficiaries.

The ethos of the NCAA centers around the sanctity of the student-athlete, with an emphasis on an even split between the two roles. With access to a prestigious education and the ability to play professionally later on, why should college athletes be compensated further? Add money to the mix, and the purity of college sports gets corrupted. But the financial incentives of the NCAA and schools demand that players prioritize their sport over everything else, including their education. Allowing athletes to profit off their work—through endorsement and licensing deals at the very least—would actually fit the model of what the NCAA has become, not violate it.

The NCAA’s inability to ensure that college athletes receive a quality education undermines their central claim about the value of amateurism. The NCAA argues that “maintaining amateurism is crucial to preserving an academic environment in which acquiring a quality education is the first priority.” But athletes’ experiences reveal that they are forced to put their sport, not their learning, first. In a 2014 case arguing for the unionization of the Northwestern football team, quarterback Kain Colter described the effect of the fifty hours per week commitment required for his sport, saying “it makes it hard for you to succeed. You can’t ever reach your academic potential with the time demands. You have to sacrifice, and we’re not allowed to sacrifice football.”

A 2015 study of over four hundred Pac-12 athletes across a number of sports told a similar story. A majority of athletes said that their sport interfered with their ability to succeed academically, affecting their ability to attend class, study for exams, and even get the amount of sleep they need to perform well in the classroom and on the field. The time demand left them “too exhausted to study effectively.” If the NCAA really was interested in ensuring student-athletes’ academics come first, they would address this issue.

Schools also often conspire to decrease the worth of athletes’ educations by funneling them into easier classes so they can focus on their sport. For example, Stephen Cline, a football player at Kansas State, was told to switch from his passion for veterinary work so that he could focus on his athletics. Cline reflects, “the whole time...I felt stuck – stuck in football, stuck in my major. Now I look back and say, ‘well what did I really go to college for?’ Crap classes you won’t use the rest of your life? I was majoring in football.”

Sometimes, these shortcuts cross the line into academic fraud. The University of North Carolina was exposed for running over 1,800 “paper classes” from 1999-2011, which required minimal work and inflated grades to help athletes to maintain their eligibility. The NCAA declined to punish the university. Ten years of exploitation, as UNC and the NCAA pocketed billions from those athletes’ performances on fields and courts over the years. Countless athletes who did not get the education the NCAA claims to hold so dear. And no consequences for the people who facilitated it.

Meanwhile, athletes are routinely punished for violating ambiguous rules. In an op-ed Draymond Green, an alum of Michigan State and now a player for the Golden State Warriors, called the NCAA a “dictatorship” because of its archaic rules. He recalled an instance when he was given only three tickets for his family to attend his Final Four game, meaning his whole family could not attend. If someone gifted his grandmother a ticket or Green sold his autograph to pay for it, he would have been punished. In Green’s words, the NCAA “controls everything you do. And if you don’t follow its archaic rules, it will prohibit you from playing.”

It seems like a tiny rule, but it is just one example of the litany of tripwires that await student-athletes. Minor, common-sense infractions threaten their eligibility and by extension their future opportunities. A predominantly white institution holds in its hands the futures of predominantly black athletes, and they are powerless to fight back.

This year, University of Memphis star basketball player James Wiseman was suspended because in 2017, while Wiseman was in high school, his family—without Wiseman’s knowledge—accepted an $11,500 payment from Penny Hardaway to help him move to Memphis and play for Hardway’s team. Hardaway is now the coach at the University of Memphis. The NCAA ruled this an “improper benefit” because Hardaway had donated$1 million to the university in 2008, making him a booster for the school. To get back on the court, Wiseman would have to serve his 12-game suspension and pay back the $11,500. James Wiseman withdrew from the University of Memphis after the NCAA suspended him for violating its rules. Photo credit: Karen Pulfer Focht/Associated Press. What may seem like a technicality took a significant toll on Wiseman. He described the experience as “dehumanizing,” creating a sense of “mental agony” that left him “crying every night” as the pressure of the legal issues interfered with his ability to play the game he loved. Rather than returning to the team after his 12-game suspension, Wiseman withdrew from the university to focus on preparing for the NBA draft. He explained that, being “just a regular college student,” his inability to pay the$11,500 contributed to his decision to leave Memphis, along with the risk of injury. He joins a growing trend, as the two other players projected to top the NBA draft along with Wiseman are currently playing overseas for pay rather than in the NCAA as they await draft eligibility. They see through the NCAA’s game, and are taking back their agency.

On the one hand, the NCAA insists on college athletes placing as much emphasis on their education as they focus on their athletics, while at the same time doing everything they can to prioritize profit, often at the expense of athletes’ academics. Even Mark Lewis, a former NCAA vice president turned player advocate, recognizes this: “The challenge with college sports is you’ve made everything else professional, except the labor model.” And it is impossible to ignore the fact that this disenfranchised labor model is comprised of mostly black athletes.

The $14 billion in revenue that college sports programs brought in last year surpasses every professional league in the world except the NFL. The time to oppose the commercialization of college athletics is long gone, especially for the NCAA, the very institution that fueled it. If everyone around athletes benefits from their labor, athletes have a right to share in the rewards they generate. The argument that the opportunity for future earnings justifies amateurism falls flat as well. Essentially, the NCAA requires athletes to sacrifice their bodies, which their livelihood depends on, for the miniscule chance of making it to the professional league, and an even lower chance of lasting there. According to the NCAA, of the tens of thousands of athletes who sacrifice so much for their schools, only 1.6% of football, 1.2% of men’s basketball, and 0.9% of women’s basketball players make it to the professionals. If they are among the few who make it to the next level, the average NFL career lasts only 3.3 years. These statistics reveal just how valuable an athlete’s college-age years are—it may well be their only chance to capitalize on their talent and hard work. Yet they have to spend those years laboring for an institution that does not value them. The possibility of being able to earn in the future is extremely precarious. Take Zion Williamson for example. A highly-recruited, top-performing freshman for Duke basketball last year, Williamson was expected to be drafted first overall in the NBA draft before the season even started. But he had to spend at least a year in college, delaying his ability to earn his due off his talent and risking an injury that could derail it all. And it nearly did. Zion Williamson injured his knee after his sneaker split apart 30 seconds into a game. Photo credit: Rob Kinnan/USA Today Sports, via Reuters. Thirty seconds into a game last winter, Williamson’s shoe broke open, the sole completely separating from the rest of the sneaker, leaving the star with a sprained knee. In one bizarre moment, we saw how quickly an athletes’ future can disappear, how fragile their opportunity really is. A number of observers, including Scottie Pippen and Isaiah Thomas, argued that Williamson should have forgone the rest of the season. Donovan Mitchell, a player for the Utah Jazz, tweeted “let’s remember all the money that went into this game.... and these players get none of it.... and now Zion gets hurt... something has to change @NCAA.” That game, the latest chapter in Duke’s famed rivalry with the University of North Carolina, is a perfect microcosm of the asymmetry of how money runs through college athletics. It was the most-viewed weekday game in NCAA history, with 4.3 million people tuning in. Tickets on game day cost$4000, matching the Super Bowl that year. Duke has a lucrative deal with Nike to equip its athletes. The details of the deal are not public, but the University of Michigan recently signed a deal with Nike worth $127 million over eleven years, while UNC will receive over$90 million over its ten-year partnership with the brand. UNC’s coaches also have contracts with Nike—the men’s basketball head coach Roy Williams will receive \$300,000 a year. All this money swirled around the game, yet the players on the court received none of it.

A former Nike executive, Sonny Vacarro, who helped start the sneaker endorsement trend in college sports back in the 1970s, now realizes the unfairness of the industry. While schools and coaches profit, “we see the kids wearing the shoes and selling the product all over the world — and the kids never got anything. The money has served the same people, except for the most important ones.”

The argument for allowing student-athletes to earn money does not imply that college athletics are inherently bad. In an interview a few months ago, Williamson recounted how he wanted to stay at Duke, and did not decide to enter the draft until deadline day. But as much as he enjoyed college, the incentives to stay were not compelling enough—why stay in a place where he cannot make money and would risk his ability to do so in the future when teams and brands were lining up to reward him now? If he was able to support himself and his family while enjoying the college experience, perhaps it would have made more sense for Williamson and others like him to stay in school longer.

When his sneaker broke open, so potentially did Williamson’s chance to earn a share of the profits his school and the NCAA had already pocketed. The NCAA is comfortable making athletes like Williamson into walking billboards, but somehow allowing them to advertise for their own benefit is a bridge too far.

A movement is growing among states to implement laws allowing athletes to profit from their name, image, and likeness, for example through endorsement deals and merchandising. Last year, California was first to pass such a law, which will go into effect in 2021. Many states, and even Congress, are beginning to follow suit, as they should.

If the NCAA wants student-athletes to be treated as full people, and wants to put the power behind that hyphen, it should support allowing college athletes to reap the rewards of their labor. Allowing athletes to share in the benefits of effort they put into athletics acknowledges and appreciates that work, rather than taking it for granted.

It is unacceptable that student-athletes should be struggling to get by while everyone around them makes a fortune. It is unjust that an athlete should risk his or her entire future for a university that shares none of the profits of their work. If the NCAA wants to focus on education, it should stop giving schools every incentive to prioritize profit. If it wants college athletics to continue to be a multibillion dollar industry, it should not keep athletes from getting their fair share.

Recent News

Princeton University is actively monitoring the situation around coronavirus (COVID-19). The latest University guidance for students, faculty and...

Today on episode 44 of The Quarantine Tapes, Paul Holdengräber speaks with professor and author Imani Perry. They discuss what it means for artists...
Tags:  AAS Faculty
Princeton seniors Matthew Oakland and Olivia Ott have been awarded two of the University’s highest awards for graduating students. Oakland, of Elk...
Tags:  AAS Students

format: plain


text:
# Elementary proof of claim in Baby Rudin 3.31

On p65 Rudin states: $$e-s_n = \frac{1}{(n+1)!}+\frac{1}{(n+2)!}+\frac{1}{(n+3)!}+... < \frac{1}{(n+1)!}(1 + \frac{1}{n+1}+\frac{1}{(n+1)^2}+...)=\frac{1}{n!n}$$ Where $s_n = \sum_{k=0}^{n}{\frac{1}{k!}}$. What I understand:

• Each partial sum for $n\ge 2$ on the left is less than the one on the right. So the total sum on the left is less than or equal to the one on the right.
• If the sum on the left is equal to the sum on the right, then $e = s_n + \frac{1}{n!n}$ would be rational.

I was wondering:

Is there a more constructive way to show that the sum on the left is not equal to that on the right?

• The sum on the left is strictly less than that on the right, because starting from the $2$nd term, the term on the left is less than the corresponding one on the right. Nov 5, 2014 at 10:09
• Could you please explain why this is true? I thought about the general case, but consider $S_n = 1-\frac{1}{n^2}, T_n = 1-\frac{1}{n^3}$ Then starting from the second partial sum, $S_n < T_n$ but $S_n \rightarrow 1$ and $S_n \rightarrow 1$. Nov 5, 2014 at 10:14

Series are different from sequences. Suppose that $a_n\le b_n$ for all $n$ and $a_N<b_N$ for some fixed $N$. Then for any $m>N$ $$\sum^m_{n=1}b_n-\sum^m_{n=1}a_n=\sum^m_{n=1}(b_n-a_n)\ge b_N-a_N.$$ Pushing $m\to \infty$, we get $$\sum b_n-\sum a_n\ge b_N-a_N.$$

Note: The given argument actually shows that $e$ is irrational. One of the most elementary arguments I know of.

• Thanks! This was exactly what I was looking for. Nov 6, 2014 at 0:31

The inmequality is true since

$$\frac1{(n+1)!}+\frac1{(n+2)!}+\frac1{(n+3)!}+\ldots=\frac1{(n+1)!}\left(1+\frac1{n+2}+\frac1{(n+2)(n+3)}+\ldots\right)<$$

$$<\frac1{(n+1)!}\left(1+\frac1{n+1}+\frac1{(n+1)^2}+\ldots\right)$$

since

$$(n+1)<(n+i)\;,\;\;\forall\;2\le i\le k\implies(n+1)^k<(n+2)(n+3)\cdot\ldots\cdot(n+k)$$


text:
This post includes all the major updates since the last post about VF2++. Each section is dedicated to a different sub-problem and presents the progress on it so far. General progress, milestones and related issues can be found here.

## Node ordering

The node ordering is one major modification that VF2++ proposes. Basically, the nodes are examined in an order that makes the matching faster by first examining nodes that are more likely to match. This part of the algorithm has been implemented, however there is an issue. The existence of detached nodes (not connected to the rest of the graph) causes the code to crash. Fixing this bug will be a top priority during the next steps. The ordering implementation is described by the following pseudocode.

Matching Order

1. Set $M = \varnothing$.
2. Set $\bar{V1}$ : nodes not in order yet
3. while $\bar{V1}$ not empty do
• $rareNodes=[$nodes from $V_1$ with the rarest labels$]$
• $maxNode=argmax_{degree}(rareNodes)$
• $T=$ BFSTree with $maxNode$ as root
• for every level in $T$ do
• $V_d=[$nodes of the $d^{th}$ level$]$
• $\bar{V_1} \setminus V_d$
• $ProcessLevel(V_d)$
4. Output $M$: the matching order of the nodes.

Process Level

1. while $V_d$ not empty do
• $S=[$nodes from $V_d$ with the most neighbors in M$]$
• $maxNodes=argmax_{degree}(S)$
• $rarestNode=[$node from $maxNodes$ with the rarest label$]$
• $V_d \setminus m$
• Append m to M

## $T_i$ and $\tilde{T_i}$

According to the VF2++ paper notation:

$$T_1=(u\in V_1 \setminus m: \exists \tilde{u} \in m: (u,\tilde{u}\in E_1))$$

where $V_1$ and $E_1$ contain all the nodes and edges of the first graph respectively, and $m$ is a dictionary, mapping every node of the first graph to a node of the second graph. Now if we interpet the above equation, we conclude that $T_1$ contains uncovered neighbors of covered nodes. In simple terms, it includes all the nodes that do not belong in the mapping $m$ yet, but are neighbors of nodes that are in the mapping. In addition,

$$\tilde{T_1}=(V_1 \setminus m \setminus T_1)$$

The following figure is meant to provide some visual explanation of what exactly $T_i$ is.

The blue nodes 1,2,3 are nodes from graph G1 and the green nodes A,B,C belong to the graph G2. The grey lines connecting those two indicate that in this current state, node 1 is mapped to node A, node 2 is mapped to node B, etc. The yellow edges are just the neighbors of the covered (mapped) nodes. Here, $T_1$ contains the red nodes (4,5,6) which are neighbors of the covered nodes 1,2,3, and $T_2$ contains the grey ones (D,E,F). None of the nodes depicted would be included in $\tilde{T_1}$ or $\tilde{T_2}$. The latter sets would contain all the remaining nodes from the two graphs.

Regarding the computation of these sets, it’s not practical to use the brute force method and iterate over all nodes in every step of the algorithm to find the desired nodes and compute $T_i$ and $\tilde{T_i}$. We use the following observations to implement an incremental computation of $T_i$ and $\tilde{T_i}$ and make VF2++ more efficient.

• $T_i$ is empty in the beggining, since there are no mapped nodes ($m=\varnothing$) and therefore no neighbors of mapped nodes.
• $\tilde{T_i}$ initially contains all the nodes from graph $G_i, i=1,2$ which can be realized directly from the notation if we consider both $m$ and $T_1$ empty sets.
• Every step of the algorithm either adds one node $u$ to the mapping or pops one from it.

We can conclude that in every step, $T_i$ and $\tilde{T_i}$ can be incrementally updated. This method avoids a ton of redundant operations and results in significant performance improvement.

The above graph shows the difference in performance between using the exhaustive brute force and incrementally updating $T_i$ and $\tilde{T_i}$. The graph used to obtain these measurements was a regular GNP Graph with a probability for an edge equal to $0.7$. It can clearly be seen that execution time of the brute force method increases much more rapidly with the number of nodes/edges than the incremental update method, as expected. The brute force method looks like this:

def compute_Ti(G1, G2, mapping, reverse_mapping):
T1 = {nbr for node in mapping for nbr in G1[node] if nbr not in mapping}
T2 = {
nbr
for node in reverse_mapping
for nbr in G2[node]
if nbr not in reverse_mapping
}

T1_out = {n1 for n1 in G1.nodes() if n1 not in mapping and n1 not in T1}
T2_out = {n2 for n2 in G2.nodes() if n2 not in reverse_mapping and n2 not in T2}
return T1, T2, T1_out, T2_out

If we assume that G1 and G2 have the same number of nodes (N), the average number of nodes in the mapping is $N_m$, and the average node degree of the graphs is $D$, then the time complexity of this function is:

$$O(2N_mD + 2N) = O(N_mD + N)$$

in which we have excluded the lookup times in $T_i$, $mapping$ and $reverse\_mapping$ as they are all $O(1)$. Our incremental method works like this:

def update_Tinout(
G1, G2, T1, T2, T1_out, T2_out, new_node1, new_node2, mapping, reverse_mapping
):
# This function should be called right after the feasibility is established and node1 is mapped to node2.
uncovered_neighbors_G1 = {nbr for nbr in G1[new_node1] if nbr not in mapping}
uncovered_neighbors_G2 = {
nbr for nbr in G2[new_node2] if nbr not in reverse_mapping
}

# Add the uncovered neighbors of node1 and node2 in T1 and T2 respectively
T1 = T1.union(uncovered_neighbors_G1)
T2 = T2.union(uncovered_neighbors_G2)

# todo: maybe check this twice just to make sure
T1_out = T1_out - uncovered_neighbors_G1
T2_out = T2_out - uncovered_neighbors_G2

return T1, T2, T1_out, T2_out

which based on the previous notation, is:

$$O(2D + 2(D + M_{T_1}) + 2D) = O(D + M_{T_1})$$

where $M_{T_1}$ is the expected (average) number of elements in $T_1$.

Certainly, the complexity is much better in this case, as $D$ and $M_{T_1}$ are significantly smaller than $N_mD$ and $N$.

In this post we investigated how node ordering works at a high level, and also how we are able to calculate some important parameters so that the space and time complexity are reduced. The next post will continue with examining two more significant components of the VF2++ algorith: the candidate node pair selection and the cutting/consistency rules that decide when the mapping should or shouldn’t be extended. Stay tuned!


text:
# Using a grad class as a prereq for stat/biostat MS in a unique situation.

#### DoIhaveashot?

##### New Member
Hello all,

I guess I'll begin with my goal: to obtain an MS in stat/biostats in order to change careers. I do not intend to pursue education beyond the MS level. Also the schools I intend to apply to are not top tier, just solid regional schools where I'd like to settle.

I have a unique situation in that my undergraduate background was not formally in mathematics. In fact I have a BA in English. After graduation, when the urge to change careers crept in, I began taking mathematics courses to satisfy the min prereqs for stats degrees, calc I,II,III, diff eq, and linear algebra, receiving an A in each.

That left me with just one more prereq, a calc based stats course. Thinking I'd be slick and complete a prereq and get a degree requirement out of the way in one shot, I enrolled in a grad level mathematical statistics course at my states second largest public university. I then found out the differences between undergrad and grad level....THe hours of study, the level of expectation, and quality of teaching, totally different... but overall I learned more than any class I've ever taken--I liked it. Unfortunately I only cleared a B in the course, and therein lies my predicament. What does this grad level B say about me as a student?

It seems grad level Bs are vary a lot from institution to institution...some claim a B is a borderline failure others say that a B is not bad at all, even the norm. The course grade was a product of only two things, homework and single, five question final. I did great on homework, really enjoying working our the difficult problems, but the test posed an issue. I needed more time...and just didn't have it. I only mention this because I feel the test (thus the grade) did not completely reflect my abilities throughout the semester, but that is just the way it is...

So given your knowledge of grad school admissions (since you and your peers have gone through it) how would such a situation rank? Do I have a shot at getting accepted? I will note that I have no issue retaking the course once matriculated in a program.

Thanks for the help!

#### hlsmith

##### Less is more. Stay pure. Stay poor.
You sound like you have a good background. Just for curiousity, what was your overall GPA. Will the program you are applying to required a standardized test score, say GRE (which has a quantitative component). If it is not an upper tier school, I bet you can get in. I wouldn't sweat the one B.

#### DoIhaveashot?

##### New Member
You sound like you have a good background. Just for curiousity, what was your overall GPA. Will the program you are applying to required a standardized test score, say GRE (which has a quantitative component). If it is not an upper tier school, I bet you can get in. I wouldn't sweat the one B.
My undergrad GPA was 3.5, but that is not with factoring in the additional 5 As from the calcs linear and diff eqs.

I'm taking the GRE tomorrow. I've been pre testing around a 160-162 for quant... I'm hoping to pull the 160+ but you never know. Unfortunately I've only had about 2 weeks to study.

#### spunky

##### Can't make spagetti
uhm... did you take real analysis or any other courses that are heavy on the "theorem-proof-theorem-proof" base approach to teaching math?

#### DoIhaveashot?

##### New Member
uhm... did you take real analysis or any other courses that are heavy on the "theorem-proof-theorem-proof" base approach to teaching math?
No. The two stat programs I'm looking at claim to just require the calc sequence, linear, algebra, and mathematical stats as a background....they claim to be 'professionally focused.' The biostat program is vague, claiming only quant mature student.

They are Umass Amherst stat and biostat, and Umass Lowell stat

Umass Lowell requires analysis as part of the MS itself.

Note***the mathematical stat grad course I took was of this nature. Lectures generally concerned proving theorems, homework extended the proofs with some light "show this or show that type problems." I was not required to truly prove a complete theorems. Ex. the prof would prove something like the weak law of large numbers, he central limit theorem, or random variable transformations, we would be required to work with and demonstrate various results from the theorem.

Last edited:

#### spunky

##### Can't make spagetti
OMG YOU'RE RIGHT! UMass doesn't ask you for a major in Statistics/Math to get into their MSc program. heck, had i known this i would have applied there!

anyhoo, you've been through the basic calc stream and you've done linear algebra. you're clearly somewhat familiar with the method of proof and got to sample a graduate-level course in Statistics.

my vote goes for 'yes', you should be fine.

#### DoIhaveashot?

##### New Member
I pulled a 159 Quant and a 162 Verbal.

Not the best quant ever, but I can only assume the two programs at Umass Amherst are not too competitive. What do yo think of these scores?

#### Dason

I pulled a 159 Quant and a 162 Verbal.

Not the best quant ever, but I can only assume the two programs at Umass Amherst are not too competitive. What do yo think of these scores?
I didn't realize they changed the scoring in 2011 so when I read those scores for a moment I just thought you were *terrible* and then I realized that when I took it the min score was 200 so something must be wrong...

#### spunky

##### Can't make spagetti
well... your quant score is a little bit lower compared to what i've seen in other graduate programs, but you're still above the 70th percentile so i think you're probably OK. besides, UMass' website says you're encouraged to submit the scores but that it's not required.

do you have any programming experience? that would help enhance your qualifications as a candidate.

i wouldn't jump too fast on this idea that since the program is not competitive it would be easy to get in. ever since people figured out there's money to be made in big data analytics, Applied Statistics programs have seen a boost in candidates to try and secure getting a job. i mean, you admit yourself that you're trying to change careers (wouldn't blame you. i do research in un/underemployment and i know how tough things can be depending on which major you chose in college). and the fact that UMass has no requirement for a BSc in Math/Stats means the potential pool of people who can apply is a lot larger.

have you considered an educational measurement/psychometrics program as a Plan B, just in case?

#### DoIhaveashot?

##### New Member
well... your quant score is a little bit lower compared to what i've seen in other graduate programs, but you're still above the 70th percentile so i think you're probably OK. besides, UMass' website says you're encouraged to submit the scores but that it's not required.

do you have any programming experience? that would help enhance your qualifications as a candidate.

i wouldn't jump too fast on this idea that since the program is not competitive it would be easy to get in. ever since people figured out there's money to be made in big data analytics, Applied Statistics programs have seen a boost in candidates to try and secure getting a job. i mean, you admit yourself that you're trying to change careers (wouldn't blame you. i do research in un/underemployment and i know how tough things can be depending on which major you chose in college). and the fact that UMass has no requirement for a BSc in Math/Stats means the potential pool of people who can apply is a lot larger.

have you considered an educational measurement/psychometrics program as a Plan B, just in case?
Definitely some good thoughts. Yes, at some points I have...actually I work in education now and regularly use the results of psychometric testing (I think). I am apprehensive about getting into a doctorate program at this stage in my life. I guess my plan b is Umass Lowell. The graduate coordinator claimed that a B in the course I took would give me a pretty good chance at getting in.

As for coding, I can do some work with python, but I'd consider myself a beginner. I would like to play around with some data with R over the next few weeks. I am considering taking the second semester of math stats at Umass Lowell while it is still fresh in my mind and I have momentum...

I may have enough time for a retest, but it will be close. App deadlines for both schools is 1/31. I can test next 1/10/15.

Would you recommend a second go at the GRE?

#### spunky

##### Can't make spagetti
it depends. if you think you can increase your score a lot (like maybe you were not feeling well that day or you were too nervous, etc.) then it's probably worth it. but if you feel like you tried your best, there's probably no point on it. keep in mind you're still above the 70th percentile, so that's a good thing.

if i were you i would try to get as many math/stats/programming courses under my belt as i can and get good grades on them (which you're already doing). the angle you need to take here is that you're not some lost English major with no clue of how to do math. good grades in tough courses/programming experience are probably gonna speak for themselves better that GRE scores (unless UMass is one of those schools who uses the GRE to filter out candidates in which case it's high-scores-or-die. my school does that in many programs).

to be honest with you, my quant GRE was not great either (actually all of my GRE was not great ) but i have a major in Math so my advisor immediately ignored my low GRE and focused on my grades/research experience/statement of purpose.

#### DoIhaveashot?

##### New Member
it depends. if you think you can increase your score a lot (like maybe you were not feeling well that day or you were too nervous, etc.) then it's probably worth it. but if you feel like you tried your best, there's probably no point on it. keep in mind you're still above the 70th percentile, so that's a good thing.

if i were you i would try to get as many math/stats/programming courses under my belt as i can and get good grades on them (which you're already doing). the angle you need to take here is that you're not some lost English major with no clue of how to do math. good grades in tough courses/programming experience are probably gonna speak for themselves better that GRE scores (unless UMass is one of those schools who uses the GRE to filter out candidates in which case it's high-scores-or-die. my school does that in many programs).

to be honest with you, my quant GRE was not great either (actually all of my GRE was not great ) but i have a major in Math so my advisor immediately ignored my low GRE and focused on my grades/research experience/statement of purpose.
Yeah, I figured that was the case. To me (as I'm sure with anyone here) the GRE math is rather easy, it's just the speed and accuracy that trip me up. I feel like I tried my best, but then again I only practiced for about two weeks...4 days seriously. I probably could do better, but maybe not. With the GRE the difference between a 162 and 159 is a couple simple mistakes. I know I could do better, but you never really know until you're actually there. I could have a headache, or need to pee, or .... any number of things. If you don't think the score is an abomination then I'll probably save the $200 and not take it. I know I am not the most competitive person... but do you think a 162 would really seal the deal? I know it would be highly unlikely for me to score a 170 simply because I am bit shaky with standardized tests...and I could probably land better than a 160, but maybe not...the math is easy, but the speed messes with me. Also, Spunky, thank you again for entertaining my thoughts. I really do appreciate it. #### spunky ##### Can't make spagetti to be honest with you, i think that once you've crossed over the 65th-70th percentile threshold then it comes down to assessing each program individually to see how you measure up with respect to other applicants. do you have any possibility to see the average GRE score of people who were admitted in your program? a lot of universities publish them and it and that gives you a good idea of where your standing could be. admission decisions related to GRE scores are tricky because there is no universal standard that you can apply. it varies program to program, department to department and university to university. i honestly wouldn't bother re-taking the GRE unless i could confidently say "i can increase my score to somewhere around the 85th percentile or higher". i mean, it's still$200, right? and you have your grades in your graduate courses to back you up. and UMass says that submitting the GRE scores is recommended but not required (although in your case maybe you definitely want to send them because you're coming from a liberal arts degree). what about taking the Math subject GRE? i know it says it's 'not required' for the Statistics program, but you need to show an admission committee that you're comfortable around math. like "sure, i have an English degree, but don't let that suggest i can't do math. i got a decent score in the quant section of the GRE AND i have a (hopefully good) score in the Math subject GRE AND i have all these advanced classes AND some programming experience!" i mean, that would definitely buff up your application.

and it is not a problem. i do my research/grad studies in the Department of Education. every year we get more and more people who want to upgrade their credentials because they want to open up their career prospects and this is usually something that comes up a lot (i.e. how do i get into a more "scientific/technological" field if my formal education is in liberal arts/social sciences/humanities?"). i was almost sure that UMass had an MEd program in Psychometrics for which you would be more than qualified, but i see they only offer it at the EdD level. the world is a scary place out there in terms of career development and one thing that you can be sure of is that number-crunchers will always be needed.

#### hlsmith

##### Less is more. Stay pure. Stay poor.
I just rewatched The Fighter, "pride of Lowell!


text:
Operating Systems

Midterm Exam Review Questions

Notice a tyop typo? Please submit an issue or open a PR.

Midterm Exam Review Questions

What are the key roles of an operating system?

The operating system has three main roles:

• hide hardware complexity
• manage underlying hardware resources
• provide isolation and protection

Hide Hardware Complexity

An application developer should not need to have to worry about the how to directly interface with the CPU, memory, or I/O devices. The OS provides abstractions to these hardware components to separate the application developer from the intimate details of the hardware. For example, the operating system provides the file abstraction as a representation of logical components of information stored on disk.

Manage Underlying Hardware Resources

Since the operating system is the interface between the user level applications the physical hardware, it makes sense that its duties include managing those hardware resources. The operating system allocates a certain amount of memory to an application, schedules it to run on the CPU, and controls access to various I/O devices, among other responsibilities.

These first two responsibilities can be summarized by the phrase abstract and arbitrate.

Provide Isolation And Protection

With multiple applications running concurrently, the operating system must make sure that no one application interferes with the execution of another application. For example, the operating system ensures that memory allocated to one application is neither read from nor written to by another application.

What Is The Distinction Between OS Abstractions, Mechanisms And Policies?

Abstractions are entities that represent other entities, often in a simplified manner. For example, all of the complexity of reading and manipulating physical storage is abstracted out into the file, an abstraction the operating system exposes to layers above. We can interact with the file interface, and let the operating system handle the complexities involved in the implementation. Apart from simplicity, another benefit of abstractions is their portability. Operating systems are free to swap out their implementations to suit different hardware resources, and as long as their API remains constant, programs will still run.

Example of abstractions include:

• file, socket, memory page (hardware abstractions)

Policies are the rules around how a system is maintained and resources are utilized. For example, a common technique for swapping memory to disk is the least recently used (LRU) policy. This policy states that the memory that was least recently accessed will be swapped to disk. Policies help dictate the rules a system follows to manage and maintain a workable state. Note that policies can be different in different contexts or a different times in a system.

Mechanisms are the tools by which policies are implemented. For example, in order to enforce the LRU policy of memory management above, memory addresses/blocks may be moved to the front of a queue every time they are accessed. When it comes time to swap memory to disk, the memory at the back of the queue can be swapped. In this example, the queue is the mechanism by which the LRU policy is implemented.

What does the principle of separation of mechanism and policy mean?

The idea behind separation of mechanism and policy is that how you enforce a policy shouldn't be coupled to the policy itself. Since a given policy is only valid in some contexts or during some states of execution, having a mechanism that only suits that policy is very brittle. Instead, we should try to make sure that our mechanism is able to support a variety of policies, as any one of these policies may be in effect at a given point in time.

That being said, certain policies may occur more frequently than others, so it may make sense to optimize our mechanisms a little bit in one direction or anything while still maintaining their flexibility.

What does the principle optimize for the common case mean?

Optimizing for the common case means ensuring that the most frequent path of execution operates as performantly as possible. This is valuable for two reasons:

• it's simpler than trying to optimize across all possible cases
• it leads to the largest performance gains as you are optimizing the flow that by definition is executed the most often

A great example of this is discussed in the SunOS paper, when talking about using threads for signal handling instead of changing masks before entering/after exiting a mutex:

is about 40 SPARC instructions. The savings in the mutex enter/exit path is about 12 instructions. However, mutex operations are much more frequent than interrupts, so there is a net gain in time cost, as long as interrupts don't block too frequently. The work to convert an interrupt into a "real" thread is performed only when there is lock contention.

What happens during a user-kernel mode crossing?

Distinguishing between user and kernel mode is supported directly in the hardware. For instance, when operating in kernel mode, a special bit is set on the CPU, and if that bit is set, any instruction that directly manipulates the hardware is allowed. When in user mode, the bit will not be set, and any attempt to perform such privileged operations will be forbidden.

Such forbidden attempts will actually cause a trap. The executing application will be interrupted, and the hardware will switch control back to the operating system a specific location - the trap handler. At this point, the operating system will have a chance to determine what caused the trap and then decide if it should grant access or perhaps terminate the transgressive process.

This context switch takes CPU cycles to perform which is real overhead on the system. In addition, context switching will most likely invalidate the hardware cache (hot -> cold), meaning that memory accesses for the kernel context will initially come from main memory and not from cache, which is slow.

What are some of the reasons why user-kernel mode crossing happens?

Basically, user/kernel mode crossing occurs any time any application needs access to underlying hardware, be it physical memory, storage, or I/O devices.

User/kernel cross may occur if an application wishes to

• write to a file
• listen on a socket
• allocate memory
• free memory

User/kernel crossings may occur in response to a hardware trap as mentioned above, or may occur through the process of the application invoking a system call, requesting that the operating system perform some service for them.

What is a kernel trap? Why does it happen? What are the steps that take place during a kernel trap?

A kernel trap is a signal that the hardware sends to the operating system when the it detects that something has occurred.

A kernel trap will occur if the hardware detects an attempt to perform an unprivileged operation, which is basically any operation that occurs when the special bit is not set on the CPU. As well, the hardware may issue a trap if it detects an attempt to access memory that requires special privileges.

During a kernel trap, the hardware sends a signal to the operating system, which initiates controls and invokes its trap handler. The operating system can then examine the process that caused the trap as well as the reason for the trap and make a decision as to whether it will allow the attempted operation or potentially kill the process.

What is a system call? How does it happen? What are the steps that take place during a system call?

A system call is an operation that the operating system exposes that an application can directly invoke if it needs the operating system to perform a specific service and to perform certain privileged access on its behalf.

Examples of system calls include open, send, malloc.

When a user process makes a system call, the operating system needs to context switch from that process to the kernel, making sure it holds onto the arguments passed to that system call. Before the kernel can actually carry out the system call, the trap bit on the CPU must be adjusted to let the CPU know the execution mode is kernel mode. Once this occurs, the kernel must jump to the system call and execute it. After the execution, the kernel must reset the trap bit in the CPU, and context switch back to the user process, passing back the results.

Contrast the design decisions and performance tradeoffs among monolithic, modular and microkernel-based OS designs.

Monolithic

Pros

• Everything included
• Inlining, compile-time optimizations

Cons

• No customization
• Not too portable/manageable
• Large memory footprint (which can impact performance)

Modular

Pros

• Maintainability
• Smaller footprint
• Less resource needs

Cons

• All the modularity/indirection can reduce some opportunities for optimization (but eh, not really)
• Maintenance can still be an issue as modules from different codebases can be slung together at runtime

Microkernel

Pros

• Size
• Verifiability (great for embedded devices)

Cons

• Bad portability (often customized to underlying hardware)
• Harder to find common OS components due to specialized use case
• Expensive cost of frequent user/kernel crossing

What are the differences between processes and threads? What happens on a process vs. thread context switch?

A process is defined by two main components: it's virtual address mapping, and it's execution context. The virtual address mapping contains the code of the program, any data that the program is initialized with, and the heap. The execution context contains the stack and CPU registers associated with the process's execution.

Different processes will have different virtual address mappings and different execution contexts, all represented by the process control block. Different threads will exist within the same process, so they will share the virtual address mapping of the process. Only the execution context will be different. As a result, a multiprocess application will require a much larger memory footprint than a multithreaded application.

Greater memory needs mean that data will need to be swapped to disk more often, which implies that multithreaded applications will be more performant than multiprocess applications. In addition, process-process communication via IPC is often more resource intensive that thread-thread communication, which often just consists of reading/writing shared variables.

Since threads share more data than processes, less data needs to be swapped during a context switch. Because of this, thread context switching can be performed more quickly than process context switching. Process context switching involves the indirect cost of going from a hot cache to a cold cache. When a process is swapped out, most of the information the new process needs is in main memory and needs to be brought into the hardware cache. Since threads share more information - have more locality with one another - a new thread may still be able to benefit from the cache that was used by an older thread.

Describe the states in a lifetime of a process?

When a process is created, it's in the new state. At this point, the operating system initializes the PCB for the process, and it moves to the ready state. In this state it is able to be executed, but it is not being executed. Once the process is scheduled and moved on to the CPU it is in the running state. If the process is then interrupted by the scheduler, it moves back the the ready state. If the process is running, and then makes an I/O request, it will move onto the wait queue for that I/O device and be in the waiting state. After the request is serviced, the process will move back to the ready state. If a running process exits, it moves to the terminated state.

A thread can be created (a new execution context can be created and initialized). To create a thread, we need to specify what procedure it will run, and what arguments to pass to that procedure. Once the thread has been created, it will be a separate entity from the thread that created it, and we will say at this point that the process overall is multithreaded.

During the lifetime of a thread, the thread may be executing on the CPU - similar to how processes may be executing on the CPU at any point in time - or it may be waiting.

Threads may wait for several different reasons. They may be waiting to be scheduled on the CPU (just like processes). They may be waiting to acquire some synchronization construct - like a mutex - or they may be waiting on some condition to become true or some signal to be received - like a condition variable. Different queues may be maintained depending on the context of the waiting.

Finally, at the end of their life, threads can be joined back in to their parents. Through this join, threads can convey the result of the work they have done back to their parents. Alternatively, detachable threads cannot be joined back into their parent, so this step does not apply to them.

Threads can also be zombies! A zombie thread is a thread that has completed its work, but whose data has not yet been reclaimed. A zombie thread is doing nothing but taking up space. Zombies live on death row. Every once in a while, a special reaper thread comes and cleans up these zombie threads. If a new thread is requested before a zombie thread is reaped, the allocated data structures for the zombie will be reused for the new thread.

Describe all the steps which take place for a process to transition form a waiting (blocked) state to a running (executing on the CPU) state.

When a process is in a blocked state, this means that process is currently waiting for an I/O request to be fulfilled. Usually this means that the process is sitting on an I/O queue within the kernel that is associated with the device it's making the request to. Once the request is fulfilled, the process moves back to a ready state, where it can be executed, although it is not yet scheduled. The currently executing process must be preempted, and the ready process must be switched in. At this point, the process is executing on the CPU.

Message Passing IPC

The benefits of message passing IPC is that the operating system will manage the message passing channel, and already has system calls in place for operations like read/write and recv/send. The user doesn't need to worry about any of the details.

The downside of messaged-based IPC is the overhead. Every piece of data that is sent between processes must first be copied from the sending process's address space into memory associated with the kernel and then into the receiving process's address space. There is user/kernel crossing for every message.

Shared-Memory IPC

The benefit of this approach is that the kernel is completely uninvolved. The processes can read from and write to this memory as they would with any other memory in their address space. Unfortunately, without the kernel, a lot of the APIs that were taken for granted with message passing IPC may have to be re-implemented. For example, the user now has to manage all of the synchronization themselves.

There are two main benefits of multithreading, namely parallelization and concurrency.

Parallelization comes into effect on multi CPU systems in which separate threads can be executing at the same time on different processors. Parallelizing work allows for the work to be accomplished more quickly.

Concurrency refers to the idea that the CPU can do a little bit of work on one thread, and then switch and do a little bit of work on another thread. Succinctly, concurrency refers to the idea that the execution of tasks can be interwoven with one another.

The primary benefit of concurrency without parallelization - that is, concurrency on single CPU platforms - is the hiding of I/O latency. When a thread is waiting in an I/O queue, that thread is blocked: it's execution cannot proceed. In a multithreaded environment, a thread scheduler can detect a blocked thread, and switch in a thread that can accomplish some work. This way, it looks as if progress is always being made (CPU utilization is high) even though one or more threads may be waiting idle for I/O to complete at any given time.

While new threads require less memory than new processes, they still do require memory. This means that threads cannot be made for free, and in fact thread creation is often quite expensive. In addition, thread synchronization can add more overhead to the system, in terms of the CPU cycles and memory that must be consumed to represent and operate synchronously.

Describe the boss-workers multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a boss-worker model? What are the limiting factors in improving performance with this pattern?

In the boss-workers problem, you have one boss thread and n worker threads. For each task that enters the system, the boss dispatches the tasks that the workers consume.

This is often, though not necessarily, done through a shared request queue/buffer. In this case, the boss will add items to the queue, and the workers will consume items from the queue.

If you wanted to improve throughput or response time in this model, there are mainly two things you could do. First, increase the number of threads. The more you leverage concurrency, the more potential you have to increase the efficiency of your processing. That being said, dynamic thread creation is expensive, so it makes sense to just have a pool of workers up front instead of creating new threads on the fly. Increasing the size of the pool may help performance.

Second, decrease the amount of work the boss has to do. Since the boss has to do some processing on every request, the throughput of the system is correlated to this processing time. Make sure to make this is low as possible.

This approach is still limited by the amount of processing power you have. After a certain number of threads, the work will become CPU-bound. Some threads will end up just having to wait their turn for computing resources.

In addition, this approach lacks locality. The boss doesn't keep track of what any of the workers were doing last. It is possible that a thread is just finishing a task that is very similar to an incoming task, and therefore may be best suited to complete that task. The boss has no insight into this fact.

Describe the pipelined multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a pipelined model? What are the limiting factors in improving performance with this pattern?

In the pipeline pattern, the execution of the task is broken down into stages. Threads are assigned to continually complete the work at once stage, receiving requests from the stage before it and passing work on to the stage after it.

One of the benefits of this process is locality. Since each thread performs the same (small) task over and over again, it is more likely that the hardware cache will be hot, increasing performance.

On a larger level, this pattern will be bottle necked by the stage that takes the longest to complete. One way to overcome the difference in processing needed for each stage is to allocate a different number of threads to each stage. For example, a stage that takes three times as long as another stage should have three times the amount of threads.

A downside of this approach is that it is difficult to keep the pipeline balanced over time. When the input rate changes, or the resources at a given stage are exhausted, rebalancing may be required.

What are mutexes?

Mutexes are synchronization constructs that enforce the principle of mutual exclusion. Mutual exclusion is the requirement that one thread of execution never enter its critical section at the same time that another concurrent thread of execution enters its own critical section.

What are condition variables?

Condition variables are constructs used in conjunction with mutexes to control concurrent execution. While mutexes and mutual exclusion represent binary states - either the thread can access a shared resource or it cannot - condition variables allow for more complex states. Threads can wait on condition variables until a condition is met, and threads can signal/broadcast on condition variables when a condition is met.

Can you quickly write the steps/code for entering/existing a critical section for problems such as reader/writer, reader/writer with selective priority (e.g., reader priority vs. writer priority)?

mutex_lock(&m);

while(status == -1)

status++;

mutex_unlock(&m);

// work
// work
// work, work, work

mutex_lock(&m);

if(--status == 0)
signal(&cond_writer);

mutex_unlock(&m);

Writer

mutex_lock(&m);

while(status != 0)
wait(&cond_writer, &m);

status = -1;
mutex_unlock(&m);

// work
// work
// work, work, work

mutex_lock(&m);
status = 0;
mutex_unlock(&m);

signal(&cond_writer);
broadcast(&cond_reader);

What are spurious wake-ups, how do you avoid them, and can you always avoid them?

Spurious wake ups occur when a thread is woken up when the application is in a state during which it's impossible for that thread to make progress. This often occurs when one thread tries to signal/broadcast while holding a mutex. Threads associated with condition variable being signaled on will be woken up from the wait queue associated with the condition variable, but since the signaling thread holds the mutex, they will immediately be placed on the wait queue associated with acquiring the mutex. CPU cycles will be wasted.

Spurious wake ups can often be avoided by placing signal/broadcast calls outside of the mutex. Note that, this cannot always happen: if a signaling call depends on some configuration of shared state, this must be checked while holding the mutex, as with any other shared state access.

Do you understand the need for using a while() look for the predicate check in the critical section entry code examples in the lessons?

When a condition variable is signaled on, and a thread is to be "woken up", two things occur:

• The thread is removed from the wait queue
• The thread reacquires the mutex

The two steps are logically independent. What this means is that another thread may be given CPU time (and potentially the mutex) in between these two steps. As a result, the shared state may be updated before the waking up thread reacquires the mutex. Therefore, the thread must do another check when it actually acquires the mutex to ensure the condition it needs to proceed is still true.

What's a simple way to prevent deadlocks? Why?

Simplest way to prevent deadlocks is to maintain a lock order. This will prevent a cycle in the wait graph, which is necessary and sufficient for a deadlock to occur. Two threads can deadlock if they are each trying to acquire mutexes the other holds. A thread can also deadlock with itself if it tries to acquire a mutex it already holds. Enforcing a lock order can ensure that neither of these scenarios occurs.

Can you explain the relationship among kernel vs. user-level threads? Think though a general mxn scenario (as described in the Solaris papers), and in the current Linux model. What happens during scheduling, synchronization and signaling in these cases?

User level threads are associated with a user level library (like pthreads), while kernel level threads are associated with the kernel threading implementation (like NPTL). For a user thread to run, it must be associated with a kernel thread, which in turn must be scheduled on the CPU.

In the one-to-one model, there is one kernel thread for every user thread. That means that when a user thread is created, a kernel thread is also created. This 1:1 model is the current situation in Linux and is supported at the kernel level by the task struct. The benefit of the approach is that the kernel understands that the process is multithreaded, and it also understands what those threads need. Since the operating system already supports threading mechanisms to manage its thread, the user libraries can benefit directly from the multithreading support available in the kernel.

One downside of this approach is that is it expensive: for every operation we must go to the kernel and pay the cost of a system call. Another downside is that since we are relying on the mechanisms and policies supported by the kernel, we are limited to only those policies and mechanisms. As well, execution of our applications on different operating systems may give different results.

In a so-called many-to-many scenario, there can be one or more user threads scheduled on one or more kernel threads. The kernel is aware that the process is multithreaded since it has assigned multiple kernel level threads to the process. This means that if one kernel level thread blocks on an operation, we can context switch to another, and the process as a whole can proceed. One of the downsides of this model is that is requires extra coordination between the user- and kernel-level thread managers.

Signaling in a many to many scenario comes with complexities. If the kernel thread has a signal enabled but the user thread does not, the user threading library may have to send directed signals back down into the kernel to get the right user level thread to respond to the signal.

Can you explain why some of the mechanisms described in the Solaris papers (for configuring the degree concurrency, for signaling, the use of LWP…) are not used or necessary in the current threads model in Linux?

The mechanisms described in the Solaris paper were all mechanisms for rationing the number of threads that are created at any given point in time. Configuring the degree of concurrency implied that you couldn't just be automatically given as much as you needed. Having LWPs multiplex over kernel threads indicated that kernel threads needed to be shared. The rationing was based on real concerns about the available memory in a system at any given time.

The native implementation of threads in Linux is the Native POSIX Threads Library (NPTL). This is a 1:1 model, meaning that there is a kernel level task for each user level thread. In NPTL, the kernel sees every user level thread. This is acceptable because kernel trapping has become much cheaper, so user/kernel crossings are much more affordable. Also, modern platforms have more memory - removing the constraints to keep the number of kernel threads as small as possible.

What's an interrupt? What's a signal? What happens during interrupt or signal handling? How does the OS know what to execute in response to a interrupt or signal? Can each process configure their own signal handler? Can each thread have their own signal handler?

Interrupts

Interrupts are signals that the hardware sends to the CPU that signal that something has occurred. For example, when a user-level application tries to perform a illegal task using the hardware, the kernel is notified via an interrupt. An interrupt is handled on a per-CPU basis, and the operating system maintains an interrupt table, which maps interrupts by number to handling procedures. When the interrupt occurs, the kernel jumps to the associated interrupt handler and executes that code.

Which interrupts occur is a function of the platform on which you are running. How those interrupts are handled is a function of the OS on top of the physical system.

Signals

Signals are notifications that are delivered from the kernel to a user process. For example, if a process tries to access memory it has not allocated, the operating system may throw a SIGSEGV (segmentation fault). Signals are operating system specific.

Each process maintains its own signal handling table, which is very similar to kernel-level interrupt handling table. Each entry contains a reference to the signal and a reference to the handling code. When a signal comes in, the process jumps to the handling code. Threads cannot have their own handler, although they can set their own signal masks to ensure that they can disable signals they don't want to receive.

What's the potential issue if a interrupt or signal handler needs to lock a mutex? What's the workaround described in the Solaris papers?

Since handlers are executed within a thread's stack, there is the potential for a thread to deadlock with itself if it tries to lock a mutex it has already acquired. This is because the current stack frame needs the mutex that was acquired in a lower stack frame to be released.

The solution is to have signal handlers execute in another thread. This way, the signal handling code can contend for a mutex like any other thread, which removes the possibility of deadlock.

Another solution is to have threads alter their signal masks before entering and after exiting their critical sections. While this solution requires fewer SPARC instructions than creating a new thread to handle signals, mutex acquisition happens much more frequently than signals. This is another example of optimizing for the common case!

Contrast the pros-and-cons of a multithreaded (MT) and multiprocess (MP) implementation of a webserver, as described in the Flash paper.

Multiprocess

The main benefits of the MP model are its simplicity. Each request is handled in a new process with it's own address space: there is no need for any (explicit) synchronization code. However, this benefit comes at the cost of performance. First, the memory foot print of the MP implementation is large. Processes have discrete address spaces, which means that memory usage grows steeply with request count. As a result, there is less memory available for caching, which means that computation becomes disk-bound more quickly. As well, context switching slows down the performance of the MP implementation. Context switching between processes consumes CPU cycles, which could otherwise be spent handling requests.

The main benefits of the MT model, compared to the MP model are that it is more efficient. MT applications share the address space of the process they are contained in, so they are more memory efficient than MP applications. As well, this sharing allows for smaller context switches (and often leaves hotter hardware caches), which can help performance. Unfortunately, this benefit comes at the cost of complexity. MT applications require explicit synchronization code to be written (mutexes, condition variables, etc). In addition, MT applications require kernel MT support, which wasn't a sure bet at the time of this paper.

What are the benefits of the event-based model described in the Flash paper over MT and MP? What are the limitations? Would you convert the AMPED model into a AMTED (async multi-threaded event-driven)? How do you think an AMTED version of Flash would compare to the AMPED version of Flash?

The event-based model operated primarily in one thread, which makes its memory footprint smaller than both the MT and MP model. As well, the cost of context switching was not (as) present. That being said, helper processes were involved, but their utilization was as needed: they weren't created blindly for every new request entering the system. The benefit of the smaller memory footprint was that more memory was available for the various types of caching done in the system. This meant that Flash could delay becoming disk-bound longer than the MT/MP models.

Limitations of the main approach behind Flash was that not every kernel supported asynchronous I/O. As a result, Flash had to fake it in a sense, utilizing helper processes to make I/O look async.

I think that the AMTED model would perform better than the AMPED model, as the MT model uses less memory than the MP model, which again allows for a bigger cache. I think the main reason for choosing process-based helpers was that kernel support for multithreading was spotty at the time of the writing of the paper; thus, a process based approach was the most portable. That being said, I think the performance differential would be on par with that between the standard MP/MT models, which is to say, not that much.

There are several sets of experimental results from the Flash paper discussed in the lesson. Do you understand the purpose of each set of experiments (what was the question they wanted to answer)? Do you understand why the experiment was structured in a particular why (why they chose the variables to be varied, the workload parameters, the measured metric…).

Single File Test

This test was a test of "best case": to show what performance would look like across the servers when the request pattern was optimal. To achieve this, requests were made for a single file which varied in size. SPED performed better than AMPED - which performs the extra check to see if the file is in memory (not an issue here because its one file and is always going to be in memory). Both performed better than MT/MP, which were slowed by context switching overhead.

Owlnet Trace

This tests workloads that can primarily be served from cache, but not completely. AMPED performs slightly better than SPED here. Since some of the work is disk-bound SPED blocks where AMPED context switches. Both of these approaches are better than MT/MP models, which have more memory allocated to them (less for cache size), and still incur the overhead of context switching.

CS Trace

This tests workloads that become disk-bound very quickly. In this case, AMPED, and MT/MP smoke SPED. Since SPED is single-threaded, with not helpers, SPED blocks a lot when the workload is disk-bound. AMPED only has enough helper processes to keep the disk busy, so it has a smaller memory footprint and few context switching overheads than MP/MT

Optimizations

Looking at connection rate as a result of file size across the various combination of optimizations - pathname lookup caching, response header caching, and mapped file caching - shows that the combination containing all optimizations can handle the highest connection rate.

Performance Under WAN

MT/AMPED/SPED all caused stable performance improvements when more clients were added. The per-process overhead of the MP model caused performance to degrade in this model.

If you ran your server from the class project for two different traces: (i) many requests for a single file, and (ii) many random requests across a very large pool of very large files, what do you think would happen as you add more threads to your server? Can you sketch a hypothetical graph?

Single file

Adding more threads would likely increase the throughput of the GETFILE server. Files need to be read from disk into memory before they can be served. Once a file is read into memory, it can stay in memory until its contents need to be replaced. More threads would be able to serve more concurrent requests.

Random requests across a large pool of large files

Adding more threads may not have a huge impact on throughput in this scenario. Any given new request is not likely to be able to read from main memory, since the range of inputs is so wide. This means that this application would likely be disk-bound from the get-go. Increasing the number of threads allows for more concurrent requests to be processed, but each thread will likely have to pull content from disk.

I would say that the graph for throughput vs threads in both cases would be logarithmically increasing, with the graph for the single file example rising much more sharply than the graph for the large pool.

OMSCS Notes is made with in NYC by Matt Schlenker.