1. Go to /boot
  2. See which kernel you are using
  3. Clean up
  4. If apt based solution does not work, pray and do this before the Clean Up step
    1. Delete old kernels besides this one

Do you have messages like this?

update-initramfs: Generating /boot/initrd.img-4.4.0-119-generic
W: mdadm: /etc/mdadm/mdadm.conf defines no arrays.

gzip: stdout: No space left on device
E: mkinitramfs failure cpio 141 gzip 1
update-initramfs: failed for /boot/initrd.img-4.4.0-119-generic with 1.

Your /boot partition is full, but it has old linux kernels and the current one. apt-get is never able to clean up, because the /boot partition is full! How to clean this?

Go to /boot

cd /boot

See which kernel you are using

uname -r

Clean up

dpkg --list | grep linux-image
# For every kernel that is not the one you are using, run:
sudo apt-get -f purge linux-image-extra-4.4.0-1*

# when you are finished, clean up everything
sudo apt autoremove

# update grub
sudo update-grub2
# reboot
sudo reboot

If apt based solution does not work, pray and do this before the Clean Up step

Delete old kernels besides this one

cd /boot
# **Modify the wildcarded versions according to your existing kernel!**
sudo rm -rf vmlinuz-4.4.0-1* System.map-4.4.0-1* abi-4.4.0-1* initrd-4.4.0-1* config-4.4.0-1*