24.03.18 운영체제, KEYWORD, PintOS

운영체제

21. 락

• 프로그래머들은 소스코드의 임계영역을 락으로 둘러서 그 임계영역이 마치 하나의 원자단위 명령어인것 처럼 실행되도록 한다.

21.1 락 : 기본개념

• 락은 둘 중 하나의 상태를 갖는다.
  • 첫 번째는 사용가능(available) 상태 (unblocked 또는 free) 이다. 즉, 어떤 쓰레드도 락을 소유하고 있지 않다.
  • 두 번째는 사용 중(acquired) 상태이다. 즉, 임계영역에서 정확히 하나의 쓰레드가 락을 획득한 상태이다.
• lock과 unlock 루틴의 의미는 간단하다. lock() 루틴 호출을 통해 락 획득을 시도한다. 만약 어떤 쓰레드도 락을 갖고 있지 않으면 그 쓰레드는 락을 획득하여 임계영역 내로 진입한다. 이렇게 락을 획득한 쓰레드를 락 소유자(owner)라고 부른다. 만약 다른 쓰레드가 lock()을 호출한 경우, 락이 사용중인 동안에는 lock() 함수는 리턴하지 않는다. 락을 소유한 쓰레드가 임계영역에 존재하는 상태에서는 다른 쓰레드들이 임계영역으로 진입할 수가 없다.
• 락의 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 어떤 쓰레드도 이 락을 대기하고 있지 않았다면 락의 상태는 사용 가능으로 유지된다. 만약에 대기중이던 쓰레드가 있었다면, 락의 상태가 변경되었다는 것을 인지하고 락을 획득하여 임계영역 내로 진입하게 된다.
• 락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 일반적으로 쓰레드는 프로그래머가 생성하고, 운영체제가 제어한다. 락은 쓰레드에 대한 제어권을 일부 이양 받을 수 있도록 해준다. 락으로 코드를 감싸서 프로그래머는 그 코드내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다.

21.2 락의 평가

• 락 설계시, 락의 정상동작 여부 판단을 위한 평가 기준을 정해야 한다.
  • 첫째, 상호배제를 제대로 지원하는가
  • 둘째, 공정성(fairness), 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가, 락을 전혀 얻지 못하는 기아(starve)상태가 발생하는가
  • 마지막, 성능(performance), 락 사용 시간적 오버헤드. 하나는 경쟁이 전혀 없는 경우의 성능, 다음은 여러 쓰레드가 단일 CPU상에서 락을 획득하려고 경쟁할 때 성능, 마지막은 멀티 CPU 상황에서 락 경쟁시의 성능.

21.3 인터럽트 제어

• 초창기 단일 프로세스 시스템에서는 상호배제 지원을 위해 임계영역내에서 인터럽트를 비활성화 하는 방법을 사용했다.
• 단일 프로세서 시스템에서 임계영역 진입 전에 특별한 하드웨어 명령어를 사용해서 인터럽트를 비활성화 시킨다면 임계영역 내의 코드에서는 인터럽트가 발생할 수 없다. 임계영역 내의 일련의 명령어들을 한 묶음으로, 원자적으로 실행할 수 있게 된다. 모든 동작이 끝난 후에 다시 하드웨어 명령어를 통해 인터럽트를 활성화하여 프로그램이 이전처럼 실행된다. 인터럽트가 발생하지 않으면, 코드가 실행중에 다른 쓰레드가 중간에 끼어들지 않는다는 것을 보장할 수 있다.
• 이 방법은 단점이 많다. 먼저 이 요청을 하는 쓰레드가 인터럽트를 활성/비활성화 하는 특권(privileged) 연산을 실행할 수 있도록 허가해야 한다. 또 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다.
• 두 번째 단점은 멀티 프로세서에서는 적용을 할 수가 없다는 것이다. 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행중인 프로그램에는 전혀 영향을 주지 않는다.
• 세 번째 단점은 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다는 것이다.
• 마지막으로 비효율적이다. 일반적인 명령어의 실행에 비해 인터럽트를 비활성화 시키는 코드들은 최신의 CPU들에서는 느리게 실행되는 경우가 있다.
• 위의 이유로 상호배제를 위해 인터럽트를 비활성화 하는 것은 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제가 내부 자료 구조에 대한 원자적 연산을 위해 인터럽트를 비활성화 할 수 있다.

21.4 Test-And-Set을 사용하여 작동하는 스핀 락 구현하기

• 하드웨어 기법 중 가장 기본은 test-and-set 명령어 또는 원자적 교체(atomic exchange)로 알려진 명령어다.
• test-and-set 명령어가 하는 동작은 다음과 같다. ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다. 여기서 핵심은 이 동작들이 원자적으로 수행된다는 것이다. test-and-set 이라고 부르는 이유가 이전 값을 검사(test)하는 동시에 메모리에 새로운 값을 설정(set) 하기 때문이다.
• 락의 값을 검사(test)하고 새로운 값으로 설정(set)하는 동작을 원자적 연산으로 만듦으로써 오직 하나의 쓰레드만 락을 획득할 수 있도록 만들었다.
• 스핀락은 가장 기본적인 형태의 락으로서 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다. 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러(Preemptive scheduler)를 사용한다. 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행 될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다. 선점형이 아니면 단일 CPU에서 스핀락의 사용은 불가능하다. while문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점하기 때문이다.

21.5 스핀락 평가

• 상호배제
  • 스핀락은 임의의 시간에 단 하나의 쓰레드만이 임계영역에 진입할 수 있도록 한다.
• 공정성
  • 스핀락은 어떠한 공정성도 보장해 줄 수없다. while문을 회전중인 쓰레드는 경쟁에 밀려서 계속 그 상태에 남아 있을 수 있다.
• 성능
  • 단일 CPU의 경우 스핀락이 갖는 오버헤드는 상당히 클 수가 있다. 쓰레드는 할당 받은 기간동안 CPU사이클을 낭비하면서 락을 획득 하기위해 대기한다.
  • 반면에 CPU가 여러개인 경우 꽤 합리적으로 동작한다. 다른 프로세서에서 락을 획득하기 위해 while문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다.

21.6 Compare-And-Swap

• SPARC의 Compare-And-Swap, x86에서는 Compare-And-Exchange라고 한다.
• compare-and-swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치 한다면 아무것도 하지 않는다. 원래의 메모리 값을 반환하여 compare-and-swap을 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

21.7 Load-Linked 그리고 Store-Conditional

• MIPS구조에서의 load-linked와 store-conditional.
• load-linked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. 실제 차이는 store-conditional 명령에서 나타난다. store-conditional 명령어는 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공한다. 저장이 성공하면, load-linked가 탑재했던 값을 갱신한다. 성공한 경우에는 store-conditional은 1을 반환하고 ptr이 가리키는 value의 값을 갱신한다. 실패한 경우에는 ptr이 가리키는 value 값이 갱신되지 않고 0을 반환한다.

21.8 Fetch-And-Add

• fetch-and-add 명령어는 원자적으로 특정 주소의 예전값을 반환하면서 값을 증가시킨다.
• 하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket)과 차례(turn) 조합을 사용하여 락을 만든다. 기본 연산은 간단하다. 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다. 결과값은 해당 쓰레드의 차례(my turn)를 나타낸다. 전역 공유 변수인 lock→turn 을 사용하여 어느 쓰레드의 차례인지 판단한다. 만약 한 쓰레드가 (my turn == turn)이라는 조건에 부합하면 그 쓰레드가 임계 영역에 진입할 차례인 것이다. 언락 동작은 차례 변수의 값을 증가시켜서 대기중인 다음 쓰레드에게 임계영역 진입 차례를 넘겨준다.
• 이전까지의 접근 방법과 이번 해법의 중요한 차이 중 하나는 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다. 쓰레드가 티켓 값을 할당 받았다면 미래의 어느때에 실행되기 위해 스케줄 되어 있다는 것이다.

21.9 조건 없는 양보

• 하드웨어의 지원을 받아 많은 것을 해결한다. 동작이 검증된 락과 락 획득의 공정성까지도 해결할 수 있었다. 하지만 아직도 문제가 남아있다. 문맥교환이 되어 쓰레드가 실행이 되었지만 이전 스레드가 인터럽트에 걸리기 전에 락을 이미 획득한 상태라서 그 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에 어떻게 해야 할 것인가?
• 첫 번째 시도는 단순하고 친근한 방법이다. 락이 해제되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하는 것이다.
• 하나의 쓰레드는 실행중(running), 준비(ready), 막힘(blocked)이라는 세 가지 상태가 있다.
• 양보(yield)라는 시스템 콜은 호출 쓰레드 상태를 실행 중(running)에서 준비(ready)로 변환하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다. 결과적으로 양보 동작은 스케줄상에서 자신을 빼는 것(deschedule)이나 마찬가지다.
• 문맥교환 비용의 낭비와 굶주림 문제가 있다.

21.10 큐의 사용 : 스핀 대신 잠자기

• 이전 방법들의 근본 문제는 너무 많은 부분을 운에 맡긴다는 것이다. 스케줄러가 다음 실행될 쓰레드를 잘못 선택한 경우, 선택된 쓰레드는 락을 대기하면서 스핀하거나, CPU를 즉시 반납해야 하는 경우가 발생 할 수 있다.
• 다수의 쓰레드가 락을 대기하고 있을 경우, 다음으로 락을 획득할 쓰레드를 명시적으로 선택할 수 있어야 한다. 이를 위해서는 운영체제의 적절한 지원과 큐를 이용한 대기 쓰레드들의 관리가 필요하다.

21.11 다른 운영체제, 다른 지원

• linux의 경우 futex라는 것을 지원한다. futex는 특정 물리 메모리 주소 그리고 커널에 정의된 큐를 갖고있다. 호출자는 futex관련 함수를 호출하여 잠을 자거나 잠에서 깨어난다.
• futex는 두 개의 명령어가 있다. futex_wait(address, expected)명령어는 address의 값과 expected의 값이 동일한 경우 쓰레드를 블럭시킨다. 같지않다면 리턴한다. futex_wake(address)명령어를 호출하면 큐에서 대기하고 있는 쓰레드 하나를 꺠운다.
• 이 코드에서는 하나의 정수를 이용하여 락의 사용 중 여부와, 대기자 수를 동시에 표현한다. 따라서 락이 음수라면 락이 사용중인 것을 나타낸다.
• 둘 째, 이 코드는 경쟁이 없는 경우에 대해 최적화 되어있다. 하나의 쓰레드가 락 획득과 해제를 반복할 경우, 특별히 빠르게 동작한다.

21.12 2단계 락(two-phase lock)

• 2단계 락은 락이 곧 해제될 것 같으면, 회전 대기가 더 유용하다는 점에 착안하였다. 첫 번째 단계에서는 회전하며 대기한다. 락이 빠른 시간내에 해제될 것을 가정한다. 만약 첫 단계에서 락을 획득하지 못 했다면 두 번째 단계로 진입한다. 두 번째 단계에서 호출자는 차단된다. 락 해제 시 블럭된 쓰레드 중 하나를 잠에서 깨운다. 앞서 다룬 linux 락은 이런 형태를 갖는다. 일반화된 방법은 futex가 일정시간 동안 반복문 내에서 회전한 후에 블럭하는 것이다.
• 2단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어내는 하이브리드 방식이다. 물론, 이 기법의 우수성은 하드웨어 환경이나, 쓰레드의 개수, 그리고 세부 작업량 등과 같은 많은 것들에 의해 결정된다.

KEYWORD

USER MODE VS KERNEL MODE

• 커널에서 중요한 자원을 관리하기 때문에, 사용자가 그 중요한 자원에 접근하지 못하도록 모드를 2가지로 나눈 것이다.
• 시스템 콜을 이용해서 전환한다.

USERMODE

• 유저가 접근할 수 있는 영역을 제한적으로 두고, 프로그램의 자원에 함부로 침범하지 못하는 모드이다.
• 우리는 여기서 코드를 작성하고, 프로세스를 실행하는 등의 행동을 할 수 있다.
• 간단하게 유저 어플리케이션 코드가 유저모드에서 실행된다 라고 말할 수 있다.

KERNELMODE

• 모든 자원(드라이버, 메모리, CPU등)에 접근, 명령을 할 수 있다.

Register VS Memory

• 운영체제 관점에서 레지스터와 메모리는 컴퓨터 시스템에서 데이터를 저장하고 처리하는 데 필수적인 두 가지 리소스이다.
• 속도는 레지스터가 CPU 내부에 있어 메모리보다 빠르다.
• 용량은 메모리가 레지스터보다 훨씬 더 많은 양의 데이터를 저장할 수 있다.
• 레지스터는 현재 CPU가 처리 중인 작업에 필요한 데이터를 빠르게 처리하기 위해 사용된다. 메모리는 프로그램의 코드와 데이터를 저장하는데 사용된다.

Register

• CPU내부에 위치한 매우 빠른 데이터 저장소이다.
• 소량의 데이터를 저장할 수 있으며, CPU가 직접 접근하여 사용한다.
• 명령어 실행, 계산 중간 결과나 임시 값등, 임시 데이터 저장을 한다.

Memory

• 컴퓨터 시스템에서 데이터를 저장하는 주요 장치이다.
• 레지스터보다 용량이 크지만, 속도는 레지스터보다 느리다.
• 프로그램의 코드와 데이터를 저장하는 데 사용된다.
• 실행중인 프로그램의 코드와 데이터를 저장하고, 프로그램 실행 중 생성되는 데이터를 임시 저장한다.
• 실제 물리적 메모리를 초과하는 데이터를 디스크에 저장하고 필요할 때 불러오는 역할을 한다.

USERSTACK

• 사용자 스택은 프로그램 실행 중 발생하는 다양한 작업들을 관리하기 위한 메모리 구조로, 프로세스의 실행 상태를 효과적으로 관리하는 데 필수적이다.
• 프로그램의 실행 중에 함수 호출과 반환, 지역 변수, 함수 매개변수등을 저장하는 데 사용되는 메모리 영역이다.
• LIFO 구조를 가진다.

SYSCALL

• 사용자 모드에서 실행 중인 프로그램이 커널 모드의 운영체제 서비스를 요청할 때 사용하는 매커니즘이다.
• 파일 시스템 작업, 프로세스 관리, 네트워킹, 메모리 관리 등 운영체제의 핵심 기능을 사용자 프로그램에게 제공한다.
• 사용자 프로그램은 시스템 호출을 요청하고, 이 요청은 트랩(trap)이라는 매커니즘을 통해 커널 모드로 전환된다.

Cache

• 캐시 메모리는 속도가 빠른 장치와 느린 장치 간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리다.
• 메인 메모리에서 자주 사용하는 프로그램과 데이터를 저장해두어 속도를 빠르게 한다.
• 캐시의 지역성(locality)를 이용한다.

ATOMIC OPERATION

• 처리 중간에 다른 것이 끼어들 여지를 주지 않는다. ‘반쯤 했다’ 라는 것은 없고, 단지 했다와 안했다만 존재하는 연산이다. 무 아니면 전체
• 여러 쓰레드에서 동시에 접근하는 공유 데이터의 일관성을 유지하기 위한 도구다. Atomic 연산은 all-or-nothing 원칙을 따르는데, 이는 연산이 완전히 수행되거나, 아니면 전혀 수행되지 않아야 함을 의미한다. 이를 통해 멀티 쓰레드 환경에서 공유 데이터를 안전하게 처리할 수 있다.

PintOS

• Close를 구현하면서 여러 문제에 당착했다.
• allocate하는 부분에서 스택영역에 저장되기 때문에 함수가 리턴하면서 그 값이 가비지값으로 변하게 되는데, 그를 처리해주기 위해서 malloc을 사용했다.
• #include 이슈도 있었다. 잘 확인하자.
• read도 구현을 했다. 어렵다 어려워 만석님의 많은 도움을 받고 있다.

int allocate_fd(struct file *file, struct list *fd_table)
{
	struct file_descriptor* file_descriptor;
	file_descriptor = malloc(sizeof(struct file_descriptor));
	if(file_descriptor == NULL)
		return -1;
	file_descriptor->fd = (thread_current()->last_created_fd)++;
	file_descriptor->file = file;
	list_push_back(fd_table,&file_descriptor->fd_elem);
	return file_descriptor->fd;
}

void close (int fd) {
	struct file_descriptor *file_desc = find_file_descriptor(fd);
	if(file_desc == NULL)
		return;
	file_close(file_desc->file);
	list_remove(&file_desc->fd_elem);
	free(file_desc);
}
int read (int fd, void *buffer, unsigned size)
{
	if(pml4_get_page(thread_current()->pml4, buffer) == NULL || buffer == NULL || !is_user_vaddr(buffer) || fd < 0)
		exit(-1);
	int byte = 0;
	char* _buffer = buffer;
	if(fd == 0)
	{
		while(byte < size)
		{
			_buffer[byte++] = input_getc();
		}
	}
	else if(fd == 1)
	{
		return -1;
	}
	else
	{
		struct file_descriptor *file_desc = find_file_descriptor(fd);
		if(file_desc == NULL)
			return -1;
		byte = file_read(file_desc->file,buffer,size);
	}
	return byte;
}

• 진행과정

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
FAIL tests/userprog/read-bad-ptr
pass tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
FAIL tests/userprog/read-bad-fd
FAIL tests/userprog/write-normal
FAIL tests/userprog/write-bad-ptr
FAIL tests/userprog/write-boundary
FAIL tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
FAIL tests/userprog/fork-once
FAIL tests/userprog/fork-multiple
FAIL tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
FAIL tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
FAIL tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
FAIL tests/userprog/bad-read
FAIL tests/userprog/bad-write
FAIL tests/userprog/bad-read2
FAIL tests/userprog/bad-write2
FAIL tests/userprog/bad-jump
FAIL tests/userprog/bad-jump2
FAIL tests/filesys/base/lg-create
FAIL tests/filesys/base/lg-full
FAIL tests/filesys/base/lg-random
FAIL tests/filesys/base/lg-seq-block
FAIL tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
FAIL tests/filesys/base/sm-full
FAIL tests/filesys/base/sm-random
FAIL tests/filesys/base/sm-seq-block
FAIL tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
FAIL tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
FAIL tests/userprog/no-vm/multi-oom
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
44 of 95 tests failed.

힘들당