12/23

week08 키워드

• PROJECT1 : Thread
• Alarm clock, Priority Scheduling, Advanced Scheduling
• Context Switching, Scheduler(Round Robin, Priority, Mulit-Level Feedback Queue), Thread
• Timer Interrupt, Timer sleep
• Synchronization(Semaphore, lock, condvar)

채널코퍼레이션 설명회

leetcode

• 125. Valid Palindrome
• 344. Reverse String

---

12/24

OS 개념공부(KAIST PintOS Assignment)

• Quick Emulator(qemu)
• Synchronization
  • non-maskable interrupts(NMIs)
  • intr_level
    • intr_get_level, intr_set_level
    • intr_enable, intr_disable
  • Semaphore
    • P(wait), V(signal)
  • Monitor
  • Optimization Barrier
    • busy_wait
• Thread
  • synchronization primitives(semaphore, lock, condition variable, optimization barrier)
  • idle thread
  • context switch
  • status(RUNNING, READY, BLOCKED, DYING)
• Alarm Clock
• Priority Scheduling
  • priority inversion
  • donate
• Advanced Scheduler
  • mulitlevel feedback queue scheduler
  • round robin

OS 개념공부(blog)

• Loader
• Low-level Kernel Initialization
• High-level Kernel Initialization
• Kernel thread
• 범용 레지스터
• Assembly
• Process
  • Process Control Block(PCB)
  • states(Active-swapped in, Suspended-swapped out)
  • context switching
• Interrupt
  • interrupt handling
  • interrupt service routine
• Thread
  • Light Weight Process(LWP)
  • User Thread
  • Kernel Thread
• Scheduling
  • Preemptive / Non-preemptive
  • Priority
  • First-Come-First-Service(FCFS)
  • Shortest-Process-Next(SPN)
  • Round-Robin(RR)
  • High Response Ratio Next(HRRN)
  • Multi-level Feedback Queue(MFQ)
• Alarm clock
  • busy-waiting
  • sleep, awake
• Priority Scheduling
  • donate, sema
  • lock, semaphore, condition variable
  • inversion
  • multiple donation, nested donation
• Advanced Scheduler
  • mulit-level feedback queue scheduler

leetcode

• 937. Reorder Data in Log Files
• 819. Most Common Word

---

12/25

OS 개념공부(youtube)

• HPC Lab. KOREATECH

leetcode

• 49. Group Anagrams
• 5. Longest Palindromic Substring
• 1. Two Sum
• 42. Trapping Rain Water

---

12/26

alarm clock 구현

leetcode

• 15. 3Sum
• 561. Array Partition I
• 238. Product of Array Except Self
• 121. Best Time to Buy and Sell Stock

---

12/27

OS 개념공부(권영진 교수님)

priority scheduler 구현

leetcode

• 234. Palindrome Linked List
• 21. Merge Two Sorted Lists
• 206. Reverse Linked List
• 2. Add Two Numbers

---

12/28

priority scheduler 구현

• semaphore
• lock
• condition variable(monitor)

leetcode

• 24. Swap Nodes in Pairs
• 328. Odd Even Linked List
• 92. Reverse Linked List II
• 20. Valid Parentheses

---

12/29

priority scheduler 구현

• inversion(donation)

WIL(Weekly I Learned)

• alarm-clock
  • busy wait 문제가 발생했다. busy 는 runninng중인 쓰레드가 cpu를 점유하고있는데, 하는일은 yield 밖에 안하는 상태이다.
  • 자원낭비 발생하기 때문에, 해결해야한다.
  • 해결방법 : sleep/awake 방식 사용, 타이머 슬립에서 busy 코드를 지우고, thread sleep 함수를 작성하여 호출하였다.
  • thread_sleep 은 block 한 쓰레드를 sleep_list에 추가하는 함수이다.
  • 전역변수로, next_tick 을 사용하여, 깨울쓰레드가 있을 때만 thread awake 를 호출하였다.
  • 그이유는, 매 틱마다 쓰레드 awake 를 쓸데없이 호출하는것을 없애기 위함이다.(sleep list 를 다 돌 필요가 없다.)
• priority scheduling
  • 지금까지는 레디리스트에 새롭게 실행되는 쓰레드들이 뒷쪽에 추가되고 먼저들어온 쓰레드를 먼저 실행하는 FCFS(FIFO) 방식이었다.
  • 각 쓰레드마다 우선순위를 반영하여, 우선순위가 높은 쓰레드를 먼저 실행하도록 구현하는것을 목표로 하였다.
  • 레디리스트에 우선순위 기준인 내림차순으로 정렬이 되어있으면 맨앞에 있는 쓰레드가 가장 높은 우선순위를 가지는 쓰레드다.
  • list_insert_ordered 함수를 사용하여 우선순위를 반영한 레디 리스트를 만들었다.
  • 우선순위가 높은 쓰레드가 레디리스트에 들어오면 cpu 를 선점할수있도록 구현하였다.
• Synchronization - condition variable, sema, lock
  • condition variable와 semaphore, lock을 사용해 동기화하여 임계영역에서 여러 쓰레드가 접근을 못하도록 하였다.
  • 우선순위 스케줄링에서 priority inversion이나, deadlock 일어날 수 있음
  • 이 문제를 해결하기 위해 자신보다 낮은 쓰레드에게 자신의 우선순위 부여하는 방식으로 문제 해결

leetcode

• 316. Remove Duplicate Letters
• 739. Daily Temperatures
• 225. Implement Stack using Queues
• 232. Implement Queue using Stacks

---

12/30

week09 발제

---

comment

꾸준히 파이썬 알고리즘 인터뷰 풀이
정글은 장기전, 나중엔 체력 필요하니 운동 시작
핀토스는 어려움