Sim, eles podem. Na maioria dos sistemas operacionais eu estou ciente e, certamente, no Windows e no Linux, não há nada que diga que apenas um dos threads de um processo possa ser executado por vez. Na verdade, o agendador do Windows presta pouca atenção a "de qual processo veio um thread?" na tomada de decisões. Em um sistema com núcleos n , os encadeamentos n podem ser executados literalmente ao mesmo tempo. Não importa se são todos de um processo, de quatro processos diferentes ou de qualquer combinação.
Para o Windows, você pode demonstrar isso facilmente com o aplicativo "cpustres". Você pode encontrar isso no "Windows Internals book tools", um pacote distribuído por Mark Russinovich no site de ferramentas da sysinternals. Coloque o seu sistema o mais silencioso possível e, em seguida, use cpustres para criar dois threads e definir seu "nível de atividade" no máximo. Em seguida, verifique os gráficos de tempo da CPU no Gerenciador de Tarefas. Ou use o Process Explorer para observar o tempo de CPU dos dois threads.
O livro Windows Internals inclui informações completas sobre como o agendador (e não o "agendador de tarefas", o agendador de threads) faz seu trabalho. É uma leitura longa, mas vale a pena. A versão mais recente desse livro cobre o Windows 7, mas não houve grandes mudanças nessa área desde então.